构建更好的HashMap

在7月的Java理论与实践 （“ 并发集合类 ”）中，我们回顾了可伸缩性瓶颈，并讨论了如何在共享数据结构中实现更高的并发性和吞吐量。 有时，最好的学习方法是检查专家的工作，因此本月我们将研究Doug Lea的util.concurrent包中ConcurrentHashMap的实现。 由JSR 133指定的，针对新Java内存模型（JMM）优化的ConcurrentHashMap版本将包含在JDK 1.5中的java.util.concurrent包中。 util.concurrent的版本已通过旧内存模型和新内存模型的线程安全性审核。

优化吞吐量

ConcurrentHashMap使用多种技巧来实现高级别的并发性并避免锁定，包括对不同的哈希存储桶使用多个写锁定，并利用JMM的不确定性来最大程度地减少持有锁定的时间-或完全避免获得锁定。 针对最常用的用法进行了优化，该用法是检索地图中可能已经存在的值。 实际上，大多数成功的get()操作将在没有任何锁定的情况下运行。 （警告：不要在家中尝试！试图超越JMM的难度比它看起来要难得多，并且不能轻率地进行util.concurrent类是由并发专家编写的，并且经过JMM安全性的广泛同行评审）

多个写锁

回想一下， Hashtable （或Collections.synchronizedMap ）的主要可伸缩性障碍在于，它使用单个地图范围的锁，该锁必须在整个插入，删除或检索操作（有时甚至是整个操作）时都必须保留。遍历迭代器。 这样即使持有空闲处理器，也可以防止其他线程在持有锁的情况下完全访问Map ，从而极大地限制了并发性。

ConcurrentHashMap放弃了单个地图范围的锁，而是使用了32个锁的集合，每个锁都保护着哈希桶的子集。 锁主要由可变（ put()和remove() ）操作使用。 具有32个单独的锁意味着最多可以同时修改32个线程。 这并不一定意味着如果当前少于32个线程正在写入映射，则另一个写操作将不会阻塞-32是写程序的理论上的并发限制，但实际上并非总是可以实现。 尽管如此，32仍然比1好很多，并且对于在当前计算机系统上运行的大多数应用程序来说应该绰绰有余。

地图范围内的操作

具有32个单独的锁，每个锁都保护哈希桶的子集，这意味着需要对映射进行独占访问的操作必须获取所有32个锁。 某些地图范围的操作（例如size()和isEmpty()可能能够逃脱而无需立即锁定整个地图（通过适当地限定这些操作的语义），但是某些操作，例如地图重新哈希（扩展（随着地图的增长，散列桶和重新分配元素的数量）必须保证独占访问。 Java语言没有提供获取一组可变大小的锁的简单方法。 在很少需要执行此操作的情况下，可以通过递归来完成。

JMM概述

在我们进入put() ， get()和remove() ，让我们简要回顾一下JMM，它控制一个线程对内存的操作（读和写）如何影响其他线程对内存的操作。 由于使用处理器寄存器和每处理器高速缓存来提高内存访问的性能优势，因此Java语言规范（JLS）允许某些内存操作对所有其他线程不立即可见。 有两种语言机制可确保跨线程的内存操作的一致性： synchronized volatile 。

根据JLS，“在没有显式同步的情况下，实现可以自由地以可能令人惊讶的顺序更新主存储器。” 这意味着在没有同步的情况下，在给定线程中以一个顺序发生的写操作似乎可能以不同的顺序发生在另一个线程中，并且对内存变量的更新可能需要花费不确定的时间才能从一个线程传播到另一个线程。

尽管使用同步的最常见原因是为了保证对关键代码段的原子访问，但是同步实际上提供了三个独立的功能-原子性，可见性和排序。 原子性非常简单-同步强制执行可重入的互斥体，从而防止多个线程同时执行由给定监视器保护的代码块。 不幸的是，大多数文本集中于同步的原子性方面，而排除了其他方面。 但是，同步在JMM中也起着重要作用，导致JVM在获取和释放监视器时执行内存屏障。

当线程获取监视器时，它将执行读取屏障 -使缓存在线程本地内存中的所有变量（例如处理器上的缓存或处理器寄存器）无效，这将导致处理器重新读取内存中使用的任何变量。来自主存储器的同步块。 同样，在释放监视器时，线程执行写屏障 -将所有已修改的变量刷新回主内存。 互斥和内存屏障的结合意味着只要程序遵循正确的同步规则（即，只要编写了另一个线程可能接下来读取的变量或读取了另一个线程最后写入的变量，就进行同步） ），则每个线程都会看到其使用的任何共享变量的正确值。

