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

ArrayList

ArrayList內部就是一個默認大小為10的動態對象數組容器，每當add一個新數據的時候，如果大于原來的容器大小，則會通過Arrays.copyOf把容器大小增加到原來的1.5倍，以此類推。當可以預知數據大小，可以通過initialCapacity來默認設置動態數據的大小，減少擴容帶來的資源消耗。

時間復雜度：

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

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

add(idnex, E) - 插入數據后需要移動后面的數據 - O(n)

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

LinkedList

LinkedList內部是一個雙向鏈表，add新數據的時候，其實就是調用linklast在鏈表尾部插入數據。刪除的時候直接找到對應數據，替換掉鏈表的前后節點即可。

時間復雜度：

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

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

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

remove() - 直接調用removeLast刪除最后數據 - O(1)

remove(index) - 需要先查找到原來index位置的數據 - O(n)

HashMap

HashMap內部其實是一個數組，每個數組下是一個單向鏈表。HashMap中的數組是一個取名為Entry的類，類包含(key, value, next)這幾個屬性。存放規則為，數組下標按hash(key)%len獲得，取得數組后則查找對應數組的值。HashMap還有個負載因子（默認0.75），當里面數組填滿了75%的時候，會進行擴展到原來大小的2倍。

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

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

public V put(K key, V value) { if (key == null) return putForNullKey(value); //null總是放在數組的第一個鏈表中 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; }

補充：

在java8之后hashmap進行了優化：由于單向鏈表的查詢時間復雜度為O(n)，在極端情況下可能存在性能問題，于是java8針對鏈表長度大于8的情況會使用時間復雜度為O(log n)的紅黑樹進行存儲來提升存儲查詢的效率。

LinkedHashMap

LinkedHashMap內部雙向鏈表和HashMap的結合，支持多種迭代順序，默認按插入順序，也可以按訪問順序。

訪問順序（accessOrder=true）：調用過get訪問的元素會放到鏈尾，迭代會從鏈首開始

插入順序（accessOrder=false）：按插入順序迭代出來

TreeMap

TreeMap內部是基于紅黑樹實現的，并且默認會通過compareTo按照key類型進行自然排序。TreeSet的低層是TreeMap。

來自：http://www.jointforce.com/jfperiodical/article/4192