java7-8中的 HashMap和ConcurrentHashMap全解析_java_其他

<html xmlns="http://www.w3.org/1999/xhtml"><head><meta charset="utf-8"><meta name="generator" content="pdf2htmlEX"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/base.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/11906539/raw.css"><script src="https://csdnimg.cn/release/download_crawler_static/js/compatibility.min.js"></script><script src="https://csdnimg.cn/release/download_crawler_static/js/pdf2htmlEX.min.js"></script><script>try{pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});}catch(e){}</script><title></title></head><body><div id="sidebar" style="display: none"><div id="outline"></div></div><div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/11906539/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> 回首页 (/) 新的主题，右下角可以设置，欢迎大家提出建议。</div><div class="t m0 x2 h3 y2 ff2 fs1 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析</div><div class="t m0 x3 h2 y3 ff1 fs0 fc1 sc0 ls0 ws0">更新时间：2018-02-24</div><div class="t m0 x4 h2 y4 ff1 fs0 fc1 sc0 ls0 ws0">今天发一篇"水文"，可能很多读者都会表示不理解，不过我想把它作为并发序列文章中不可缺少的一块来介</div><div class="t m0 x4 h2 y5 ff1 fs0 fc1 sc0 ls0 ws0">绍。本来以为花不了多少时间的，不过最终还是投入了挺多时间来完成这篇文章的。</div><div class="t m0 x4 h2 y6 ff1 fs0 fc1 sc0 ls0 ws0">网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少，不过缺斤少两的文章比较多，所以才想自己</div><div class="t m0 x4 h2 y7 ff1 fs0 fc1 sc0 ls0 ws0">也写一篇，把细节说清楚说透，尤其像 Java8 中的 ConcurrentHashMap，大部分文章都说不清楚。终归是</div><div class="t m0 x4 h2 y8 ff1 fs0 fc1 sc0 ls0 ws0">希望能降低大家学习的成本，不希望大家到处找各种不是很靠谱的文章，看完一篇又一篇，可是还是模模糊</div><div class="t m0 x4 h2 y9 ff1 fs0 fc1 sc0 ls0 ws0">糊。</div><div class="t m0 x4 h2 ya ff1 fs0 fc1 sc0 ls0 ws0">阅读建议：四节基本上可以进行独立阅读，建议初学者可按照 Java7 HashMap -> Java7</div><div class="t m0 x4 h2 yb ff1 fs0 fc1 sc0 ls0 ws0">ConcurrentHashMap -> Java8 HashMap -> Java8 ConcurrentHashMap 顺序进行阅读，可适当降低阅读</div><div class="t m0 x4 h2 yc ff1 fs0 fc1 sc0 ls0 ws0">门槛。</div><div class="t m0 x4 h2 yd ff1 fs0 fc1 sc0 ls0 ws0">阅读前提：本文分析的是源码，所以至少读者要熟悉它们的接口使用，同时，对于并发，读者至少要知道</div><div class="t m0 x4 h2 ye ff1 fs0 fc1 sc0 ls0 ws0">CAS、ReentrantLock、UNSAFE 操作这几个基本的知识，文中不会对这些知识进行介绍。Java8 用到了红黑</div><div class="t m0 x4 h2 yf ff1 fs0 fc1 sc0 ls0 ws0">树，不过本文不会进行展开，感兴趣的读者请自行查找相关资料。</div><div class="t m0 x5 h2 y10 ff1 fs0 fc1 sc0 ls0 ws0">Java7 HashMap</div><div class="t m0 x6 h2 y11 ff1 fs0 fc1 sc0 ls0 ws0">put 过程分析</div><div class="t m0 x7 h2 y12 ff1 fs0 fc1 sc0 ls0 ws0">数组初始化</div><div class="t m0 x7 h2 y13 ff1 fs0 fc1 sc0 ls0 ws0">计算具体数组位置</div><div class="t m0 x7 h2 y14 ff1 fs0 fc1 sc0 ls0 ws0">添加节点到链表中</div><div class="t m0 x7 h2 y15 ff1 fs0 fc1 sc0 ls0 ws0">数组扩容</div><div class="t m0 x6 h2 y16 ff1 fs0 fc1 sc0 ls0 ws0">get 过程分析</div><div class="t m0 x5 h2 y17 ff1 fs0 fc1 sc0 ls0 ws0">Java7 ConcurrentHashMap</div><div class="t m0 x6 h2 y18 ff1 fs0 fc1 sc0 ls0 ws0">初始化</div><div class="t m0 x6 h2 y19 ff1 fs0 fc1 sc0 ls0 ws0">put 过程分析</div><div class="t m0 x7 h2 y1a ff1 fs0 fc1 sc0 ls0 ws0">初始化槽: ensureSegment</div><div class="t m0 x0 h4 y1b ff3 fs2 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析 https://javadoop.com/post/hashmap</div><div class="t m0 x0 h4 y1c ff3 fs2 fc1 sc0 ls0 ws0">第1页 共57页 2019/1/4 16:26</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div></body></html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/11906539/bg2.jpg"><div class="t m0 x7 h2 y1d ff1 fs0 fc1 sc0 ls0 ws0">获取写入锁: scanAndLockForPut</div><div class="t m0 x7 h2 y1e ff1 fs0 fc1 sc0 ls0 ws0">扩容: rehash</div><div class="t m0 x6 h2 y1f ff1 fs0 fc1 sc0 ls0 ws0">get 过程分析</div><div class="t m0 x6 h2 y20 ff1 fs0 fc1 sc0 ls0 ws0">并发问题分析</div><div class="t m0 x5 h2 y21 ff1 fs0 fc1 sc0 ls0 ws0">Java8 HashMap</div><div class="t m0 x6 h2 y22 ff1 fs0 fc1 sc0 ls0 ws0">put 过程分析</div><div class="t m0 x7 h2 y23 ff1 fs0 fc1 sc0 ls0 ws0">数组扩容</div><div class="t m0 x6 h2 y24 ff1 fs0 fc1 sc0 ls0 ws0">get 过程分析</div><div class="t m0 x5 h2 y25 ff1 fs0 fc1 sc0 ls0 ws0">Java8 ConcurrentHashMap</div><div class="t m0 x6 h2 y26 ff1 fs0 fc1 sc0 ls0 ws0">初始化</div><div class="t m0 x6 h2 y27 ff1 fs0 fc1 sc0 ls0 ws0">put 过程分析</div><div class="t m0 x7 h2 y28 ff1 fs0 fc1 sc0 ls0 ws0">初始化数组：initTable</div><div class="t m0 x7 h2 y29 ff1 fs0 fc1 sc0 ls0 ws0">链表转红黑树: treeifyBin</div><div class="t m0 x6 h2 y2a ff1 fs0 fc1 sc0 ls0 ws0">扩容：tryPresize</div><div class="t m0 x7 h2 y2b ff1 fs0 fc1 sc0 ls0 ws0">数据迁移：transfer</div><div class="t m0 x6 h2 y2c ff1 fs0 fc1 sc0 ls0 ws0">get 过程分析</div><div class="t m0 x5 h2 y2d ff1 fs0 fc1 sc0 ls0 ws0">总结</div><div class="t m0 x4 h5 y2e ff2 fs3 fc1 sc0 ls0 ws0">Java7 HashMap</div><div class="t m0 x4 h2 y2f ff1 fs0 fc1 sc0 ls0 ws0">HashMap 是最简单的，一来我们非常熟悉，二来就是它不支持并发操作，所以源码也非常简单。</div><div class="t m0 x4 h2 y30 ff1 fs0 fc1 sc0 ls0 ws0">首先，我们用下面这张图来介绍 HashMap 的结构。</div><div class="t m0 x0 h4 y1b ff3 fs2 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析 https://javadoop.com/post/hashmap</div><div class="t m0 x0 h4 y1c ff3 fs2 fc1 sc0 ls0 ws0">第2页 共57页 2019/1/4 16:26</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/11906539/bg3.jpg"><div class="t m0 x1 h2 y31 ff1 fs0 fc1 sc0 ls0 ws0">这个仅仅是示意图，因为没有考虑到数组要扩容的情况，具体的后面再说。</div><div class="t m0 x4 h2 y32 ff1 fs0 fc1 sc0 ls0 ws0">大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。</div><div class="t m0 x4 h2 y33 ff1 fs0 fc1 sc0 ls0 ws0">上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表</div><div class="t m0 x4 h2 y34 ff1 fs0 fc1 sc0 ls0 ws0">的 next。</div><div class="t m0 x4 h2 y35 ff1 fs0 fc1 sc0 ls0 ws0">capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。</div><div class="t m0 x4 h2 y36 ff1 fs0 fc1 sc0 ls0 ws0">loadFactor：负载因子，默认为 0.75。</div><div class="t m0 x4 h2 y37 ff1 fs0 fc1 sc0 ls0 ws0">threshold：扩容的阈值，等于 capacity * loadFactor</div><div class="t m0 x4 h3 y38 ff2 fs1 fc1 sc0 ls0 ws0">put 过程分析</div><div class="t m0 x4 h2 y39 ff1 fs0 fc1 sc0 ls0 ws0">还是比较简单的，跟着代码走一遍吧。</div><div class="t m0 x0 h4 y1b ff3 fs2 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析 https://javadoop.com/post/hashmap</div><div class="t m0 x0 h4 y1c ff3 fs2 fc1 sc0 ls0 ws0">第3页 共57页 2019/1/4 16:26</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/11906539/bg4.jpg"><div class="t m0 x8 h6 y3a ff4 fs4 fc1 sc0 ls0 ws0">public V put(K key, V value) {</div><div class="t m0 x9 h7 y3b ff4 fs4 fc1 sc0 ls0 ws0">// 当插入第一个元素的时候，需要先初始化数组大小</div><div class="t m0 x9 h6 y3c ff4 fs4 fc1 sc0 ls0 ws0">if (table == EMPTY_TABLE) {</div><div class="t m0 x8 h6 y3d ff4 fs4 fc1 sc0 ls0 ws0"> inflateTable(threshold);</div><div class="t m0 x8 h6 y3e ff4 fs4 fc1 sc0 ls0 ws0"> }</div><div class="t m0 x9 h7 y3f ff4 fs4 fc1 sc0 ls0 ws0">// 如果 key 为 null，感兴趣的可以往里看，最终会将这个 entry 放到 table[0] 中</div><div class="t m0 x9 h6 y40 ff4 fs4 fc1 sc0 ls0 ws0">if (key == null)</div><div class="t m0 xa h6 y41 ff4 fs4 fc1 sc0 ls0 ws0">return putForNullKey(value);</div><div class="t m0 x9 h7 y42 ff4 fs4 fc1 sc0 ls0 ws0">// 1. 求 key 的 hash 值</div><div class="t m0 x9 h6 y43 ff4 fs4 fc1 sc0 ls0 ws0">int hash = hash(key);</div><div class="t m0 x9 h7 y44 ff4 fs4 fc1 sc0 ls0 ws0">// 2. 找到对应的数组下标</div><div class="t m0 x9 h6 y45 ff4 fs4 fc1 sc0 ls0 ws0">int i = indexFor(hash, table.length);</div><div class="t m0 x9 h7 y46 ff4 fs4 fc1 sc0 ls0 ws0">// 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，</div><div class="t m0 x9 h7 y47 ff4 fs4 fc1 sc0 ls0 ws0">// 如果有，直接覆盖，put 方法返回旧值就结束了</div><div class="t m0 x9 h6 y48 ff4 fs4 fc1 sc0 ls0 ws0">for (Entry<K,V> e = table[i]; e != null; e = e.next) {</div><div class="t m0 x8 h6 y49 ff4 fs4 fc1 sc0 ls0 ws0"> Object k;</div><div class="t m0 xa h6 y4a ff4 fs4 fc1 sc0 ls0 ws0">if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {</div><div class="t m0 x8 h6 y4b ff4 fs4 fc1 sc0 ls0 ws0"> V oldValue = e.value;</div><div class="t m0 x8 h6 y4c ff4 fs4 fc1 sc0 ls0 ws0"> e.value = value;</div><div class="t m0 x8 h6 y4d ff4 fs4 fc1 sc0 ls0 ws0"> e.recordAccess(this);</div><div class="t m0 xb h6 y4e ff4 fs4 fc1 sc0 ls0 ws0">return oldValue;</div><div class="t m0 x8 h6 y4f ff4 fs4 fc1 sc0 ls0 ws0"> }</div><div class="t m0 x8 h6 y50 ff4 fs4 fc1 sc0 ls0 ws0"> }</div><div class="t m0 x8 h6 y51 ff4 fs4 fc1 sc0 ls0 ws0"> modCount++;</div><div class="t m0 x9 h7 y52 ff4 fs4 fc1 sc0 ls0 ws0">// 4. 不存在重复的 key，将此 entry 添加到链表中，细节后面说</div><div class="t m0 x8 h6 y53 ff4 fs4 fc1 sc0 ls0 ws0"> addEntry(hash, key, value, i);</div><div class="t m0 x9 h6 y54 ff4 fs4 fc1 sc0 ls0 ws0">return null;</div><div class="t m0 x8 h6 y55 ff4 fs4 fc1 sc0 ls0 ws0">}</div><div class="t m0 x4 h8 y56 ff2 fs5 fc1 sc0 ls0 ws0">数组初始化</div><div class="t m0 x4 h2 y57 ff1 fs0 fc1 sc0 ls0 ws0">在第一个元素插入 HashMap 的时候做一次数组的初始化，就是先确定初始的数组大小，并计算数组扩容的阈</div><div class="t m0 x4 h2 y58 ff1 fs0 fc1 sc0 ls0 ws0">值。</div><div class="t m0 x0 h4 y1b ff3 fs2 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析 https://javadoop.com/post/hashmap</div><div class="t m0 x0 h4 y1c ff3 fs2 fc1 sc0 ls0 ws0">第4页 共57页 2019/1/4 16:26</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/11906539/bg5.jpg"><div class="t m0 x8 h6 y3a ff4 fs4 fc1 sc0 ls0 ws0">private void inflateTable(int toSize) {</div><div class="t m0 x9 h7 y3b ff4 fs4 fc1 sc0 ls0 ws0">// 保证数组大小一定是 2 的 n 次方。</div><div class="t m0 x9 h7 y3c ff4 fs4 fc1 sc0 ls0 ws0">// 比如这样初始化：new HashMap(20)，那么处理成初始数组大小是 32</div><div class="t m0 x9 h6 y3d ff4 fs4 fc1 sc0 ls0 ws0">int capacity = roundUpToPowerOf2(toSize);</div><div class="t m0 x9 h7 y3e ff4 fs4 fc1 sc0 ls0 ws0">// 计算扩容阈值：capacity * loadFactor</div><div class="t m0 x8 h6 y3f ff4 fs4 fc1 sc0 ls0 ws0"> threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);</div><div class="t m0 x9 h7 y40 ff4 fs4 fc1 sc0 ls0 ws0">// 算是初始化数组吧</div><div class="t m0 x8 h6 y41 ff4 fs4 fc1 sc0 ls0 ws0"> table = new Entry[capacity];</div><div class="t m0 x8 h6 y42 ff4 fs4 fc1 sc0 ls0 ws0"> initHashSeedAsNeeded(capacity); //ignore</div><div class="t m0 x8 h6 y43 ff4 fs4 fc1 sc0 ls0 ws0">}</div><div class="t m0 x4 h2 y59 ff1 fs0 fc1 sc0 ls0 ws0">这里有一个将数组大小保持为 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都</div><div class="t m0 x4 h2 y5a ff1 fs0 fc1 sc0 ls0 ws0">有相应的要求，只不过实现的代码稍微有些不同，后面再看到的时候就知道了。</div><div class="t m0 x4 h8 y5b ff2 fs5 fc1 sc0 ls0 ws0">计算具体数组位置</div><div class="t m0 x4 h2 y5c ff1 fs0 fc1 sc0 ls0 ws0">这个简单，我们自己也能 YY 一个：使用 key 的 hash 值对数组长度进行取模就可以了。</div><div class="t m0 x8 h6 y5d ff4 fs4 fc1 sc0 ls0 ws0">static int indexFor(int hash, int length) {</div><div class="t m0 x9 h6 y5e ff4 fs4 fc1 sc0 ls0 ws0">// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";</div><div class="t m0 x9 h6 y5f ff4 fs4 fc1 sc0 ls0 ws0">return hash & (length-1);</div><div class="t m0 x8 h6 y60 ff4 fs4 fc1 sc0 ls0 ws0">}</div><div class="t m0 x4 h2 y61 ff1 fs0 fc1 sc0 ls0 ws0">这个方法很简单，简单说就是取 hash 值的低 n 位。如在数组长度为 32 的时候，其实取的就是 key 的 hash</div><div class="t m0 x4 h2 y62 ff1 fs0 fc1 sc0 ls0 ws0">值的低 5 位，作为它在数组中的下标位置。</div><div class="t m0 x4 h8 y63 ff2 fs5 fc1 sc0 ls0 ws0">添加节点到链表中</div><div class="t m0 x4 h2 y64 ff1 fs0 fc1 sc0 ls0 ws0">找到数组下标后，会先进行 key 判重，如果没有重复，就准备将新值放入到链表的表头。</div><div class="t m0 x0 h4 y1b ff3 fs2 fc1 sc0 ls0 ws0">Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析 https://javadoop.com/post/hashmap</div><div class="t m0 x0 h4 y1c ff3 fs2 fc1 sc0 ls0 ws0">第5页 共57页 2019/1/4 16:26</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>