更多 Java 集合類方面的文章，請(qǐng)參見文集《Java 集合類》
最近看到了一篇文章 無鎖HASHMAP的原理與實(shí)現(xiàn)妻枕，很受用焦辅，做一些筆記。
Hashtable Collections.synchronizedMap ConcurrentHashMap在實(shí)現(xiàn)的具體細(xì)節(jié)上婚惫，都或多或少地用到了互斥鎖氛赐。
互斥鎖會(huì)造成線程阻塞，降低運(yùn)行效率先舷，并有可能產(chǎn)生死鎖艰管、優(yōu)先級(jí)翻轉(zhuǎn)等一系列問題。
無鎖鏈表的實(shí)現(xiàn)
如果一個(gè)鏈表在執(zhí)行插入操作時(shí)蒋川，不添加鎖牲芋，在多線程的情況下，可能會(huì)產(chǎn)生問題捺球。
例如：
- 線程T1嘗試在節(jié)點(diǎn)A和節(jié)點(diǎn)B之間插入節(jié)點(diǎn)C缸浦。該過程包括如下兩步：
C.next = B;A.next = C;
- 線程T2嘗試在節(jié)點(diǎn)A和節(jié)點(diǎn)B之間插入節(jié)點(diǎn)D。該過程包括如下兩步：
D.next = B;A.next = D;
如果我們不做任何判斷氮兵，可能造成其他線程插入節(jié)點(diǎn)的丟失裂逐。例如 T1 先執(zhí)行，T2 后執(zhí)行胆剧，則會(huì)丟失節(jié)點(diǎn)C絮姆。
我們可以利用 CAS 操作，在為節(jié)點(diǎn)A的 next 指針賦值時(shí)秩霍，判斷其是否仍然指向B篙悯，如果節(jié)點(diǎn)A的 next 指針發(fā)生了變化（例如指向了節(jié)點(diǎn)C）則重試整個(gè)插入操作。大致代碼如下：
private void listInsert(Node head, Node C) {
for (;;) { // 放在一個(gè)死循環(huán)中
Node A = findInsertionPlace(head);
Node B = A.next.get();
C.next.set(B);
if (A.next.compareAndSet(B, C))
return;
}
}
Node類的 next 字段為 AtomicReference<Node> 類型铃绒，即指向Node類型的原子性引用鸽照，具體使用請(qǐng)參見 Java 原子性引用 AtomicReference
無鎖鏈表的 查找操作 與普通鏈表沒有區(qū)別。
而其 刪除操作颠悬，則需要找到待刪除節(jié)點(diǎn)前方的節(jié)點(diǎn)A和后方的節(jié)點(diǎn)B矮燎，利用CAS操作驗(yàn)證并更新節(jié)點(diǎn)A的 next 指針，使其指向節(jié)點(diǎn)B赔癌。
無鎖 HashMap 的難點(diǎn)與突破
HashMap 主要有插入诞外、刪除、查找以及 ReHash 四種基本操作灾票。
一個(gè)典型的 HashMap 實(shí)現(xiàn)峡谊，會(huì)用到一個(gè)數(shù)組，數(shù)組的每項(xiàng)元素為一個(gè)節(jié)點(diǎn)的鏈表。
對(duì)于此鏈表既们，我們可以利用上文提到的操作方法濒析，執(zhí)行插入、刪除以及查找操作啥纸。
