HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导_Dylanu的博客-程序员秘密

技术标签： ThinkInProgramming Java 算法 java 链表 foundation 数据结构

PS:由于文档是我在本地编写好之后再复制过来的，有些文本格式没能完整的体现，故提供下述图片，供大家阅览，以便有更好的阅读体验：
在这里插入图片描述

HashMap在扩容时，需要先创建一个新数组,然后再将旧数组中的数据转移到新数组上来
此时，旧数组上的数据就会根据(e.hash & oldCap) 是否等于0这个算法,被很巧妙地分为2类:
① 等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记为低位区链表lo开头-low;
② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区链表hi开头high.
具体,详见下述的算法推导解析:
算法：
(e.hash & oldCap)=0
前提：
 e.hash代表的是旧数组中节点或元素或数据e的hash值，该hash值是根据key确定过的：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) ；
 oldCap为旧数组的数组长度，是2的n次幂的整数。即e.hash&2^n=0

推导过程1(e.hash & oldCap)=0：

因为oldCap是2的n次幂的整数,其二进制表达为1个1后面跟n个0：1000…0，若想要e.hash&oldCap的结果为0，则e.hash的二进制形式中与对应oldCap的二进制的1的位置一定为0，其他位置的可以随意，这样即可保证结果为0；
假设：
oldCap= 2 ^ 3 =8 = 1000
则e.hash可以是 0101

e.hash&oldCap 0000=0
3. (2oldCap -1)=2 ^ 4-1=01111，其二进制位数比oldCap多一位，但多的这一位是0,其余都是1(其低三位肯定也是1);(oldCap-1)=2 ^ 3-1=0111，其二进制位数与oldCap相同,且其低3位的值都是1。故(2oldCap-1)和(oldCap -1)两者与只有4位且首位为0的e.hash=0101计算时，其实只有低3位真正能影响计算结果，而两者的低3位相同，都是111；
4. 故在前提条件下，(2oldCap-1)和(oldCap -1)两者与e.hash进行&运算之后的结果一样：
(2oldCap -1)=2 ^ 4-1= 01111 (oldCap-1)=2 ^ 3-1= 0111
e.hash 0101 e.hash 0101

e.hash&oldCap 00101=5 e.hash&oldCap 0101=5
5. 而(oldCap -1) &e.hash恰巧代表的就是e元素在旧数组中的索引位置；
而(2oldCap -1) &e.hash则代表的就是e元素在旧数组长度扩容2倍后的新数组里的索引位置
6. 综上，可得出满足e.hash&oldCap=0的元素，其在新旧数组中的索引位置不变；

推导过程2(e.hash & oldCap)不等于0：

因为oldCap是2的n次幂的整数,其二进制表达为1个1后面跟n个0：1000…0，若想要e.hash&oldCap的结果不为0，则e.hash的二进制形式中与对应oldCap的二进制的1的位置一定不为0，其他位置的可以随意，这样即可保证结果不为0；
假设：
oldCap= 2 ^ 3 =8 = 1000
则e.hash可以是 1101

e.hash&oldCap 1000=13
3. (2oldCap -1)=2 ^ 4-1=01111,其二进制位数比oldCap多一位,但多的这一位是0,其余都是1(其低三位肯定也是1,其从左到右数的第4位为1);(oldCap-1)=2 ^ 3-1=0111,其二进制位数与oldCap相同,且其低3位的值都是1, 其从左到右数的第4位为0,。故(2oldCap-1)和(oldCap -1)两者与只有4位且首位为1的e.hash=1101计算时,其实也只有从左到右数的第4位(0)真正能影响计算结果,因为低3位完全一样都是1;
4. 故在前提条件下，(2oldCap-1)和(oldCap -1)两者与e.hash进行&运算后结果相差了oldCap：
(2oldCap -1)=2^4-1= 01111 ( oldCap - 1 ) =2 ^ 3-1= 0111
e.hash 1101 e.hash 1101

(2oldCap -1)& e.hash 01101=8+5 (2oldCap -1)&e.hash 0101=5
5. 而(oldCap -1) &e.hash恰巧代表的就是e元素在旧数组中的索引位置；
而(2oldCap -1) &e.hash则代表的就是e元素在旧数组长度扩容2倍后的新数组里的索引位置
6. 综上，可得出满足e.hash&oldCap不等于0的元素，其在新数组中的索引位置是其在旧数组中索引位置的基础上再加上旧数组长度个偏移量。

本文链接：https://blog.csdn.net/u010425839/article/details/106620440

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

2019年华为开发者大会_如何在2019年及以后成为自由开发者的品牌_cumian8165的博客-程序员秘密

2019年华为开发者大会The web development industry is booming. Web开发行业正在蓬勃发展。 This may be advantageous for freelancers, but it also has its negatives. 这对于自由职业者可能是有利的，但也有其负面影响。 What negatives? 什么负面因素？ When i...

如何正确理解《中医医院信息化建设基本规范》和《中医医院信息系统基本功能规范》_computersoftware的博客-程序员秘密

《中医医院信息化建设基本规范》（下称《建设规范》）和《中医医院信息系统基本功能规范》（下称《功能规范》）是国家中医药管理局2011年10月制定印发的，规范提出以医院管理和中医电子病历为重点，构建中医药特色鲜明、技术平台先进、服务管理规范、系统安全高效的现代化中医医院。《功能规范》主要分为基础功能与医院信息集成平台、临床服务部分和医院管理部分。《功能规范》指出，中医医院信息系

跟我来学小程序（一）项目目录和项目文件介绍_pages目录的作用_ShrMuscles的博客-程序员秘密

大家好，我是一个爱举铁的程序员Shr。本篇文件介绍小程序项目的目录和项目文件。源码地址：https://github.com/ShrMus/wechat_xcx/tree/master/demo_20180603 一、新建项目打开微信web开发者工具，选择小程序项目，由于没有新建过项目，打开之后是下图的界面，选择项目目录，填写注册之后获得的AppID，填写项目名...

Unity用键盘控制物体左右旋转前后移动的c#脚本_猿憨憨的博客-程序员秘密

using System.Collections;using System.Collections.Generic;using UnityEngine;public class CubeScript : MonoBehaviour {void Start () {}void Update () { float Hor = Input.Get

敌兵布阵（树状数组） HDU 1166_敌兵布阵(树状数组)【hdu1166】_SY_Pistachio的博客-程序员秘密

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 123593 Accepted Submission(s): 51789 Problem Description C国的死对头A国...