ConcurrentHashMap的put源码解析

2019-05-16 18:31:23

阅读次数 - 596

Java 并发

大概走了一遍ConcurrentHashMap的put过程。源码是JDK 11的,跟JDK 8基本没有什么改动,但与JDK 7相差甚大。主要核心思想是以某个位置的头结点(链表的头结点或红黑树的root结点)为锁,配合自旋+CAS避免不必要的锁开销。

public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { // key 和 value都不能为空 if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); // 再哈希,防止用户自己写的哈希算法导致分布不均匀 int binCount = 0; // 这个位置元素的个数 // 死循环 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; K fk; V fv; // 如果没有初始化,就先进行初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); // 根据hash,取table上相应位置的第一个结点f,判断它是否为空 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 如果为空,用cas添加进去 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; // 直接结束循环 } // 如果当前节点是一个forwarding节点,表示在resize过程中 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); // 如果在resize过程中,帮助转换 else if (onlyIfAbsent // 检查第一个没有申请锁的结点 && fh == hash && ((fk = f.key) == key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; else { // 接下段代码块 } } // 元素计数加1,根据binCount来检验是否需要检查和扩容 // 如果<0,不会检查。这里不会小于0 // 如果<=1,会检查uncontended。 // 如果>1,会检查并尝试扩容 addCount(1L, binCount); return null; }
else { V oldVal = null; synchronized (f) { // 以第一个结点为锁 // 如果f是第一个结点 if (tabAt(tab, i) == f) { // 如果f的hash大于0,说明不是在特殊状态,也不是红黑树 if (fh >= 0) { binCount = 1; // 死循环,每次binCount加1 for (Node<K,V> e = f;; ++binCount) { K ek; // 如果当前节点的hash等于key的hashCode, // 且当前节点的key equals key if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; // 说明key已经存在,获取原来的值 if (!onlyIfAbsent) e.val = value; // 替换这个节点的值 break; // 退出死循环 } Node<K,V> pred = e; // 如果弄到最后还是为空,说明key不存在 if ((e = e.next) == null) { // 在链表尾部插入一个新的节点 pred.next = new Node<K,V>(hash, key, value); break; // 结束内层死循环 } } } // 如果是红黑树结点 else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; // 调用红黑树的put方法,其内部也是使用的CAS,并判断key是否已存在 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; // key存在,得到原来值 if (!onlyIfAbsent) p.val = value; // 设置新值 } } // 如果是保留的Node类型 else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } // 如果binCount不为0,插入成功了,否则会进入再一次的循环 if (binCount != 0) { // 如果大于转换红黑树的阈值 if (binCount >= TREEIFY_THRESHOLD) // 转换成红黑树,内部以根结点为锁 treeifyBin(tab, i); // 如果key已存在,有原值,返回原值 if (oldVal != null) return oldVal; break; // 结束外层死循环 } }

Reference:

// 再hash, 跟HashMap的再哈希类似,让高位和低位同时参与 static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; } /* * Encodings for Node hash fields. See above for explanation. */ static final int MOVED = -1; // hash for forwarding nodes static final int TREEBIN = -2; // hash for roots of trees static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash static final class ReservationNode<K,V> extends Node<K,V> { ReservationNode() { super(RESERVED, null, null); } Node<K,V> find(int h, Object k) { return null; } }

没有细看扩容相关的helpTransfer、addCount,以及初始化方法initTable,以后有机会再分析。

总结一下put的过程:

  1. 先检查key和value都不能为空,如果为空,就抛出空指针异常;
  2. 对key再哈希,防止用户自己写的哈希算法导致分布不均匀;
  3. 检查是否已经进行了初始化,如果没有,要先初始化;
  4. 根据再hash的值,计算在table上的位置的第一个结点f,如果f为空,用CAS直接插入;否则,进行第5步;
  5. 检查f是否是一个forwarding结点,如果是表示正在扩容,当前线程就去帮助扩容;如果不是,进行第6步;
  6. 检查f的key是不是等于要插入的key,如果是,获取原来的值并替换成新的值,如果不是,进行第7步;
  7. 以第一个结点为锁;
  8. 如果f不是红黑树结点,进行第9步,如果是红黑树结点,进行第11步;
  9. 根据链表向下找,如果找到key相等的位置,获取原来的值并替换成新的值;
  10. 如果一直到链表末尾也没有找到相等的key,就在链表尾部插入一个新节点;
  11. 调用红黑树的putTreeVal方法,其内部是使用CAS,也会判断key是否已经存在并返回旧值;
  12. 如果是保留的Node类型ReservationNode,直接抛出异常;
  13. 根据binCount判断是否达到链表转红黑树的阈值,如果达到了,转成红黑树,这个过程会以根节点为锁;

感谢阅读


觉得文章还不错?点击下方按钮分享吧!

评论

快来占个沙发吧~


TO: