为什么哈希图拆分方法需要在loHead.treeify (选项卡)之前确定(hiHead！= Null)

哈希图拆分方法需要在loHead.treeify之前确定hiHead不为Null的原因是为了确保在进行哈希图拆分时，能够正确地将元素分配到新的哈希桶中。

在哈希图拆分过程中，首先会创建一个新的哈希桶，然后将原哈希桶中的元素重新分配到新的哈希桶中。这个过程需要保证原哈希桶中的元素能够正确地分配到新的哈希桶中，否则可能会导致元素分布不均匀，影响哈希表的性能。

在哈希图拆分方法中，loHead和hiHead分别表示原哈希桶中的低位链表和高位链表。loHead.treeify表示将低位链表转化为树形结构，而hiHead表示高位链表。在进行哈希图拆分时，需要先确定hiHead不为Null，即高位链表不为空，才能进行拆分操作。

这是因为在哈希图拆分过程中，会先将原哈希桶中的元素重新分配到新的哈希桶中，其中低位链表的元素会保持在原哈希桶中，而高位链表的元素会被移动到新的哈希桶中。如果hiHead为Null，即高位链表为空，那么就没有需要移动的元素，也就没有必要进行哈希图拆分操作。

因此，为了确保哈希图拆分的正确性和有效性，需要在loHead.treeify之前确定hiHead不为Null，以保证元素能够正确地分配到新的哈希桶中，从而保证哈希表的性能和稳定性。

腾讯云相关产品和产品介绍链接地址：

腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云云数据库 MySQL 版：https://cloud.tencent.com/product/cdb_mysql
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云人工智能（AI）：https://cloud.tencent.com/product/ai
腾讯云物联网（IoT）：https://cloud.tencent.com/product/iot
腾讯云移动开发（移动推送）：https://cloud.tencent.com/product/umeng
腾讯云区块链（BCS）：https://cloud.tencent.com/product/bcs
腾讯云元宇宙（Tencent XR）：https://cloud.tencent.com/product/xr

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

Java源码系列4——HashMap扩容时究竟对链表和红黑树做了什么?

= null; // 链表2存放在高位（原索引 + 旧数组长度） Node hiHead = null, hiTail = null; Node next; do { next...这波操作是不是很666，为什么 2 的整数幂 - 1可以作 & 操作可以代替求余计算，因为 2 的整数幂 - 1 的二进制比较特殊，就是一串 11111，与这串数字 1 作 & 操作，结果就是保留下原数字的低位...= null) // (else is already treeified) loHead.treeify(tab); } } // 树化高位链表...= null) hiHead.treeify(tab); } } } 从源码可以看出，红黑树的拆分和链表的逻辑基本一致，不同的地方在于，重新映射后...，会将红黑树拆分成两条链表，根据链表的长度，判断需不需要把链表重新进行树化。

8584 0

集合系列 Map（十二）：HashMap

0 : (h = key.hashCode()) ^ (h >>> 16); } 看这个方法的逻辑好像是通过位运算重新计算 hash，那么这里为什么要这样做呢？...为什么不直接用键的 hashCode 方法产生的 hash 呢？在上面的讲解我们知道，我们最终会用 n - 1 和 hash 进行与运算，就像下面这样。...remove HashMap 的删除操作并不复杂，仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。...initCapacity else if (oldThr > 0) newCap = oldThr; else { // 1.3 到这里，说明之前没有初始化...= null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead

4554 1

HashMap的扩容机制—resize()「建议收藏」

hash(key) : 0;//为什么要再次计算一下hash值呢？..., loTail = null; Node hiHead = null, hiTail = null; Node..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0;...= null) // (else is already treeified) loHead.treeify(tab); }...(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。 (4) JDK1.8引入红黑树大程度优化了HashMap的性能。

2932 0

HashMap 源码解析-终章

看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1..., loTail = null; // 存储索引位置为:“原索引位置”的节点 Node hiHead = null, hiTail = null...null, hiTail = null; // 存储索引位置为:“原索引+oldCap”的节点 int lc = 0, hc = 0; // 1.以调用此方法的节点开始，遍历整个红黑树节点...= null) // 4.4 以loHead为根节点, 构建新的红黑树 loHead.treeify(tab);...= null) // 5.4 以hiHead为根节点, 构建新的红黑树 hiHead.treeify(tab);

2762 0

结合面试详细分析 HashMap 源码

JDK版本数据结构 JDK1.7 数组+链表 JDK1.8 数组 + （链表红黑树） 2、树化与退化 1、为什么要用红黑树，为何一上来不树化，树化阈值为何是 8？...在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表 remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc...= null) // (else is already treeified) loHead.treeify(tab);...e 头插节点 a，a 的 next 指向了 b（之前 a.next 一直是 null），b 的 next 指向 a，死链已成当循环结束时，e 指向 next 也就是 null，因此第四次循环时会正常退出

