目錄導讀

• Collection
• List
• Set
• Queue

1.Collection集合的操作

(1)增

boolean add(Object o); //添加單個元素
boolean addAll(Collection c); //將c中的所有元素添加至this對應(yīng)的集合中绩脆，類似于復制

(2)刪

void clear(); //清空集合
boolean remove(Object o); //刪除指定元素o未玻，有多個o時蜒蕾，只刪除第一個
boolean removeAll(Collection c);// 差集盈匾。從集合中刪除c里包含的元素
boolean retainAll(Collection c); //交集臀栈。從集合中刪除c里不包含的元素

(3)判斷

boolean contains(Object o); // 判斷是否包含o元素
boolean containsAll(Collection c); //判斷是否包含c中所有的元素
boolean isEmpty(); //叛空

(4)獲取

int size(); //返回集合元素的個數(shù) 

注意：
    數(shù)組[]是length屬性
    字符串是length()方法
    集合是size()方法

Iterator iterator(); //返回Iterator對象，用于遍歷集合

(5)轉(zhuǎn)換

Object[] toArray(); //把集合元素轉(zhuǎn)換為數(shù)組止后，底層是

(6)遍歷

1.迭代器Iterator遍歷

//如
Collection c = new ArrayList();
Iterator it = c.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

2.foreach循環(huán)遍歷
3.Java8新增的方法：forEachRemaining(Consumer action)

2.List集合

• ArrayList
• LinkedList
• Vector(可以忽略不記憶)

1) List 集合的通用情況

由于List集合是有序的近哟，因此它的方法體系里多了一些利用索引操作集合的方法。除了同Collection部分的方法外钱豁，下面只展示不同的部分

(1)增

void add(int index, Object element); //將元素element插入到List集合的index處
boolean addAll(int index, Collection c); //將集合c中的所有的元素插入到List集合的index處

(2)刪除

Object remove(int index); //刪除并返回index處的元素
注意：List集合中判斷兩個對象是否相等是通過equals()方法返回true即可認為它們是相等的

(3)獲取

Object get(int index); //返回集合index索引處的元素
int indexOf(Object o); //返回元素o在集合List中首次出現(xiàn)的索引
int lastIndextOf(Object o); //返回元素o在集合List中最后一次出現(xiàn)的索引
List subList(int fromIndex, int toIndex); //返回集合List中[fromIndex, toIndex)的元素組成的子集合
ListIterator<E> listIterator(); //雙向迭代器
    ListIterator方法：
    · void add(E e); //增
    · void remove(); //刪
    //向后遍歷
    · boolean hasNext();
    · E next();
    //想前遍歷
    · boolean hasPrevious();
    · E previous();

(4)修改

Object set(int index, Object element);//將index處的元素替換為element耻卡，返回被替換的元素

(5)遍歷

1.普通for循環(huán)遍歷，因為有g(shù)et(int index)方法
2.foreach循環(huán)
3.迭代器

Iterator(后向迭代)
ListIterator(雙向迭代)

(6)Java8新增方法

void sort(Comparator c); //根據(jù)Comparator參數(shù)對List集合的元素進行排序
void replaceAll(UnaryOperator operator); // 根據(jù)operator指定的計算規(guī)則重新設(shè)置List集合的所有元素

2) ArrayList 和 Vector 集合

支持的操作同List牲尺，自己沒有什么單獨的特色了卵酪。
ArrayList 和 Vector 集合的區(qū)別？

同：
  1.ArrayList和Vector是底層是基于數(shù)組實現(xiàn)的谤碳，它們封裝了一個動態(tài)的允許再分配的Object[]數(shù)組溃卡。
  2.數(shù)組的默認長度為10,也可以在創(chuàng)建時指定長度

異：
  1.Vector：是古老的類，方法名稱很長蜒简，缺點很多(一般不建議使用該類)瘸羡，是線程安全的(故性能低)
  2.Vector有個子類Stack，是模擬'棧'的搓茬，也是線程安全犹赖、性能差的，同樣不建議使用它來模擬棧
  3.ArrayList：是線程不安全的(性能稍高卷仑，可用Collections工具類將其包裝成線程安全的)  
   注意：
    在Arrays工具類中峻村，有個'static <T> List<T> asList(T... a)' 方法，該方法可以把一個數(shù)組或指定個數(shù)的對象轉(zhuǎn)換為一個List集合锡凝，但這個List集合并不是ArrayList或Vector集合
