HashCode 为什么使用 31 作为乘数？

为什么java的hashcode的选用31次方？

以下是java源码部分

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;
}

我们自己编写测试方法

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;
}

通过上万个单词表，分别设置不同的次方进行验证

//定义次方数组
List<Integer> multipliers = new ArrayList<>(List.of(2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199));

//遍历次方
for (Integer ints : multipliers) {
    List<Integer> ins = new ArrayList<>();
    for (String work : words) {
        //计算哈希数值
        Integer integer = HashCode.hashCode(work, ints);

        //添加当前哈希数值
        ins.add(integer);
    }
    //获取去重数量
    long distinctCount = ins.stream().distinct().count();

    //碰撞数量 = 单词数量 - 去重数量
    Long collisionCount = words.size() - distinctCount;

    //碰撞概率
    Double rateVal = collisionCount * 1.0 / words.size() * 100;

    System.out.println(String.format("乘数 = %4d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", ints, collisionCount, rateVal));
}

乘数 =    2, 碰撞数量 = 60382, 碰撞概率 = 58.0730%
乘数 =    3, 碰撞数量 = 24300, 碰撞概率 = 23.3708%
乘数 =    5, 碰撞数量 =  7994, 碰撞概率 = 7.6883%
乘数 =    7, 碰撞数量 =  3826, 碰撞概率 = 3.6797%
乘数 =   17, 碰撞数量 =   576, 碰撞概率 = 0.5540%
乘数 =   31, 碰撞数量 =     2, 碰撞概率 = 0.0019%
乘数 =   32, 碰撞数量 = 34947, 碰撞概率 = 33.6106%
乘数 =   33, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =   39, 碰撞数量 =     0, 碰撞概率 = 0.0000%
乘数 =   41, 碰撞数量 =     1, 碰撞概率 = 0.0010%
乘数 =  199, 碰撞数量 =     0, 碰撞概率 = 0.0000%

以上就可以得出结论31次方的碰撞概率较为稳定，并且次方值较小

以下是哈希值分段存放验证代码

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);
}

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());

输出结果

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 103910, 34, 0, 18, 0, 0, 7, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0]
[310, 364, 284, 292, 393, 506, 656, 460, 451, 410, 441, 522, 485, 458, 725, 559, 391, 493, 319, 308, 479, 469, 454, 354, 491, 486, 361, 425, 347, 442, 245, 317, 38397, 15253, 286, 371, 869, 1509, 2012, 1049, 1186, 2890, 7992, 6821, 975, 1061, 1467, 1130, 1350, 1200, 482, 291, 319, 301, 241, 245, 324, 239, 260, 272, 433, 317, 266, 471]
[1292, 1065, 1197, 1148, 1217, 978, 1157, 1157, 1203, 1099, 1737, 3011, 2235, 2160, 1612, 2443, 2004, 1941, 3268, 2047, 1792, 1615, 1257, 1316, 1350, 1297, 1234, 1698, 1318, 1137, 1217, 1385, 8237, 8404, 1214, 1205, 1199, 1174, 1092, 1203, 1472, 1047, 1125, 1264, 1317, 1075, 1527, 1231, 1552, 1041, 1201, 1085, 1258, 1153, 1255, 1223, 1289, 1084, 1008, 1440, 1230, 1400, 1107, 1277]
[0, 0, 1607, 1044, 1614, 1559, 1135, 1575, 1664, 2360, 1733, 2642, 1305, 301, 195, 0, 0, 0, 3653, 1745, 3973, 2144, 2987, 1750, 1090, 3674, 2153, 2471, 1390, 391, 579, 0, 6948, 7109, 2489, 2931, 1340, 980, 1016, 2407, 5064, 2291, 3314, 4285, 1138, 351, 658, 0, 0, 0, 2142, 988, 2709, 485, 1919, 587, 547, 2290, 612, 1555, 870, 57, 160, 0]
[1415, 1455, 1617, 1642, 1491, 1418, 1506, 1663, 1694, 1594, 1450, 1428, 1462, 1545, 1693, 1566, 1354, 1413, 1495, 1720, 1648, 1641, 1473, 1386, 1401, 1468, 1548, 1518, 1342, 1409, 1561, 1656, 4110, 1423, 1319, 1327, 1404, 1639, 1579, 1389, 1406, 1452, 1613, 3019, 3373, 3030, 1748, 1471, 1490, 1469, 1457, 1396, 1457, 1644, 1754, 1624, 1503, 1498, 1304, 1507, 1458, 1501, 1486, 1454]

哈希分散也较为分布