1542 0

HashMap 源码详细分析（JDK1.8）

HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。...0 : (h = key.hashCode()) ^ (h >>> 16); } 看这个方法的逻辑好像是通过位运算重新计算 hash，那么这里为什么要这样做呢？...为什么不直接用键的 hashCode 方法产生的 hash 呢？大家先可以思考一下，我把答案写在下面。这样做有两个好处，我来简单解释一下。...对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。...= null) loHead.treeify(tab); } } // 与上面类似 if (hiHead !

1.9K24 0

HashMap JDK 1.8 后它改了什么？

链表部分对应上面 transfer 的代码： Node loHead = null, loTail = null; Node hiHead = null, hiTail = null...p = replacementTreeNode(e, null); if (tl == null) //确定树头节点 hd = p;...if (root == null) { //头回进入循环，确定头结点，为黑色 x.parent = null; x.red = false...= null); return null; } 由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。...= null) // (else is already treeified) loHead.treeify(tab); } } if

2592 0

HashMap 源码详细分析（JDK1.8）

3993 0

什么是HashMap容器

【2】jdk1.8 之前 HashMap 由数组 + 链表组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用...： Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; 反之如果是1.5倍，那么散落在的槽位就不确定了...= null; Node hiHead = null, hiTail = null; Node next..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0;...= null) // (else is already treeified) loHead.treeify(tab); } }

5103 0

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）

, loTail = null; Node hiHead = null, hiTail = null;..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0...= null) // (else is already treeified) loHead.treeify(tab); }...HashMap默认初始化长度为16，并且每次自动扩展或者是手动初始化容量时，为什么必须是2的次幂？为了数据的均匀分布，减少哈希碰撞。...因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。

3321 0

Java 集合深入理解（17）：HashMap 在 JDK 1.8 后新增的红黑树结构

TreeNode p = replacementTreeNode(e, null); if (tl == null) //确定树头节点...if (root == null) { //头回进入循环，确定头结点，为黑色 x.parent = null; x.red = false...= null); return null; } 由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0;...= null) // (else is already treeified) loHead.treeify(tab); }

1.2K7 0

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

