一、接口繼承關(guān)系和實現(xiàn)
集合類存放于Java.util包中，主要有3種：set(集）、list(列表包含Queue）和map(映射)。
1. Collection：Collection是集合List、Set、Queue的最基本的接口。
2. Map：是映射表的基礎(chǔ)接口
3. Iterator：迭代器，可以通過迭代器遍歷集合中的數(shù)據(jù)
二、List
List是有序的Collection。
Java List一共三個實現(xiàn)類： 分別是ArrayList、Vector和LinkedList。
ArrayList（數(shù)組）
ArrayList 是最常用的 List 實現(xiàn)類，內(nèi)部是通過數(shù)組實現(xiàn)的，它允許對元素進行快速隨機訪問。
數(shù)組的缺點是每個元素之間不能有間隔，當(dāng)數(shù)組大小不滿足時需要增加存儲能力，就要將已經(jīng)有數(shù)組的數(shù)據(jù)復(fù)制到新的存儲空間中。當(dāng)從 ArrayList 的中間位置插入或者刪除元素時，需要對數(shù)組進 行復(fù)制、移動、代價比較高。
因此，它適合隨機查找和遍歷，不適合插入和刪除。
Vector（數(shù)組實現(xiàn)、線程同步）
Vector與ArrayList一樣，也是通過Object數(shù)組實現(xiàn)的，不同的是它支持線程的同步，即某一時刻只有一 個線程能夠?qū)?Vector，避免多線程同時寫而引起的不一致性，但實現(xiàn)同步需要很高的花費，因此， 訪問它比訪問ArrayList慢
LinkList（鏈表）
LinkedList是用鏈表結(jié)構(gòu)存儲數(shù)據(jù)的，很適合數(shù)據(jù)的動態(tài)插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當(dāng)作堆、棧、隊列和雙向隊列使用。
三、Set
Set注重獨一無二的性質(zhì)，該體系集合用于存儲無序(存入和取出的順序不一定相同)元素，值不能重復(fù)。
對象的相等性本質(zhì)是對象hashCode值（java是依據(jù)對象的內(nèi)存地址計算出的此序號）判斷的，如果想要讓兩個不同的對象視為相等的，就必須覆蓋Object的hashCode方法和equals方法。
HashSet（Hash 表）
哈希表邊存放的是哈希值。HashSet存儲元素的順序并不是按照存入時的順序（和List顯然不同） 而是按照哈希值來存的，所以取數(shù)據(jù)也是按照哈希值取得。
元素的哈希值是通過元素的 hashcode方法來獲取的，HashSet首先判斷兩個元素的哈希值，如果哈希值一樣，接著會比較 equals方法；如果equls結(jié)果為true ，HashSet就視為同一個元素。如果equals為false就不是 同一個元素。
哈希值相同、equals為false的元素是怎么存儲呢，就是在同樣的哈希值下順延（可以認(rèn)為哈希值相同的元素放在一個哈希桶中）。HashSet通過hashCode值來確定元素在內(nèi)存中的位置。一個hashCode位置上可以存放多個元 素。
TreeSet（二叉樹）
TreeSet()是使用二叉樹的原理對新add()的對象按照指定的順序排序（升序、降序），每增加一個對象都會進行排序，將對象插入的二叉樹指定的位置。
Integer和String對象都可以進行默認(rèn)的TreeSet排序，而自定義類的對象是不可以的，自己定義的類必須實現(xiàn)Comparable接口，并且覆寫相應(yīng)的compareTo()函數(shù)，才可以正常使用。
在覆寫compare()函數(shù)時，要返回相應(yīng)的值才能使TreeSet按照一定的規(guī)則來排序。
比較此對象與指定對象的順序。如果該對象小于、等于或大于指定對象，則分別返回負(fù)整 數(shù)、零或正整數(shù)
LinkHashSet（HashSet+LinkedHashMap）
對于 LinkedHashSet 而言，它繼承于HashSet、又基于 LinkedHashMap 來實現(xiàn)的。
LinkedHashSet 底層使用 LinkedHashMap 來保存所有元素，它繼承與 HashSet，其所有的方法 操作上又與HashSet相同，因此LinkedHashSet 的實現(xiàn)上非常簡單，只提供了四個構(gòu)造方法，并 通過傳遞一個標(biāo)識參數(shù)，調(diào)用父類的構(gòu)造器，底層構(gòu)造一個 LinkedHashMap 來實現(xiàn)，在相關(guān)操 作上與父類HashSet的操作相同，直接調(diào)用父類HashSet的方法即可。
四、Map
HashMap（數(shù)組+鏈表+紅黑樹） 重點?。?！
HashMap根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。
HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。
HashMap非線程安全，即任一時刻可以有多個線程同時寫 HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用 ConcurrentHashMap。我們用下面這張圖來介紹 HashMap 的結(jié)構(gòu)。
Java7實現(xiàn)
大方向上，HashMap 里面是一個數(shù)組，然后數(shù)組中每個元素是一個單向鏈表。上圖中，每個綠色的實體是嵌套類 Entry 的實例，Entry 包含四個屬性：key, value, hash 值和用于單向鏈表的 next。
- capacity：當(dāng)前數(shù)組容量，始終保持 2^n，可以擴容，擴容后數(shù)組大小為當(dāng)前的 2 倍。
- loadFactor：負(fù)載因子，默認(rèn)為 0.75。
- threshold：擴容的閾值，等于 capacity * loadFactor
Java8實現(xiàn)
Java8 對 HashMap 進行了一些修改，最大的不同就是利用了紅黑樹，所以其由 數(shù)組+鏈表+紅黑樹 組成。
根據(jù) Java7 HashMap 的介紹，我們知道，查找的時候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo)，但是之后的話，需要順著鏈表一個個比較下去才能找到我們需要的，時間復(fù)雜度取決于鏈表的長度，為 O(n)。為了降低這部分的開銷，在 Java8 中，當(dāng)鏈表中的元素超過了 8個以后， 會將鏈表轉(zhuǎn)換為紅黑樹，在這些位置進行查找的時候可以降低時間復(fù)雜度為 O(logN)。
ConcurrentHashMap（線程安全的HashMap）
Segment段： ConcurrentHashMap 和 HashMap 思路是差不多的，但是因為它支持并發(fā)操作，所以要復(fù)雜一 些。整個 ConcurrentHashMap 由一個個 Segment 組成，Segment 代表”部分“或”一段“的 意思，所以很多地方都會將其描述為分段鎖。
線程安全（Segment 繼承 ReentrantLock 加鎖）： 簡單理解就是，ConcurrentHashMap 是一個 Segment 數(shù)組，Segment 通過繼承 ReentrantLock 來進行加鎖，所以每次需要加鎖的操作鎖住的是一個 segment，這樣只要保證每個Segment是線程安全的，也就實現(xiàn)了全局的線程安全。
并行度(默認(rèn)16): concurrencyLevel：并發(fā)數(shù)，默認(rèn)是 16，也就是說 ConcurrentHashMap 有 16 個 Segments，所以理論上，這個時候，最多可以同時支持16 個線程并發(fā)寫，只要它們的操作分別分布在不同的Segment上。這個值可以在初始化的時候設(shè)置為其他值，但是一旦初始化以后，它是不可以擴容的。再具體到每個 Segment 內(nèi)部，其實每個 Segment 很像之前介紹的HashMap，不過它要保證線程安全，所以處理起來要麻煩些。
Java8 實現(xiàn)(引入了紅黑樹)：Java8 對 ConcurrentHashMap 進行了比較大的改動，Java8 也引入了紅黑樹。
HashTable（線程安全）
Hashtable 是遺留類，很多映射的常用功能與 HashMap 類似，不同的是它承自 Dictionary 類。
Hashtable是線程安全的，任一時間只有一個線程能寫 Hashtable，并發(fā)性不如 ConcurrentHashMap， 因為 ConcurrentHashMap 引入了分段鎖。
Hashtable 不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。
TreeMap（可排序）
TreeMap 實現(xiàn) SortedMap 接口，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序， 也可以指定排序的比較器，當(dāng)用Iterator遍歷TreeMap時，得到的記錄是排過序的。
如果使用排序的映射，建議使用TreeMap。
在使用 TreeMap 時，key 必須實現(xiàn) Comparable 接口或者在構(gòu)造 TreeMap 傳入自定義的 Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。
LinkHashMap（記錄插入順序）
LinkedHashMap 是 HashMap 的一個子類，保存了記錄的插入順序，在用 Iterator 遍歷 LinkedHashMap時，先得到的記錄肯定是先插入的，也可以在構(gòu)造時帶參數(shù)，按照訪問次序排序。
