为什么String的hashCode选择 31 作为乘子?

选择31的原因

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

`s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]`

```假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]```

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: `31 * i == (i << 5) - i`. Modern VMs do this sort of optimization automatically.

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

实验及数据可视化

```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 code 冲突率，顺便分析一下 hash code 最大值和最小值，并输出
* @param multiplier
* @param hashs
*/
public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
int maxHash = hashs.stream().max(cp).get();
int minHash = hashs.stream().min(cp).get();

// 计算冲突数及冲突率
int uniqueHashNum = (int) hashs.stream().distinct().count();
int conflictNum = hashs.size() - uniqueHashNum;
double conflictRate = (conflictNum * 1.0) / hashs.size();

System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
}```

``` /**
* 将整个哈希空间等分成64份，统计每个空间内的哈希值数量
* @param hashs
*/
public static Map<Integer, Integer> partition(List<Integer> hashs) {
// step = 2^32 / 64 = 2^26
final int step = 67108864;
List<Integer> nums = new ArrayList<>();
Map<Integer, Integer> statistics = new LinkedHashMap<>();
int start = 0;
for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
final long min = i;
final long max = min + step;
int num = (int) hashs.parallelStream()
.filter(x -> x >= min && x < max).count();

statistics.put(start++, num);
}

// 为了防止计算出错，这里验证一下
int hashNum = nums.stream().reduce((x, y) -> x + y).get();
assert hashNum == hashs.size();

return statistics;
}```

3作为乘子时，算出的哈希值分布情况和2很像，只不过稍微好了那么一点点。从图中可以看出绝大部分的哈希值最终都落在了第32分区里，哈希值的分布性很差。这个也没啥用，拖出去枪毙5分钟吧。在看看数字17的情况怎么样：

（完）

0 条评论

• 面试被问：你会性能调优吗？

很多工作两三年的同行都跟我说，认为性能调优没什么用。刚工作的时候我也这样以为，但后来我才知道我当时想法多么的天真。

• SpringMVC与Struts2的区别与比较总结

1、Struts2是类级别的拦截， 一个类对应一个request上下文，SpringMVC是方法级别的拦截，一个方法对应一个request上下文，而方法同时又跟...

• 你真的会写二分查找吗？

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间...

• 科普：String hashCode 方法为什么选择数字31作为乘子

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...

• 科普：String hashCode 方法为什么选择数字31作为乘子

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...

• 面试官：你看过String的hashCode源码吗？

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...

• 科普：为什么 String hashCode 方法选择数字 31 作为乘子

某天，我在写代码的时候，无意中点开了 String 的 hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现...

• 为什么String的hashCode选择 31 作为乘子?

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...

• 面试官问：为什么String的hashCode选择 31 作为乘子?

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...

• 科普：为什么 String hashCode 方法选择数字 31 作为乘子

某天，我在写代码的时候，无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现，发现并不是很复杂。但是我从源码中发现了一...