ConcurrentHashMap数据结构
作者:binjava7中,concurrentHashMap使用的是若干个segement,每个segement中又一个数组,数组下面是链表。
线程并发时候锁住的是一个整个segement
java8中,concurrentHashMap使用的是数组 + 链表、数组 + 红黑树的结构。
线程并发的时候,只锁住数组的第一个节点node即可。
concurrentHashMapd的putVal:
if (tab == null || (n = tab.length) == 0) //懒初始化 tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //头节点为空,cas方式去设置值 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) //如果节点在被扩容中,那么就加入帮助扩容 tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) { //锁住头节点 if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { //链表结构往后找 K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { //树结构调用putTreeVal Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) //超过阈值,链表转树 treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } //累加,看看是否需要扩容 addCount(1L, binCount);
helpTransfer方法的作用是,如果concurrentHaspMap在扩容着,那么加入帮助扩容,扩容的方式就是按容量来分配任务,每个线程负责一个区间,如果只有一个线程做的话,那么区间不断往前移动直到做完,如果有线程加入扩容,那么就会分摊任务,加速扩容