ConcurrentHashMap之实现细节3

实现细节

修改操作

先来看下删除操作remove(key)。

Java代码
  1. public V remove(Object key) {  
  2. hash = hash(key.hashCode());  
  3.     return segmentFor(hash).remove(key, hash, null);  
  4. }  
public V remove(Object key) { int hash = hash(key.hashCode()); return segmentFor(hash).remove(key, hash, null); }

整个操作是先定位到段，然后委托给段的remove操作。当多个删除操作并发进行时，只要它们所在的段不相同，它们就可以同时进行。下面是Segment的remove方法实现：

Java代码 <embed height="15" width="14" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" allowscriptaccess="always" quality="high" flashvars="clipboard=%20%20%20%20%20%20%20%20V%20remove(Object%20key%2C%20int%20hash%2C%20Object%20value)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20lock()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20try%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20c%20%3D%20count%20-%201%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%5B%5D%20tab%20%3D%20table%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20index%20%3D%20hash%20%26%20(tab.length%20-%201)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%20first%20%3D%20tab%5Bindex%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%20e%20%3D%20first%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(e%20!%3D%20null%20%26%26%20(e.hash%20!%3D%20hash%20%7C%7C%20!key.equals(e.key)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20e%20%3D%20e.next%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20V%20oldValue%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(e%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20V%20v%20%3D%20e.value%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(value%20%3D%3D%20null%20%7C%7C%20value.equals(v))%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20oldValue%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20All%20entries%20following%20removed%20node%20can%20stay%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20in%20list%2C%20but%20all%20preceding%20ones%20need%20to%20be%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20cloned.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%2BmodCount%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%20newFirst%20%3D%20e.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(HashEntry%3CK%2CV%3E%20p%20%3D%20first%3B%20p%20!%3D%20e%3B%20p%20%3D%20p.next)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newFirst%20%3D%20new%20HashEntry%3CK%2CV%3E(p.key%2C%20p.hash%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20newFirst%2C%20p.value)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tab%5Bindex%5D%20%3D%20newFirst%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%20%3D%20c%3B%20%2F%2F%20write-volatile%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20oldValue%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20finally%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20unlock()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D" src="http://www.javaeye.com/javascripts/syntaxhighlighter/clipboard_new.swf" lk_mediaid="lk_juiceapp_mediaPopup_1236652704298" lk_media="yes">
  1. V remove(Object key, int hash, Object value) {  
  2.      lock();  
  3.     try {  
  4.         int c = count - 1;  
  5.          HashEntry<K,V>[] tab = table;  
  6.         int index = hash & (tab.length - 1);  
  7.          HashEntry<K,V> first = tab[index];  
  8.          HashEntry<K,V> e = first;  
  9.         while (e != null && (e.hash != hash || !key.equals(e.key)))  
  10.              e = e.next;  
  11.   
  12.          V oldValue = null;  
  13.         if (e != null) {  
  14.              V v = e.value;  
  15.             if (value == null || value.equals(v)) {  
  16.                  oldValue = v;  
  17.                 // All entries following removed node can stay  
  18.                 // in list, but all preceding ones need to be  
  19.                 // cloned.  
  20.                  ++modCount;  
  21.                  HashEntry<K,V> newFirst = e.next;  
  22.                 for (HashEntry<K,V> p = first; p != e; p = p.next)  
  23.                      newFirst = new HashEntry<K,V>(p.key, p.hash,  
  24.                                                    newFirst, p.value);  
  25.                  tab[index] = newFirst;  
  26.                  count = c; // write-volatile  
  27.              }  
  28.          }  
  29.         return oldValue;  
  30.      } finally {  
  31.          unlock();  
  32.      }  
  33. }  
V remove(Object key, int hash, Object value) { lock(); try { int c = count - 1; HashEntry<K,V>[] tab = table; int index = hash & (tab.length - 1); HashEntry<K,V> first = tab[index]; HashEntry<K,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; HashEntry<K,V> newFirst = e.next; for (HashEntry<K,V> p = first; p != e; p = p.next) newFirst = new HashEntry<K,V>(p.key, p.hash, newFirst, p.value); tab[index] = newFirst; count = c; // write-volatile } } return oldValue; } finally { unlock(); } }

整个操作是在持有段锁的情况下执行的，空白行之前的行主要是定位到要删除的节点e。接下来，如果不存在这个节点就直接返回null，否则就要将e前面的结点复制一遍，尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。下面是个示意图，我直接从这个网站 上复制的（画这样的图实在是太麻烦了，如果哪位有好的画图工具，可以推荐一下）。

删除元素之前：

a hash chain before an element is removed

删除元素3之后：

the chain with element 3 removed

第二个图其实有点问题，复制的结点中应该是值为2的结点在前面，值为1的结点在后面，也就是刚好和原来结点顺序相反，还好这不影响我们的讨论。

整个remove实现并不复杂，但是需要注意如下几点。第一，当要删除的结点存在时，删除的最后一步操作要将count的值减一。这必须是最后一步 操作，否则读取操作可能看不到之前对段所做的结构性修改。第二，remove执行的开始就将table赋给一个局部变量tab，这是因为table是 volatile变量，读写volatile变量的开销很大。编译器也不能对volatile变量的读写做任何优化，直接多次访问非volatile实例 变量没有多大影响，编译器会做相应优化。

接下来看put操作，同样地put操作也是委托给段的put方法。下面是段的put方法：

Java代码 <embed height="15" width="14" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" allowscriptaccess="always" quality="high" flashvars="clipboard=%20%20%20%20%20%20%20%20V%20put(K%20key%2C%20int%20hash%2C%20V%20value%2C%20boolean%20onlyIfAbsent)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20lock()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20try%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20c%20%3D%20count%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(c%2B%2B%20%3E%20threshold)%20%2F%2F%20ensure%20capacity%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rehash()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%5B%5D%20tab%20%3D%20table%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20index%20%3D%20hash%20%26%20(tab.length%20-%201)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%20first%20%3D%20tab%5Bindex%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20HashEntry%3CK%2CV%3E%20e%20%3D%20first%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(e%20!%3D%20null%20%26%26%20(e.hash%20!%3D%20hash%20%7C%7C%20!key.equals(e.key)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20e%20%3D%20e.next%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20V%20oldValue%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(e%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20oldValue%20%3D%20e.value%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(!onlyIfAbsent)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20e.value%20%3D%20value%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20oldValue%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%2BmodCount%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tab%5Bindex%5D%20%3D%20new%20HashEntry%3CK%2CV%3E(key%2C%20hash%2C%20first%2C%20value)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%20%3D%20c%3B%20%2F%2F%20write-volatile%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20oldValue%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20finally%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20unlock()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D" src="http://www.javaeye.com/javascripts/syntaxhighlighter/clipboard_new.swf" lk_mediaid="lk_juiceapp_mediaPopup_1236652704304" lk_media="yes">
  1. V put(K key, int hash, V value, boolean onlyIfAbsent) {  
  2.      lock();  
  3.     try {  
  4.         int c = count;  
  5.         if (c++ > threshold) // ensure capacity  
  6.              rehash();  
  7.          HashEntry<K,V>[] tab = table;  
  8.         int index = hash & (tab.length - 1);  
  9.          HashEntry<K,V> first = tab[index];  
  10.          HashEntry<K,V> e = first;  
  11.         while (e != null && (e.hash != hash || !key.equals(e.key)))  
  12.              e = e.next;  
  13.   
  14.          V oldValue;  
  15.         if (e != null) {  
  16.              oldValue = e.value;  
  17.             if (!onlyIfAbsent)  
  18.                  e.value = value;  
  19.          }  
  20.         else {  
  21.              oldValue = null;  
  22.              ++modCount;  
  23.              tab[index] = new HashEntry<K,V>(key, hash, first, value);  
  24.              count = c; // write-volatile  
  25.          }  
  26.         return oldValue;  
  27.      } finally {  
  28.          unlock();  
  29.      }  
  30. }  
V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c = count; if (c++ > threshold) // ensure capacity rehash(); HashEntry<K,V>[] tab = table; int index = hash & (tab.length - 1); HashEntry<K,V> first = tab[index]; HashEntry<K,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 HashEntry<K,V>(key, hash, first, value); count = c; // write-volatile } return oldValue; } finally { unlock(); } }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/danghuijian/p/4400693.html