HashCode为什么使用31作为乘数

1. 前言

HashMap是用来存储键值对的数据结构，是用哈希表来实现的，可以实现O(1)时间复杂度的插入和查找。哈希表的基本原理即通过计算key的哈希值将元素插入到指定位置，因此在分析HashMap源码之前需要先分析一下哈希值的计算过程。

查看String类的源码可以发现，它重写了hashcode方法：

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

可以看到String类的hashcode方法遍历字符串的每个字符做与31做乘积运算，公式如下：$s[0]^{n-1}+s[1]^{n-2}+…s[n-1]$，那这里为什么要使用31作为乘数呢？

stackoverflow中有一篇讨论文章Why does Java’s hashCode() in String use 31 as a multiplier? - Stack Overflow，其中有一个高赞回答：

Goodrich and Tamassia computed from over 50,000 English words (formed as the union of the word lists provided in two variants of Unix) that using the constants 31, 33, 37, 39, and 41 will produce fewer than 7 collisions in each case. This may be the reason that so many Java implementations choose such constants.

即计算超过50000个单词的hashcode，分别使用31，33，37，39作为乘数，计算碰撞结果。下面我们就来做这个实验，观察不同乘数的碰撞结果。

2. hashcode碰撞概率统计

2.1 计算hashcode碰撞概率

首先准备10万个单词：

1
2
3
4
5
1	a	"n.(A)As 或 A's  安(ampere(a) art.一;n.字母A /[军] Analog.Digital,模拟/数字 /(=account of) 帐上"
2	aaal	American Academy of Arts and Letters 美国艺术和文学学会
3	aachen	 亚琛[德意志联邦共和国西部城市]
4	aacs	Airways and Air Communications Service (美国)航路与航空通讯联络处
...

读取单词：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//读取每一个单词，并将单词保存在一个Set集合中。
public static Set<String> readWordList(String url) {
    Set<String> list = new HashSet<>();
    try {
        InputStreamReader isr = new InputStreamReader(new FileInputStream(url), StandardCharsets.UTF_8);
        BufferedReader br = new BufferedReader(isr);
        String line = "";
        while ((line = br.readLine()) != null) {
            String[] ss = line.split("\t");
            list.add(ss[1]);
        }
        br.close();
        isr.close();
    } catch (Exception ignore) {
        return null;
    }
    return list;
}

hashcode函数：

1
2
3
4
5
6
7
public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = multiplier * hash + str.charAt(i);
    }
    return hash;
}

计算hash碰撞概率：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//计算hash碰撞概率
private static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashCodeList) {
    int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
    int minHash = hashCodeList.stream().min(Integer::compareTo).get();
	//将hashcode去重，计算重复元素的比例
    int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
    double collisionRate = (collisionCount * 1.0) / hashCodeList.size();

    return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
}

//计算不同乘数的hash碰撞概率
public static List<RateInfo> collisionRateList(Set<String> strList, Integer... multipliers) {
    List<RateInfo> rateInfoList = new ArrayList<>();
    for (Integer multiplier : multipliers) {
        List<Integer> hashCodeList = new ArrayList<>();
        for (String str : strList) {
            Integer hashCode = hashCode(str, multiplier);
            hashCodeList.add(hashCode);
        }
        rateInfoList.add(hashCollisionRate(multiplier, hashCodeList));
    }
    return rateInfoList;
}

这里RateInfo为自定义类：

1
2
3
4
5
6
7
public class RateInfo {
    private int maxHash;            // 最大Hash
    private int minHash;            // 最小Hash
    private int multiplier;         // hash计算乘机因子
    private int collisionCount;     // 碰撞数
    private double collisionRate;   // 碰撞比率
}

2.2 单元测试

编写单元测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private Set<String> words;

@Before
public void before() {
    "abc".hashCode();
    // 读取文件，103976个英语单词库.txt
    words = FileUtil.readWordList("103976个英语单词库.txt");
}

@Test
public void test_collisionRate() {
    System.out.println("单词数量：" + words.size());
    List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
    for (RateInfo rate : rateInfoList) {
        System.out.println(String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
    }
}

测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
单词数量：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%

根据不同乘数的碰撞概率绘制图像如下：

image-20240901161440223

根据结果可以看出，乘数为2、3、5、7、17、32时，碰撞概率都较大，乘数为31、33、39、41、199时，碰撞概率较小，但是乘数较大时，hashcode也会溢出，导致丢失信息。

3. hashcode散列分布

除了计算不同乘数下的hashcode碰撞概率，还需要计算hashcode的分布，只有当hashcode分布均匀时，才能减少碰撞。

为了计算hashcode的散列分布，可以将int的取值范围2^64分成64份，统计每个范围的hashcode数量即可。

3.1 哈希值分段存放

计算每个区间的hashcode数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static Map<Integer, Integer> hashArea(List<Integer> hashCodeList) {
    Map<Integer, Integer> statistics = new LinkedHashMap<>();
    int start = 0;
    for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
        long min = i;
        long max = min + 67108864;
        // 筛选出每个区间的哈希值数量
        int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
        statistics.put(start++, num);
    }
    return statistics;
}

public static Map<Integer, Integer> hashArea(Set<String> strList, Integer multiplier){
    List<Integer> hashCodeList = new ArrayList<>();
    for (String str : strList) {
        Integer hashCode = hashCode(str, multiplier);
        hashCodeList.add(hashCode);
    }
    return hashArea(hashCodeList);
}

3.2 单元测试

1
2
3
4
5
6
7
8
@Test
public void test_hashArea() {
    System.out.println(HashCode.hashArea(words, 2).values());
    System.out.println(HashCode.hashArea(words, 7).values());
    System.out.println(HashCode.hashArea(words, 31).values());
    System.out.println(HashCode.hashArea(words, 32).values());
    System.out.println(HashCode.hashArea(words, 199).values());
}

上面计算了不同乘数在每个区间的hashcode数量，绘制图像如下：

可以看到乘数为2、7、32时，hashcode分布都不是很均匀，乘数为31、199时分布较均匀，只有部分区间包含较多元素，但是使用199作为乘数会导致数据溢出，丢失信息，不能选择，因此选择31作为乘数是比较适合的。

4. 总结

本文主要分析了String类中的hashcode为什么使用31作为乘数，通过使用不同的乘数计算hashcode，统计hashcode的碰撞概率和散列分布情况，得出结论：使用31作为乘数时，hashcode的碰撞概率较小，分布区间较均匀，并且hashcode的数据范围较小，不易产生溢出和数据丢失问题。

数据结构与算法
#Java
HashCode为什么使用31作为乘数
http://caohuisheng.github.io/2024/09/01/HashMap源码分析/
Author
John Doe
Posted on
September 1, 2024
Licensed under