《concurrenthashmap分析》由会员分享，可在线阅读，更多相关《concurrenthashmap分析（13页珍藏版）》请在金锄头文库上搜索。
1、ConcurrentHashMap 分析 作者：yyg 撰写日期：2011-10-28 - 2011-10-30转自 http:/ 是 Java 5 中引入的支持高并发、高吞吐量的线程安全 HashMap 实现。在这之前我对 ConcurrentHashMap 只有一些肤浅的理解，仅知道它采用了多个锁，大概也足够了。但是在经过一次惨痛的面试经历之后，我觉得必须深入研究它的实现。面试中被问到读是否要加锁，因为 读写会发生冲突，我说必须要加锁，我和面试官也因此发生了冲突，结果可想而知。还是闲话少说，通过仔细阅读源代码，现在总算理解 ConcurrentHashMap 实现机制了，其实现之精巧，令人
2、叹服，与大家共享之。实现原理 锁分离 (Lock Stripping) ConcurrentHashMap 允许多个修改操作并发进行，其关键在于使用了锁分离技术。 它使用了多个锁来控制对 hash表的不同部分进行的修改。ConcurrentHashMap 内部使用段(Segment)来表示这些不同的部分，每个段 其实就是一个小的 hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。有些方法需要跨段，比如 size()和 containsValue()，它们可能需要锁定整个 表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。
3、这里“按顺序”是很重要的，否则极有可能出现死锁，在 ConcurrentHashMap 内部，段数组是 final 的，并且其成员变量实际上也是 final 的，但是，仅仅是将数组声明为 final 的并不保证 数组成员也是 final 的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。不变性是多线程编程占有很重要的地位，下面还要谈 到。1. /* 2. * The segments, each of which is a specialized hash table 3. */ 4. final Segment segments; 不变(Immutable)和易变(V
4、olatile)ConcurrentHashMap 完全允许多个读操作并发进行，读操作并不需要加锁。如果使 用传统的技术，如 HashMap中的实现，如果允许可以在 hash 链的中间添加或删除元素，读操作不加锁将得到不一致的数据。 ConcurrentHashMap 实现技术是保证 HashEntry 几乎是不可变的。HashEntry 代表每个 hash 链中的一个节点，其结构如下所 示：static final class HashEntry 1. final K key; 2. final int hash; 3. volatile V value; 4. final HashEntr
5、y next; 5. 可以看到除了 value 不是 final 的，其它值都是 final 的，这意味着不能从 hash 链 的中间或尾部添加或删除节点，因为这需要修改 next 引用值，所有的节点的修改只能从头部开始。对于 put 操作，可以一律添加到 Hash 链的头部。但是对 于 remove 操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制一遍，最后一个节点指向要删除结点的下一个结点。这在讲解 删除操作时还会详述。为了确保读操作能够看到最新的值，将 value设置成 volatile，这避免了加锁。其它为了加快定位段以及段中 hash 槽的速度，每个段 h
6、ash 槽的的个数都是 2n，这使得通过 位运算就可以定位段和段中 hash 槽的位置。当并发级别为默认值 16 时，也就是段的个数，hash 值的高 4 位决定分配在哪个段中。但是我们也不要忘记算 法导论给我们的教训：hash 槽的的个数不应该是 2n，这可能导致 hash 槽分配不均，这需要对 hash 值重新再 hash 一次。这是重新 hash 的算法，还比较复杂，我也懒得去理解了。Java 代码1.private static int hash(int h) 2. / Spread bits to regularize both segment and index locations
7、, 3. / using variant of single-word Wang/Jenkins hash. 4. h += (h 10); 6. h += (h 6); 8. h += (h 16); 10. 这是定位段的方法：Java 代码1.final Segment segmentFor(int hash) 2. return segments(hash segmentShift) 3. 数据结构关于 Hash 表的基础数据结构，这里不想做过多的探讨。Hash 表的一个很重要方面就是如何解 决 hash 冲突，ConcurrentHashMap 和 HashMap 使用相同的方式，都是
8、将 hash 值相同的节点放在一个 hash 链中。与 HashMap 不同的是，ConcurrentHashMap 使用多个子 Hash 表，也就是段(Segment)。下面是 ConcurrentHashMap 的数据成员：Java 代码1.public class ConcurrentHashMap extends AbstractMap 2. implements ConcurrentMap, Serializable 3. /* 4. * Mask value for indexing into segments. The upper bits of a 5. * keys hash
9、 code are used to choose the segment. 6. */ 7. final int segmentMask; 8. 9. /* 10. * Shift value for indexing within segments. 11. */ 12. final int segmentShift; 13. 14. /* 15. * The segments, each of which is a specialized hash table 16. */ 17. final Segment segments; 18. 所有的成员都是 final 的，其中 segment
10、Mask 和 segmentShift 主要是为了定位段，参见上面的 segmentFor 方法。每个 Segment 相当于一个子 Hash 表，它的数据成员如下：Java 代码1. static final class Segment extends ReentrantLock implements Serializable 2.private static final long serialVersionUID = 2249069246763182397L; 3. /* 4. * The number of elements in this segments region. 5. */
11、6. transient volatile int count; 7. 8. /* 9. * Number of updates that alter the size of the table. This is 10. * used during bulk-read methods to make sure they see a 11. * consistent snapshot: If modCounts change during a traversal 12. * of segments computing size or checking containsValue, then 13
12、. * we might have an inconsistent view of state so (usually) 14. * must retry. 15. */ 16. transient int modCount; 17. 18. /* 19. * The table is rehashed when its size exceeds this threshold. 20. * (The value of this field is always (int)(capacity * 21. * loadFactor).) 22. */ 23. transient int thresh
13、old; 24. 25. /* 26. * The per-segment table. 27. */ 28. transient volatile HashEntry table; 29. 30. /* 31. * The load factor for the hash table. Even though this value 32. * is same for all segments, it is replicated to avoid needing 33. * links to outer object. 34. * serial 35. */ 36. final float l
14、oadFactor; 37. count 用来统计该段数据的个数，它是 volatile，它用来协调修改和读取操作，以保证 读取操作能够读取到几乎最新的修改。协调方式是这样的，每次修改操作做了结构上的改变，如增加/删除节点(修改节点的值不算结构上的改变)，都要写 count 值，每次读取操作开始都要读取 count 的值。这利用了 Java 5 中对 volatile 语义的增强，对同一个 volatile 变量的写和读存在 happens-before 关系。modCount 统计段结构改变的次 数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变，在讲述跨段操作时会还会详述。threashold 用来表示需要进行 rehash 的界限 值。table 数组存储段中节点，每个数组元素是个 hash 链，用 HashEntry 表示。table 也是 volatile，这使得能够读取到最新的 table 值而不需要同步。 loadFactor 表示负载因子。实现细节修改操作 先来看下删除操作 remove(key)。Java 代码1.public V remove(Object key) 2. hash = hash(key.hashCod
