hashmap计算hashcode时为什么要把高位右移16位

蔚落 2023-01-13 09:00 10阅读 0赞

**写在前面：**

1、如有错误请看官斧正。

2、建议把例子复制出去，自己用各种位运算算一下，然后也像我这样把异同处标出来，这样能在自己计算的过程中有更深的领悟。

# 一、hashmap计算hashcode时为什么要把高位右移16位 #

![20210417000527576.png][]

**有一个hashcode值的二进制形式**

key.hashcode()

**二进制：**0010-0101 1100-0100 0010-0101 1011-0110

**十进制：**633611702

上面这么写只是为了便于观察，并不遵循任何规范。

key.hashcode() >>> 16 （无符号右移16位）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70][]

这个地方是个人理解，不一定准确

亦或运算：不同为1，相同为0  异或运算能更好的保留各部分的特征(变化的地方01都有)

与运算：  有0则0，全1则1  结果偏向于0 (变化的地方都变0了)

或运算：  有1则1，全0则0  结果偏向于1（变化的地方都变1了）

# 二、再看hashmap是怎么取元素存放位置的 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70 1][]

可以看到在取元素存放位置时，1.7和1.8是用的同一方法，

都是hash^(n-1)【哈希值与上entry数组长度-1】

小白提问1：为啥要&entryLength-1呢

抛开上面提到的右移16位问题，你想想，一个对象取完hash值了，它得往entry数组里放吧，但是数组长度又是有限的，不可能一个萝卜一个坑。

**以默认初始长度为16为例**

想把一个编号大于16的数，在16个格子里找个位置放下，要是你自己设计会咋做呢(不能乱放)

绝大多数人都会选择取余法，就是：编号%格子数

小白举例： 17%16 = 1  放在第一个格子。

取余操作涉及到底层汇编和运算器电路设计，虽然我本科是电子信息的，但早就把知识还给老师了。

大家只要知道一个结论，就是取余运算没位运算快就行。

经过上面的科普，大家已经知道取余运算没位运算快了（手动狗头脸）。

本着安全第一，效率至上的原则就只能用位运算了。

**几个重要因素：**

1.  参与运算的值：hashcode、entry数组长度
2.  运算方式：位运算 (与&，或|，非~)
3.  预期结果：有规律可循，起码结果要和取余运算相同。
4.

那就开始设计吧~

(呃....我也没啥好的设计，还是分析下源码吧)

Entry长度-1 = 15；

15的二进制形式

0000-0000 0000-0000 0000-0000 0000-1111

十进制取余算法：

**633611702 % 16 = 6**

**633611702 % 32 = 22**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70 2][]

![20210417000803567.png][]

到这为止有三个问题继续解答

1.  ### 为啥数组长度要是2的n次幂？ ###
2.  ### 为啥entry数组长度要-1？ ###
3.  ### 为啥要右移16位进行亦或？ ###

这不是呼之欲出么，呼你妹啊，我到现在还都不知道为啥。

## 个人理解： ##

### 第一个问题 ###

1.  优化需要：hash & （length -1） 在结果上与 取余算法一致
2.  符合计算机思维，在计算机中跟数据相关的数值基本都是2的n次

如：MySQL页的大小为16kb

操作系统文件管理系统一次IO读取的数据大小同样为1页（4kb）相当于8个扇区（512bytes ）

### 第二个问题 ###

1.  数组长度不减1的话，低位都是0，与操作下低位都没法参与运算，而且还有结果越界的情况(如上面的反例)
2.  减1再与运算，可以使低位都参与运算，增加散列程度。

### 第三个问题 ###

请各位看官再回去搂一眼最上面的三个例子，右移后再亦或，高位和低位做了混合，在之后的hash & (length-1) 中高位就也参与进运算了，增加了散列程度。

[20210417000527576.png]: /images/20221022/6f627f89dbbd420c935fa71222457d42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70]: /images/20221022/12b90ee53b904665a0032ccf8e0d5195.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70 1]: /images/20221022/e3325d5920334341b9cd4c760f973457.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70 2]: /images/20221022/6758d3d3254543a6b01d845fa3568abd.png
[20210417000803567.png]: /images/20221022/9f91788ecb0c420399a5da02ef8c7b62.png