无锁HashMap的原理与实现
(本文由onetwogoo投稿)
在《疫苗：Java HashMap的死循环》中，我们看到，java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap，主要有以下几种选择：
- 使用线程安全的java.util.Hashtable作为替代。
- 使用java.util.Collections.synchronizedMap方法，将已有的HashMap对象包装为线程安全的。
- 使用java.util.concurrent.ConcurrentHashMap类作为替代，它具有非常好的性能。
而以上几种方法在实现的具体细节上，都或多或少地用到了互斥锁。互斥锁会造成线程阻塞，降低运行效率，并有可能产生死锁、优先级翻转等一系列问题。
CAS(Compare And Swap)是一种底层硬件提供的功能，它可以将判断并更改一个值的操作原子化。关于CAS的一些应用，《无锁队列的实现》一文中有很详细的介绍。
Java中的原子操作
在java.util.concurrent.atomic包中，Java为我们提供了很多方便的原子类型，它们底层完全基于CAS操作。
例如我们希望实现一个全局公用的计数器，那么可以：
private AtomicInteger counter = new AtomicInteger(3);
public void addCounter() {
for (;;) {
int oldValue = counter.get();
int newValue = oldValue + 1;
if (counter.compareAndSet(oldValue, newValue))
return;
}
}
(30 人打了分，平均分： 3.40 )
Loading...
在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障，并且这个事发生了很多次，原因是在Java语言在并发情况下使用HashMap造成Race Condition，从而导致死循环。这个事情我4、5年前也经历过，本来觉得没什么好写的，因为Java的HashMap是非线程安全的，所以在并发下必然出现问题。但是，我发现近几年，很多人都经历过这个事（在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事）所以，觉得这个是个普遍问题，需要写篇疫苗文章说一下这个事，并且给大家看看一个完美的“Race Condition”是怎么形成的。