的實例粘昨，而是Arrays的內(nèi)部類ArrayList的實例，即Arrays$ArrayList

3) LinkedList 集合

LinkedList集合實現(xiàn)了List接口(故是個List集合)，同時也實現(xiàn)了Deque接口(故可以被當成雙端隊列來使用)张肾，因此芭析，LinkedList即可以當成'棧'用也可以當成'隊'使用。

(1)當成List集合

方法同List的方法

注意：
    由于底層是基于鏈表實現(xiàn)的吞瞪，所以放刨，get(int index) 方法的執(zhí)行效率并不高，時間為 O(N)

(2)當成棧

//增
void push(E e); //棧頂添加元素
//刪
E poll(); // 棧頂元素出棧
E pollFirst(); //取出棧的第一個元素 
E pollLast(); //取出棧的最后一個元素

(3)當成隊

//增
boolean offer(E e); //隊尾添加元素
boolean offerFirst(E e); //對頭添加
boolean offerLast(E e); //隊尾添加

小分析：
  LinkedList(底層是鏈表實現(xiàn))與ArrayList(數(shù)組實現(xiàn))尸饺、ArrayDeque(數(shù)組實現(xiàn))的實現(xiàn)機制完全不同，LinkedList的隨機訪問(作為List集合的特點)集合元素的性能較差助币，但在插入和刪除元素時性能出色浪听。ArrayList和ArrayDeque的隨機訪問性能較好。
  Vector雖然底層也是數(shù)組實現(xiàn)眉菱，但由于要實現(xiàn)線程同步(且實現(xiàn)機制還不好)迹栓，所以性能很差。

3.個List實現(xiàn)類的性能分析

List就是一個線性表接口俭缓，而ArrayList,LinkedList又是兩種典型實現(xiàn)克伊。

ArrayList是基于數(shù)組實現(xiàn)的，因此华坦，它的隨機訪問性能比較好愿吹。適合在訪問多于插入刪除的場合

LinkedList是基于鏈表實現(xiàn)的，因此插入惜姐、刪除性能較好犁跪，但是訪問性能就不如ArrayList了。適合用于插入刪除較多的場合

對于集合的遍歷：
  ArrayList集合應(yīng)該采用隨機訪問的方法來遍歷
  LinkedList集合應(yīng)該采用迭代器(Iterator)來遍歷

4.Set集合

• HashSet(線程不安全)
• LinkedHashSet(線程不安全)
• TreeSet(內(nèi)容較多, 線程不安全)
• EnumSet(有序, 線程不安全)

Set集合其實是由Map集合實現(xiàn)來的歹袁，value全為null的鍵值對

Set集合類似于一個瓶子坷衍，里面的元素沒有順序，且不允許元素重復条舔，它的操作同Collection一樣枫耳，并沒有增加什么多余的方法

1.HashSet 集合類(重要)

- HashSet的底層是基Hash算法來存儲集合中的元素，因此具有很好的存取和查找性能
- 元素無序孟抗，線程不安全
- 集合的元素可以為null

HashSet中添加元素的步驟：
  存入一個元素時迁杨，HashSet會調(diào)用該對象的hashCode()方法以獲得該對象的hashCode值，然后根據(jù)這個值決定該對象存放的位置夸浅。 
  注意：
    1.我們認為的元素重復(字面內(nèi)容重復就行)和HashSet中認為的元素重復(equals()和hashCode()方法都相等)是不一樣的仑最。
    2.在HashSet中如果兩個對象通過equals()返回true,但它們的hashCode()返回值不一樣，就會造成兩個"一樣的"的元素可以添加成功帆喇，這就與Set集合的特點(元素不重復)矛盾了警医。因此，當要重寫HashSet的equals()方法時，其hashCode()方法也應(yīng)該重寫预皇，而且返回值要一致侈玄。
    3.如果兩個對象通過equals()返回false, 但它們的hashCode()返回值一樣,那就會造成所謂的沖突(數(shù)據(jù)結(jié)構(gòu)中有講)，那么會處理沖突(如使用鏈地址法)吟温，這樣就會使得HashSet的性能下降序仙。

2.LinkedHashSet 集合類

- 是HashSet的子類。也是根據(jù)元素的hashCode值來決定元素的存儲位置鲁豪，但同時也使用了鏈表來維護元素的添加次序潘悼，因此性能略低于HashSet集合
- 底層是基于Hash算法來存儲元素，用鏈表來維護元素的有序