如果访问共享变量时无法同步，则​​可能会发生一些非常奇怪的事情。 有些更改可能会立即反映在线程之间，而其他更改可能需要一些时间（由于关联缓存的性质）。 结果，如果没有同步，则无法确保您具有一致的内存视图（相关变量可能彼此不一致）或当前的内存视图（某些值可能过时）。 避免这些危险的常用方法（建议使用）当然是正确同步。 但是，在某些情况下，例如在非常广泛使用的库类（例如ConcurrentHashMap ，可能值得在开发中应用一些额外的专业知识和精力（这可能是很多倍的精力）来获得更高的性能。

ConcurrentHashMap实现

如前所述， ConcurrentHashMap所使用的数据结构在实现上与Hashtable或HashMap相似，具有可调整大小的哈希桶数组，每个哈希桶由Map.Entry元素链组成，如清单1所示。集合锁， ConcurrentHashMap使用固定的锁池，这些池在存储桶集合上形成分区。

清单1. ConcurrentHashMap使用的Map.Entry元素

protected static class Entry implements Map.Entry { protected final Object key; protected volatile Object value; protected final int hash; protected final Entry next; ... }

遍历数据结构而无需锁定

与Hashtable或典型的锁池Map实现不同， ConcurrentHashMap.get()操作不一定需要获取与相关存储桶关联的锁。 在没有锁定的情况下，实现必须准备好处理它使用的任何变量的陈旧或不一致的值，例如列表头指针和Map.Entry元素的字段（包括组成链接列表的链接指针）。每个哈希存储桶的条目）。

大多数并发类使用同步来确保对数据结构的独占访问以及对数据结构的一致视图。 并不是假设排他性和一致性，而是精心设计了ConcurrentHashMap使用的链接列表，以便实现可以检测到其列表视图不一致或陈旧。 如果它检测到其视图不一致或过时，或者只是未找到其要查找的条目，则它将在适当的存储桶锁上进行同步并再次搜索链。 在大多数情况下，这可以优化查找-大多数情况下检索成功，并且检索次数超过插入和删除次数。

利用不变性

通过使Entry元素几乎不可变，避免了一个显着的不一致源-除了value字段是可变的之外，所有字段都是最终字段。 这意味着不能将元素添加到哈希链的中间或末端或从哈希链的中间或末端删除—元素只能在开头添加，并且删除涉及克隆链的全部或部分并更新列表头指针。 因此，一旦您有对哈希链的引用，虽然您可能不知道是否有对列表头的引用，但您确实知道列表的其余部分不会改变其结构。 另外，由于value字段是易失性的，因此您将能够立即看到value字段的更新，从而大大简化了编写Map实现的过程，该实现可以处理可能过时的内存视图。

尽管新的JMM为最终变量提供了初始化安全性，但旧的JMM却没有，这意味着另一个线程可能会看到final字段的默认值，而不是对象的构造函数在其中放置的值。 实现也必须准备好检测到它，方法是确保每个Entry字段的默认值都不是有效值。 该列表的构造使得，如果任何Entry字段似乎都具有其默认值（零或null ），则搜索将失败，从而提示get()实现再次同步并遍历该链。

检索操作

检索操作首先进行以​​下操作：找到所需存储桶的头部指针（这是在没有锁定的情况下完成的，因此可能是过时的），并且在没有获取该存储桶的锁的情况下遍历存储桶链。 如果找不到所需的值，它将进行同步并尝试再次找到该条目，如清单2所示：

清单2. ConcurrentHashMap.get（）实现

