什么是 HashCode
HashCode（哈希码）是计算机科学中的一个概念，它是由哈希函数（Hash Function）计算得出的一个固定长度的值。HashCode通常用于在数据结构和算法中，用来快速查找、比较和存储数据。
HashCode 最重要的两个特点
唯一性：理论上，HashCode应该是唯一的，不同的对象应该有不同的哈希码。这是为了确保在哈希表等数据结构中，每个对象都可以被正确地映射到唯一的槽位，避免哈希碰撞。效率性：计算哈希码的过程应该是高效的，不应该占用过多的计算资源。通常，好的哈希函数应该在短时间内能够计算出哈希码。
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?
31 是一个合适的质数,质数公共因子少,质数太小会分布不均,太大会出现数据丢失。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 虫洞栈
本文章首发在 LearnKu.com 网站上。