注意：
1.盡管LinkedHashSet是有序的(用鏈表維護插入順序)爬橡，但它本質(zhì)仍是HashSet集合治唤，是靠hashCode值來決定存儲位置的，因此糙申，其內(nèi)的元素是不允許重復的宾添。
2.由于是用鏈表來維護內(nèi)部順序的，因此在迭代訪問Set里的全部元素時將有很好的性能柜裸。

3.TreeSet 集合類

是SortedSet接口的實現(xiàn)類缕陕，可以保正元素處于排序的狀態(tài)(注意，不是有序哦)疙挺。

底層是基于紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的數(shù)據(jù)存儲及排序扛邑。

獨有的幾個方法(因為有序才增加了這些方法):
Comparator comparator(); //如果Treeset采用了定制排序，則該方法返回定制排序所使用的Comparator;如果采用的是自然排序铐然，則返回null
Object first(); //返回集合中的第一個元素
Object last(); //返回集合中的最后一個元素
Object lower(Object e); //返回集合中位于e元素之前的元素鹿榜，e可以不是集合中的元素
Object higher(Object e); //返回集合中位于e元素之后的元素，e可以不是集合中的元素
SortedSet subSet(Object fromElement, Object toElement); //返回[fromElement, toElement)的子集
SortedSet headSet(Object toElement); //返回所有小于toElement的子集
SortedSet tailSet(Object fromElement); //返回所有大于或等于fromElement的元素

TreeSet的兩種排序方式：

自然排序(升序排序)
定制排序

實現(xiàn)：

1.自然排序(升序排序) —— 元素具備比較性
  使用TreeSet的無參構(gòu)造器
            
當采用自然排序時锦爵，TreeSet會調(diào)用集合元素的compareTo(Object obj)方法來比較元素之間的大小關(guān)系舱殿，然后將元素安升序排列。這中方式就是自然排序险掀。      
  注：
    1.這個compareTo(Object obj)方法是Comparable接口(java.lang包下的)的方法沪袭，要想加入TreeSet集合里，那么該對象須實現(xiàn)Comparable接口(只有添加的第一個對象可以不用實現(xiàn)Comparable接口樟氢？實驗過了冈绊，還是會報錯啊)，否則會報錯java.lang.ClassCastException
    
//如何讓自定義集合元素實現(xiàn)Comparable接口
public class Student implements Comparable {
  ...
  //重寫compareToe()方法,根據(jù)年齡大小來比較
  public int compareTo(Object o) {
    Student s = (Student)o;
     return this.age - s.age;
  }
}

//集合添加元素 
public class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet<Student> tr = new TreeSet<Student>();
    Student s1 = new Student("小明", 12);
    Student s1 = new Student("小江", 14);
    tr.add(s1);
    tr.add(s2); 
    System.out.println(tr); 
  }
}                   
    2.TreeSet中添加元素埠啃，判斷兩個元素是否相等唯一標準就是compareTo(Object o)是否返回0死宣，與equals()方法無關(guān)
    3.自定義類中，重寫equals()和compareTo(Object o)方法應(yīng)該具有相一致的比較結(jié)果碴开。
    4.實現(xiàn)了Comparable接口的常用類：
        - BigDecimal, BigInteger, 各種數(shù)值類型的包裝類
        - Character 
        - Boolean(true > false)
        - String
        - Date, Time

2.定制排序 —— 集合具備比較性
通過Comparator接口的幫助毅该，該接口里有 int compare(T o1, T o2)方法博秫，用于比較o1與o2的大小。利用TreeSet的這個構(gòu)造器  TreeSet(Comparator<? super E> comparator) 傳入Comparator的實現(xiàn)類實例即可眶掌。

注意：
    TreeSet判斷兩個對象是否相等的唯一標準是：通過compare()方法返回值是否為0挡育。       
//如下代碼示例
public class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet<String> tr = new TreeSet<String>(new MyComparator());
    tr.add("hello");
    tr.add("world"); //長度和“hello”相等，會當成是重復元素朴爬，故不會被添加進去
    tr.add("xi");
    tr.add("dian");
    System.out.println(tr); //[xi, dian, hello]
   }
}

//實現(xiàn)的Comparator接口
class MyComparator implements Comparator<String> {
  public int compare(String s1, String s2) {
    return s1.length() - s2.length();
  }
}

4.EnumSet 集合類