JDK1.8之前，HashMap并没有采用红黑树，所以哈希桶上的链表过长时，就会有效率问题。.../** * 移除给定节点, 调用该方法时要确保节点存在....TreeNode loHead = null, loTail = null; TreeNode hiHead = null, hiTail = null;...= null) // (else is already treeified) loHead.treeify(tab); } } //判断upper...树是否为null if (hiHead !

7974 0

HashMap扩容流程

为什么扩容？...(int)ft : Integer.MAX_VALUE); } // 最后确定阈值 threshold = newThr; 待续...... } resize()方法的前半部分主要是对于新阈值和新容量的确定...Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do {...next = e.next; // 如果entry的哈希值高位为0，会被拆分到lo链表 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead...= e; else loTail.next = e; loTail = e; } else { // 如果entry的哈希值高位为1，会被拆分到hi链表 if (hiTail == null)

4.2K3 0

HashMap源码分析

, loTail = null; Node hiHead = null, hiTail = null; Node...= null) { hiTail.next = null; newTab[j + oldCap] = hiHead..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0; //...和链表差不多，都是遍历，然后记录拆分位置 for (TreeNode e = b, next; e !...= null) loHead.treeify(tab); } } if (hiHead !

3225 0

HashMap源码分析 - jdk8

put方法的核心方法，在调用putVal方法之前会先计算key的hash值。...确定key所在位置后，需要判断元素是否存在，如果存在则不为null，不存在为null。如果为红黑树结构，则调用红黑树的插入方法进行插入元素。..., loTail = null; Node hiHead = null, hiTail = null; Node..., loTail = null; //新数组位置的结点 TreeNode hiHead = null, hiTail = null; int lc = 0, hc =...= null) //老的红黑树结构被改变，重新转换为红黑树 loHead.treeify(tab); } }

4511 0

聊聊java中的哪些Map：（二）HashMap中的TreeNode

)x.next; //在使用之前将当前节点左右都置空 x.left = x.right = null; //判断root是否赋值，如果没有则将root指向..., loTail = null; TreeNode hiHead = null, hiTail = null; int lc = 0, hc = 0; //按next链表顺序遍历节点...= null) // (else is already treeified) loHead.treeify(tab); } } //高位数处理...= null) hiHead.treeify(tab); } } } 上面提到了这个地方对整个map中每个槽位的元素进行resize之后，会拆分为两部分...看完整个过程，忽然明白hashMap为什么初始大小为16。因为只要为16，这个两个位移计算就非常方便。这使得hashMap就很高效。 3.11 rotateRight 右旋操作。

1.2K2 0

面试官:JDK1.8 HashMap扩容rehash算法是如何优化的？

我们都知道HashMap扩容是通过resize来实现的，所以我们看看resize方法的实现 final Node[] resize() { Node[] oldTab..., loTail = null; Node hiHead = null, hiTail = null;...1）单个节点其实重新进行hash寻址算法，找到对应数组的下标，放上就行了 2）链表仔细阅读源码会发现，就是将之前的链表rehash之后重新拆分为了两个链表，一个链表rehash之后还是在当前的位置...index，另一个链表rehash之后的位置变成了index + oldCap，画个图理解一下至于为什么可以分为两个链表，这里说明一下。...所以在JDK1.8的rehash算法优化就是对原来的链表或者红黑树进行拆分成两部分，然后分别挂在原来数组的位置和数组的位置 + oldCap的位置，这样做就避免了大量的节点进行重新hash寻址算法和重新放到

6203 0

今日面试之HashMap考点

loadFactor 加载因子是哈希表在其容量自动增加之前可以达到多满的一种饱和度百分比，其衡量了一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。..., loTail = null; Node hiHead = null, hiTail = null; Node<K...这个设计非常赞，因为 hash 值本来就是随机性的，所以 hash 按位与上 newTable 得到的 0（扩容前的索引位置）和 1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈西冲突的元素再随机的分布到不同的索引去...其次，由于 JDK1.7 中发生哈西冲突时仅仅采用了链表结构存储冲突元素，所以扩容时仅仅是重新计算其存储位置而已，而 JDK1.8 中为了性能在同一索引处发生哈西冲突到一定程度时链表结构会转换为红黑数结构存储冲突元素...，故在扩容时如果当前索引中元素结构是红黑树且元素个数小于链表还原阈值（哈西冲突程度常量）时就会把树形结构缩小或直接还原为链表结构（其实现就是上面代码片段中的 split() 方法）。

5094 0

java集合介绍_java代码分析框架

六、HashMap 添加元素在之前获取下标的例子中，我们知道 put()方法依赖于 putVal()方法，事实上，包括 putAll()在内，所有添加元素的方法都需要依赖于 putVal()。...3.为什么key可以为null 我们回顾一下 hash()方法： (key == null) ?...= null && key.equals(k)); 因为可能存在哈希冲突，或者为 null 的 key，因此所以光判断哈希值是不够的，事实上，当我们试图添加或者找到一个 key 的时候，方法会根据三方面来确定一个唯一的...()算出来的值；比较 equlas()是否相等：Object.equlas()方法在不重写的时候，默认比较的是内存地址；比较 key 是否为 null； 为什么要重写equals和hashcode方法...equals和hashCode方法 HashMap 在get()和set()的时候都会通过 Object.equals() 和 Object.hashCode() 方法来确定唯一 key。

7703 0

HashMap 夺命 14 问！

哈喽，小伙伴们好。金三银四可能很多小伙伴都考虑换个环境，那么面试是少不了的，基础更加重要。...当溢出发生时，将所有溢出数据统一放到溢出区注意开放定址法和再哈希法的区别是开放定址法只能使用同一种 hash 函数进行再次 hash，再哈希法可以调用多种不同的 hash 函数进行再次 hash 04 为什么要在数组长度大于...只要两个元素的 key 计算的hash码值相同就会发生 hash 碰撞，jdk8 之前使用链表解决哈希碰撞，jdk8 之后使用链表+红黑树解决哈希碰撞 09 HashMap的put方法流程以 jdk8..., loTail = null; //高位链表，存放扩容之后的数组的下标位置，=原索引+扩容之前数组容量...，那么键对象正确的重写这两个方法是非常重要的，这些类很规范的重写了hashCode()以及equals()方法 12 为什么 Map 桶中节点个数超过 8 才转为红黑树？

3382 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

为什么哈希图拆分方法需要在loHead.treeify (选项卡)之前确定(hiHead！= Null)

相关·内容

Java源码系列4——HashMap扩容时究竟对链表和红黑树做了什么?

集合系列 Map（十二）：HashMap

HashMap的扩容机制—resize()「建议收藏」

HashMap 源码解析-终章

结合面试详细分析 HashMap 源码

HashMap 源码详细分析（JDK1.8）

HashMap JDK 1.8 后它改了什么？

HashMap 源码详细分析（JDK1.8）

什么是HashMap容器

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）

Java 集合深入理解（17）：HashMap 在 JDK 1.8 后新增的红黑树结构

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

HashMap扩容流程

HashMap源码分析

HashMap源码分析 - jdk8

聊聊java中的哪些Map：（二）HashMap中的TreeNode

面试官:JDK1.8 HashMap扩容rehash算法是如何优化的？

今日面试之HashMap考点

java集合介绍_java代码分析框架

HashMap 夺命 14 问！

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