2.1 集合

Java的集合類被定義在Java.util包中，主要有4種集合，分別為List、Queue、Set和Map，每種集合的具體分類如圖2-1所示。

2.1.1 List：可重復

List是非常常用的數據類型，是有序的Collection，一共有三個實現類，分別是ArrayList、Vector和LinkedList。

1．ArrayList：基于數組實現，增刪慢，查詢快，線程不安全

ArrayList是使用最廣泛的List實現類，其內部數據結構基于數組實現，提供了對List的增加（add）、刪除（remove）和訪問（get）功能。

ArrayList的缺點是對元素必須連續存儲，當需要在ArrayList的中間位置插入或者刪除元素時，需要將待插入或者刪除的節點后的所有元素進行移動，其修改代價較高，因此，ArrayList不適合隨機插入和刪除的操作，更適合隨機查找和遍歷的操作。

ArrayList不需要在定義時指定數組的長度，在數組長度不能滿足存儲要求時，ArrayList會創建一個新的更大的數組并將數組中已有的數據復制到新的數組中。

2．Vector：基于數組實現，增刪慢，查詢快，線程安全

Vector的數據結構和ArrayList一樣，都是基于數組實現的，不同的是Vector支持線程同步，即同一時刻只允許一個線程對Vector進行寫操作（新增、刪除、修改），以保證多線程環境下數據的一致性，但需要頻繁地對Vector實例進行加鎖和釋放鎖操作，因此，Vector的讀寫效率在整體上比ArrayList低。

3．LinkedList：基于雙向鏈表實現，增刪快，查詢慢，線程不安全

LinkedList采用雙向鏈表結構存儲元素，在對LinkedList進行插入和刪除操作時，只需在對應的節點上插入或刪除元素，并將上一個節點元素的下一個節點的指針指向該節點即可，數據改動較小，因此隨機插入和刪除效率很高。但在對LinkedList進行隨機訪問時，需要從鏈表頭部一直遍歷到該節點為止，因此隨機訪問速度很慢。除此之外，LinkedList還提供了在List接口中未定義的方法，用于操作鏈表頭部和尾部的元素，因此有時可以被當作堆棧、隊列或雙向隊列使用。

2.1.2 Queue

Queue是隊列結構，Java中的常用隊列如下。

◎ ArrayBlockingQueue：基于數組數據結構實現的有界阻塞隊列。

◎ LinkedBlockingQueue：基于鏈表數據結構實現的有界阻塞隊列。

◎ PriorityBlockingQueue：支持優先級排序的無界阻塞隊列。

◎ DelayQueue：支持延遲操作的無界阻塞隊列。

◎ SynchronousQueue：用于線程同步的阻塞隊列。

◎ LinkedTransferQueue：基于鏈表數據結構實現的無界阻塞隊列。

◎ LinkedBlockingDeque：基于鏈表數據結構實現的雙向阻塞隊列。

2.1.3 Set：不可重復

Set核心是獨一無二的性質，適用于存儲無序且值不相等的元素。對象的相等性在本質上是對象的HashCode值相同，Java依據對象的內存地址計算出對象的HashCode值。如果想要比較兩個對象是否相等，則必須同時覆蓋對象的hashCode方法和equals方法，并且hashCode方法和equals方法的返回值必須相同。

1．HashSet:HashTable實現，無序

HashSet存放的是散列值，它是按照元素的散列值來存取元素的。元素的散列值是通過元素的hashCode方法計算得到的，HashSet首先判斷兩個元素的散列值是否相等，如果散列值相等，則接著通過equals方法比較，如果equls方法返回的結果也為true, HashSet就將其視為同一個元素；如果equals方法返回的結果為false, HashSet就不將其視為同一個元素。

2．TreeSet：二叉樹實現

TreeSet基于二叉樹的原理對新添加的對象按照指定的順序排序（升序、降序），每添加一個對象都會進行排序，并將對象插入二叉樹指定的位置。

Integer和String等基礎對象類型可以直接根據TreeSet的默認排序進行存儲，而自定義的數據類型必須實現Comparable接口，并且覆寫其中的compareTo函數才可以按照預定義的順序存儲。若覆寫compare函數，則在升序時在this．對象小于指定對象的條件下返回-1，在降序時在this．對象大于指定對象的條件下返回1。

