HashMap为什么要扰动函数？|Java刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目：HashMap为什么要扰动函数？

书接上回，上次写的简单HashMap存在哪些问题？？？ 严格意义不算HashMap 只算是一种散列数据结构

1. 这里所有的元素存放都需要获取一个索引位置，而如果元素的位置不够散列碰撞严重，那么就失去了散列表存放的意义，没有达到预期的性

2. 这里所有的元素存放都需要获取一个索引位置，而如果元素的位置不够散列碰撞严重，那么就失去了散列表存放的意义，没有达到预期的性能。

3. 在获取索引 ID 的计算公式中，需要数组长度是 2 的倍数，那么怎么进行初始化这个数组大小。

4. 数组越小碰撞的越大，数组越大碰撞的越小，时间与空间如何取舍。4. 目前存放 7 个元素，已经有两个位置都存放了 2 个字符串，那么链表越来越长怎么优化。

5. 随着元素的不断添加，数组长度不足扩容时，怎么把原有的元素，拆分到新的位置上去。

以上这些问题可以归纳为；扰动函数、初始化容量、负载因子、扩容方法以及链表和
红黑树转换的使用等。

本章分析的内容为扰动函数！

二、扰动函数是什么？

在 HashMap 存放元素时候有这样一段代码来处理哈希值，这是 java 8 的散列值
扰动函数，用于优化散列效果；

1.7版本

final int hash(Object k) {
    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);
}
复制代码

1.8版本

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

1.8版本对hash方法进行了精简，可能是因为做多了离散分布提升不明显，还是为了效率考虑，进行了缩减。这里我们就不去深度研究具体做了哪些

三、为什么使用扰动函数？

理论上来说字符串的 hashCode是一个 int 类型值，那可以直接作为数组下标了，且肯定不会出现碰撞
但hashCode的取值范围在[-2147483648, 2147483647]，在32以上编译器为 -2^31 到 2^31-1，java采用的是2进制补码机制，第一位符号位，最大值为0x7FFFFFFF，即（2147483647）也就是int的最大值

将近 40 亿的长度，谁也不能把数组初始化的这么大，内存也是放不下的。

默认初始化的 Map 大小是 16 个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4，
所以获取的 Hash 值并不能直接作为下标使用，需要与数组长度进行取模运算得到一个下标值，也就是上篇文章的例子

那么，hashMap 源码这里不只是直接获取哈希值，还进行了一次扰动计算，(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。计算方式如下图；

说白了，使用扰动函数就是为了增加随机性，让数据元素更加均衡的散列，减少碰撞。

四、实验验证扰动函数

扰动函数使用了哈希值的高半区和低半区做异或，混合原始哈希码的高位和低位，以此来加大低位区的随机性。
但看不到实验数据的话，这终究是一段理论，具体这段哈希值真的被增加了随机性没有，并不知道。所以这里我们要做一个实验，这个实验是这样做；

1. 选取 10 万个单词词库

2. 定义 128 位长度的数组格子

3. 分别计算在扰动和不扰动下，10 万单词的下标分配到 128 个格子的数量

4. 统计各个格子数量，生成波动曲线。如果扰动函数下的波动曲线相对更平稳，那么证明扰动函数有效果。

1.扰动代码测试

扰动函数对比方法

public class Disturb {
    //disturbHashIdx 扰动函数下，下标值计算
    public static int disturbHashIdx(String key, int size) {
        return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
    }
    //hashIdx 非扰动函数下，下标值计算
    public static int hashIdx(String key, int size) {
        return (size - 1) & key.hashCode();
    } 
}
复制代码