jdk1.8中HashMap扰动函数及数组长度为什么是2的n次方介绍

jdk1.8中HashMap扰动函数及数组长度为什么是2的n次方介绍

文章目录

前言一、什么是二进制？二、计算机采用二进制的原因三.十进制与二进制相互转换

十进制转成二进制二进制转换为十进制 与、或、异或运算

按位异或按位与运算按位或运算 Jdk1.8中HashMap扰动函数Jdk1.8中HashMap数组的长度为什么是2的n次方

---

前言

在阅读jdk1.8中HashMap源码的过程中发现代码中使用了相关二进制位 *** 作的运算，本文先讲解了什么是二进制，及为什么计算机要使用二进制。然后讲解十进制与二进制如何进行转换，及与、或、异或运算 方式。最后介绍了了HashMap的扰动函数及数组的长度定义。

---

一、什么是二进制？

二进制（binary），发现者莱布尼茨，是在数学和数字电路中以2为基数的记数系统，是以2为基数代表系统的二进位制。这一系统中，通常用两个不同的符号0（代表零）和1（代表一）来表示 [1] 。数字电子电路中，逻辑门的实现直接应用了二进制，现代的计算机和依赖计算机的设备里都使用二进制。每个数字称为一个比特（Bit，Binary digit的缩写）。

二、计算机采用二进制的原因

二进位计数制仅用两个数码。0和1，所以，任何具有二个不同稳定状态的元件都可用来表示数的某一位。而在实际上具有两种明显稳定状态的元件很多。例如，氖灯的“亮”和“熄” ；开关的“开” 和 “关”；电压的“高” 和“低”、“正”和 “负”；纸带上的“有孔”和“无孔”；电路中的“有信号” 和 “无信号”； 磁性材料的南极和北极等等，不胜枚举。 利用这些截然不同的状态来代表数字，是很容易实现的。不仅如此，更重要的是两种截然不同的状态不单有量上的差别，而且是有质上的不同。这样就能大大提高机器的抗干扰能力，提高可靠性。而要找出一个能表示多于二种状态而且简单可靠的器件，就困难得多了 。 二进位计数制的四则运算规则十分简单。而且四则运算最后都可归结为加法运算和移位，这样，电子计算机中的运算器线路也变得十分简单了。不仅如此，线路简化了，速度也就可以提高。这也是十进位计数制所不能相比的 。 在电子计算机中采用二进制表示数可以节省设备。可 以从理论上证明，用三进位制最省设备，其次就是二进位制。但由于二进位制有包括三进位制在内的其他进位制所没有的优点，所以大多数电子计算机还是采用二进制。此外，由于二进制中只用二个符号 “ 0” 和“1”，因而可用布尔代数来分析和综合机器中的逻辑线路。 这为设计电子计算机线路提供了一个很有用的工具 。 二进制的符号“1”和“0”恰好与逻辑运算中的“对”（true)与“错”（false）对应，便于计算机进行逻辑运算。

三.十进制与二进制相互转换 十进制转成二进制

除二取余，然后倒序排列，高位补零。将正的十进制数除以二，得到的商再除以二，依次类推直到商为零或一时为止，然后在旁边标出各步的余数，最后倒着写出来，高位补零就行了。这里以15位例：

二进制转换为十进制 “按权展开求和”，该方法的具体步骤是先将二进制的数写成加权系数展开式，而后根据十进制的加法规则进行求和 。

规律：个位上的数字的次数是0，十位上的数字的次数是1，…，依次递增，而十分位的数字的次数是-1，百分位上数字的次数是-2，…，依次递减。

与、或、异或运算 按位异或 ^ 表示按位异或，也就是2个二进制码异或，2个数不同则结果为1，否则为0。例如：

按位与运算 &表示按位与运算，有0则0，全1则1 结果偏向于0 (变化的地方都变0了)。例如：

按位或运算 |表示按位或运算： 有1则1，全0则0 结果偏向于1（变化的地方都变1了）例如：

Jdk1.8中HashMap扰动函数 在jdk1.8中HashMap的hash计算方式如下

   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h = key.hashCode) ^ (h >>> 16) 这个是什么意思？h >>> 16 表示将hashCode的二进制码右移16位，右移16位后和hashCode做异或。举个例子，假如我们key传入的是229769141，由于整数的hashcode是它本身。229769141的二进制为（可以使用Integer.toBinaryString(229769141)方法）：1101 1011 0001 1111 1111 1011 0101，右移16位异或后的结果为：

• 为什么要用扰动函数？
右移16位正好为32bit的一半，自己的高半区和低半区做异或，是为了混合原始哈希吗的高位和低位，来加大低位的随机性，使值可以均匀的分布在数组中。而且混合后的低位掺杂了高位的部分特征，使高位的信息也被保留下来

Jdk1.8中HashMap数组的长度为什么是2的n次方

1. (n - 1) & hash ≈ hash % n ,因为2进制的运算速度远远高于取模，所以就使用了这种方式，所以要求为2的幂
2. 减少hash碰撞，使得添加的元素均匀分布在HashMap的每个位置上
我们在读取数据的时候使用了：(n - 1) & hash，n-1 表示map数组的长度减1，假设数组的长度位16，位与结果如下：

其实就是保留最后4位，将其他位都清零，再转换成10进制 0100就是4，也就是在 tab[4] 这个地方读取数据。我们可以得出如下结论：
当length=16时 下标运算结果取决于哈希值的低四位
当length=32时 下标运算结果取决于哈希值的低五位
当length=2的N次方， 下标运算结果取决于哈希值的低N位。
假设长度不是2的幂，长度位10。我们使用10101，01010，11010和10做与运算。第一个和第三个就发生了碰撞

假设数组的长度是16，2的4次方（a power of two），2的4次方-1 转换成二进制末尾都是1。利用这种方式来使得插入的数据尽量不会落在同一个地方，均匀分布在数组的各个位置。如下：

参考：
https://blog.csdn.net/supercmd/article/details/100042302
https://blog.csdn.net/weixin_33748818/article/details/91994025
https://blog.csdn.net/supercmd/article/details/100042302