HashMap介紹
基本實(shí)現(xiàn)原理
- jdk1.7是數(shù)組+鏈表實(shí)現(xiàn)噪馏。
- jdk1.8是數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)狡蝶，鏈表長(zhǎng)度達(dá)到8會(huì)轉(zhuǎn)成紅黑樹阳柔。
一些擴(kuò)展知識(shí)
- 為啥使用紅黑樹不用AVL樹：紅黑樹的平衡性相對(duì)avl來說稍差，但是旋轉(zhuǎn)操作更少王财，插入和刪除效率更高。
- 為啥每次擴(kuò)容2倍：方便位運(yùn)算裕便，以及降低hash沖突（初始容量是16）绒净。
- 為啥并發(fā)下會(huì)出現(xiàn)死循環(huán)：1.7版本之前hash沖突是使用頭插法，在多線程并發(fā)同時(shí)擴(kuò)容時(shí)可能會(huì)出現(xiàn)死循環(huán)偿衰。1.8版本使用尾插法解決挂疆。
ConcurrentHashMap介紹
基本實(shí)現(xiàn)原理
- jdk1.7采用分段鎖，內(nèi)部是是個(gè)Segment數(shù)組下翎，Segment里面是一個(gè)數(shù)組+鏈表缤言。Segment繼承了ReentrantLock。往map里面put數(shù)據(jù)的時(shí)候视事，會(huì)先定位數(shù)據(jù)在哪個(gè)Segment上胆萧，然后對(duì)這個(gè)Segment進(jìn)行加鎖
- jdk1.8是采用cas+synchronized，在沒有hash沖突時(shí)俐东，使用cas將元素放到數(shù)組對(duì)應(yīng)的位置上中跌穗。當(dāng)出現(xiàn)hash沖突時(shí)订晌，會(huì)使用synchronized對(duì)數(shù)組中對(duì)應(yīng)位置上的node節(jié)點(diǎn)加鎖。
一些擴(kuò)展知識(shí)
- 擴(kuò)容加速：擴(kuò)容時(shí)其它線程寫操作會(huì)協(xié)助擴(kuò)容蚌吸，而不是阻塞等待
- 計(jì)數(shù)器優(yōu)化：采用了longadder的思想腾仅，空間換時(shí)間，將個(gè)數(shù)分散到一個(gè)數(shù)組中套利，不同線程對(duì)不同的槽位進(jìn)行累加，減少并發(fā)度鹤耍，從而達(dá)到更高的性能
- 為什么key和val不允許為null：在多線程并發(fā)情況下肉迫，null會(huì)帶來二義性。當(dāng)我們通過get獲取到key的value為null時(shí)稿黄，你無法判斷是put的時(shí)候value為null喊衫，還是這個(gè)key本身就不在map里面