3．LinkHashSet:HashTable實現數據存儲，雙向鏈表記錄順序

LinkedHashSet在底層使用LinkedHashMap存儲元素，它繼承了HashSet，所有的方法和操作都與HashSet相同，因此LinkedHashSet的實現比較簡單，只提供了4個構造方法，并通過傳遞一個標識參數調用父類的構造器，在底層構造一個LinkedHashMap來記錄數據訪問，其他相關操作與父類HashSet相同，直接調用父類HashSet的方法即可。

2.1.4 Map

1．HashMap：數組+鏈表存儲數據，線程不安全

HashMap基于鍵的HashCode值唯一標識一條數據，同時基于鍵的HashCode值進行數據的存取，因此可以快速地更新和查詢數據，但其每次遍歷的順序無法保證相同。HashMap的key和value允許為null。

HashMap是非線程安全的，即在同一時刻有多個線程同時寫HashMap時將可能導致數據的不一致。如果需要滿足線程安全的條件，則可以用Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。

HashMap的數據結構如圖2-2所示，其內部是一個數組，數組中的每個元素都是一個單向鏈表，鏈表中的每個元素都是嵌套類Entry的實例，Entry實例包含4個屬性：key、value、hash值和用于指向單向鏈表下一個元素的next。

HashMap常用的參數如下。

◎ capacity：當前數組的容量，默認為16，可以擴容，擴容后數組的大小為當前的兩倍，因此該值始終為2n。

◎ loadFactor：負載因子，默認為0.75。

◎ threshold：擴容的閾值，其值等于capacity×loadFactor。

HashMap在查找數據時，根據HashMap的Hash值可以快速定位到數組的具體下標，但是在找到數組下標后需要對鏈表進行順序遍歷直到找到需要的數據，時間復雜度為O(n)。

為了減少鏈表遍歷的開銷，Java 8對HashMap進行了優化，將數據結構修改為數組+鏈表或紅黑樹。在鏈表中的元素超過8個以后，HashMap會將鏈表結構轉換為紅黑樹結構以提高查詢效率，因此其時間復雜度為O(log N)。Java 8 HashMap的數據結構如圖2-3所示。

2．ConcurrentHashMap：分段鎖實現，線程安全

與HashMap不同，ConcurrentHashMap采用分段鎖的思想實現并發操作，因此是線程安全的。ConcurrentHashMap由多個Segment組成（Segment的數量也是鎖的并發度），每個Segment均繼承自ReentrantLock并單獨加鎖，所以每次進行加鎖操作時鎖住的都是一個Segment，這樣只要保證每個Segment都是線程安全的，也就實現了全局的線程安全。ConcurrentHashMap的數據結構如圖2-4所示。

在ConcurrentHashMap中有個concurrencyLevel參數表示并行級別，默認是16，也就是說ConcurrentHashMap默認由16個Segments組成，在這種情況下最多同時支持16個線程并發執行寫操作，只要它們的操作分布在不同的Segment上即可。并行級別concurrencyLevel可以在初始化時設置，一旦初始化就不可更改。ConcurrentHashMap的每個Segment內部的數據結構都和HashMap相同。

Java 8在ConcurrentHashMap中引入了紅黑樹，具體的數據結構如圖2-5所示。

3．HashTable：線程安全

HashTable是遺留類，很多映射的常用功能都與HashMap類似，不同的是它繼承自Dictionary類，并且是線程安全的，同一時刻只有一個線程能寫HashTable，并發性不如ConcurrentHashMap。

4．TreeMap：基于二叉樹數據結構

TreeMap基于二叉樹數據結構存儲數據，同時實現了SortedMap接口以保障元素的順序存取，默認按鍵值的升序排序，也可以自定義排序比較器。

TreeMap常用于實現排序的映射列表。在使用TreeMap時其key必須實現Comparable接口或采用自定義的比較器，否則會拋出java.lang.ClassCastException異常。

5．LinkedHashMap：基于HashTable數據結構，使用鏈表保存插入順序

LinkedHashMap為HashMap的子類，其內部使用鏈表保存元素的插入順序，在通過Iterator遍歷LinkedHashMap時，會按照元素的插入順序訪問元素。