對(duì)于常用的集合大家都不陌生，但是深入到內(nèi)部原理可能都是一知半解，通過(guò)閱讀源碼理解如下。

ArrayList

ArrayList內(nèi)部就是一個(gè)默認(rèn)大小為10的動(dòng)態(tài)對(duì)象數(shù)組容器，每當(dāng)add一個(gè)新數(shù)據(jù)的時(shí)候，如果大于原來(lái)的容器大小，則會(huì)通過(guò)Arrays.copyOf把容器大小增加到原來(lái)的1.5倍，以此類推。當(dāng)可以預(yù)知數(shù)據(jù)大小，可以通過(guò)initialCapacity來(lái)默認(rèn)設(shè)置動(dòng)態(tài)數(shù)據(jù)的大小，減少擴(kuò)容帶來(lái)的資源消耗。

時(shí)間復(fù)雜度：

get() - 直接讀取下標(biāo) - O(1)

add(E) - 直接在后面添加 - O(1)

add(idnex, E) - 插入數(shù)據(jù)后需要移動(dòng)后面的數(shù)據(jù) - O(n)

remove(index) - 刪除后需要移動(dòng) - O(n)

LinkedList

LinkedList內(nèi)部是一個(gè)雙向鏈表，add新數(shù)據(jù)的時(shí)候，其實(shí)就是調(diào)用linklast在鏈表尾部插入數(shù)據(jù)。刪除的時(shí)候直接找到對(duì)應(yīng)數(shù)據(jù)，替換掉鏈表的前后節(jié)點(diǎn)即可。

時(shí)間復(fù)雜度：

get() - 需要遍歷 - O(n)

add(E) - 調(diào)用linklast直接添加在最后 - O(1)

add(index, E) - 需要先查找到原來(lái)index位置的數(shù)據(jù)，再重新指定鏈表前后的數(shù)據(jù) - O(n)

remove() - 直接調(diào)用removeLast刪除最后數(shù)據(jù) - O(1)

remove(index) - 需要先查找到原來(lái)index位置的數(shù)據(jù) - O(n)

HashMap

HashMap內(nèi)部其實(shí)是一個(gè)數(shù)組，每個(gè)數(shù)組下是一個(gè)單向鏈表。HashMap中的數(shù)組是一個(gè)取名為Entry的類，類包含(key, value, next)這幾個(gè)屬性。存放規(guī)則為，數(shù)組下標(biāo)按hash(key)%len獲得，取得數(shù)組后則查找對(duì)應(yīng)數(shù)組的值。HashMap還有個(gè)負(fù)載因子（默認(rèn)0.75），當(dāng)里面數(shù)組填滿了75%的時(shí)候，會(huì)進(jìn)行擴(kuò)展到原來(lái)大小的2倍。

那么問(wèn)題來(lái)了，如果在put的時(shí)候，取到hash(key)%len的值相等時(shí)不就沖突了？HashMap的處理方法是：原來(lái)有一個(gè)Entry[0] = A，此時(shí)來(lái)一個(gè)index也是0的B，則會(huì)把Entry[0] = B，B.next = A，又來(lái)一個(gè)C的時(shí)候，則會(huì)把Entry[0] = C，C.next = B，以此類推。這樣Entry就會(huì)形成一個(gè)鏈表，取的時(shí)候則是遍歷鏈表取值。

這里需要提到的是，使用hashMap的時(shí)候，引入的key對(duì)象必須重寫hashCode()和equal()兩個(gè)函數(shù)，原因可以參考源碼判斷條件(if (e.hash == hash && ((k = e.key) == key || key.equals(k))))，如果hashCode()沒(méi)重寫，則壓根找不到對(duì)應(yīng)數(shù)組，如果equal()沒(méi)重寫，則無(wú)法判斷key值的內(nèi)容是否相等。

public V put(K key, V value) { if (key == null) return putForNullKey(value); //null總是放在數(shù)組的第一個(gè)鏈表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //遍歷鏈表 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果key在鏈表中已存在，則替換為新value if (e.hash == hash && ((k = e.key) == key || key.equals(k))){ V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

補(bǔ)充：

在java8之后hashmap進(jìn)行了優(yōu)化：由于單向鏈表的查詢時(shí)間復(fù)雜度為O(n)，在極端情況下可能存在性能問(wèn)題，于是java8針對(duì)鏈表長(zhǎng)度大于8的情況會(huì)使用時(shí)間復(fù)雜度為O(log n)的紅黑樹(shù)進(jìn)行存儲(chǔ)來(lái)提升存儲(chǔ)查詢的效率。

LinkedHashMap

LinkedHashMap內(nèi)部雙向鏈表和HashMap的結(jié)合，支持多種迭代順序，默認(rèn)按插入順序，也可以按訪問(wèn)順序。

訪問(wèn)順序（accessOrder=true）：調(diào)用過(guò)get訪問(wèn)的元素會(huì)放到鏈尾，迭代會(huì)從鏈?zhǔn)组_(kāi)始

插入順序（accessOrder=false）：按插入順序迭代出來(lái)

TreeMap

TreeMap內(nèi)部是基于紅黑樹(shù)實(shí)現(xiàn)的，并且默認(rèn)會(huì)通過(guò)compareTo按照key類型進(jìn)行自然排序。TreeSet的低層是TreeMap。

來(lái)自：http://www.jointforce.com/jfperiodical/article/4192