HashMap如何确定key的存储位置

ゞ浴缸里的玫瑰 2023-10-13 23:37 26阅读 0赞

## 前言 ##

HashMap 作为 Java 中最常用的数据结构之一，用于存储和管理键值对。HashMap 基于哈希函数实现，能通过将 key 映射到特定的位置来实现快速存储、查找和删除数据。

HashMap 通过哈希函数确定 key 的存储位置这一映射过程，可使得 HashMap 在常数时间内完成插入、查找和删除操作，那么大家是否有了解过 HashMap 底层是如何使用哈希函数实现映射的呢？是如何高效确认 key 的存储位置的呢？

接下来将从源码角度分析以通俗易懂的方式向大家讲解一下 HashMap 如何确定 key 的存储位置的。

## 源码分析 ##

下面以 JDK 1.8 版本查看 HashMap 中最为常用的方法之一 put(K key, V value) 方法来看看 key 是如何确定存储位置的。

![image.png][]

![get_code_MmRkOTNjMjBkMjcxMTExYThkODQ5NjVmOGU1NmFhZjcsMTY5MDI1MjYxNDA1Mw][]

可以看到这里 key 会先通过 hash() 方法进行处理，进入 hash() 方法一探究竟。

## 扰动函数 hash() ##

> **JDK 1.8 中的 hash() 方法**

源码：

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

第一次看到 (h = key.hashCode()) ^ (h >>> 16) 这个式子可能有点不太好理解，我们分开来看：

*  可以看到式子中的 key.hashCode()，说明 HashMap 会将传入的 key 调用自身父类 Object 的 hashCode() 来进行哈希计算。
 *  然后将计算得到的哈希值 h 通过 h ^ (h >>> 16) 把高 16 位异或（^）低 16 位形成新的哈希值（hashCode() 方法返回的是 int 类型，也就是 32 位的数据）。

以 (h = "key".hashCode() ^ (h >>> 16)) 为例：

![key的存储位置.png][key_.png]

![get_code_NzU3ODIwYWM0OGQ3YWMwYzcyYjdhYjViOWVlYWNmZjYsMTY5MDI1MjYxNDA1Mw][]

将计算后的哈希值的高 16 位与低 16 位异或（^）的目的是为了通过把原本的低 16 位变成高 16 位和低 16 位的混合结果来使得低 16 位的随机性增大，这样在数组长度较小时，能起到保证高 16 位也参与到 Hash 计算中（这个在后面的取模操作中很好的体现），同时不会造成太大的性能开销。

JDK1.8 中 HashMap 的 hash() 方法也叫做扰动函数，其目的就是为了增加随机性，让数据元素更加均衡的散列，减少碰撞。

> **补充 JDK 1.7 的 hash() 方法**

java复制代码static int hash(int h) {
        int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12); 
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

JDK 1.7 中对 hashCode() 方法计算出的哈希值进行了四次扰动，所以在性能上要差一点。在 JDK 1.8 对其优化了扰动算法，使得计算的性能开销降低许多。这里也是 JDK 1.7 和 1.8 在计算 key 的存储位置上不同的地方了。

--------------------

## 取模操作 ##

在扰动函数 hash() 方法中可以看到返回的是一个 int 类型的值，即值的范围在 \[-2147483648, 2147483647\] 内，也就是说通过 hash() 映射到的位置可以在近 40 亿的长度的数组中。

但是实际上的内存不允许数组达到这么大，那么 HashMap 是如何将这个哈希值映射到数组中呢，相信读者们的第一反应一定是取模了，那么 HashMap 是怎样进行取模操作的呢，深入 putVal() 方法可以看到：

![image.png][image.png 1]

![get_code_YWJiZGMyODE3MzcxZTQ4NGMwYzhlNWQ2ODI4YTM2MmIsMTY5MDI1MjYxNDA1Mw][]

可以看到方法中通过 (n - 1) & hash 来确定最终 key 的存储位置，其实 (n - 1) & hash 这个式子就是取模操作，把通过 hash() 方法计算后得到的 hash 和当前 HashMap 的数组长度 - 1 进行与运算，相当于 hash % n，从而将其映射到数组特定的索引中。那么为什么 (n - 1) & hash 等价于 hash % n 呢？

