Java理论与实践: 构建一个更好的HashMap

Java理论与实践: 构建一个更好的HashMap2010-12-21 IBM Brian GoetzConcurrentHashMap 是 Doug Lea的 util.concurrent 包的一部分，它提供比Hashtable 或者 synchronizedMap 更高程度的并发性。而且，对于大多数成功的 get（）操作它会设法避免完全锁定，其结果就是使得并发应用程序有着非常好的吞吐量。这个月，BrianGoetz 仔细分析了 ConcurrentHashMap的代码，并探讨 Doug Lea 是如何在不损失线程安全的情况下取得这么骄人成绩的。

在7月份的那期 Java理论与实践（“ Concurrent collections classes”）中，我们简单地回顾了可伸缩性的瓶颈，并讨论了怎么用共享数据结构的方法获得更高的并发性和吞吐量。有时候学习的最好方法是分析专家的成果，所以这个月我们将分析 Doug Lea的 util.concurrent 包中的 ConcurrentHashMap的实现。JSR 133 将指定 ConcurrentHashMap的一个版本，该版本针对 Java 内存模型（JMM）作了优化，它将包含在JDK 1.5的 java.util.concurrent 包中。 util.concurrent 中的版本在老的和新的内存模型中都已通过线程安全审核。

针对吞吐量进行优化

ConcurrentHashMap 使用了几个技巧来获得高程度的并发以及避免锁定，包括为不同的 hash bucket（桶）使用多个写锁和使用 JMM的不确定性来最小化锁被保持的时间――或者根本避免获取锁。对于大多数一般用法来说它是经过优化的，这些用法往往会检索一个很可能在map 中已经存在的值。事实上，多数成功的 get（）操作根本不需要任何锁定就能运行。（警告：不要自己试图这样做！想比 JMM 聪明不像看上去的那么容易。 util.concurrent 类是由并发专家编写的，并且在JMM 安全性方面经过了严格的同行评审。）

多个写锁

我们可以回想一下，Hashtable（或者替代方案 Collections.synchronizedMap ）的可伸缩性的主要障碍是它使用了一个 map 范围（map-wide）的锁，为了保证插入、删除或者检索操作的完整性必须保持这样一个锁，而且有时候甚至还要为了保证迭代遍历操作的完整性保持这样一个锁。这样一来，只要锁被保持，就从根本上阻止了其他线程访问 Map，即使处理器有空闲也不能访问，这样大大地限制了并发性。

ConcurrentHashMap 摒弃了单一的 map 范围的锁，取而代之的是由 32 个锁组成的集合，其中每个锁负责保护 hash bucket的一个子集。锁主要由变化性操作（ put（）和remove（））使用。具有 32 个独立的锁意味着最多可以有 32 个线程可以同时修改 map。这并不一定是说在并发地对 map 进行写操作的线程数少于 32 时，另外的写操作不会被阻塞――32 对于写线程来说是理论上的并发限制数目，但是实际上可能达不到这个值。但是，32 依然比 1 要好得多，而且对于运行于目前这一代的计算机系统上的大多数应用程序来说已经足够了。 &#160

map 范围的操作

有 32 个独立的锁，其中每个锁保护 hash bucket的一个子集，这样需要独占访问 map的操作就必须获得所有32个锁。一些 map 范围的操作，比如说 size（）和isEmpty（），也许能够不用一次锁整个 map（通过适当地限定这些操作的语义），但是有些操作，比如 map 重排（扩大 hash bucket的数量，随着 map的增长重新分布元素），则必须保证独占访问。Java 语言不提供用于获取可变大小的锁集合的简便方法。必须这么做的情况很少见，一旦碰到这种情况，可以用递归方法来实现。

JMM概述

在进入 put（）、 get（）和remove（）的实现之前，让我们先简单地看一下 JMM。JMM 掌管着一个线程对内存的动作（读和写）影响其他线程对内存的动作的方式。由于使用处理器寄存器和预处理 cache 来提高内存访问速度带来的性能提升，Java 语言规范（JLS）允许一些内存操作并不对于所有其他线程立即可见。有两种语言机制可用于保证跨线程内存操作的一致性―― synchronized 和 volatile。

按照 JLS的说法，“在没有显式同步的情况下，一个实现可以自由地更新主存，更新时所采取的顺序可能是出人意料的。”其意思是说，如果没有同步的话，在一个给定线程中某种顺序的写操作对于另外一个不同的线程来说可能呈现出不同的顺序，并且对内存变量的更新从一个线程传播到另外一个线程的时间是不可预测的。

虽然使用同步最常见的原因是保证对代码关键部分的原子访问，但实际上同步提供三个独立的功能――原子性、可见性和顺序性。原子性非常简单――同步实施一个可重入的（reentrant）互斥，防止多于一个的线程同时执行由一个给定的监视器保护的代码块。不幸的是，多数文章都只关注原子性方面，而忽略了其他方面。但是同步在JMM 中也扮演着很重要的角色，会引起 JVM 在获得和释放监视器的时候执行内存壁垒（memory barrier）。

一个线程在获得一个监视器之后，它执行一个读屏障（read barrier）―― 使得缓存在线程局部内存（比如说处理器缓存或者处理器寄存器）中的所有变量都失效，这样就会导致处理器重新从主存中读取同步代码块使用的变量。与此类似，在释放监视器时，线程会执行一个写屏障（write barrier）――将所有修改过的变量写回主存。互斥独占和内存壁垒结合使用意味着只要您在程序设计的时候遵循正确的同步法则（也就是说，每当写一个后面可能被其他线程访问的变量，或者读取一个可能最后被另一个线程修改的变量时，都要使用同步），每个线程都会得到它所使用的共享变量的正确的值。

如果在访问共享变量的时候没有同步的话，就会发生一些奇怪的事情。一些变化可能会通过线程立即反映出来，而其他的则需要一些时间（这由关联缓存的本质所致）。结果，如果没有同步您就不能保证内存内容必定一致（相关的变量相互间可能会不一致），或者不能得到当前的内存内容（一些值可能是过时的）。避免这种危险情况的常用方法（也是推荐使用的方法）当然是正确地使用同步。然而在有些情况下，比如说在像 ConcurrentHashMap 之类的一些使用非常广泛的库类中，在开发过程当中还需要一些额外的专业技能和努力（可能比一般的开发要多出很多倍）来获得较高的性能。