一、概論
????這篇文章的目的只有一個(gè)就是對日常開發(fā)中遇到的一些數(shù)據(jù)結(jié)構(gòu)對其特點(diǎn)逝淹，進(jìn)行歸納總結(jié)耕姊，具體的細(xì)節(jié)再后續(xù)的文章再一一解釋。
二栅葡、特點(diǎn)分析
2.1 ArrayList
- 基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)茉兰，當(dāng)創(chuàng)建一個(gè) ArrayList 對象時(shí)，實(shí)際上是創(chuàng)建了一個(gè) Object 類型的數(shù)組欣簇，初始容量為 10
- 當(dāng)添加元素時(shí)规脸，如果數(shù)組已滿，ArrayList 會(huì)自動(dòng)擴(kuò)容熊咽，它會(huì)創(chuàng)建一個(gè)新的數(shù)組莫鸭，并將原數(shù)組中的元素復(fù)制到新數(shù)組中。
- 使用了快速失敗機(jī)制 (Fail-Fast)
指的是在多線程環(huán)境下横殴，如果一個(gè)線程修改了ArrayList的結(jié)構(gòu)（增加被因、刪除或修改元素），那么其他線程在訪問ArrayList時(shí)衫仑，如果發(fā)現(xiàn)modCount屬性（記錄ArrayList結(jié)構(gòu)修改次數(shù)的屬性）與自己持有的modCount屬性不一致梨与，就會(huì)拋出ConcurrentModificationException異常，從而防止多個(gè)線程同時(shí)修改ArrayList的結(jié)構(gòu)文狱，導(dǎo)致數(shù)據(jù)不一致的情況發(fā)生粥鞋。
2.2 LinkedList
優(yōu)點(diǎn)：
鏈表的主要優(yōu)點(diǎn)是在插入和刪除節(jié)點(diǎn)時(shí)具有較低的時(shí)間復(fù)雜度。因?yàn)殒湵碇械墓?jié)點(diǎn)可以在內(nèi)存中非連續(xù)地分布瞄崇，插入和刪除操作只涉及到修改指針的指向呻粹，而不需要移動(dòng)其他節(jié)點(diǎn)到踏。這使得鏈表在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)、頻繁的插入和刪除操作以及不需要事先知道數(shù)據(jù)大小的情況下非常有用尚猿。缺點(diǎn)：
然而窝稿，鏈表的缺點(diǎn)是訪問特定位置的節(jié)點(diǎn)需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為O(n)凿掂。與數(shù)組相比伴榔，鏈表的隨機(jī)訪問效率較低。此外庄萎，鏈表需要額外的內(nèi)存來存儲(chǔ)指針或引用踪少。LinkedList是List接口的雙向鏈表非同步實(shí)現(xiàn)，并允許包括null在內(nèi)的所有元素糠涛。
底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向鏈表的援奢，該數(shù)據(jù)結(jié)構(gòu)我們稱為節(jié)點(diǎn)
允許所有元素為null
它的查找是分兩半查找，先判斷index是在鏈表的哪一半忍捡，然后再去對應(yīng)區(qū)域查找集漾，這樣最多只要遍歷鏈表的一半節(jié)點(diǎn)即可找到
鏈表的特點(diǎn)就是在指定位置插入和刪除元素的效率較高，但是查找的 效率就不如數(shù)組那么高了
2.3 HashMap
HashMap 內(nèi)部維護(hù)了一個(gè)數(shù)組砸脊，稱為哈希表具篇，每個(gè)元素都是一個(gè)鏈表的頭結(jié)點(diǎn)，該鏈表被稱為桶（bucket）凌埂。當(dāng)我們向 HashMap 中添加一個(gè)元素時(shí)驱显，首先會(huì)根據(jù)該元素的鍵值（key）計(jì)算出一個(gè)哈希值（hash code），然后根據(jù)哈希值確定該元素在數(shù)組中的位置瞳抓，如果該位置上已經(jīng)存在了元素埃疫，則將該元素添加到該位置上對應(yīng)的桶中，如果該位置上沒有元素孩哑，則創(chuàng)建一個(gè)新的桶栓霜，并將該元素添加到該桶中。
在查找元素時(shí)臭笆，HashMap 會(huì)根據(jù) key 的哈希值確定其在數(shù)組中的位置叙淌，然后遍歷該位置上的鏈表秤掌，查找是否存在對應(yīng)的 key愁铺。如果存在，則返回其對應(yīng)的 value闻鉴；如果不存在茵乱，則返回 null。由于哈希值可能會(huì)發(fā)生沖突孟岛，因此同一個(gè)桶上可能會(huì)有多個(gè)元素瓶竭，需要遍歷鏈表才能找到對應(yīng)的元素督勺。
- HashMap 是非線程安全的，因?yàn)樗皇峭降慕锓。鄠€(gè)線程同時(shí)對 HashMap 進(jìn)行操作可能會(huì)導(dǎo)致數(shù)據(jù)不一致的問題智哀。
- HashMap的實(shí)現(xiàn)原理是通過將鍵對象的哈希碼映射到哈希表的索引位置來存儲(chǔ)和獲取值對象。當(dāng)多個(gè)鍵對象的哈希碼映射到同一個(gè)索引位置時(shí)荧恍，會(huì)使用鏈表或紅黑樹等數(shù)據(jù)結(jié)構(gòu)來解決沖突問題瓷叫。
優(yōu)點(diǎn)：
- 高效的插入、刪除和查找操作：由于使用哈希表來存儲(chǔ)鍵值對送巡，HashMap提供了快速的插入摹菠、刪除和查找操作
- 可以存儲(chǔ)null鍵和null值：HashMap允許存儲(chǔ)null鍵和null值，這在某些場景下非常有用
- 動(dòng)態(tài)擴(kuò)容：HashMap會(huì)根據(jù)當(dāng)前存儲(chǔ)的元素?cái)?shù)量動(dòng)態(tài)調(diào)整內(nèi)部數(shù)組的大小骗爆，以提高性能
缺點(diǎn)：
- 不保證元素的順序：HashMap不保證元素的順序次氨，如果需要有序的鍵值對集合，可以考慮使用LinkedHashMap
- 線程不安全：HashMap是非線程安全的摘投，如果在多線程環(huán)境下使用煮寡，需要進(jìn)行額外的同步處理，或者使用線程安全的ConcurrentHashMap犀呼。
2.4 ConcurrentHashMap
ConcurrentHashMap是Java中的一種線程安全的哈希表實(shí)現(xiàn)洲押，它是HashMap的一個(gè)線程安全版本。與HashMap不同的是圆凰，ConcurrentHashMap可以在多線程環(huán)境下進(jìn)行并發(fā)操作而不需要額外的同步措施杈帐。它提供了高效的并發(fā)讀取和更新操作，并且保證了線程安全性专钉。
ConcurrentHashMap的實(shí)現(xiàn)原理是將整個(gè)哈希表分成多個(gè)小的子哈希表（稱為段）挑童，每個(gè)段都可以獨(dú)立地進(jìn)行讀寫操作。每個(gè)段內(nèi)部使用了與HashMap類似的哈希桶和鏈表（或紅黑樹）的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)鍵值對跃须。當(dāng)多個(gè)線程同時(shí)訪問不同的段時(shí)站叼，它們可以并發(fā)地進(jìn)行讀寫操作，從而提高了并發(fā)性能菇民。
優(yōu)點(diǎn)：
- 高效的并發(fā)讀取和更新操作：ConcurrentHashMap允許多個(gè)線程同時(shí)進(jìn)行讀取和更新操作尽楔，提供了較好的并發(fā)性能。
- 線程安全性：ConcurrentHashMap通過使用鎖分段技術(shù)來保證線程安全性第练，不需要額外的同步措施阔馋。
- 動(dòng)態(tài)擴(kuò)容：ConcurrentHashMap可以根據(jù)需要?jiǎng)討B(tài)調(diào)整大小，以適應(yīng)不同的并發(fā)訪問情況娇掏。
缺點(diǎn)：
內(nèi)存占用較大：由于ConcurrentHashMap需要維護(hù)多個(gè)段擎浴，因此相對于HashMap來說联逻，它的內(nèi)存占用會(huì)更大一些。
迭代性能較低：由于ConcurrentHashMap的內(nèi)部結(jié)構(gòu)是分段的歧寺，因此在迭代操作時(shí)性能可能會(huì)受到一定的影響。
ConcurrentHashMap在實(shí)際開發(fā)中常用于需要高并發(fā)讀寫操作的場景，例如緩存、并發(fā)任務(wù)處理和并發(fā)計(jì)算等。它提供了一種線程安全的哈希表實(shí)現(xiàn)讶坯，可以有效地處理多線程環(huán)境下的并發(fā)訪問問題。
2.5 HashTable
Hashtable底層也采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)岗屏，當(dāng)哈希沖突發(fā)生時(shí)闽巩，使用鏈表來解決沖突。與HashMap不同的是担汤，Hashtable在JDK 8及以前沒有使用紅黑樹解決哈希沖突涎跨，這導(dǎo)致了其效率相對較低。
Hashtable是線程安全的類崭歧，即多個(gè)線程同時(shí)操作Hashtable中的元素也不會(huì)產(chǎn)生錯(cuò)誤的結(jié)果或者拋出ConcurrentModificationException異常隅很。
Hashtable不允許存儲(chǔ)null值和null鍵，否則將會(huì)拋出NullPointerException異常率碾。
Hashtable在JDK 8及以前沒有使用紅黑樹解決哈希沖突叔营，相對于HashMap而言，Hashtable的效率比較低所宰。另外绒尊，由于Hashtable不支持null鍵和null值，因此對其進(jìn)行操作時(shí)要額外小心仔粥。Hashtable的查找婴谱、插入和刪除操作平均時(shí)間復(fù)雜度為O(1)，但是在極端情況下躯泰，因?yàn)楣_突的原因谭羔，可能會(huì)退化到O(n)。
參考文獻(xiàn)
ArrayList 的底層原理和源碼分析
深入理解Array麦向、List瘟裸、Map集合框架底層實(shí)現(xiàn)原理
ArrayList的底層實(shí)現(xiàn)原理
LinkedList 的實(shí)現(xiàn)原理
LinkedList原理解析
hashmap & hashtable 區(qū)別
hashmap hashtable學(xué)習(xí)筆記
ConcurrentHashMap 底層原理
深入理解ConcurrentHashMap
深度解析Hashtable
