常用容器操作實現(xiàn)原理匯總
ArrayList實現(xiàn)原理要點概括
ArrayList是List接口的可變數(shù)組非同步實現(xiàn)员寇，并允許包括null在內(nèi)的所有元素。
底層使用數(shù)組實現(xiàn) 陆爽。
該集合是可變長度數(shù)組扳缕，數(shù)組擴容時别威，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中省古，每次數(shù)組容量增長大約是其容量的1.5倍仔拟，這種操作的代價很高。
若是能預(yù)估到頂峰容量科侈，可以設(shè)置一個足夠大的量以避免數(shù)組容量以后的擴展炒事。
采用了Fail-Fast機制，面對并發(fā)的修改時挠乳，迭代器很快就會完全失敗睡扬，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風險 。
remove方法會讓下標到數(shù)組末尾的元素向前移動一個單位卖怜，并把最后一位的值置空马靠，方便GC 。
add逞度、remove操作對于ArrayList其運行時間是O（N）妙啃，因為在它當中在前端進行添加或移除構(gòu)造新數(shù)組是O（N）操作；get方法的調(diào)用為O（1）操作茁瘦。
要是使用一個增強的for循環(huán)储笑，對于任意List的運行時間都是O（N），因為迭代器將有效地從一項到下一項推進腔稀。
LinkedList實現(xiàn)原理要點概括
LinkedList是List接口的雙向鏈表非同步實現(xiàn)焊虏，并允許包括null在內(nèi)的所有元素。
底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向鏈表的炼团，該數(shù)據(jù)結(jié)構(gòu)我們稱為節(jié)點疏尿。
雙向鏈表節(jié)點對應(yīng)的類Node的實例，Node中包含成員變量：prev锌俱，next敌呈，item磕洪。
其中，prev是該節(jié)點的上一個節(jié)點鲫咽，next是該節(jié)點的下一個節(jié)點叫榕，item是該節(jié)點所包含的值姊舵。
它的查找是分兩半查找括丁，先判斷index是在鏈表的哪一半，然后再去對應(yīng)區(qū)域查找尖昏，這樣最多只要遍歷鏈表的一半節(jié)點即可找到 构资。
add、remove操作對于LinkedList其運行時間是O（1）迹淌；get方法的調(diào)用為O（N）操作。
要是使用一個增強的for循環(huán)耙饰，對于任意List的運行時間都是O（N）纹份，因為迭代器將有效地從一項到下一項推進蔓涧。
HashMap實現(xiàn)原理要點概括
HashMap是基于哈希表的Map接口的非同步實現(xiàn)，允許使用null值和null鍵拨齐，但不保證映射的順序昨寞。
底層使用數(shù)組實現(xiàn)援岩，數(shù)組中每一項是個單向鏈表，即數(shù)組和鏈表的結(jié)合體羽峰；當鏈表長度大于一定閾值時添瓷，鏈表轉(zhuǎn)換為紅黑樹，這樣減少鏈表查詢時間坯汤。
HashMap在底層將key-value當成一個整體進行處理惰聂，這個整體就是一個Node對象咱筛。
HashMap底層采用一個Node[]數(shù)組來保存所有的key-value對，當需要存儲一個Node對象時溉愁，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置饲趋，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當需要取出一個Node時投队，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置敷鸦，再根據(jù)equals方法從該位置上的鏈表中取出該Node。
HashMap進行數(shù)組擴容需要重新計算擴容后每個元素在數(shù)組中的位置值依，很耗性能。
采用了Fail-Fast機制漾脂，通過一個modCount值記錄修改次數(shù)辆亏，對HashMap內(nèi)容的修改都將增加這個值鳖目。
迭代器初始化過程中會將這個值賦給迭代器的expectedModCount领迈，在迭代過程中，判斷modCount跟expectedModCount是否相等衷蜓，如果不相等就表示已經(jīng)有其他線程修改了Map尘喝，馬上拋出異常瞧省。
HashMap解決沖突的方式是鏈地址法,詳情可參考文章Java基礎(chǔ)-集合類-哈希鳍贾，HashMap通過鍵對象的equals()方法用來找到鍵以及對應(yīng)的值的骑科。如果鏈表大小超過閾值（TREEIFY_THRESHOLD, 8），鏈表就會被改造為樹形結(jié)構(gòu)梁棠。
Hashtable實現(xiàn)原理要點概括
Hashtable是基于哈希表的Map接口的同步實現(xiàn)置森，不允許使用null值和null鍵。
底層使用數(shù)組實現(xiàn)符糊，數(shù)組中每一項是個單鏈表凫海，即數(shù)組和鏈表的結(jié)合體。
Hashtable在底層將key-value當成一個整體進行處理男娄，這個整體就是一個Entry對象行贪。
Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對，當需要存儲一個Entry對象時模闲，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置建瘫，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當需要取出一個Entry時尸折，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置啰脚，再根據(jù)equals方法從該位置上的鏈表中取出該Entry实夹。
synchronized是針對整張Hash表的橄浓，即每次鎖住整張表讓線程獨占。
HashSet實現(xiàn)原理要點概括
HashSet由哈希表(實際上是一個HashMap實例)支持亮航，不保證set的迭代順序贮配，并允許使用null元素。
基于HashMap實現(xiàn)塞赂，API也是對HashMap的行為進行了封裝泪勒，可參考HashMap。
LinkedHashMap實現(xiàn)原理要點概括
LinkedHashMap繼承于HashMap宴猾，底層使用哈希表和雙向鏈表來保存所有元素圆存，并且它是非同步，允許使用null值和null鍵仇哆。
基本操作與父類HashMap相似沦辙，通過重寫HashMap相關(guān)方法，重新定義了數(shù)組中保存的元素Entry讹剔，來實現(xiàn)自己的鏈接列表特性油讯。
該Entry除了保存當前對象的引用外，還保存了其上一個元素before和下一個元素after的引用延欠，從而構(gòu)成了雙向鏈接列表陌兑。
LinkedHashSet實現(xiàn)原理要點概括
對于LinkedHashSet而言，它繼承與HashSet由捎、又基于LinkedHashMap來實現(xiàn)的兔综。LinkedHashSet底層使用LinkedHashMap來保存所有元素，它繼承與HashSet，其所有的方法操作上又與HashSet相同软驰。
ConcurrentHashMap實現(xiàn)原理要點概括
ConcurrentHashMap允許多個修改操作并發(fā)進行涧窒，其關(guān)鍵在于使用了鎖分離技術(shù)。
它使用了多個鎖來控制對hash表的不同段進行的修改锭亏，每個段其實就是一個小的hashtable纠吴，它們有自己的鎖。
只要多個并發(fā)發(fā)生在不同的段上慧瘤，它們就可以并發(fā)進行呜象。
ConcurrentHashMap在底層將key-value當成一個整體進行處理，這個整體就是一個Entry對象碑隆。
Hashtable底層采用一個Entry[]數(shù)組來保存所有的key-value對恭陡，當需要存儲一個Entry對象時，會根據(jù)key的hash算法來決定其在數(shù)組中的存儲位置上煤，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置休玩；當需要取出一個Entry時，也會根據(jù)key的hash算法找到其在數(shù)組中的存儲位置劫狠，再根據(jù)equals方法從該位置上的鏈表中取出該Entry拴疤。
與HashMap不同的是，ConcurrentHashMap使用多個子Hash表独泞，也就是段(Segment) ConcurrentHashMap完全允許多個讀操作并發(fā)進行呐矾，讀操作并不需要加鎖。
如果使用傳統(tǒng)的技術(shù)懦砂，如HashMap中的實現(xiàn)蜒犯，如果允許可以在hash鏈的中間添加或刪除元素，讀操作不加鎖將得到不一致的數(shù)據(jù)荞膘。
ConcurrentHashMap實現(xiàn)技術(shù)是保證HashEntry幾乎是不可變的罚随。
ConcurrentHashMap實現(xiàn)原理詳細介紹
