更多 Java 集合类方面的文章，请参见文集《Java 集合类》
最近看到了一篇文章 无锁HASHMAP的原理与实现，很受用，做一些笔记。
Hashtable Collections.synchronizedMap ConcurrentHashMap在实现的具体细节上，都或多或少地用到了互斥锁。
互斥锁会造成线程阻塞，降低运行效率，并有可能产生死锁、优先级翻转等一系列问题。
无锁链表的实现
如果一个链表在执行插入操作时，不添加锁，在多线程的情况下，可能会产生问题。
例如：
- 线程T1尝试在节点A和节点B之间插入节点C。该过程包括如下两步：
C.next = B;A.next = C;
- 线程T2尝试在节点A和节点B之间插入节点D。该过程包括如下两步：
D.next = B;A.next = D;
如果我们不做任何判断，可能造成其他线程插入节点的丢失。例如 T1 先执行，T2 后执行，则会丢失节点C。
我们可以利用 CAS 操作，在为节点A的 next 指针赋值时，判断其是否仍然指向B，如果节点A的 next 指针发生了变化（例如指向了节点C）则重试整个插入操作。大致代码如下：
private void listInsert(Node head, Node C) {
for (;;) { // 放在一个死循环中
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类型的原子性引用，具体使用请参见 Java 原子性引用 AtomicReference
无锁链表的 查找操作 与普通链表没有区别。
而其 删除操作，则需要找到待删除节点前方的节点A和后方的节点B，利用CAS操作验证并更新节点A的 next 指针，使其指向节点B。
无锁 HashMap 的难点与突破
HashMap 主要有插入、删除、查找以及 ReHash 四种基本操作。
一个典型的 HashMap 实现，会用到一个数组，数组的每项元素为一个节点的链表。
对于此链表，我们可以利用上文提到的操作方法，执行插入、删除以及查找操作。
引用：
无锁HASHMAP的原理与实现
