网站建设公司业务培训,为什么建设长虹网站,网站的网页设计毕业设计,网站建设 企炬转载自 Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少#xff0c;不过缺斤少两的文章比较多#xff0c;所以才想自己也写一篇#xff0c;把细节说清楚说透#xff0c;尤其像 Java8 中的 ConcurrentHashMap#…转载自 Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少不过缺斤少两的文章比较多所以才想自己也写一篇把细节说清楚说透尤其像 Java8 中的 ConcurrentHashMap大部分文章都说不清楚。终归是希望能降低大家学习的成本不希望大家到处找各种不是很靠谱的文章看完一篇又一篇可是还是模模糊糊。
阅读建议四节基本上可以进行独立阅读建议初学者可按照 Java7 HashMap - Java7 ConcurrentHashMap - Java8 HashMap - Java8 ConcurrentHashMap 顺序进行阅读可适当降低阅读门槛。
阅读前提本文分析的是源码所以至少读者要熟悉它们的接口使用同时对于并发读者至少要知道 CAS、ReentrantLock、UNSAFE 操作这几个基本的知识文中不会对这些知识进行介绍。Java8 用到了红黑树不过本文不会进行展开感兴趣的读者请自行查找相关资料。
Java7 HashMap
HashMap 是最简单的一来我们非常熟悉二来就是它不支持并发操作所以源码也非常简单。
首先我们用下面这张图来介绍 HashMap 的结构。这个仅仅是示意图因为没有考虑到数组要扩容的情况具体的后面再说。大方向上HashMap 里面是一个数组然后数组中每个元素是一个单向链表。
上图中每个绿色的实体是嵌套类 Entry 的实例Entry 包含四个属性key, value, hash 值和用于单向链表的 next。
capacity当前数组容量始终保持 2^n可以扩容扩容后数组大小为当前的 2 倍。
loadFactor负载因子默认为 0.75。
threshold扩容的阈值等于 capacity * loadFactor
put 过程分析
还是比较简单的跟着代码走一遍吧。
1234567891011121314151617181920212223242526272829publicV put(K key, V value) { // 当插入第一个元素的时候需要先初始化数组大小 if(table EMPTY_TABLE) { inflateTable(threshold); } // 如果 key 为 null感兴趣的可以往里看最终会将这个 entry 放到 table[0] 中 if(key null) returnputForNullKey(value); // 1. 求 key 的 hash 值 inthash hash(key); // 2. 找到对应的数组下标 inti indexFor(hash, table.length); // 3. 遍历一下对应下标处的链表看是否有重复的 key 已经存在 // 如果有直接覆盖put 方法返回旧值就结束了 for(EntryK,V e table[i]; e ! null; e e.next) { Object k; if(e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value; e.value value; e.recordAccess(this); returnoldValue; } } modCount; // 4. 不存在重复的 key将此 entry 添加到链表中细节后面说 addEntry(hash, key, value, i); returnnull;}数组初始化
在第一个元素插入 HashMap 的时候做一次数组的初始化就是先确定初始的数组大小并计算数组扩容的阈值。
12345678910privatevoid inflateTable(inttoSize) { // 保证数组大小一定是 2 的 n 次方。 // 比如这样初始化new HashMap(20)那么处理成初始数组大小是 32 intcapacity roundUpToPowerOf2(toSize); // 计算扩容阈值capacity * loadFactor threshold (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1); // 算是初始化数组吧 table newEntry[capacity]; initHashSeedAsNeeded(capacity);//ignore}这里有一个将数组大小保持为 2 的 n 次方的做法Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相应的要求只不过实现的代码稍微有些不同后面再看到的时候就知道了。
计算具体数组位置
这个简单我们自己也能 YY 一个使用 key 的 hash 值对数组长度进行取模就可以了。
1234staticint indexFor(inthash, intlength) { // assert Integer.bitCount(length) 1 : length must be a non-zero power of 2; returnhash (length-1);}这个方法很简单简单说就是取 hash 值的低 n 位。如在数组长度为 32 的时候其实取的就是 key 的 hash 值的低 5 位作为它在数组中的下标位置。
添加节点到链表中
找到数组下标后会先进行 key 判重如果没有重复就准备将新值放入到链表的表头。
12345678910111213141516171819voidaddEntry(inthash, K key, V value, intbucketIndex) { // 如果当前 HashMap 大小已经达到了阈值并且新值要插入的数组位置已经有元素了那么要扩容 if((size threshold) (null! table[bucketIndex])) { // 扩容后面会介绍一下 resize(2* table.length); // 扩容以后重新计算 hash 值 hash (null! key) ? hash(key) : 0; // 重新计算扩容后的新的下标 bucketIndex indexFor(hash, table.length); } // 往下看 createEntry(hash, key, value, bucketIndex);}// 这个很简单其实就是将新值放到链表的表头然后 sizevoidcreateEntry(inthash, K key, V value, intbucketIndex) { EntryK,V e table[bucketIndex]; table[bucketIndex] newEntry(hash, key, value, e); size;}这个方法的主要逻辑就是先判断是否需要扩容需要的话先扩容然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。
数组扩容
前面我们看到在插入新值的时候如果当前的 size 已经达到了阈值并且要插入的数组位置上已经有元素那么就会触发扩容扩容后数组大小为原来的 2 倍。
1234567891011121314voidresize(intnewCapacity) { Entry[] oldTable table; intoldCapacity oldTable.length; if(oldCapacity MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return; } // 新的数组 Entry[] newTable newEntry[newCapacity]; // 将原来数组中的值迁移到新的更大的数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table newTable; threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);}扩容就是用一个新的大数组替换原来的小数组并将原来数组中的值迁移到新的数组中。
由于是双倍扩容迁移过程中会将原来 table[i] 中的链表的所有节点分拆到新的数组的 newTable[i] 和 newTable[i oldLength] 位置上。如原来数组长度是 16那么扩容后原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置。代码比较简单这里就不展开了。
get 过程分析
相对于 put 过程get 过程是非常简单的。
根据 key 计算 hash 值。找到相应的数组下标hash (length – 1)。遍历该数组位置处的链表直到找到相等(或equals)的 key。
123456789publicV get(Object key) { // 之前说过key 为 null 的话会被放到 table[0]所以只要遍历下 table[0] 处的链表就可以了 if(key null) returngetForNullKey(); // EntryK,V entry getEntry(key); returnnull entry ? null: entry.getValue();}getEntry(key):
1234567891011121314151617finalEntryK,V getEntry(Object key) { if(size 0) { returnnull; } inthash (key null) ? 0: hash(key); // 确定数组下标然后从头开始遍历链表直到找到为止 for(EntryK,V e table[indexFor(hash, table.length)]; e ! null; e e.next) { Object k; if(e.hash hash ((k e.key) key || (key ! null key.equals(k)))) returne; } returnnull;}Java7 ConcurrentHashMap
ConcurrentHashMap 和 HashMap 思路是差不多的但是因为它支持并发操作所以要复杂一些。
整个 ConcurrentHashMap 由一个个 Segment 组成Segment 代表”部分“或”一段“的意思所以很多地方都会将其描述为分段锁。注意行文中我很多地方用了“槽”来代表一个 segment。
简单理解就是ConcurrentHashMap 是一个 Segment 数组Segment 通过继承 ReentrantLock 来进行加锁所以每次需要加锁的操作锁住的是一个 segment这样只要保证每个 Segment 是线程安全的也就实现了全局的线程安全。concurrencyLevel并行级别、并发数、Segment 数怎么翻译不重要理解它。默认是 16也就是说 ConcurrentHashMap 有 16 个 Segments所以理论上这个时候最多可以同时支持 16 个线程并发写只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值但是一旦初始化以后它是不可以扩容的。
再具体到每个 Segment 内部其实每个 Segment 很像之前介绍的 HashMap不过它要保证线程安全所以处理起来要麻烦些。
初始化
initialCapacity初始容量这个值指的是整个 ConcurrentHashMap 的初始容量实际操作的时候需要平均分给每个 Segment。
loadFactor负载因子之前我们说了Segment 数组不可以扩容所以这个负载因子是给每个 Segment 内部使用的。
1234567891011121314151617181920212223242526272829303132333435363738394041424344publicConcurrentHashMap(intinitialCapacity, floatloadFactor, intconcurrencyLevel) { if(!(loadFactor 0) || initialCapacity 0|| concurrencyLevel 0) thrownew IllegalArgumentException(); if(concurrencyLevel MAX_SEGMENTS) concurrencyLevel MAX_SEGMENTS; // Find power-of-two sizes best matching arguments intsshift 0; intssize 1; // 计算并行级别 ssize因为要保持并行级别是 2 的 n 次方 while(ssize concurrencyLevel) { sshift; ssize 1; } // 我们这里先不要那么烧脑用默认值concurrencyLevel 为 16sshift 为 4 // 那么计算出 segmentShift 为 28segmentMask 为 15后面会用到这两个值 this.segmentShift 32- sshift; this.segmentMask ssize - 1; if(initialCapacity MAXIMUM_CAPACITY) initialCapacity MAXIMUM_CAPACITY; // initialCapacity 是设置整个 map 初始的大小 // 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小 // 如 initialCapacity 为 64那么每个 Segment 或称之为槽可以分到 4 个 intc initialCapacity / ssize; if(c * ssize initialCapacity) c; // 默认 MIN_SEGMENT_TABLE_CAPACITY 是 2这个值也是有讲究的因为这样的话对于具体的槽上 // 插入一个元素不至于扩容插入第二个的时候才会扩容 intcap MIN_SEGMENT_TABLE_CAPACITY; while(cap c) cap 1; // 创建 Segment 数组 // 并创建数组的第一个元素 segment[0] SegmentK,V s0 newSegmentK,V(loadFactor, (int)(cap * loadFactor), (HashEntryK,V[])newHashEntry[cap]); SegmentK,V[] ss (SegmentK,V[])newSegment[ssize]; // 往数组写入 segment[0] UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0] this.segments ss;}初始化完成我们得到了一个 Segment 数组。
我们就当是用 new ConcurrentHashMap() 无参构造函数进行初始化的那么初始化完成后
Segment 数组长度为 16不可以扩容Segment[i] 的默认大小为 2负载因子是 0.75得出初始阈值为 1.5也就是以后插入第一个元素不会触发扩容插入第二个会进行第一次扩容这里初始化了 segment[0]其他位置还是 null至于为什么要初始化 segment[0]后面的代码会介绍当前 segmentShift 的值为 32 – 4 28segmentMask 为 16 – 1 15姑且把它们简单翻译为移位数和掩码这两个值马上就会用到
put 过程分析
我们先看 put 的主流程对于其中的一些关键细节操作后面会进行详细介绍。
123456789101112131415161718publicV put(K key, V value) { SegmentK,V s; if(value null) thrownew NullPointerException(); // 1. 计算 key 的 hash 值 inthash hash(key); // 2. 根据 hash 值找到 Segment 数组中的位置 j // hash 是 32 位无符号右移 segmentShift(28) 位剩下低 4 位 // 然后和 segmentMask(15) 做一次与操作也就是说 j 是 hash 值的最后 4 位也就是槽的数组下标 intj (hash segmentShift) segmentMask; // 刚刚说了初始化的时候初始化了 segment[0]但是其他位置还是 null // ensureSegment(j) 对 segment[j] 进行初始化 if((s (SegmentK,V)UNSAFE.getObject // nonvolatile; recheck (segments, (j SSHIFT) SBASE)) null)// in ensureSegment s ensureSegment(j); // 3. 插入新值到 槽 s 中 returns.put(key, hash, value, false);}第一层皮很简单根据 hash 值很快就能找到相应的 Segment之后就是 Segment 内部的 put 操作了。
Segment 内部是由 数组链表 组成的。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859finalV put(K key, inthash, V value, booleanonlyIfAbsent) { // 在往该 segment 写入前需要先获取该 segment 的独占锁 // 先看主流程后面还会具体介绍这部分内容 HashEntryK,V node tryLock() ? null: scanAndLockForPut(key, hash, value); V oldValue; try{ // 这个是 segment 内部的数组 HashEntryK,V[] tab table; // 再利用 hash 值求应该放置的数组下标 intindex (tab.length - 1) hash; // first 是数组该位置处的链表的表头 HashEntryK,V first entryAt(tab, index); // 下面这串 for 循环虽然很长不过也很好理解想想该位置没有任何元素和已经存在一个链表这两种情况 for(HashEntryK,V e first;;) { if(e ! null) { K k; if((k e.key) key || (e.hash hash key.equals(k))) { oldValue e.value; if(!onlyIfAbsent) { // 覆盖旧值 e.value value; modCount; } break; } // 继续顺着链表走 e e.next; } else{ // node 到底是不是 null这个要看获取锁的过程不过和这里都没有关系。 // 如果不为 null那就直接将它设置为链表表头如果是null初始化并设置为链表表头。 if(node ! null) node.setNext(first); else node newHashEntryK,V(hash, key, value, first); intc count 1; // 如果超过了该 segment 的阈值这个 segment 需要扩容 if(c threshold tab.length MAXIMUM_CAPACITY) rehash(node);// 扩容后面也会具体分析 else // 没有达到阈值将 node 放到数组 tab 的 index 位置 // 其实就是将新的节点设置成原链表的表头 setEntryAt(tab, index, node); modCount; count c; oldValue null; break; } } }finally{ // 解锁 unlock(); } returnoldValue;}整体流程还是比较简单的由于有独占锁的保护所以 segment 内部的操作并不复杂。至于这里面的并发问题我们稍后再进行介绍。
到这里 put 操作就结束了接下来我们说一说其中几步关键的操作。
初始化槽: ensureSegment
ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]对于其他槽来说在插入第一个值的时候进行初始化。
这里需要考虑并发因为很可能会有多个线程同时进来初始化同一个槽 segment[k]不过只要有一个成功了就可以。
1234567891011121314151617181920212223242526272829privateSegmentK,V ensureSegment(intk) { finalSegmentK,V[] ss this.segments; longu (k SSHIFT) SBASE; // raw offset SegmentK,V seg; if((seg (SegmentK,V)UNSAFE.getObjectVolatile(ss, u)) null) { // 这里看到为什么之前要初始化 segment[0] 了 // 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k] // 为什么要用“当前”因为 segment[0] 可能早就扩容过了 SegmentK,V proto ss[0]; intcap proto.table.length; floatlf proto.loadFactor; intthreshold (int)(cap * lf); // 初始化 segment[k] 内部的数组 HashEntryK,V[] tab (HashEntryK,V[])newHashEntry[cap]; if((seg (SegmentK,V)UNSAFE.getObjectVolatile(ss, u)) null) { // 再次检查一遍该槽是否被其他线程初始化了。 SegmentK,V s newSegmentK,V(lf, threshold, tab); // 使用 while 循环内部用 CAS当前线程成功设值或其他线程成功设值后退出 while((seg (SegmentK,V)UNSAFE.getObjectVolatile(ss, u)) null) { if(UNSAFE.compareAndSwapObject(ss, u, null, seg s)) break; } } } returnseg;}总的来说ensureSegment(int k) 比较简单对于并发操作使用 CAS 进行控制。
我没搞懂这里为什么要搞一个 while 循环CAS 失败不就代表有其他线程成功了吗为什么要再进行判断获取写入锁: scanAndLockForPut
前面我们看到在往某个 segment 中 put 的时候首先会调用 node tryLock() ? null : scanAndLockForPut(key, hash, value)也就是说先进行一次 tryLock() 快速获取该 segment 的独占锁如果失败那么进入到 scanAndLockForPut 这个方法来获取锁。
下面我们来具体分析这个方法中是怎么控制加锁的。
123456789101112131415161718192021222324252627282930313233343536373839privateHashEntryK,V scanAndLockForPut(K key, inthash, V value) { HashEntryK,V first entryForHash(this, hash); HashEntryK,V e first; HashEntryK,V node null; intretries -1;// negative while locating node // 循环获取锁 while(!tryLock()) { HashEntryK,V f; // to recheck first below if(retries 0) { if(e null) { if(node null)// speculatively create node // 进到这里说明数组该位置的链表是空的没有任何元素 // 当然进到这里的另一个原因是 tryLock() 失败所以该槽存在并发不一定是该位置 node newHashEntryK,V(hash, key, value, null); retries 0; } elseif (key.equals(e.key)) retries 0; else // 顺着链表往下走 e e.next; } // 重试次数如果超过 MAX_SCAN_RETRIES单核1多核64那么不抢了进入到阻塞队列等待锁 // lock() 是阻塞方法直到获取锁后返回 elseif (retries MAX_SCAN_RETRIES) { lock(); break; } elseif ((retries 1) 0 // 这个时候是有大问题了那就是有新的元素进到了链表成为了新的表头 // 所以这边的策略是相当于重新走一遍这个 scanAndLockForPut 方法 (f entryForHash(this, hash)) ! first) { e first f; // re-traverse if entry changed retries -1; } } returnnode;}这个方法有两个出口一个是 tryLock() 成功了循环终止另一个就是重试次数超过了 MAX_SCAN_RETRIES进到 lock() 方法此方法会阻塞等待直到成功拿到独占锁。
这个方法就是看似复杂但是其实就是做了一件事那就是获取该 segment 的独占锁如果需要的话顺便实例化了一下 node。
扩容: rehash
重复一下segment 数组不能扩容扩容是 segment 数组某个位置内部的数组 HashEntry\[] 进行扩容扩容后容量为原来的 2 倍。
首先我们要回顾一下触发扩容的地方put 的时候如果判断该值的插入会导致该 segment 的元素个数超过阈值那么先进行扩容再插值读者这个时候可以回去 put 方法看一眼。
该方法不需要考虑并发因为到这里的时候是持有该 segment 的独占锁的。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960// 方法参数上的 node 是这次扩容后需要添加到新的数组中的数据。privatevoid rehash(HashEntryK,V node) { HashEntryK,V[] oldTable table; intoldCapacity oldTable.length; // 2 倍 intnewCapacity oldCapacity 1; threshold (int)(newCapacity * loadFactor); // 创建新数组 HashEntryK,V[] newTable (HashEntryK,V[])newHashEntry[newCapacity]; // 新的掩码如从 16 扩容到 32那么 sizeMask 为 31对应二进制 ‘000...00011111’ intsizeMask newCapacity - 1; // 遍历原数组老套路将原数组位置 i 处的链表拆分到 新数组位置 i 和 ioldCap 两个位置 for(inti 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 intidx e.hash sizeMask; if(next null) // 该位置处只有一个元素那比较好办 newTable[idx] e; else{ // Reuse consecutive sequence at same slot // e 是链表表头 HashEntryK,V lastRun e; // idx 是当前链表的头结点 e 的新位置 intlastIdx idx; // 下面这个 for 循环会找到一个 lastRun 节点这个节点之后的所有元素是将要放到一起的 for(HashEntryK,V last next; last ! null; last last.next) { intk 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; inth p.hash; intk h sizeMask; HashEntryK,V n newTable[k]; newTable[k] newHashEntryK,V(h, p.key, v, n); } } } } // 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部 intnodeIndex node.hash sizeMask; // add the new node node.setNext(newTable[nodeIndex]); newTable[nodeIndex] node; table newTable;}这里的扩容比之前的 HashMap 要复杂一些代码难懂一点。上面有两个挨着的 for 循环第一个 for 有什么用呢
仔细一看发现如果没有第一个 for 循环也是可以工作的但是这个 for 循环下来如果 lastRun 的后面还有比较多的节点那么这次就是值得的。因为我们只需要克隆 lastRun 前面的节点后面的一串节点跟着 lastRun 走就是了不需要做任何操作。
我觉得 Doug Lea 的这个想法也是挺有意思的不过比较坏的情况就是每次 lastRun 都是链表的最后一个元素或者很靠后的元素那么这次遍历就有点浪费了。不过 Doug Lea 也说了根据统计如果使用默认的阈值大约只有 1/6 的节点需要克隆。
get 过程分析
相对于 put 来说get 真的不要太简单。
计算 hash 值找到 segment 数组中的具体位置或我们前面用的“槽”槽中也是一个数组根据 hash 找到数组中具体的位置到这里是链表了顺着链表进行查找即可
1234567891011121314151617181920publicV get(Object key) { SegmentK,V s; // manually integrate access methods to reduce overhead HashEntryK,V[] tab; // 1. hash 值 inth hash(key); longu (((h segmentShift) segmentMask) SSHIFT) SBASE; // 2. 根据 hash 找到对应的 segment if((s (SegmentK,V)UNSAFE.getObjectVolatile(segments, u)) ! null (tab s.table) ! null) { // 3. 找到segment 内部数组相应位置的链表遍历 for(HashEntryK,V e (HashEntryK,V) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) h)) TSHIFT) TBASE); e ! null; e e.next) { K k; if((k e.key) key || (e.hash h key.equals(k))) returne.value; } } returnnull;}并发问题分析
现在我们已经说完了 put 过程和 get 过程我们可以看到 get 过程中是没有加锁的那自然我们就需要去考虑并发问题。
添加节点的操作 put 和删除节点的操作 remove 都是要加 segment 上的独占锁的所以它们之间自然不会有问题我们需要考虑的问题就是 get 的时候在同一个 segment 中发生了 put 或 remove 操作。
put 操作的线程安全性。初始化槽这个我们之前就说过了使用了 CAS 来初始化 Segment 中的数组。添加节点到链表的操作是插入到表头的所以如果这个时候 get 操作在链表遍历的过程已经到了中间是不会影响的。当然另一个并发问题就是 get 操作在 put 之后需要保证刚刚插入表头的节点被读取这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。扩容。扩容是新创建了数组然后进行迁移数据最后面将 newTable 设置给属性 table。所以如果 get 操作此时也在进行那么也没关系如果 get 先行那么就是在旧的 table 上做查询操作而 put 先行那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。remove 操作的线程安全性。remove 操作我们没有分析源码所以这里说的读者感兴趣的话还是需要到源码中去求实一下的。get 操作需要遍历链表但是 remove 操作会”破坏”链表。如果 remove 破坏的节点 get 操作已经过去了那么这里不存在任何问题。如果 remove 先破坏了一个节点分两种情况考虑。 1、如果此节点是头结点那么需要将头结点的 next 设置为数组该位置的元素table 虽然使用了 volatile 修饰但是 volatile 并不能提供数组内部操作的可见性保证所以源码中使用了 UNSAFE 来操作数组请看方法 setEntryAt。2、如果要删除的节点不是头结点它会将要删除节点的后继节点接到前驱节点中这里的并发保证就是 next 属性是 volatile 的。
Java8 HashMap
Java8 对 HashMap 进行了一些修改最大的不同就是利用了红黑树所以其由 数组链表红黑树 组成。
根据 Java7 HashMap 的介绍我们知道查找的时候根据 hash 值我们能够快速定位到数组的具体下标但是之后的话需要顺着链表一个个比较下去才能找到我们需要的时间复杂度取决于链表的长度为 O(n)。
为了降低这部分的开销在 Java8 中当链表中的元素超过了 8 个以后会将链表转换为红黑树在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
来一张图简单示意一下吧注意上图是示意图主要是描述结构不会达到这个状态的因为这么多数据的时候早就扩容了。下面我们还是用代码来介绍吧个人感觉Java8 的源码可读性要差一些不过精简一些。
Java7 中使用 Entry 来代表每个 HashMap 中的数据节点Java8 中使用 Node基本没有区别都是 keyvaluehash 和 next 这四个属性不过Node 只能用于链表的情况红黑树的情况需要使用 TreeNode。
我们根据数组元素中第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。
put 过程分析
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263publicV put(K key, V value) { returnputVal(hash(key), key, value, false,true);}// 第三个参数 onlyIfAbsent 如果是 true那么只有在不存在该 key 时才会进行 put 操作// 第四个参数 evict 我们这里不关心finalV putVal(inthash, K key, V value, booleanonlyIfAbsent, booleanevict) { NodeK,V[] tab; NodeK,V p; intn, i; // 第一次 put 值的时候会触发下面的 resize()类似 java7 的第一次 put 也要初始化数组长度 // 第一次 resize 和后续的扩容有些不一样因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量 if((tab table) null|| (n tab.length) 0) n (tab resize()).length; // 找到具体的数组下标如果此位置没有值那么直接初始化一下 Node 并放置在这个位置就可以了 if((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else{// 数组该位置有数据 NodeK,V e; K k; // 首先判断该位置的第一个数据和我们要插入的数据key 是不是相等如果是取出这个节点 if(p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; // 如果该节点是代表红黑树的节点调用红黑树的插值方法本文不展开说红黑树 elseif (p instanceofTreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else{ // 到这里说明数组该位置上是一个链表 for(intbinCount 0; ; binCount) { // 插入到链表的最后面(Java7 是插入到链表的最前面) if((e p.next) null) { p.next newNode(hash, key, value, null); // TREEIFY_THRESHOLD 为 8所以如果新插入的值是链表中的第 9 个 // 会触发下面的 treeifyBin也就是将链表转换为红黑树 if(binCount TREEIFY_THRESHOLD - 1)// -1 for 1st treeifyBin(tab, hash); break; } // 如果在该链表中找到了相等的 key( 或 equals) if(e.hash hash ((k e.key) key || (key ! null key.equals(k)))) // 此时 break那么 e 为链表中[与要插入的新值的 key 相等]的 node break; p e; } } // e!null 说明存在旧值的key与要插入的key相等 // 对于我们分析的put操作下面这个 if 其实就是进行 值覆盖然后返回旧值 if(e ! null) { V oldValue e.value; if(!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); returnoldValue; } } modCount; // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值需要进行扩容 if(size threshold) resize(); afterNodeInsertion(evict); returnnull;}和 Java7 稍微有点不一样的地方就是Java7 是先扩容后插入新值的Java8 先插值再扩容不过这个不重要。
数组扩容
resize() 方法用于初始化数组或数组扩容每次扩容后容量为原来的 2 倍并进行数据迁移。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586finalNodeK,V[] resize() { NodeK,V[] oldTab table; intoldCap (oldTab null) ? 0: oldTab.length; intoldThr threshold; intnewCap, newThr 0; if(oldCap 0) { // 对应数组扩容 if(oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; returnoldTab; } // 将数组大小扩大一倍 elseif ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) // 将阈值扩大一倍 newThr oldThr 1;// double threshold } elseif (oldThr 0)// 对应使用 new HashMap(int initialCapacity) 初始化后第一次 put 的时候 newCap oldThr; else{// 对应使用 new HashMap() 初始化后第一次 put 的时候 newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if(newThr 0) { floatft (float)newCap * loadFactor; newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold newThr; // 用新的数组大小初始化新的数组 NodeK,V[] newTab (NodeK,V[])newNode[newCap]; table newTab; // 如果是初始化数组到这里就结束了返回 newTab 即可 if(oldTab ! null) { // 开始遍历原数组进行数据迁移。 for(intj 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; // 如果是红黑树具体我们就不展开了 elseif (e instanceofTreeNode) ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else{ // 这块是处理链表的情况 // 需要将此链表拆成两个链表放到新的数组中并且保留原来的先后顺序 // loHead、loTail 对应一条链表hiHead、hiTail 对应另一条链表代码还是比较简单的 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; // 第二条链表的新的位置是 j oldCap这个很好理解 newTab[j oldCap] hiHead; } } } } } returnnewTab;}get 过程分析
相对于 put 来说get 真的太简单了。
计算 key 的 hash 值根据 hash 值找到对应数组下标: hash (length-1)判断数组该位置处的元素是否刚好就是我们要找的如果不是走第三步判断该元素类型是否是 TreeNode如果是用红黑树的方法取数据如果不是走第四步遍历链表直到找到相等(或equals)的 key
1234publicV get(Object key) { NodeK,V e; return(e getNode(hash(key), key)) null? null: e.value;}1234567891011121314151617181920212223finalNodeK,V getNode(inthash, Object key) { NodeK,V[] tab; NodeK,V first, e; intn; K k; if((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 判断第一个节点是不是就是需要的 if(first.hash hash // always check first node ((k first.key) key || (key ! null key.equals(k)))) returnfirst; if((e first.next) ! null) { // 判断是否是红黑树 if(first instanceofTreeNode) return((TreeNodeK,V)first).getTreeNode(hash, key); // 链表遍历 do{ if(e.hash hash ((k e.key) key || (key ! null key.equals(k)))) returne; }while((e e.next) ! null); } } returnnull;}Java8 ConcurrentHashMap
Java7 中实现的 ConcurrentHashMap 说实话还是比较复杂的Java8 对 ConcurrentHashMap 进行了比较大的改动。建议读者可以参考 Java8 中 HashMap 相对于 Java7 HashMap 的改动对于 ConcurrentHashMapJava8 也引入了红黑树。
说实话Java8 ConcurrentHashMap 源码真心不简单最难的在于扩容数据迁移操作不容易看懂。
我们先用一个示意图来描述下其结构结构上和 Java8 的 HashMap 基本上一样不过它要保证线程安全性所以在源码上确实要复杂一些。
初始化
1234567891011// 这构造函数里什么都不干publicConcurrentHashMap() {}publicConcurrentHashMap(intinitialCapacity) { if(initialCapacity 0) thrownew IllegalArgumentException(); intcap ((initialCapacity (MAXIMUM_CAPACITY 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity (initialCapacity 1) 1)); this.sizeCtl cap;}这个初始化方法有点意思通过提供初始容量计算了 sizeCtlsizeCtl 【 (1.5 * initialCapacity 1)然后向上取最近的 2 的 n 次方】。如 initialCapacity 为 10那么得到 sizeCtl 为 16如果 initialCapacity 为 11得到 sizeCtl 为 32。
sizeCtl 这个属性使用的场景很多不过只要跟着文章的思路来就不会被它搞晕了。
如果你爱折腾也可以看下另一个有三个参数的构造方法这里我就不说了大部分时候我们会使用无参构造函数进行实例化我们也按照这个思路来进行源码分析吧。
put 过程分析
仔细地一行一行代码看下去
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091publicV put(K key, V value) { returnputVal(key, value, false);}finalV putVal(K key, V value, booleanonlyIfAbsent) { if(key null|| value null)thrownew NullPointerException(); // 得到 hash 值 inthash spread(key.hashCode()); // 用于记录相应链表的长度 intbinCount 0; for(NodeK,V[] tab table;;) { NodeK,V f; intn, i, fh; // 如果数组空进行数组初始化 if(tab null|| (n tab.length) 0) // 初始化数组后面会详细介绍 tab initTable(); // 找该 hash 值对应的数组下标得到第一个节点 f elseif ((f tabAt(tab, i (n - 1) hash)) null) { // 如果数组该位置为空 // 用一次 CAS 操作将这个新值放入其中即可这个 put 操作差不多就结束了可以拉到最后面了 // 如果 CAS 失败那就是有并发操作进到下一个循环就好了 if(casTabAt(tab, i, null, newNodeK,V(hash, key, value, null))) break; // no lock when adding to empty bin } // hash 居然可以等于 MOVED这个需要到后面才能看明白不过从名字上也能猜到肯定是因为在扩容 elseif ((fh f.hash) MOVED) // 帮助数据迁移这个等到看完数据迁移部分的介绍后再理解这个就很简单了 tab helpTransfer(tab, f); else{ // 到这里就是说f 是该位置的头结点而且不为空 V oldVal null; // 获取数组该位置的头结点的监视器锁 synchronized(f) { if(tabAt(tab, i) f) { if(fh 0) { // 头结点的 hash 值大于 0说明是链表 // 用于累加记录链表的长度 binCount 1; // 遍历链表 for(NodeK,V e f;; binCount) { K ek; // 如果发现了相等的 key判断是否要进行值覆盖然后也就可以 break 了 if(e.hash hash ((ek e.key) key || (ek ! null key.equals(ek)))) { oldVal e.val; if(!onlyIfAbsent) e.val value; break; } // 到了链表的最末端将这个新值放到链表的最后面 NodeK,V pred e; if((e e.next) null) { pred.next newNodeK,V(hash, key, value,null); break; } } } elseif (f instanceofTreeBin) { // 红黑树 NodeK,V p; binCount 2; // 调用红黑树的插值方法插入新节点 if((p ((TreeBinK,V)f).putTreeVal(hash, key, value)) ! null) { oldVal p.val; if(!onlyIfAbsent) p.val value; } } } } // binCount ! 0 说明上面在做链表操作 if(binCount ! 0) { // 判断是否要将链表转换为红黑树临界值和 HashMap 一样也是 8 if(binCount TREEIFY_THRESHOLD) // 这个方法和 HashMap 中稍微有一点点不同那就是它不是一定会进行红黑树转换 // 如果当前数组的长度小于 64那么会选择进行数组扩容而不是转换为红黑树 // 具体源码我们就不看了扩容部分后面说 treeifyBin(tab, i); if(oldVal ! null) returnoldVal; break; } } } // addCount(1L, binCount); returnnull;}put 的主流程看完了但是至少留下了几个问题第一个是初始化第二个是扩容第三个是帮助数据迁移这些我们都会在后面进行一一介绍。
初始化数组initTable
这个比较简单主要就是初始化一个合适大小的数组然后会设置 sizeCtl。
初始化方法中的并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。
1234567891011121314151617181920212223242526272829privatefinal NodeK,V[] initTable() { NodeK,V[] tab; intsc; while((tab table) null|| tab.length 0) { // 初始化的功劳被其他线程抢去了 if((sc sizeCtl) 0) Thread.yield();// lost initialization race; just spin // CAS 一下将 sizeCtl 设置为 -1代表抢到了锁 elseif (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try{ if((tab table) null|| tab.length 0) { // DEFAULT_CAPACITY 默认初始容量是 16 intn (sc 0) ? sc : DEFAULT_CAPACITY; // 初始化数组长度为 16 或初始化时提供的长度 NodeK,V[] nt (NodeK,V[])newNode?,?[n]; // 将这个数组赋值给 tabletable 是 volatile 的 table tab nt; // 如果 n 为 16 的话那么这里 sc 12 // 其实就是 0.75 * n sc n - (n 2); } }finally{ // 设置 sizeCtl 为 sc我们就当是 12 吧 sizeCtl sc; } break; } } returntab;}链表转红黑树: treeifyBin
前面我们在 put 源码分析也说过treeifyBin 不一定就会进行红黑树转换也可能是仅仅做数组扩容。我们还是进行源码分析吧。
123456789101112131415161718192021222324252627282930313233privatefinal void treeifyBin(NodeK,V[] tab, intindex) { NodeK,V b; intn, sc; if(tab ! null) { // MIN_TREEIFY_CAPACITY 为 64 // 所以如果数组长度小于 64 的时候其实也就是 32 或者 16 或者更小的时候会进行数组扩容 if((n tab.length) MIN_TREEIFY_CAPACITY) // 后面我们再详细分析这个方法 tryPresize(n 1); // b 是头结点 elseif ((b tabAt(tab, index)) ! null b.hash 0) { // 加锁 synchronized(b) { if(tabAt(tab, index) b) { // 下面就是遍历链表建立一颗红黑树 TreeNodeK,V hd null, tl null; for(NodeK,V e b; e ! null; e e.next) { TreeNodeK,V p newTreeNodeK,V(e.hash, e.key, e.val, null,null); if((p.prev tl) null) hd p; else tl.next p; tl p; } // 将红黑树设置到数组相应位置中 setTabAt(tab, index, newTreeBinK,V(hd)); } } } }}扩容tryPresize
如果说 Java8 ConcurrentHashMap 的源码不简单那么说的就是扩容操作和迁移操作。
这个方法要完完全全看懂还需要看之后的 transfer 方法读者应该提前知道这点。
这里的扩容也是做翻倍扩容的扩容后数组容量为原来的 2 倍。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051// 首先要说明的是方法参数 size 传进来的时候就已经翻了倍了privatefinal void tryPresize(intsize) { // csize 的 1.5 倍再加 1再往上取最近的 2 的 n 次方。 intc (size (MAXIMUM_CAPACITY 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size (size 1) 1); intsc; while((sc sizeCtl) 0) { NodeK,V[] tab table; intn; // 这个 if 分支和之前说的初始化数组的代码基本上是一样的在这里我们可以不用管这块代码 if(tab null|| (n tab.length) 0) { n (sc c) ? sc : c; if(U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try{ if(table tab) { SuppressWarnings(unchecked) NodeK,V[] nt (NodeK,V[])newNode?,?[n]; table nt; sc n - (n 2);// 0.75 * n } }finally{ sizeCtl sc; } } } elseif (c sc || n MAXIMUM_CAPACITY) break; elseif (tab table) { // 我没看懂 rs 的真正含义是什么不过也关系不大 intrs resizeStamp(n); if(sc 0) { NodeK,V[] nt; if((sc RESIZE_STAMP_SHIFT) ! rs || sc rs 1|| sc rs MAX_RESIZERS || (nt nextTable) null|| transferIndex 0) break; // 2. 用 CAS 将 sizeCtl 加 1然后执行 transfer 方法 // 此时 nextTab 不为 null if(U.compareAndSwapInt(this, SIZECTL, sc, sc 1)) transfer(tab, nt); } // 1. 将 sizeCtl 设置为 (rs RESIZE_STAMP_SHIFT) 2) // 我是没看懂这个值真正的意义是什么不过可以计算出来的是结果是一个比较大的负数 // 调用 transfer 方法此时 nextTab 参数为 null elseif (U.compareAndSwapInt(this, SIZECTL, sc, (rs RESIZE_STAMP_SHIFT) 2)) transfer(tab,null); } }}这个方法的核心在于 sizeCtl 值的操作首先将其设置为一个负数然后执行 transfer(tab, null)再下一个循环将 sizeCtl 加 1并执行 transfer(tab, nt)之后可能是继续 sizeCtl 加 1并执行 transfer(tab, nt)。
所以可能的操作就是执行 1 次 transfer(tab, null) 多次 transfer(tab, nt)这里怎么结束循环的需要看完 transfer 源码才清楚。
数据迁移transfer
下面这个方法很点长将原来的 tab 数组的元素迁移到新的 nextTab 数组中。
虽然我们之前说的 tryPresize 方法中多次调用 transfer 不涉及多线程但是这个 transfer 方法可以在其他地方被调用典型地我们之前在说 put 方法的时候就说过了请往上看 put 方法是不是有个地方调用了 helpTransfer 方法helpTransfer 方法会调用 transfer 方法的。
此方法支持多线程执行外围调用此方法的时候会保证第一个发起数据迁移的线程nextTab 参数为 null之后再调用此方法的时候nextTab 不会为 null。
阅读源码之前先要理解并发操作的机制。原数组长度为 n所以我们有 n 个迁移任务让每个线程每次负责一个小任务是最简单的每做完一个任务再检测是否有其他没做完的任务帮助迁移就可以了而 Doug Lea 使用了一个 stride简单理解就是步长每个线程每次负责迁移其中的一部分如每次迁移 16 个小任务。所以我们就需要一个全局的调度者来安排哪个线程执行哪几个任务这个就是属性 transferIndex 的作用。
第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置然后从后往前的 stride 个任务属于第一个线程然后将 transferIndex 指向新的位置再往前的 stride 个任务属于第二个线程依此类推。当然这里说的第二个线程不是真的一定指代了第二个线程也可以是同一个线程这个读者应该能理解吧。其实就是将一个大的迁移任务分为了一个个任务包。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199privatefinal void transfer(NodeK,V[] tab, NodeK,V[] nextTab) { intn tab.length, stride; // stride 在单核下直接等于 n多核模式下为 (n3)/NCPU最小值是 16 // stride 可以理解为”步长“有 n 个位置是需要进行迁移的 // 将这 n 个任务分为多个任务包每个任务包有 stride 个任务 if((stride (NCPU 1) ? (n 3) / NCPU : n) MIN_TRANSFER_STRIDE) stride MIN_TRANSFER_STRIDE; // subdivide range // 如果 nextTab 为 null先进行一次初始化 // 前面我们说了外围会保证第一个发起迁移的线程调用此方法时参数 nextTab 为 null // 之后参与迁移的线程调用此方法时nextTab 不会为 null if(nextTab null) { try{ // 容量翻倍 NodeK,V[] nt (NodeK,V[])newNode?,?[n 1]; nextTab nt; }catch(Throwable ex) { // try to cope with OOME sizeCtl Integer.MAX_VALUE; return; } // nextTable 是 ConcurrentHashMap 中的属性 nextTable nextTab; // transferIndex 也是 ConcurrentHashMap 的属性用于控制迁移的位置 transferIndex n; } intnextn nextTab.length; // ForwardingNode 翻译过来就是正在被迁移的 Node // 这个构造方法会生成一个Nodekey、value 和 next 都为 null关键是 hash 为 MOVED // 后面我们会看到原数组中位置 i 处的节点完成迁移工作后 // 就会将位置 i 处设置为这个 ForwardingNode用来告诉其他线程该位置已经处理过了 // 所以它其实相当于是一个标志。 ForwardingNodeK,V fwd newForwardingNodeK,V(nextTab); // advance 指的是做完了一个位置的迁移工作可以准备做下一个位置的了 booleanadvance true; booleanfinishing false;// to ensure sweep before committing nextTab /* * 下面这个 for 循环最难理解的在前面而要看懂它们应该先看懂后面的然后再倒回来看 * */ // i 是位置索引bound 是边界注意是从后往前 for(inti 0, bound 0;;) { NodeK,V f; intfh; // 下面这个 while 真的是不好理解 // advance 为 true 表示可以进行下一个位置的迁移了 // 简单理解结局i 指向了 transferIndexbound 指向了 transferIndex-stride while(advance) { intnextIndex, nextBound; if(--i bound || finishing) advance false; // 将 transferIndex 值赋给 nextIndex // 这里 transferIndex 一旦小于等于 0说明原数组的所有位置都有相应的线程去处理了 elseif ((nextIndex transferIndex) 0) { i -1; advance false; } elseif (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound (nextIndex stride ? nextIndex - stride : 0))) { // 看括号中的代码nextBound 是这次迁移任务的边界注意是从后往前 bound nextBound; i nextIndex - 1; advance false; } } if(i 0|| i n || i n nextn) { intsc; if(finishing) { // 所有的迁移操作已经完成 nextTable null; // 将新的 nextTab 赋值给 table 属性完成迁移 table nextTab; // 重新计算 sizeCtln 是原数组长度所以 sizeCtl 得出的值将是新数组长度的 0.75 倍 sizeCtl (n 1) - (n 1); return; } // 之前我们说过sizeCtl 在迁移前会设置为 (rs RESIZE_STAMP_SHIFT) 2 // 然后每有一个线程参与迁移就会将 sizeCtl 加 1 // 这里使用 CAS 操作对 sizeCtl 进行减 1代表做完了属于自己的任务 if(U.compareAndSwapInt(this, SIZECTL, sc sizeCtl, sc - 1)) { // 任务结束方法退出 if((sc - 2) ! resizeStamp(n) RESIZE_STAMP_SHIFT) return; // 到这里说明 (sc - 2) resizeStamp(n) RESIZE_STAMP_SHIFT // 也就是说所有的迁移任务都做完了也就会进入到上面的 if(finishing){} 分支了 finishing advance true; i n; // recheck before commit } } // 如果位置 i 处是空的没有任何节点那么放入刚刚初始化的 ForwardingNode ”空节点“ elseif ((f tabAt(tab, i)) null) advance casTabAt(tab, i, null, fwd); // 该位置处是一个 ForwardingNode代表该位置已经迁移过了 elseif ((fh f.hash) MOVED) advance true;// already processed else{ // 对数组该位置处的结点加锁开始处理数组该位置处的迁移工作 synchronized(f) { if(tabAt(tab, i) f) { NodeK,V ln, hn; // 头结点的 hash 大于 0说明是链表的 Node 节点 if(fh 0) { // 下面这一块和 Java7 中的 ConcurrentHashMap 迁移是差不多的 // 需要将链表一分为二 // 找到原链表中的 lastRun然后 lastRun 及其之后的节点是一起进行迁移的 // lastRun 之前的节点需要进行克隆然后分到两个链表中 intrunBit fh n; NodeK,V lastRun f; for(NodeK,V p f.next; p ! null; p p.next) { intb 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) { intph p.hash; K pk p.key; V pv p.val; if((ph n) 0) ln newNodeK,V(ph, pk, pv, ln); else hn newNodeK,V(ph, pk, pv, hn); } // 其中的一个链表放在新数组的位置 i setTabAt(nextTab, i, ln); // 另一个链表放在新数组的位置 in setTabAt(nextTab, i n, hn); // 将原数组该位置处设置为 fwd代表该位置已经处理完毕 // 其他线程一旦看到该位置的 hash 值为 MOVED就不会进行迁移了 setTabAt(tab, i, fwd); // advance 设置为 true代表该位置已经迁移完毕 advance true; } elseif (f instanceofTreeBin) { // 红黑树的迁移 TreeBinK,V t (TreeBinK,V)f; TreeNodeK,V lo null, loTail null; TreeNodeK,V hi null, hiTail null; intlc 0, hc 0; for(NodeK,V e t.first; e ! null; e e.next) { inth e.hash; TreeNodeK,V p newTreeNodeK,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; } } // 如果一分为二后节点数少于 8那么将红黑树转换回链表 ln (lc UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! 0) ? newTreeBinK,V(lo) : t; hn (hc UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! 0) ? newTreeBinK,V(hi) : t; // 将 ln 放置在新数组的位置 i setTabAt(nextTab, i, ln); // 将 hn 放置在新数组的位置 in setTabAt(nextTab, i n, hn); // 将原数组该位置处设置为 fwd代表该位置已经处理完毕 // 其他线程一旦看到该位置的 hash 值为 MOVED就不会进行迁移了 setTabAt(tab, i, fwd); // advance 设置为 true代表该位置已经迁移完毕 advance true; } } } } }}说到底transfer 这个方法并没有实现所有的迁移任务每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作其他的需要由外围来控制。
这个时候再回去仔细看 tryPresize 方法可能就会更加清晰一些了。
get 过程分析
get 方法从来都是最简单的这里也不例外
计算 hash 值根据 hash 值找到数组对应位置: (n – 1) h根据该位置处结点性质进行相应查找如果该位置为 null那么直接返回 null 就可以了如果该位置处的节点刚好就是我们需要的返回该节点的值即可如果该位置节点的 hash 值小于 0说明正在扩容或者是红黑树后面我们再介绍 find 方法如果以上 3 条都不满足那就是链表进行遍历比对即可
123456789101112131415161718192021222324publicV get(Object key) { NodeK,V[] tab; NodeK,V e, p; intn, eh; K ek; inth spread(key.hashCode()); if((tab table) ! null (n tab.length) 0 (e tabAt(tab, (n - 1) h)) ! null) { // 判断头结点是否就是我们需要的节点 if((eh e.hash) h) { if((ek e.key) key || (ek ! null key.equals(ek))) returne.val; } // 如果头结点的 hash 小于 0说明 正在扩容或者该位置是红黑树 elseif (eh 0) // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k) return(p e.find(h, key)) ! null? p.val : null; // 遍历链表 while((e e.next) ! null) { if(e.hash h ((ek e.key) key || (ek ! null key.equals(ek)))) returne.val; } } returnnull;}简单说一句此方法的大部分内容都很简单只有正好碰到扩容的情况ForwardingNode.find(int h, Object k) 稍微复杂一些不过在了解了数据迁移的过程后这个也就不难了所以限于篇幅这里也不展开说了。
总结
其实也不是很难嘛虽然没有像之前的 AQS 和线程池一样一行一行源码进行分析但还是把所有初学者可能会糊涂的地方都进行了深入的介绍只要是稍微有点基础的读者应该是很容易就能看懂 HashMap 和 ConcurrentHashMap 源码了。
