让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)

本文主要是介绍让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

分析HashMap的resize()即扩容方法的源码,会发现主要分两部分操作:

  1. 为创建新数组初始化新数组容量和新数组扩容阈值;
  2. 创建新数组后,需将数据从旧数组转移到新数组上来,旧数组上的数据会根据(e.hash & oldCap) 是否等于0,重新rehash计算其在新数组上的索引位置,分成2类:
    ① 等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low;
    ② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度,记为高位区链表hi开头high(具体推导过程,详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导》).
    具体,详见下述的源码解析:
    /*HashMap的resize()方法/
/*** Initializes or doubles table size.  If null, allocates in* accord with initial capacity target held in field threshold.
*初始化或者加倍数组长度.若未指定要扩的容量值,则按照字段threshold所持有的初始容量目标分配.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.
*另外,因为我们使用的数组长度是2的n次幂的格式,当扩容后,数组原来的每个桶中的元素要么保存在原位置,要么相比旧数组,扩容到新数组后,位置的偏移量为2的n次幂。** @return the table*/final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//旧数组int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧数组容量/长度int oldThr = threshold; //旧数组扩容阈值/临界值(旧数组容量*负载因子)int newCap, newThr = 0;//新数组容量及新数组扩容阈值if (oldCap > 0) {//如果旧数组容量>0if (oldCap >= MAXIMUM_CAPACITY) {//如果旧数组容量大于等于最大容量threshold = Integer.MAX_VALUE; //则直接修改旧数组扩容阈值为最大值return oldTab; //并返回旧数组容量,不再做其他操作}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//若旧数组容量小于最大容量且新数组容量扩大至旧数组容量的2倍后依旧小于最大容量,并且//旧数组容量大于等于默认的初始化容量16newThr = oldThr << 1; // double threshold //则将新数组扩容阈值扩大至旧数组扩容阈值的2倍}else if (oldThr > 0) // initial capacity was placed in threshold//若旧数组容量小于等于0,且旧数组扩容阈值大于0(当new HashMap(0)后再put时,会走到这里)newCap = oldThr; //则将旧数组扩容阈值赋给新数组容量else {// zero initial threshold signifies using defaults//若旧数组容量和旧数组扩容阈值均不大于0,说明数组需要初始化newCap = DEFAULT_INITIAL_CAPACITY; //将新数组容量设为默认初始化容量16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //将新数组扩容阈值设为默认负载因子0.75*默认初始化容量16=12}if (newThr == 0) {//经上述逻辑后新数组扩容阈值仍为0,说明新数组扩容阈值尚未处理过,但走到这里之前新数组容量已经被处理完了,所以需按照新数组容量*负载因子的公式重新计算float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);}threshold = newThr; //将新数组扩容阈值赋值给HashMap的扩容阈值字段@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //按照新数组容量创建新数组table = newTab; //将创建的新数组赋值给HashMap的数组字段if (oldTab != null) {//若旧数组不为null,则需要将旧数组中的数组迁移到新数组中,并将旧数组各位置置为null.for (int j = 0; j < oldCap; ++j) {//根据旧数组长度,循环遍历各数组索引下标Node<K,V> e;if ((e = oldTab[j]) != null) {//判断每个数组索引位置对应的链表的头节点是否为空,若为空则该索引位置无数据,就不需要接下来的操作,不为空才继续往下进行处理,将该链表的数据转移赋值给新数组oldTab[j] = null; //将旧数组该位置置为null,提醒gc回收if (e.next == null) //头节点无后续节点,说明只需将头节点移动到新数组newTab[e.hash & (newCap - 1)] = e; //根据新数组长度和该链表头节点已有的hash重新计算该链表头节点在新数组中的索引下标位置,并将头节点直接赋值给新数组的该索引下标。else if (e instanceof TreeNode) //判断链表头节点类型是否是红黑树((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //将树中的数据从旧数组移到新数组(此方法解读详见:《HashMap中红黑树TreeNode的split方法源码解读》)else { // preserve order//走到这里,说明链表头节点有后续节点,后面会保留原有链表的顺序进行新旧数组的数据转移
//旧数组的每个索引位置里的链表头节点转移到新数组后的索引位置是要重新rehash,重新计算的:根据(e.hash & oldCap) 是否等于0,分成2类:①等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low;②不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度,记为高位区链表hi开头high(具体推导过程,详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》)。
Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next; //用于循环递进链表(若链表上有多个节点),保持原链表的顺序if ((e.hash & oldCap) == 0) {//详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》:用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算,若(e.hash & oldCap)的结果为0,则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在旧数组的索引下标位置相同(处于同一条链表中的所有节点的hash值相同):(2oldCap -1) & e.hash=(oldCap -1) & e.hash.[注意:1.旧数组长度oldCap为2的n次幂;2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash;3.数据e的hash是根据e的key计算得到的,公式为(h=key.hashCode()) ^ (h>>>16)].if (loTail == null) //低位链表的末尾为null, 对于每个链表来说,说明是第一次走到这里,而且此处也只会走进来一次,因为后续会将非null的e赋值给loTail了。loHead = e; //说明e为低位链表头节点,并将其赋给代表低位链表头节点的loHead else//说明低位链表末尾不为null,说明至少处理过一次loTail了,即头节点肯定已经处理过了,下面应该去处理低位链表头节点的后续节点了loTail.next = e; //处理完低位链表头节点后,根据next=e.next和while((e=next)!=null),依次循环递进处理低位链表头节点的后续节点,将旧数组中的链表头节点的后续节点,追加到低位链表头节点loHead的next里。loTail=e; //将非null的e赋给loTail,首次走到这里时,loTail和loHead都指向e。}else {//详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》: 用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算,若(e.hash & oldCap)的结果不为0,则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在(旧数组的索引下标位置+旧数组长度)相等(处于同一条链表中的所有节点的hash值相同):(2oldCap -1) & e.hash=(oldCap -1) & e.hash+oldCap.[注意:1.旧数组长度oldCap为2的n次幂;2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash;3.数据e的hash是根据e的key计算得到的,公式为(h=key.hashCode()) ^ (h>>>16)].if (hiTail == null) //高位链表的末尾为null,对于每个链表来说,说明是第一次走到这里,而且此处也只会走进来一次,因为后续会将非null的赋值给hiTail了。hiHead = e; //说明e为高位链表头节点,并将其赋给代表高位链表头节点的hiTail else//说明高位链表末尾不为null,说明至少处理过一次hiTail了,即头节点肯定已经处理过了,下面应该去处理高位链表头节点的后续节点了hiTail.next = e; //处理完高位链表头节点后,根据next=e.next和while((e=next)!=null),依次循环递进处理高位链表头节点的后续节点,将旧数组中的链表头节点的后续节点,追加到高位链表头节点loHead的next里。hiTail=e; //将非null的e值赋给hiTail,首次走到这里时,hiTail和hiHead都指向e。}} while ((e = next) != null); //链表后续还有节点时,才继续处理,否则跳出循环if (loTail != null) {//低位链表尾节点不为空,说明旧数组向低位链表的数据转移已处理完,可做进一步处理loTail.next = null; //要保证低位链表尾节点的后续节点为null newTab[j] = loHead; //loHead代表了低位链表的头节点,也就代表了整条低位链表(其上已经将旧数组中j索引位置上的链表里的所有节点都转移到了该低位链表上),而从前面的处理逻辑可知,低位链表移动到新数组时的索引下标位置,与在旧数组上的索引位置相同,故直接将低位链表头节点赋给新数组的j索引下标位置即完成转移。}if (hiTail != null) {//高位链表尾节点不为空,说明旧数组向高位链表的数据转移已处理完,可做进一步处理hiTail.next = null; //要保证高位链表尾节点的后续节点为null newTab[j + oldCap] = hiHead; // hiHead代表了高位链表的头节点,也就代表了整条高位链表(其上已经要移动到新数组(j+oldCap)索引位置上的所有节点都转移到了高位链表上),而从前面的处理逻辑可知,高位链表移动到新数组时的索引下标位置,与在旧数组上的索引位置相差了一个旧数组长度oldCap,故直接将高位链表头节点赋给新数组的(j+oldCap)索引下标位置即完成转移。}}}}}return newTab; //返回处理完的新数组}

这篇关于让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988947

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置(JAVA_HOME和Path),并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk(需要登录Oracle账号,没有可以免费注册)下载完

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

SQL中如何添加数据(常见方法及示例)

《SQL中如何添加数据(常见方法及示例)》SQL全称为StructuredQueryLanguage,是一种用于管理关系数据库的标准编程语言,下面给大家介绍SQL中如何添加数据,感兴趣的朋友一起看看吧... 目录在mysql中,有多种方法可以添加数据。以下是一些常见的方法及其示例。1. 使用INSERT I