1【List、set、Map的底層實作原理】

ArrayList實作原理要點概括 

ArrayList是List接口的可變數組非同步實作，并允許包括null在内的所有元素。

底層使用數組實作

該集合是可變長度數組，數組擴容時，會将老數組中的元素重新拷貝一份到新的數組中，每次數組容量增長大約是其容量的1.5倍，這種操作的代價很高。

采用了Fail-Fast機制，面對并發的修改時，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險

remove方法會讓下标到數組末尾的元素向前移動一個機關，并把最後一位的值置空，友善GC

LinkedList實作原理要點概括 

LinkedList是List接口的雙向連結清單非同步實作，并允許包括null在内的所有元素。

底層的資料結構是基于雙向連結清單的，該資料結構我們稱為節點

雙向連結清單節點對應的類Node的執行個體，Node中包含成員變量：prev，next，item。其中，prev是該節點的上一個節點，next是該節點的下一個節點，item是該節點所包含的值。

它的查找是分兩半查找，先判斷index是在連結清單的哪一半，然後再去對應區域查找，這樣最多隻要周遊連結清單的一半節點即可找到

HashMap實作原理要點概括 

HashMap是基于哈希表的Map接口的非同步實作，允許使用null值和null鍵，但不保證映射的順序。

底層使用數組實作，數組中每一項是個單向連結清單，即數組和連結清單的結合體；當連結清單長度大于一定門檻值時，連結清單轉換為紅黑樹，這樣減少連結清單查詢時間。

HashMap在底層将key-value當成一個整體進行處理，這個整體就是一個Node對象。HashMap底層采用一個Node[]數組來儲存所有的key-value對，當需要存儲一個Node對象時，會根據key的hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Node時，也會根據key的hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的連結清單中取出該Node。

HashMap進行數組擴容需要重新計算擴容後每個元素在數組中的位置，很耗性能

采用了Fail-Fast機制，通過一個modCount值記錄修改次數，對HashMap内容的修改都将增加這個值。疊代器初始化過程中會将這個值賦給疊代器的expectedModCount，在疊代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經有其他線程修改了Map，馬上抛出異常

Hashtable實作原理要點概括

Hashtable是基于哈希表的Map接口的同步實作，不允許使用null值和null鍵

底層使用數組實作，數組中每一項是個單連結清單，即數組和連結清單的結合體

Hashtable在底層将key-value當成一個整體進行處理，這個整體就是一個Entry對象。Hashtable底層采用一個Entry[]數組來儲存所有的key-value對，當需要存儲一個Entry對象時，會根據key的hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Entry時，也會根據key的hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的連結清單中取出該Entry。

synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨占

ConcurrentHashMap實作原理要點概括 

ConcurrentHashMap允許多個修改操作并發進行，其關鍵在于使用了鎖分離技術。

它使用了多個鎖來控制對hash表的不同段進行的修改，每個段其實就是一個小的hashtable，它們有自己的鎖。隻要多個并發發生在不同的段上，它們就可以并發進行。

ConcurrentHashMap在底層将key-value當成一個整體進行處理，這個整體就是一個Entry對象。Hashtable底層采用一個Entry[]數組來儲存所有的key-value對，當需要存儲一個Entry對象時，會根據key的hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Entry時，也會根據key的hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的連結清單中取出該Entry。

與HashMap不同的是，ConcurrentHashMap使用多個子Hash表，也就是段(Segment)

ConcurrentHashMap完全允許多個讀操作并發進行，讀操作并不需要加鎖。如果使用傳統的技術，如HashMap中的實作，如果允許可以在hash鍊的中間添加或删除元素，讀操作不加鎖将得到不一緻的資料。ConcurrentHashMap實作技術是保證HashEntry幾乎是不可變的。

HashSet實作原理要點概括 

HashSet由哈希表(實際上是一個HashMap執行個體)支援，不保證set的疊代順序，并允許使用null元素。

基于HashMap實作，API也是對HashMap的行為進行了封裝，可參考HashMap

LinkedHashMap實作原理要點概括 

LinkedHashMap繼承于HashMap，底層使用哈希表和雙向連結清單來儲存所有元素，并且它是非同步，允許使用null值和null鍵。

基本操作與父類HashMap相似，通過重寫HashMap相關方法，重新定義了數組中儲存的元素Entry，來實作自己的連結清單特性。該Entry除了儲存目前對象的引用外，還儲存了其上一個元素before和下一個元素after的引用，進而構成了雙向連結清單。

LinkedHashSet實作原理要點概括