是專門為枚舉類設(shè)計的集合類, 集合元素有序即寒，是按枚舉類內(nèi)定義的順序來決定集合的元素順序的

集合元素不能為null, 加入null時會報錯，判斷是否有null元素及刪除null元素時都不會拋異常

EnumSet可以將一個枚舉類中全部或部分枚舉值放入其中召噩，并且是有序的(順序同枚舉類中的順序) 母赵。也可以將一個Collection集合的所有元素來創(chuàng)建新的EnumSet, 前提是該Collection集合中的元素是同一個枚舉類的枚舉值。

一句話總結(jié)：能放入EnumSet集合中的元素只能是枚舉類的枚舉值

5.各Set實現(xiàn)類的性能分析

HashSet和TreeSet是Set的兩個典型的實現(xiàn)類具滴。這這兩個如何選擇呢市咽？
1.HashSet的性能總是比TreeSet好，特別是元素的存儲(添加)和查找抵蚊，查找性能O(1), 結(jié)合數(shù)據(jù)結(jié)構(gòu)知識來理解
2.TreeSet需要額外的紅黑樹算法來維護集合的有序性，因此性能不如HashSet溯革。只有當需要保持Set的有序性時才選擇用它贞绳，否則都首選HashSet
3.EnumSet是Set實現(xiàn)類中性能最好的(HashSet可能會處理沖突，因此性能略低),但它只能存放同一枚舉類的枚舉值

6.Queue集合

• PriorityQueue
• ArrayDeque
• LinkedList

用于模擬隊列這種數(shù)據(jù)結(jié)構(gòu)致稀，隊列不允許隨機訪問隊列中的元素冈闭，因此，該集合不存在按索引訪問集合元素的任何方法

模擬隊列的特性抖单，設(shè)計的幾個獨特的操作方法：
//增
void add(Object e); //將指定元素添加至隊尾
boolean offer(Object e); //將指定元素添加至隊尾萎攒，當使用有容量限制的隊列時，該方法通常比add()好
//刪 
Object peek(); //獲取隊頭元素矛绘，注意不是刪除耍休，若隊為空，則返回null
Object element(); //獲取隊頭的元素货矮，注意不是刪除啊,若隊為空,會引發(fā)NoSuchElementException異常
Object poll(); //獲取隊頭元素羊精，并刪除，若隊為空囚玫，則返回null
Object remove(); //獲取隊頭元素喧锦，并刪除，如隊為空抓督，會引發(fā)NoSuchElementException異常

1) PriorityQueue 集合

- 存入該集合中的元素并不是按先后順序存放燃少，基本是按元素大小的順序存放。但是執(zhí)行铃在，將元素一個一個取出時阵具，卻是按從小到大的順序依次取出的
- PriorityQueue不允許添加null元素

PriorityQueue有兩種排序方式：自然排序碍遍、定制排序`
實現(xiàn)方式同TreeSet一樣
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) 

2)Deque 接口與 ArrayDeque 實現(xiàn)類

Deque接口是Queue接口的子接口，它代表一個雙端隊列怔昨，可以用來模擬 隊雀久，棧

基于此，這個接口里定義了一些從兩端來操作隊列的元素:

當成棧

//增
void push(E e); //棧頂添加元素
//刪
E poll(); // 棧頂元素出棧
E pollFirst(); //取出棧的第一個元素 
E pollLast(); //取出棧的最后一個元素

當成隊

//增
void addFirst(Object o);
void addLast(Object o);
boolean offer(E e); //隊尾添加元素
boolean offerFirst(E e); //對頭添加
boolean offerLast(E e); //隊尾添加

(1)ArrayDeque集合
基于數(shù)組實現(xiàn)的雙端隊列,底層封裝了一個動態(tài)數(shù)組Object[]
創(chuàng)建Deque時可以指定Object[]數(shù)組大小趁舀，默認長度為16
        
注：
  1.可以用ArrayDeque來模擬棧這種數(shù)據(jù)結(jié)構(gòu)赖捌，不要使用Stack類(Vector的子類)來模擬
  2.也可以用ArrayDeque來模擬隊這種數(shù)據(jù)結(jié)構(gòu)

3.LinkedList 集合類

LinkedList實現(xiàn)了Deque接口和List接口，因此矮烹，它同時具有這兩個集合類的特性越庇。

可以被當成：
(1)List集合
    注：可以用索引來訪問集合元素，但性能不佳奉狈，因為底層是鏈表實現(xiàn)的
(2)棧
(3)雙隊列