HashMap中hash方法的作用（详解）

最新推荐文章于 2024-08-20 21:22:20 发布

用手写的从前

最新推荐文章于 2024-08-20 21:22:20 发布

阅读量561

点赞数 6

分类专栏： Java集合文章标签： java hashMap hash 集合 Map put方法

本文链接： https://blog.csdn.net/weixin_52394141/article/details/131987773

版权

Java集合专栏收录该内容

1 篇文章 0 订阅

订阅专栏

HashMap的hash方法用于计算key的哈希码，通过高位与低位异或增强随机性，减少碰撞。在计算数组下标时使用(&)代替%运算，前提是数组长度为2的n次方。该方法旨在优化存储分布，提高查找效率。

摘要由CSDN通过智能技术生成

首先，hash方法用来干什么？

在搞清楚原理之前，我们先站在巨人的肩膀浅浅了解一下hash方法的本质作用。

实质上，它的作用很朴素，就是用key值通过某种方式计算出一个hash码

而且这个hash码我们后面要用来计算key存在底层数组的下标，所以它必须保持一定的随机性，让计算出的数组元素下标更加均衡分布，减少碰撞，其实就是更大程度上的避免hash冲突。

注：保持随机性这一性质，只有在hash方法计算hash值这一步会有所体现，后面的取模运算只是单独的为了取到余数，与保证随机性没有关系

Hash方法是什么？

这里先直观的给出它的源码：

参数 key ：需要计算哈希码的键值。

key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16) ：这是一个三目运算符，看似复杂，其实很好理解。

逻辑就是：如果键值为null，则哈希码为 0 （依旧是说如果键为 null ，则存放在第一个位置）；否则，通过调用 hashCode() 方法获取键的哈希码，并将其与右移16 位的哈希码进行异或运算。

^ 运算符：异或运算符是 Java 中的一种位运算符，它用于将两个数的二进制位进行比较，如果相同则为 0，不同则为 1 。

>>> 16 ：将哈希码向右移动 16 位，相当于将原来的哈希码分成了两个 16 位的部分。最终返回的是经过异或运算后得到的哈希码值。

这短短的一行代码，汇聚不少计算机巨佬们的聪明才智。

理论上，哈希值（即hashcode方法返回的值）是一个 int 类型，大家都知道int型在java中占4个字节，即32位，范围从 -2147483648 到 2147483648 。前后加起来大概 40 亿的映射空间，只要哈希值映射得比较均匀松散，一般是不会出现哈希碰撞（哈希冲突会降低 HashMap 的效率）。

但问题是一个 40 亿长度的数组，内存是放不下的。 HashMap 扩容之前的数组初始大小只有 16 ，所以这个哈希值是不能直接拿来用的，用之前要和数组的长度做取模运算（前文提到的 (n - 1) & hash ），用得到的余数来访问数组下标才行。

对h ^ h>>>16如何理解？

上面的h其实就是我们调用key的hashcode()方法得到的hashcode值，我们将它右移16位（因为是int型，所以总共是32位），前面16位补0，然后我们让它与原本的hashcode值进行异或，因为异或的逻辑是不同为1，相当于就是前16位与后16位进行会进行一次异或，占据最终返回的hash的后16位，然后前16位与进行补位的16个0进行异或，占据最终返回的hash的前16位，得到最终return的hash码。

上面的流程可以参考下面的图进行思考：

这样大家可能会比较疑惑，这么翻来覆去是为了啥呀，其实都是为了一个：hash码的随机性，目的还是为了避免hash冲突，毕竟hash冲突会降低HashMap的效率。

综上所述， hash 方法是用来做哈希值优化的 ，把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。

计算好了hash值，然后我们怎么使用hash值计算下标？

我们使用（n - 1）& hash的方式获取下标；（其实就是取模运算）

大家可能会比较好奇，要进行取模运算难道不该用% 吗？为什么要用位运算 &呢？

这是因为%虽然确实可以实现，但是实际效率却还是不如&

并且我们的&能够取代%，是要有一个前提条件的：

只有当 b 为 2 的 n 次方时，才存在这样一个公式：a % b = a & (b-1)

我们可以对其进行一个验证：

我们来验证一下，假如 a = 14 ， b = 8 ，也就是 2^3 ， n=3 。

14%8 （余数为 6）， 14 的二进制为 1110 ， 8 的二进制 1000 ， 8-1 = 7 ， 7 的二进制为 0111 ， 1110&0111=0110 ，也就是 0 * 2^0+1 * 2^1+1 * 2^2+0 * 2 ^3=0+2+4+0=6 ， 14%8 刚好也等于 6 。

害，计算机就是这么讲道理，没办法

也就是说，只有数组长度是2的n次方时，使用&才会取余成功，这也是为什么，我们对hashmap进行扩容时，必须是2倍扩容了

为什么会这么巧，刚好二者就相同了呢，这与一个低位掩码的概念有关，这里我们先不细讲。

顺着上一个问题的图，我们再看这个步骤进行理解：

知道了hash方法的原理以及并将其计算出来，我们还需要知道：

hash方法在哪里被用到？

1.首先当然是我们最经典的put方法，后面的putval会通过hash值来计算下标

2.其次是我们使用get方法获取元素时，会调用getNode方法，其中用到hash值

小结

hash 方法的主要作用是将 key 的 hashCode 值进行处理，得到最终的哈希值。由于 key 的hashCode 值是不确定的，可能会出现哈希冲突，因此需要将哈希值通过一定的算法映射到HashMap 的实际存储位置上。

hash 方法的原理是，先获取 key 对象的 hashCode 值，然后将其高位与低位进行异或操作，得到一个新的哈希值。为什么要进行异或操作呢？因为对于 hashCode 的高位和低位，它们的分布是比较均匀的，如果只是简单地将它们加起来或者进行位运算，容易出现哈希冲突，而异或操作可以避免这个问题。然后将新的哈希值取模（mod），得到一个实际的存储位置。这个取模操作的目的是将哈希值映射到桶（Bucket）的索引上，桶是 HashMap 中的一个数组，每个桶中会存储着一个链表（或者红黑树），装载哈希值相同的键值对（没有相同哈希值的话就只存储一个键值对）。

总的来说，HashMap 的 hash 方法就是将 key 对象的 hashCode 值进行处理，得到最终的哈希值，并通过一定的算法映射到实际的存储位置上。这个过程决定了 HashMap 内部键值对的查找效率。