做网络平台的网站有哪些,wordpress slides,上海电子网站建设,抖音seo培训前言
理解HashMap和ConcurrentHashMap的重点在于#xff1a; #xff08;1#xff09;理解HashMap的数据结构的设计和实现思路 #xff08;2#xff09;在#xff08;1#xff09;的基础上#xff0c;理解ConcurrentHashMap的并发安全的设计和实现思路 前面的文章…前言
理解HashMap和ConcurrentHashMap的重点在于 1理解HashMap的数据结构的设计和实现思路 2在1的基础上理解ConcurrentHashMap的并发安全的设计和实现思路 前面的文章已经介绍过Map结构的底层实现这里我们重点放在其扩容方法 这里分别对JDK7和JDK8版本的HashMapConcurrentHashMap来分析
JDK7的HashMap扩容 这个版本的HashMap数据结构还是数组链表的方式扩容方法如下
void transfer(Entry[] newTable) { Entry[] src table; //src引用了旧的Entry数组 int newCapacity newTable.length; for (int j 0; j src.length; j) { //遍历旧的Entry数组 EntryK, V e src[j]; //取得旧Entry数组的每个元素 if (e ! null) { src[j] null;//释放旧Entry数组的对象引用for循环后旧的Entry数组不再引用任何对象 do { EntryK, V next e.next; int i indexFor(e.hash, newCapacity); //重新计算每个元素在数组中的位置 e.next newTable[i]; //标记[1] newTable[i] e; //将元素放在数组上 e next; //访问下一个Entry链上的元素 } while (e ! null); } }
} 上面的这段代码不并不难理解对于扩容操作底层实现都需要新生成一个数组然后拷贝旧数组里面的每一个Node链表到新数组里面这个方法在单线程下执行是没有任何问题的但是在多线程下面却有很大问题主要的问题在于基于头插法的数据迁移会有几率造成链表倒置从而引发链表闭链导致程序死循环并吃满CPU。据说已经有人给原来的SUN公司提过bug但sun公司认为这是开发者使用不当造成的因为这个类本就不是线程安全的你还偏在多线程下使用这下好了吧出了问题这能怪我咯仔细想想还有点道理。 JDK7的ConcurrentHashMap扩容
HashMap是线程不安全的我们来看下线程安全的ConcurrentHashMap在JDK7的时候这种安全策略采用的是分段锁的机制ConcurrentHashMap维护了一个Segment数组Segment这个类继承了重入锁ReentrantLock并且该类里面维护了一个 HashEntryK,V[] table数组在写操作putremove扩容的时候会对Segment加锁所以仅仅影响这个Segment不同的Segment还是可以并发的所以解决了线程的安全问题同时又采用了分段锁也提升了并发的效率。  下面看下其扩容的源码
// 方法参数上的 node 是这次扩容后需要添加到新的数组中的数据。
private void rehash(HashEntryK,V node) { HashEntryK,V[] oldTable table; int oldCapacity oldTable.length; // 2 倍 int newCapacity oldCapacity 1; threshold (int)(newCapacity * loadFactor); // 创建新数组 HashEntryK,V[] newTable (HashEntryK,V[]) new HashEntry[newCapacity]; // 新的掩码如从 16 扩容到 32那么 sizeMask 为 31对应二进制 ‘000...00011111’ int sizeMask newCapacity - 1; // 遍历原数组老套路将原数组位置 i 处的链表拆分到 新数组位置 i 和 ioldCap 两个位置 for (int i 0; i oldCapacity ; i) { // e 是链表的第一个元素 HashEntryK,V e oldTable[i]; if (e ! null) { HashEntryK,V next e.next; // 计算应该放置在新数组中的位置 // 假设原数组长度为 16e 在 oldTable[3] 处那么 idx 只可能是 3 或者是 3 16 19 int idx e.hash sizeMask; if (next null) // 该位置处只有一个元素那比较好办 newTable[idx] e; else { // Reuse consecutive sequence at same slot // e 是链表表头 HashEntryK,V lastRun e; // idx 是当前链表的头结点 e 的新位置 int lastIdx idx; // 下面这个 for 循环会找到一个 lastRun 节点这个节点之后的所有元素是将要放到一起的 for (HashEntryK,V last next; last ! null; last last.next) { int k last.hash sizeMask; if (k ! lastIdx) { lastIdx k; lastRun last; } } // 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置 newTable[lastIdx] lastRun; // 下面的操作是处理 lastRun 之前的节点 // 这些节点可能分配在另一个链表中也可能分配到上面的那个链表中 for (HashEntryK,V p e; p ! lastRun; p p.next) { V v p.value; int h p.hash; int k h sizeMask; HashEntryK,V n newTable[k]; newTable[k] new HashEntryK,V(h, p.key, v, n); } } } } // 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部 int nodeIndex node.hash sizeMask; // add the new node node.setNext(newTable[nodeIndex]); newTable[nodeIndex] node; table newTable;
} 注意这里面的代码外部已经加锁所以这里面是安全的我们看下具体的实现方式先对数组的长度增加一倍然后遍历原来的旧的table数组把每一个数组元素也就是Node链表迁移到新的数组里面最后迁移完毕之后把新数组的引用直接替换旧的。此外这里这有一个小的细节优化在迁移链表时用了两个for循环第一个for的目的是为了判断是否有迁移位置一样的元素并且位置还是相邻根据HashMap的设计策略首先table的大小必须是2的n次方我们知道扩容后的每个链表的元素的位置要么不变要么是原table索引位置原table的容量大小举个例子假如现在有三个元素3,5,7要放入map里面table的的容量是2简单的假设元素位置元素的值 % 2得到如下结构
[0]null
[1]3-5-7 现在将table的大小扩容成4分布如下
[0]null
[1]5-7
[2]null
[3]3 因为扩容必须是2的n次方所以HashMap在put和get元素的时候直接取key的hashCode然后经过再次均衡后直接采用位运算就能达到取模效果这个不再细说上面这个例子的目的是为了说明扩容后的数据分布策略要么保留在原位置要么会被均衡在旧的table位置这里是1加上旧的table容量这是是2所以是3。基于这个特点第一个for循环作的优化如下假设我们现在用0表示原位置1表示迁移到indexoldCap的位置来代表元素
[0]null
[1]0-1-1-0-0-0-0 第一个for循环的会记录lastRun比如要迁移[1]的数据经过这个循环之后lastRun的位置会记录第三个0的位置因为后面的数据都是0代表他们要迁移到新的数组中同一个位置中所以就可以把这个中间节点直接插入到新的数组位置而后面附带的一串元素其实都不需要动。 接着第二个循环里面在此从第一个0的位置开始遍历到lastRun也就是第三个元素的位置就可以了只循环处理前面的数据即可这个循环里面根据位置0和1做不同的链表追加后面的数据已经被优化的迁移走了但最坏情况下可能后面一个也没优化比如下面的结构
[0]null
[1]1-1-0-0-0-0-1-0 这种情况第一个for循环没多大作用需要通过第二个for循环从头开始遍历到尾部按0和1分发迁移这里面使用的是还是头插法的方式迁移新迁移的数据是追加在链表的头部但这里是线程安全的所以不会出现循环链表导致死循环问题。迁移完成之后直接将最新的元素加入最后将新的table替换旧的table即可。 JDK8的HashMap扩容 在JDK8里面HashMap的底层数据结构已经变为数组链表红黑树的结构了因为在hash冲突严重的情况下链表的查询效率是O(n所以JDK8做了优化对于单个链表的个数大于8的链表会直接转为红黑树结构算是以空间换时间这样以来查询的效率就变为O(logN)图示如下 我们看下其扩容代码 final NodeK,V[] resize() { NodeK,V[] oldTab table; int oldCap (oldTab null) ? 0 : oldTab.length; int oldThr threshold; int newCap, newThr 0; if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold } else if (oldThr 0) // initial capacity was placed in threshold newCap oldThr; else { // zero initial threshold signifies using defaults newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr 0) { float ft (float)newCap * loadFactor; newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold newThr; SuppressWarnings({rawtypes,unchecked}) NodeK,V[] newTab (NodeK,V[])new Node[newCap]; table newTab; if (oldTab ! null) { for (int j 0; j oldCap; j) { NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null; if (e.next null) newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode) ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { //重点关注区域 // preserve order NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } } } } } return newTab; } 在JDK8中单纯的HashMap数据结构增加了红黑树是一个大的优化此外根据上面的迁移扩容策略我们发现JDK8里面HashMap没有采用头插法转移链表数据而是保留了元素的顺序位置新的代码里面采用
Java代码 //按原始链表顺序过滤出来扩容后位置不变的元素低位0放在一起 NodeK,V loHead null, loTail null; //按原始链表顺序过滤出来扩容后位置改变到indexoldCap的元素高位0放在一起 NodeK,V hiHead null, hiTail null; 把要迁移的元素分类之后最后在分别放到新数组对应的位置上
Java代码 //位置不变 if (loTail ! null) { loTail.next null; newTab[j] loHead; } //位置迁移(indexoldCap) if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; } JDK7里面是先判断table的存储元素的数量是否超过当前的thresholdtable.length*loadFactor默认0.75如果超过就先扩容在JDK8里面是先插入数据插入之后在判断下一次size的大小是否会超过当前的阈值如果超过就扩容。
JDK8的ConcurrentHashMap扩容 在JDK8中彻底抛弃了JDK7的分段锁的机制新的版本主要使用了Unsafe类的CAS自旋赋值synchronized同步LockSupport阻塞等手段实现的高效并发代码可读性稍差。
ConcurrentHashMap的JDK8与JDK7版本的并发实现相比最大的区别在于JDK8的锁粒度更细理想情况下talbe数组元素的大小就是其支持并发的最大个数在JDK7里面最大并发个数就是Segment的个数默认值是16可以通过构造函数改变一经创建不可更改这个值就是并发的粒度每一个segment下面管理一个table数组加锁的时候其实锁住的是整个segment这样设计的好处在于数组的扩容是不会影响其他的segment的简化了并发设计不足之处在于并发的粒度稍粗所以在JDK8里面去掉了分段锁将锁的级别控制在了更细粒度的table元素级别也就是说只需要锁住这个链表的head节点并不会影响其他的table元素的读写好处在于并发的粒度更细影响更小从而并发效率更好但不足之处在于并发扩容的时候由于操作的table都是同一个不像JDK7中分段控制所以这里需要等扩容完之后所有的读写操作才能进行所以扩容的效率就成为了整个并发的一个瓶颈点好在Doug lea大神对扩容做了优化本来在一个线程扩容的时候如果影响了其他线程的数据那么其他的线程的读写操作都应该阻塞但Doug lea说你们闲着也是闲着不如来一起参与扩容任务这样人多力量大办完事你们该干啥干啥别浪费时间于是在JDK8的源码里面就引入了一个ForwardingNode类在一个线程发起扩容的时候就会改变sizeCtl这个值其含义如下
Java代码 sizeCtl 默认为0用来控制table的初始化和扩容操作具体应用在后续会体现出来。 -1 代表table正在初始化 -N 表示有N-1个线程正在进行扩容操作 其余情况 1、如果table未初始化表示table需要初始化的大小。 2、如果table初始化完成表示table的容量默认是table大小的0.75倍 扩容时候会判断这个值如果超过阈值就要扩容首先根据运算得到需要遍历的次数i然后利用tabAt方法获得i位置的元素f初始化一个forwardNode实例fwd如果f null则在table中的i位置放入fwd否则采用头插法的方式把当前旧table数组的指定任务范围的数据给迁移到新的数组中然后 给旧table原位置赋值fwd。直到遍历过所有的节点以后就完成了复制工作把table指向nextTable并更新sizeCtl为新数组大小的0.75倍 扩容完成。在此期间如果其他线程的有读写操作都会判断head节点是否为forwardNode节点如果是就帮助扩容。 扩容源码如下
Java代码 private final void transfer(NodeK,V[] tab, NodeK,V[] nextTab) { int n tab.length, stride; if ((stride (NCPU 1) ? (n 3) / NCPU : n) MIN_TRANSFER_STRIDE) stride MIN_TRANSFER_STRIDE; // subdivide range if (nextTab null) { // initiating try { SuppressWarnings(unchecked) NodeK,V[] nt (NodeK,V[])new Node?,?[n 1]; nextTab nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl Integer.MAX_VALUE; return; } nextTable nextTab; transferIndex n; } int nextn nextTab.length; ForwardingNodeK,V fwd new ForwardingNodeK,V(nextTab); boolean advance true; boolean finishing false; // to ensure sweep before committing nextTab for (int i 0, bound 0;;) { NodeK,V f; int fh; while (advance) { int nextIndex, nextBound; if (--i bound || finishing) advance false; else if ((nextIndex transferIndex) 0) { i -1; advance false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound (nextIndex stride ? nextIndex - stride : 0))) { bound nextBound; i nextIndex - 1; advance false; } } if (i 0 || i n || i n nextn) { int sc; if (finishing) { nextTable null; table nextTab; sizeCtl (n 1) - (n 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc sizeCtl, sc - 1)) { if ((sc - 2) ! resizeStamp(n) RESIZE_STAMP_SHIFT) return; finishing advance true; i n; // recheck before commit } } else if ((f tabAt(tab, i)) null) advance casTabAt(tab, i, null, fwd); else if ((fh f.hash) MOVED) advance true; // already processed else { synchronized (f) { if (tabAt(tab, i) f) { NodeK,V ln, hn; if (fh 0) { int runBit fh n; NodeK,V lastRun f; for (NodeK,V p f.next; p ! null; p p.next) { int b p.hash n; if (b ! runBit) { runBit b; lastRun p; } } if (runBit 0) { ln lastRun; hn null; } else { hn lastRun; ln null; } for (NodeK,V p f; p ! lastRun; p p.next) { int ph p.hash; K pk p.key; V pv p.val; if ((ph n) 0) ln new NodeK,V(ph, pk, pv, ln); else hn new NodeK,V(ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i n, hn); setTabAt(tab, i, fwd); advance true; } else if (f instanceof TreeBin) { TreeBinK,V t (TreeBinK,V)f; TreeNodeK,V lo null, loTail null; TreeNodeK,V hi null, hiTail null; int lc 0, hc 0; for (NodeK,V e t.first; e ! null; e e.next) { int h e.hash; TreeNodeK,V p new TreeNodeK,V (h, e.key, e.val, null, null); if ((h n) 0) { if ((p.prev loTail) null) lo p; else loTail.next p; loTail p; lc; } else { if ((p.prev hiTail) null) hi p; else hiTail.next p; hiTail p; hc; } } ln (lc UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! 0) ? new TreeBinK,V(lo) : t; hn (hc UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! 0) ? new TreeBinK,V(hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i n, hn); setTabAt(tab, i, fwd); advance true; } } } } } } 在扩容时读写操作如何进行 (1)对于get读操作如果当前节点有数据还没迁移完成此时不影响读能够正常进行。 如果当前链表已经迁移完成那么头节点会被设置成fwd节点此时get线程会帮助扩容。 (2)对于put/remove写操作如果当前链表已经迁移完成那么头节点会被设置成fwd节点此时写线程会帮助扩容如果扩容没有完成当前链表的头节点会被锁住所以写线程会被阻塞直到扩容完成。
对于size和迭代器是弱一致性 volatile修饰的数组引用是强可见的但是其元素却不一定所以这导致size的根据sumCount的方法并不准确。 同理Iteritor的迭代器也一样并不能准确反映最新的实际情况
总结 本文主要了介绍了HashMapConcurrentHashMap的扩容策略扩容的原理是新生成大于原来1倍大小的数组然后拷贝旧数组数据到新的数组里面在多线程情况下这里面如果注意线程安全问题在解决安全问题的同时我们也要关注其效率这才是并发容器类的最出色的地方。
