集合類(lèi)存放在java.util包中，主要有三種：set（集），list（列表包括Queue）和map（映射）。

1. Collection：Collection是集合List、Set、Queue的最基本的接口。

2. Iterator：迭代器，可以通過(guò)迭代器遍歷集合中的數(shù)據(jù)。

3. Map：是映射表的基礎(chǔ)接口 。

一、ArrayList（數(shù)組）

ArrayList內(nèi)部是通過(guò)數(shù)組實(shí)現(xiàn)的，它允許對(duì)元素進(jìn)行快速隨機(jī)訪問(wèn)。

缺點(diǎn)是每個(gè)元素之間不能有間隔，當(dāng)數(shù)組大小不滿(mǎn)足時(shí)需要增加存儲(chǔ)能力，就要將已經(jīng)有數(shù)組的數(shù)據(jù)復(fù)制到新的存儲(chǔ)空間中。當(dāng)從 ArrayList 的中間位置插入或者刪除元素時(shí)，需要對(duì)數(shù)組進(jìn)行復(fù)制、移動(dòng)、代價(jià)比較高。因此，它適合隨機(jī)查找和遍歷，不適合插入和刪除。

二、LinkedList(鏈表)

LinkedList是用鏈表結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的，很適合數(shù)據(jù)的動(dòng)態(tài)插入和刪除，隨機(jī)訪問(wèn)和遍歷速度比較慢。另外，它還提供了List接口中沒(méi)有定義的方法，專(zhuān)門(mén)用于操作表頭和表尾元素，可以當(dāng)作堆棧、隊(duì)列和雙向隊(duì)列使用。

三、HashMap（數(shù)組+鏈表+紅黑樹(shù)）

HashMap根據(jù)鍵的hashCode值存儲(chǔ)數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問(wèn)速度，但遍歷順序卻是不確定的。HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。

HashMap非線程安全，即任一時(shí)刻可以有多個(gè)線程同時(shí)寫(xiě)HashMap，可能會(huì)導(dǎo)致數(shù)據(jù)的不一致。如果需要滿(mǎn)足線程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用 ConcurrentHashMap。

HashMap源碼解析——HashMap.hsah(Object key)

關(guān)鍵變量

HashMap源碼解析——resize

JAVA 7 實(shí)現(xiàn)

HashMap里面是一個(gè)數(shù)組，然后數(shù)組中每個(gè)元素是一個(gè)單向鏈表。上圖中，每個(gè)綠色的實(shí)體是嵌套類(lèi)Entry 的實(shí)例，Entry包含四個(gè)屬性：key, value, hash值和用于單向鏈表的next。

1. capacity：當(dāng)前數(shù)組容量，始終保持 2^n，可以擴(kuò)容，擴(kuò)容后數(shù)組大小為當(dāng)前的 2 倍。

2. loadFactor：負(fù)載因子，默認(rèn)為 0.75。

3. threshold：擴(kuò)容的閾值，等于capacity * loadFactor 。

JAVA 8 實(shí)現(xiàn)

Java 8 對(duì) HashMap 進(jìn)行了一些修改，最大的不同就是利用了紅黑樹(shù)，所以其由數(shù)組+鏈表+紅黑樹(shù)組成。
根據(jù) Java 7 HashMap 的介紹，我們知道，查找的時(shí)候，根據(jù) hash 值我們能夠快速定位到數(shù)組的 具體下標(biāo)，但是之后的話(huà)，需要順著鏈表一個(gè)個(gè)比較下去才能找到我們需要的，時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度，為 O(n)。為了降低這部分的開(kāi)銷(xiāo)，在Java8 中，當(dāng)鏈表中的元素超過(guò)了8個(gè)以后， 會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)，在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為 O(log N)。