无锁HashMap的原理与实现

无锁HashMap的原理与实现

评论 35 条评论 62,702 人阅读

 (本文由投稿)

在《疫苗：Java HashMap的死循环》中，我们看到，java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap，主要有以下几种选择：

  1. 使用线程安全的java.util.Hashtable作为替代。
  2. 使用java.util.Collections.synchronizedMap方法，将已有的HashMap对象包装为线程安全的。
  3. 使用java.util.concurrent.ConcurrentHashMap类作为替代，它具有非常好的性能。

而以上几种方法在实现的具体细节上，都或多或少地用到了互斥锁。互斥锁会造成线程阻塞，降低运行效率，并有可能产生死锁、优先级翻转等一系列问题。

CAS(Compare And Swap)是一种底层硬件提供的功能，它可以将判断并更改一个值的操作原子化。关于CAS的一些应用，《