HashMap的哈希/扰动函数的设计原理详解

创作时间:

作者:

@小白创作中心

HashMap的哈希/扰动函数的设计原理详解

引用

CSDN

https://m.blog.csdn.net/qq_52822387/article/details/138170089?spm=1001.2014.3001.5501

HashMap的哈希/扰动函数的设计
HashMap的哈希函数的作用是将key的hashCode值进行处理，得到最终的哈希值。当创建一个HashMap并使用put方法添加元素时，会用到这个方法。

我们查看put方法的实现：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看到hash(key)方法，下面，我们来看hash方法的具体实现：

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

下面是对该方法的一些解释：

参数key：需要计算哈希码的键值。
三目运算符：如果键值为null，则哈希码为0；否则，通过调用hashCode()方法获取键的哈希码，并将其与右移16位的哈希码进行异或运算。
^运算符：异或运算符是Java中的一种位运算符，用于将两个数的二进制位进行比较，如果相同则为0，不同则为1。
h >>> 16：将哈希码向右移动16位，相当于将原来的哈希码分成了两个16位的部分。最终返回的是经过异或运算后得到的哈希码值。

为什么要进行异或操作呢？因为对于hashCode的高位和低位，它们的分布是比较均匀的，如果只是简单地将它们加起来或者进行位运算，容易出现哈希冲突，而异或操作可以避免这个问题。

为什么能降低hash碰撞
因为：哈希函数是先拿到key的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

具体来看：key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为-2147 483648~2147483647，加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是，一个40亿长度的数组，内存是放不下的。假如HashMap数组的初始大小才16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算就是把散列值和数组长度 - 1 做一个 " 与 & " 操作，位运算比取余 % 运算要快。数组下标i如下：

p = tab[i = (n - 1) & hash]

这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为这样数组长度 - 1正好相当于一个“低位掩码”。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16 - 1 = 15。2进制表示是 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1111 。和某个散列值做与操作如下，结果就是截取了最低的四位值。