Java理论与实践: 构建一个更好的HashMap - 编程入门网

清单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为删除一个元素之前的 hash 链：

图1. Hash链

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

图2为删除元素3之后的链：

图2. 一个元素的删除过程

插入和更新操作

put()的实现很简单。像 remove() 一样， put() 会在执行期间保持 bucket 锁，但是由于 put() 并不是都需要获取锁，所以这并不一定会阻塞其他读线程 的执行（也不会阻塞其他写线程访问别的 bucket）。它首先会在适当的 hash 链中搜索需要的键值。如果能够找到， value 字段（易变的）就直接被更新。 如果没有找到，新会创建一个用于描述新 map的新 Entry 对象，然后插入到 bucket 列表的头部。

弱一致的迭代器

由 ConcurrentHashMap 返回的迭代器的语义又不同于 ava.util 集合中的迭 代器；而且它又是 弱一致的（weakly consistent）而非 fail-fast的（所谓 fail-fast 是指，当正在使用一个迭代器的时候，如何底层的集合被修改，就会 抛出一个异常）。当一个用户调用 keySet().iterator() 去迭代器中检索一组 hash 键的时候，实现就简单地使用同步来保证每个链的头指针是当前值。 next() 和hasNext() 操作以一种明显的方式定义，即遍历每个链然后转到下一 个链直到所有的链都被遍历。弱一致迭代器可能会也可能不会反映迭代器迭代过 程中的插入操作，但是一定会反映迭代器还没有到达的键的更新或删除操作，并 且对任何值最多返回一次。 ConcurrentHashMap 返回的迭代器不会抛出 ConcurrentModificationException 异常。

动态调整大小

随着 map 中元素数目的增长，hash 链将会变长，因此检索时间也会增加。 从某种意义上说，增加 bucket的数目和重排其中的值是非常重要的。在有些像 Hashtable 之类的类中，这很简单，因为保持一个应用到整个 map的独占锁是可 能的。在ConcurrentHashMap 中，每次一个条目插入的时候，如果链的长度超过 了某个阈值，链就被标记为需要调整大小。当有足够多的链被标记为需要调整大 小以后， ConcurrentHashMap 就使用递归获取每个 bucket 上的锁并重排每个 bucket 中的元素到一个新

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!