likes
comments
collection
share

HashMap如何确定key的存储位置

作者站长头像
站长
· 阅读数 13

前言

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

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

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

源码分析

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

HashMap如何确定key的存储位置

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

扰动函数 hash()

JDK 1.8 中的 hash() 方法

源码：

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)) 为例：

HashMap如何确定key的存储位置

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

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

补充 JDK 1.7 的 hash() 方法

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() 方法可以看到：

HashMap如何确定key的存储位置

可以看到方法中通过 (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) 结果如图：

HashMap如何确定key的存储位置

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

总要有总结

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

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

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