13518219792
循序渐进分析源码之 HashMap put 方法的执行流程（jdk 1.8 ）的示例分析，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
铁锋网站制作公司哪家好，找成都创新互联！从网页设计、网站建设、微信开发、APP开发、响应式网站建设等网站项目制作，到程序开发，运营维护。成都创新互联于2013年创立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联。
注意：这里不会讲红黑树是什么，以及如何具体实现。我们只需知道它长什么样子并了解它的好处即可。
为什么 在jdk1.8 中采用数组+链表/红黑树的数据结构存储数据？
当 Hash 冲突严重时，在数组上的链表会越来越长，此时就会会降低查询时的效率；时间复杂度为 O(N)。 引入红黑树之后查询效率直接提高到了 O(logn)。
引入红黑树后，HashMap 内部数据结构长什么样子？
什么时候会采用链表，什么时候用红黑树？
当链表的大小大于预设的阈值（8）时就要转换为红黑树
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; // 局部变量，指向容器
Node p; // 局部变量
int n, i;
// 1. 如果 HashMap 没有初始化,需要进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 根据计算出的元素所在数组中的位置，并判断目标位置是否为空
// 2.1 如果为空. new 一个新的 Node 放置在目标位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 2.2 如果不为空, 再分情况讨论
else {
Node e;
K k;
// 2.2.1 如果目标位置有值（有可能是红黑树的根节点，也有可能是链表的表头），就比较key 是否相同（相当于提前判断吧）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2.2.2 如果目标位置放的是一个红黑树，就按照红黑树的方式，写入数据
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 2.2.3 如果目标位置放置的是一个链表，就遍历整个链表。
else {
for (int binCount = 0; ; ++binCount) {
// 如果当前节点的下一个节点为空，就 new 一个新的节点，然后当前节点指向这个新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 对这个增加了一个节点的链表进行长度判断，如果长度大于阀值，就将链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果当前节点的下一个节点不为空，就要判断 key 是否相同，如果相同，就跳出循环。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 对 2.2.1 和 2.2.2 和 2.2.3 进行判断。判断成立表示要覆盖原有位置的元素。
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 下面是扩容代码，暂时忽略
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注创新互联行业资讯频道，感谢您对创新互联的支持。