public Object get(Object key) { int hash = hash(key); // throws null pointer exception if key is null // Try first without locking... Entry[] tab = table; int index = hash & (tab.length - 1); Entry first = tab[index]; Entry e; for (e = first; e != null; e = e.next) { if (e.hash == hash && eq(key, e.key)) { Object value = e.value; // null values means that the element has been removed if (value != null) return value; else break; } } // Recheck under synch if key apparently not there or interference Segment seg = segments[hash & SEGMENT_MASK]; synchronized(seg) { tab = table; index = hash & (tab.length - 1); Entry newFirst = tab[index]; if (e != null || first != newFirst) { for (e = newFirst; e != null; e = e.next) { if (e.hash == hash && eq(key, e.key)) return e.value; } } return null; } }

搬运作业

因为线程可以看到哈希链中链接指针的陈旧值，所以仅从链中删除一个元素不足以确保其他线程在执行查找时不会继续看到删除的值。 取而代之的是，如清单3所示，删除是一个两步过程-首先找到合适的Entry对象，并将其value字段设置为null ，然后克隆从头到删除的元素的链的一部分并将其连接起来。到移除元素之后的链的其余部分。 由于值字段是易失性的，因此如果另一个线程正在过时的链中查找已删除的元素，它将立即看到空值字段，并且知道可以通过同步重试检索。 最终，以被删除元素结尾的哈希链的初始部分将被垃圾回收。

清单3. ConcurrentHashMap.remove（）实现

protected Object remove(Object key, Object value) { /* Find the entry, then 1. Set value field to null, to force get() to retry 2. Rebuild the list without this entry. All entries following removed node can stay in list, but all preceding ones need to be cloned. Traversals rely on this strategy to ensure that elements will not be repeated during iteration. */ int hash = hash(key); Segment seg = segments[hash & SEGMENT_MASK]; synchronized(seg) { Entry[] tab = table; int index = hash & (tab.length-1); Entry first = tab[index]; Entry e = first; for (;;) { if (e == null) return null; if (e.hash == hash && eq(key, e.key)) break; e = e.next; } Object oldValue = e.value; if (value != null && !value.equals(oldValue)) return null; e.value = null; Entry head = e.next; for (Entry p = first; p != e; p = p.next) head = new Entry(p.hash, p.key, p.value, head); tab[index] = head; seg.count--; return oldValue; } }

图1展示了删除元素之前的哈希链：

图1.哈希链

图2显示了删除了元素3的链：

图2.删除元素

插入和更新操作

put()的实现很简单。 像remove()一样， put()在执行期间持有存储桶锁，但是由于get()并不总是需要获取该锁，因此不一定会阻止读者执行（也不会阻止其他作者）访问其他存储桶）。 首先， put()在适当的哈希链中搜索所需的密钥。 如果找到它，那么value字段（易失性）将被简单地更新。 如果未找到，则会创建一个新的Entry对象来描述新的映射，并将其插入到该存储桶的列表的开头。

弱一致性迭代器

ConcurrentHashMap返回的迭代器的语义与java.util集合的语义不同。 它们不是快速失败的 （如果在使用迭代器的同时修改了基础集合，则抛出异常），而是弱一致性 。 当用户调用keySet().iterator()来检索哈希键集的迭代器时，该实现将短暂地同步以确保每个链的头部指针都是最新的。 next()和hasNext()操作以明显的方式定义，遍历每个哈希链，然后继续执行下一个链，直到遍历所有链。 弱一致性迭代器可能反映也可能不反映迭代过程中进行的插入，但是它们肯定会反映出迭代器尚未到达的键的更新或删除，并且不会多次返回任何值。 ConcurrentHashMap返回的迭代器不会引发ConcurrentModificationException 。

动态调整大小

随着地图中元素数量的增加，哈希链将越来越长，检索时间也将增加。 在某个时候，增加存储桶数量并重新哈希值是有意义的。 在Hashtable类的类中，这很容易，因为可以在整个地图上持有排他锁。 在ConcurrentHashMap ，每次插入条目时，如果该链的长度超过某个阈值，则将该链标记为需要调整大小。 当足够多的链投票需要调整大小时， ConcurrentHashMap将使用递归来获取每个存储桶上的锁，并将每个存储桶中的元素重新散列到一个新的更大的哈希表中。 在大多数情况下，这将自动对呼叫者透明地发生。

没有锁？

要说成功进行get()操作而没有锁定是有点夸大其词，因为Entry的value字段是易变的，并且用于检测更新和删除。 在机器级别，易失性和同步通常最终被转换为相同的缓存一致性原语，因此，尽管粒度更细，并且没有获取和释放监视器的调度或JVM开销，但实际上有效地进行了一些锁定。 但是，除了语义之外， ConcurrentHashMap在许多常见情况下（其中检索次数超过插入和删除次数）实现的ConcurrentHashMap令人印象深刻。

结论

ConcurrentHashMap既是许多并发应用程序中非常有用的类，又是可以理解和利用JMM细微细节以实现更高性能的类的优秀示例。 ConcurrentHashMap是一项令人印象深刻的编码壮举，它需要对并发和JMM有深入的了解。 使用它，从中学到东西，享受它-但是除非您是Java并发专家，否则您可能不应该自己尝试。

---

翻译自: https://www.ibm.com/developerworks/java/library/j-jtp08223/index.html