什么是 HashCode

HashCode（哈希码）是计算机科学中的一个概念，它是由哈希函数（Hash Function）计算得出的一个固定长度的值。HashCode通常用于在数据结构和算法中，用来快速查找、比较和存储数据。

HashCode 最重要的两个特点

1. 唯一性：理论上，HashCode应该是唯一的，不同的对象应该有不同的哈希码。这是为了确保在哈希表等数据结构中，每个对象都可以被正确地映射到唯一的槽位，避免哈希碰撞。
2. 效率性：计算哈希码的过程应该是高效的，不应该占用过多的计算资源。通常，好的哈希函数应该在短时间内能够计算出哈希码。

String 的 HashCode 计算代码

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

上面是 HashCode 的计算代码,我们来具体列举一个例子

String str = "abc";
str.hashCode();
// 计算过程
// 设 h = 0;
// h = 31*h+97;
// h = 31*(31*h+97)+98;
// h = 31*(31*(31*h+97)+98)+99;
// 最终 hash 值就是 h

那具体为什么是31?

1. 31 是一个合适的质数,质数公共因子少,质数太小会分布不均,太大会出现数据丢失。
2. 31 是 2的n次方-1,乘法运算可以进行位运算 31 * i = (i << 5) - i。

实践

10w 单词不同乘数的碰撞

单词数量：103976
乘数 =    2, 最小Hash =          97, 最大Hash = 1842581979, 碰撞数量 = 60382, 碰撞概率 = 58.0730%
乘数 =    3, 最小Hash = -2147308825, 最大Hash = 2146995420, 碰撞数量 = 24300, 碰撞概率 = 23.3708%
乘数 =    5, 最小Hash = -2147091606, 最大Hash = 2147227581, 碰撞数量 =  7994, 碰撞概率 = 7.6883%
乘数 =    7, 最小Hash = -2147431389, 最大Hash = 2147226363, 碰撞数量 =  3826, 碰撞概率 = 3.6797%
乘数 =   17, 最小Hash = -2147238638, 最大Hash = 2147101452, 碰撞数量 =   576, 碰撞概率 = 0.5540%
乘数 =   31, 最小Hash = -2147461248, 最大Hash = 2147444544, 碰撞数量 =     2, 碰撞概率 = 0.0019%
乘数 =   32, 最小Hash = -2007883634, 最大Hash = 2074238226, 碰撞数量 = 34947, 碰撞概率 = 33.6106%
乘数 =   33, 最小Hash = -2147469046, 最大Hash = 2147378587, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =   39, 最小Hash = -2147463635, 最大Hash = 2147443239, 碰撞数量 =     0, 碰撞概率 = 0.0000%
乘数 =   41, 最小Hash = -2147423916, 最大Hash = 2147441721, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =  199, 最小Hash = -2147459902, 最大Hash = 2147480320, 碰撞数量 =     0, 碰撞概率 = 0.0000%

面经手册 · 第2篇《数据结构，HashCode为什么使用31作为乘数？》 | bugstack 虫洞栈