其实这个等价关系有一个必要的前提，**这个前提就是 n 总是 2n2^n2n**，即数组的长度总是 2 的幂次方。当数组长度为 2 的幂次方时，可以保证 (n - 1) & hash 等价于 hash % n。

这是因为当 n 为 2 的幂次方时，n - 1 可以保证高位为 0，低位全 1 的效果，所以，按位与运算的结果相当于保留了 hash 的二进制表示的低位部分，而将高位部分全部置为 0，从而确保了 (n - 1) & hash 等价于 hash % n。

举个例子：上图可以知道 "key" 的哈希值计算结果为 0000 0000 0000 0001 1001 1110 0101 1110 即 106078，假设当前数组长度为 16 即 0001 0000，那么正常取模为 106078 % 16 = 14。

106078 & (16 - 1) 结果如图：

![image.png][image.png 2]

![get_code_MGM2Yjk1ODlmOWE3MmI5ZjVmYWNlZGIyYWFlYTU4YzUsMTY5MDI1MjYxNDA1Mw][]

至于为什么要使用位运算呢？这是因为取模运算的性能开销较大，替换成位运算可以得到更高的计算效率，提高性能。并且数组长度为 2 的幂次方可以起到散列均匀分布，减少哈希碰撞的可能性。

--------------------

## 总要有总结 ##

上面就是 HashMap 如何确定 key 的存储位置的整个源码分析过程了，过程可以分为三步：

*  将传入的参数 key 调用自身的方法 hashCode() 得到哈希值 h。
 *  根据哈希值 h 调用扰动函数 hash() 计算 h ^ (h >>> 16) 得到扰动后的哈希值 hash。
 *  根据哈希值 hash 取模操作 hash & (n - 1) 从而确定 key 的存储位置。

以上就是本篇文章的全部内容了。

[image.png]: https://img-blog.csdnimg.cn/img_convert/9983ab9e7d2ccde776ef0f9a88687607.webp?x-oss-process=image/format,png
[get_code_MmRkOTNjMjBkMjcxMTExYThkODQ5NjVmOGU1NmFhZjcsMTY5MDI1MjYxNDA1Mw]: https://mp.toutiao.com/mp/agw/article_material/open_image/get?code=MmRkOTNjMjBkMjcxMTExYThkODQ5NjVmOGU1NmFhZjcsMTY5MDI1MjYxNDA1Mw==
[key_.png]: https://img-blog.csdnimg.cn/img_convert/f5a8ff37f3bbe254b56afde73324e43c.webp?x-oss-process=image/format,png
[get_code_NzU3ODIwYWM0OGQ3YWMwYzcyYjdhYjViOWVlYWNmZjYsMTY5MDI1MjYxNDA1Mw]: https://mp.toutiao.com/mp/agw/article_material/open_image/get?code=NzU3ODIwYWM0OGQ3YWMwYzcyYjdhYjViOWVlYWNmZjYsMTY5MDI1MjYxNDA1Mw==
[image.png 1]: https://img-blog.csdnimg.cn/img_convert/b2ce83f88e7ea9b4d7130f3b6c719fea.webp?x-oss-process=image/format,png
[get_code_YWJiZGMyODE3MzcxZTQ4NGMwYzhlNWQ2ODI4YTM2MmIsMTY5MDI1MjYxNDA1Mw]: https://mp.toutiao.com/mp/agw/article_material/open_image/get?code=YWJiZGMyODE3MzcxZTQ4NGMwYzhlNWQ2ODI4YTM2MmIsMTY5MDI1MjYxNDA1Mw==
[image.png 2]: https://img-blog.csdnimg.cn/img_convert/2a39a301593085604efd137d8a88dd36.webp?x-oss-process=image/format,png
[get_code_MGM2Yjk1ODlmOWE3MmI5ZjVmYWNlZGIyYWFlYTU4YzUsMTY5MDI1MjYxNDA1Mw]: https://mp.toutiao.com/mp/agw/article_material/open_image/get?code=MGM2Yjk1ODlmOWE3MmI5ZjVmYWNlZGIyYWFlYTU4YzUsMTY5MDI1MjYxNDA1Mw==