如何设计网站步骤,西安到北京航班时刻表,重庆网站设计公司排名,凡科网站建设步骤http://www.iteye.com/topic/344876 ConcurrentHashMap是Java 5中支持高并发、高吞吐量的线程安全HashMap实现。在这之前我对ConcurrentHashMap只有一些肤浅的理解#xff0c;仅知道它采用了多个锁#xff0c;大概也足够了。但是在经过一次惨痛的面试经历之后#xff0c;我觉… http://www.iteye.com/topic/344876 ConcurrentHashMap是Java 5中支持高并发、高吞吐量的线程安全HashMap实现。在这之前我对ConcurrentHashMap只有一些肤浅的理解仅知道它采用了多个锁大概也足够了。但是在经过一次惨痛的面试经历之后我觉得必须深入研究它的实现。面试中被问到读是否要加锁因为读写会发生冲突我说必须要加锁我和面试官也因此发生了冲突结果可想而知。还是闲话少说通过仔细阅读源代码现在总算理解ConcurrentHashMap实现机制了其实现之精巧令人叹服与大家共享之。 实现原理 锁分离 (Lock Stripping) ConcurrentHashMap允许多个修改操作并发进行其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分每个段其实就是一个小的hash table它们有自己的锁。只要多个修改操作发生在不同的段上它们就可以并发进行。 有些方法需要跨段比如size()和containsValue()它们可能需要锁定整个表而而不仅仅是某个段这需要按顺序锁定所有段操作完毕后又按顺序释放所有段的锁。这里“按顺序”是很重要的否则极有可能出现死锁在ConcurrentHashMap内部段数组是final的并且其成员变量实际上也是final的但是仅仅是将数组声明为final的并不保证数组成员也是final的这需要实现上的保证。这可以确保不会出现死锁因为获得锁的顺序是固定的。不变性是多线程编程占有很重要的地位下面还要谈到。 Java代码 /** * The segments, each of which is a specialized hash table */ final SegmentK,V[] segments; 不变(Immutable)和易变(Volatile) ConcurrentHashMap完全允许多个读操作并发进行读操作并不需要加锁。如果使用传统的技术如HashMap中的实现如果允许可以在hash链的中间添加或删除元素读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。HashEntry代表每个hash链中的一个节点其结构如下所示 Java代码 static final class HashEntryK,V { final K key; final int hash; volatile V value; final HashEntryK,V next; } 可以看到除了value不是final的其它值都是final的这意味着不能从hash链的中间或尾部添加或删除节点因为这需要修改next引用值所有的节点的修改只能从头部开始。对于put操作可以一律添加到Hash链的头部。但是对于remove操作可能需要从中间删除一个节点这就需要将要删除节点的前面所有节点整个复制一遍最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值将value设置成volatile这避免了加锁。 其它 为了加快定位段以及段中hash槽的速度每个段hash槽的的个数都是2^n这使得通过位运算就可以定位段和段中hash槽的位置。当并发级别为默认值16时也就是段的个数hash值的高4位决定分配在哪个段中。但是我们也不要忘记《算法导论》给我们的教训hash槽的的个数不应该是2^n这可能导致hash槽分配不均这需要对hash值重新再hash一次。这段似乎有点多余了 这是重新hash的算法还比较复杂我也懒得去理解了。 Java代码 private static int hash(int h) { // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h (h 15) ^ 0xffffcd7d; h ^ (h 10); h (h 3); h ^ (h 6); h (h 2) (h 14); return h ^ (h 16); } 这是定位段的方法 Java代码 final SegmentK,V segmentFor(int hash) { return segments[(hash segmentShift) segmentMask]; } 数据结构 关于Hash表的基础数据结构这里不想做过多的探讨。Hash表的一个很重要方面就是如何解决hash冲突ConcurrentHashMap和HashMap使用相同的方式都是将hash值相同的节点放在一个hash链中。与HashMap不同的是ConcurrentHashMap使用多个子Hash表也就是段(Segment)。下面是ConcurrentHashMap的数据成员 Java代码 public class ConcurrentHashMapK, V extends AbstractMapK, V implements ConcurrentMapK, V, Serializable { /** * Mask value for indexing into segments. The upper bits of a * keys hash code are used to choose the segment. */ final int segmentMask; /** * Shift value for indexing within segments. */ final int segmentShift; /** * The segments, each of which is a specialized hash table */ final SegmentK,V[] segments; } 所有的成员都是final的其中segmentMask和segmentShift主要是为了定位段参见上面的segmentFor方法。 每个Segment相当于一个子Hash表它的数据成员如下 Java代码 static final class SegmentK,V extends ReentrantLock implements Serializable { private static final long serialVersionUID 2249069246763182397L; /** * The number of elements in this segments region. */ transient volatile int count; /** * Number of updates that alter the size of the table. This is * used during bulk-read methods to make sure they see a * consistent snapshot: If modCounts change during a traversal * of segments computing size or checking containsValue, then * we might have an inconsistent view of state so (usually) * must retry. */ transient int modCount; /** * The table is rehashed when its size exceeds this threshold. * (The value of this field is always tt(int)(capacity * * loadFactor)/tt.) */ transient int threshold; /** * The per-segment table. */ transient volatile HashEntryK,V[] table; /** * The load factor for the hash table. Even though this value * is same for all segments, it is replicated to avoid needing * links to outer object. * serial */ final float loadFactor; } count用来统计该段数据的个数它是volatile它用来协调修改和读取操作以保证读取操作能够读取到几乎最新的修改。协调方式是这样的每次修改操作做了结构上的改变如增加/删除节点(修改节点的值不算结构上的改变)都要写count值每次读取操作开始都要读取count的值。这利用了Java 5中对volatile语义的增强对同一个volatile变量的写和读存在happens-before关系。modCount统计段结构改变的次数主要是为了检测对多个段进行遍历过程中某个段是否发生改变在讲述跨段操作时会还会详述。threashold用来表示需要进行rehash的界限值。table数组存储段中节点每个数组元素是个hash链用HashEntry表示。table也是volatile这使得能够读取到最新的table值而不需要同步。loadFactor表示负载因子。 实现细节 修改操作 先来看下删除操作remove(key)。 Java代码 public V remove(Object key) { hash hash(key.hashCode()); return segmentFor(hash).remove(key, hash, null); } 整个操作是先定位到段然后委托给段的remove操作。当多个删除操作并发进行时只要它们所在的段不相同它们就可以同时进行。下面是Segment的remove方法实现 Java代码 V remove(Object key, int hash, Object value) { lock(); try { int c count - 1; HashEntryK,V[] tab table; int index hash (tab.length - 1); HashEntryK,V first tab[index]; HashEntryK,V e first; while (e ! null (e.hash ! hash || !key.equals(e.key))) e e.next; V oldValue null; if (e ! null) { V v e.value; if (value null || value.equals(v)) { oldValue v; // All entries following removed node can stay // in list, but all preceding ones need to be // cloned. modCount; HashEntryK,V newFirst e.next; for (HashEntryK,V p first; p ! e; p p.next) newFirst new HashEntryK,V(p.key, p.hash, newFirst, p.value); tab[index] newFirst; count c; // write-volatile } } return oldValue; } finally { unlock(); } } 整个操作是在持有段锁的情况下执行的空白行之前的行主要是定位到要删除的节点e。接下来如果不存在这个节点就直接返回null否则就要将e前面的结点复制一遍尾结点指向e的下一个结点。e后面的结点不需要复制它们可以重用。下面是个示意图我直接从这个网站 上复制的画这样的图实在是太麻烦了如果哪位有好的画图工具可以推荐一下。 删除元素之前 删除元素3之后 第二个图其实有点问题复制的结点中应该是值为2的结点在前面值为1的结点在后面也就是刚好和原来结点顺序相反还好这不影响我们的讨论。 整个remove实现并不复杂但是需要注意如下几点。第一当要删除的结点存在时删除的最后一步操作要将count的值减一。这必须是最后一步操作否则读取操作可能看不到之前对段所做的结构性修改。第二remove执行的开始就将table赋给一个局部变量tab这是因为table是volatile变量读写volatile变量的开销很大。编译器也不能对volatile变量的读写做任何优化直接多次访问非volatile实例变量没有多大影响编译器会做相应优化。 接下来看put操作同样地put操作也是委托给段的put方法。下面是段的put方法 Java代码 V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c count; if (c threshold) // ensure capacity rehash(); HashEntryK,V[] tab table; int index hash (tab.length - 1); HashEntryK,V first tab[index]; HashEntryK,V e first; while (e ! null (e.hash ! hash || !key.equals(e.key))) e e.next; V oldValue; if (e ! null) { oldValue e.value; if (!onlyIfAbsent) e.value value; } else { oldValue null; modCount; tab[index] new HashEntryK,V(key, hash, first, value); count c; // write-volatile } return oldValue; } finally { unlock(); } } 该方法也是在持有段锁的情况下执行的首先判断是否需要rehash需要就先rehash。接着是找是否存在同样一个key的结点如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到hash链的头部这时一定要修改modCount和count的值同样修改count的值一定要放在最后一步。put方法调用了rehash方法reash方法实现得也很精巧主要利用了table的大小为2^n这里就不介绍了。 修改操作还有putAll和replace。putAll就是多次调用put方法没什么好说的。replace甚至不用做结构上的更改实现要比put和delete要简单得多理解了put和delete理解replace就不在话下了这里也不介绍了。 获取操作 首先看下get操作同样ConcurrentHashMap的get操作是直接委托给Segment的get方法直接看Segment的get方法 Java代码 V get(Object key, int hash) { if (count ! 0) { // read-volatile HashEntryK,V e getFirst(hash); while (e ! null) { if (e.hash hash key.equals(e.key)) { V v e.value; if (v ! null) return v; return readValueUnderLock(e); // recheck } e e.next; } } return null; } get操作不需要锁。第一步是访问count变量这是一个volatile变量由于所有的修改操作在进行结构修改时都会在最后一步写count变量通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新也就是结点值的改变由于HashEntry的value变量是volatile的也能保证读取到最新的值。接下来就是对hash链进行遍历找到要获取的结点如果没有找到直接访回null。对hash链进行遍历不需要加锁的原因在于链指针next是final的。但是头指针却不是final的这是通过getFirst(hash)方法返回也就是存在table数组中的值。这使得getFirst(hash)可能返回过时的头结点例如当执行get方法时刚执行完getFirst(hash)之后另一个线程执行了删除操作并更新头结点这就导致get方法中返回的头结点不是最新的。这是可以允许通过对count变量的协调机制get能读取到几乎最新的数据虽然可能不是最新的。要得到最新的数据只有采用完全的同步。 最后如果找到了所求的结点判断它的值如果非空就直接返回否则在有锁的状态下再读一次。这似乎有些费解理论上结点的值不可能为空这是因为put的时候就进行了判断如果为空就要抛NullPointerException。空值的唯一源头就是HashEntry中的默认值因为HashEntry中的value不是final的非同步读取有可能读取到空值。仔细看下put操作的语句tab[index] new HashEntryK,V(key, hash, first, value)在这条语句中HashEntry构造函数中对value的赋值以及对tab[index]的赋值可能被重新排序这就可能导致结点的值为空。这种情况应当很罕见一旦发生这种情况ConcurrentHashMap采取的方式是在持有锁的情况下再读一遍这能够保证读到最新的值并且一定不会为空值。 Java代码 V readValueUnderLock(HashEntryK,V e) { lock(); try { return e.value; } finally { unlock(); } } 另一个操作是containsKey这个实现就要简单得多了因为它不需要读取值 Java代码 boolean containsKey(Object key, int hash) { if (count ! 0) { // read-volatile HashEntryK,V e getFirst(hash); while (e ! null) { if (e.hash hash key.equals(e.key)) return true; e e.next; } } return false; } 跨段操作 有些操作需要涉及到多个段比如说size(), containsValaue()。先来看下size()方法 Java代码 public int size() { final SegmentK,V[] segments this.segments; long sum 0; long check 0; int[] mc new int[segments.length]; // Try a few times to get accurate count. On failure due to // continuous async changes in table, resort to locking. for (int k 0; k RETRIES_BEFORE_LOCK; k) { check 0; sum 0; int mcsum 0; for (int i 0; i segments.length; i) { sum segments[i].count; mcsum mc[i] segments[i].modCount; } if (mcsum ! 0) { for (int i 0; i segments.length; i) { check segments[i].count; if (mc[i] ! segments[i].modCount) { check -1; // force retry break; } } } if (check sum) break; } if (check ! sum) { // Resort to locking all segments sum 0; for (int i 0; i segments.length; i) segments[i].lock(); for (int i 0; i segments.length; i) sum segments[i].count; for (int i 0; i segments.length; i) segments[i].unlock(); } if (sum Integer.MAX_VALUE) return Integer.MAX_VALUE; else return (int)sum; } size方法主要思路是先在没有锁的情况下对所有段大小求和如果不能成功这是因为遍历过程中可能有其它线程正在对已经遍历过的段进行结构性更新最多执行RETRIES_BEFORE_LOCK次如果还不成功就在持有所有段锁的情况下再对所有段大小求和。在没有锁的情况下主要是利用Segment中的modCount进行检测在遍历过程中保存每个Segment的modCount遍历完成之后再检测每个Segment的modCount有没有改变如果有改变表示有其它线程正在对Segment进行结构性并发更新需要重新计算。 其实这种方式是存在问题的在第一个内层for循环中在这两条语句sum segments[i].count; mcsum mc[i] segments[i].modCount;之间其它线程可能正在对Segment进行结构性的修改导致segments[i].count和segments[i].modCount读取的数据并不一致。这可能使size()方法返回任何时候都不曾存在的大小很奇怪javadoc居然没有明确标出这一点可能是因为这个时间窗口太小了吧。size()的实现还有一点需要注意必须要先segments[i].count才能segments[i].modCount这是因为segment[i].count是对volatile变量的访问接下来segments[i].modCount才能得到几乎最新的值前面我已经说了为什么只是“几乎”了。这点在containsValue方法中得到了淋漓尽致的展现 Java代码 public boolean containsValue(Object value) { if (value null) throw new NullPointerException(); // See explanation of modCount use above final SegmentK,V[] segments this.segments; int[] mc new int[segments.length]; // Try a few times without locking for (int k 0; k RETRIES_BEFORE_LOCK; k) { int sum 0; int mcsum 0; for (int i 0; i segments.length; i) { int c segments[i].count; mcsum mc[i] segments[i].modCount; if (segments[i].containsValue(value)) return true; } boolean cleanSweep true; if (mcsum ! 0) { for (int i 0; i segments.length; i) { int c segments[i].count; if (mc[i] ! segments[i].modCount) { cleanSweep false; break; } } } if (cleanSweep) return false; } // Resort to locking all segments for (int i 0; i segments.length; i) segments[i].lock(); boolean found false; try { for (int i 0; i segments.length; i) { if (segments[i].containsValue(value)) { found true; break; } } } finally { for (int i 0; i segments.length; i) segments[i].unlock(); } return found; } 同样注意内层的第一个for循环里面有语句int c segments[i].count; 但是c却从来没有被使用过即使如此编译器也不能做优化将这条语句去掉因为存在对volatile变量count的读取这条语句存在的唯一目的就是保证segments[i].modCount读取到几乎最新的值。关于containsValue方法的其它部分就不分析了它和size方法差不多。 跨段方法中还有一个isEmpty()方法其实现比size()方法还要简单也不介绍了。最后简单地介绍下迭代方法如keySet(), values(), entrySet()方法这些方法都返回相应的迭代器所有迭代器都继承于Hash_Iterator类(提交时居然提醒我不能包含sh It只得加了下划线)里实现了主要的方法。其结构是 Java代码 abstract class Hash_Iterator{ int nextSegmentIndex; int nextTableIndex; HashEntryK,V[] currentTable; HashEntryK, V nextEntry; HashEntryK, V lastReturned; } nextSegmentIndex是段的索引nextTableIndex是nextSegmentIndex对应段中中hash链的索引currentTable是nextSegmentIndex对应段的table。调用next方法时主要是调用了advance方法 Java代码 final void advance() { if (nextEntry ! null (nextEntry nextEntry.next) ! null) return; while (nextTableIndex 0) { if ( (nextEntry currentTable[nextTableIndex--]) ! null) return; } while (nextSegmentIndex 0) { SegmentK,V seg segments[nextSegmentIndex--]; if (seg.count ! 0) { currentTable seg.table; for (int j currentTable.length - 1; j 0; --j) { if ( (nextEntry currentTable[j]) ! null) { nextTableIndex j - 1; return; } } } } } 不想再多介绍了唯一需要注意的是跳到下一个段时一定要先读取下一个段的count变量。 这种迭代方式的主要效果是不会抛出ConcurrentModificationException。一旦获取到下一个段的table也就意味着这个段的头结点在迭代过程中就确定了在迭代过程中就不能反映对这个段节点并发的删除和添加对于节点的更新是能够反映的因为节点的值是一个volatile变量。 结束语 ConcurrentHashMap是一个支持高并发的高性能的HashMap实现它支持完全并发的读以及一定程度并发的写。ConcurrentHashMap的实现也是很精巧充分利用了最新的JMM规范值得学习却不值得模仿。最后由于本人水平有限对大师的作品难免有误解如果存在还望大牛们不吝指出。 参考文章 http://www.ibm.com/developerworks/java/library/j-jtp08223/这个是讨论的是Doug Leas util.concurrent包中的ConcurrentHashMap的实现不过大致思想是一致的。 http://floatingpoint.tinou.com/2008/09/performance-optimization-in-concurrenthashmap.html 转载于:https://www.cnblogs.com/leeeee/p/7276060.html
