String hashCode 方法为什么选择数字31作为乘子

选择数字31的原因在详细说明 String hashCode 方法选择数字31的作为乘子的原因之前我们先来看看 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; }上面的代码就是 String hashCode 方法的实现是不是很简单。实际上 hashCode 方法核心的计算逻辑只有三行也就是代码中的 for 循环。我们可以由上面的 for 循环推导出一个计算公式hashCode 方法注释中已经给出。如下s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]这里说明一下上面的 s 数组即源码中的 val 数组是 String 内部维护的一个 char 类型数组。这里我来简单推导一下这个公式假设 n3 i0 - h 31 * 0 val[0] i1 - h 31 * (31 * 0 val[0]) val[1] i2 - 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]上面的公式包括公式的推导并不是本文的重点大家了解了解即可。接下来来说说本文的重点即选择31的理由。从网上的资料来看一般有如下两个原因第一31是一个不大不小的质数是作为 hashCode 乘子的优选质数之一。另外一些相近的质数比如37、41、43等等也都是不错的选择。那么为啥偏偏选中了31呢请看第二个原因。第二、31可以被 JVM 优化31 * i (i 5) - i。上面两个原因中第一个需要解释一下第二个比较简单就不说了。下面我来解释第一个理由。一般在设计哈希算法时会选择一个特殊的质数。至于为啥选择质数我想应该是可以降低哈希算法的冲突率。至于原因这个就要问数学家了我几乎可以忽略的数学水平解释不了这个原因。上面说到31是一个不大不小的质数是优选乘子。那为啥同是质数的2和101或者更大的质数就不是优选乘子呢分析如下。这里先分析质数2。首先假设n 6然后把质数2和 n 带入上面的计算公式。并仅计算公式中次数最高的那一项结果是2^5 32是不是很小。所以这里可以断定当字符串长度不是很长时用质数2做为乘子算出的哈希值数值不会很大。也就是说哈希值会分布在一个较小的数值区间内分布性不佳最终可能会导致冲突率上升。上面说了质数2做为乘子会导致哈希值分布在一个较小区间内那么如果用一个较大的大质数101会产生什么样的结果呢根据上面的分析我想大家应该可以猜出结果了。就是不用再担心哈希值会分布在一个小的区间内了因为101^5 10,510,100,501。但是要注意的是这个计算结果太大了。如果用 int 类型表示哈希值结果会溢出最终导致数值信息丢失。尽管数值信息丢失并不一定会导致冲突率上升但是我们暂且先认为质数101或者更大的质数也不是很好的选择。最后我们再来看看质数31的计算结果31^5 28629151结果值相对于32和10,510,100,501来说。是不是很nice不大不小。上面用了比较简陋的数学手段证明了数字31是一个不大不小的质数是作为 hashCode 乘子的优选质数之一。接下来我会用详细的实验来验证上面的结论不过在验证前我们先看看 Stack Overflow 上关于这个问题的讨论Why does Javas hashCode() in String use 31 as a multiplier?。其中排名第一的答案引用了《Effective Java》中的一段话这里也引用一下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.简单翻译一下选择数字31是因为它是一个奇质数如果选择一个偶数会在乘法运算中产生溢出导致数值信息丢失因为乘二相当于移位运算。选择质数的优势并不是特别的明显但这是一个传统。同时数字31有一个很好的特性即乘法运算可以被移位和减法运算取代来获取更好的性能31 * i (i 5) - i现代的 Java 虚拟机可以自动的完成这个优化。排名第二的答案设这样说的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.这段话也翻译一下正如 Goodrich 和 Tamassia 指出的那样如果你对超过 50,000 个英文单词由两个不同版本的 Unix 字典合并而成进行 hash code 运算并使用常数 31, 33, 37, 39 和 41 作为乘子每个常数算出的哈希值冲突数都小于7个所以在上面几个常数中常数 31 被 Java 实现所选用也就不足为奇了。上面的两个答案完美的解释了 Java 源码中选用数字 31 的原因。接下来我将针对第二个答案就行验证请大家继续往下看。3. 实验及数据可视化本节我将使用不同的数字作为乘子对超过23万个英文单词进行哈希运算并计算哈希算法的冲突率。同时我也将针对不同乘子算出的哈希值分布情况进行可视化处理让大家可以直观的看到数据分布情况。本次实验所使用的数据是 Unix/Linux 平台中的英文字典文件文件路径为/usr/share/dict/words。3.1 哈希值冲突率计算计算哈希算法冲突率并不难比如可以一次性将所有单词的 hash code 算出并放入 Set 中去除重复值。之后拿单词数减去 set.size() 即可得出冲突数有了冲突数冲突率就可以算出来了。当然如果使用 JDK8 提供的流式计算 API则可更方便算出代码片段如下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, ListInteger hashs) { ComparatorInteger 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)); }结果如下从上图可以看出使用较小的质数做为乘子时冲突率会很高。尤其是质数2冲突率达到了 55.14%。同时我们注意观察质数2作为乘子时哈希值的分布情况。可以看得出来哈希值分布并不是很广仅仅分布在了整个哈希空间的正半轴部分即 0 ~ 231-1。而负半轴 -231 ~ -1则无分布。这也证明了我们上面断言即质数2作为乘子时对于短字符串生成的哈希值分布性不佳。然后再来看看我们之前所说的 31、37、41 这三个不大不小的质数表现都不错冲突数都低于7个。而质数 101 和 199 表现的也很不错冲突率很低这也说明哈希值溢出并不一定会导致冲突率上升。但是这两个家伙一言不合就溢出我们认为他们不是哈希算法的优选乘子。最后我们再来看看 32 和 36 这两个偶数的表现结果并不好尤其是 32冲突率超过了了50%。尽管 36 表现的要好一点不过和 3137相比冲突率还是比较高的。当然并非所有的偶数作为乘子时冲突率都会比较高大家有兴趣可以自己验证。3.2 哈希值分布可视化上一节分析了不同数字作为乘子时的冲突率情况这一节来分析一下不同数字作为乘子时哈希值的分布情况。在详细分析之前我先说说哈希值可视化的过程。我原本是打算将所有的哈希值用一维散点图进行可视化但是后来找了一圈也没找到合适的画图工具。加之后来想了想一维散点图可能不合适做哈希值可视化因为这里有超过23万个哈希值。也就意味着会在图上显示超过23万个散点如果不出意外的话这23万个散点会聚集的很密有可能会变成一个大黑块就失去了可视化的意义了。所以这里选择了另一种可视化效果更好的图表也就是 excel 中的平滑曲线的二维散点图下面简称散点曲线图。当然这里同样没有把23万散点都显示在图表上太多了。所以在实际绘图过程中我将哈希空间等分成了64个子区间并统计每个区间内的哈希值数量。最后将分区编号做为X轴哈希值数量为Y轴就绘制出了我想要的二维散点曲线图了。这里举个例子说明一下吧以第0分区为例。第0分区数值区间是[-2147483648, -2080374784)我们统计落在该数值区间内哈希值的数量得到分区编号, 哈希值数量数值对这样就可以绘图了。分区代码如下/** * 将整个哈希空间等分成64份统计每个空间内的哈希值数量 * param hashs */ public static MapInteger, Integer partition(ListInteger hashs) { // step 2^32 / 64 2^26 final int step 67108864; ListInteger nums new ArrayList(); MapInteger, 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); nums.add(num); } // 为了防止计算出错这里验证一下 int hashNum nums.stream().reduce((x, y) - x y).get(); assert hashNum hashs.size(); return statistics; }本文中的哈希值是用整形表示的整形的数值区间是[-2147483648, 2147483647]区间大小为2^32。所以这里可以将区间等分成64个子区间每个自子区间大小为2^26。详细的分区对照表如下分区编号分区下限分区上限分区编号分区下限分区上限0-2147483648-2080374784320671088641-2080374784-201326592033671088641342177282-2013265920-1946157056341342177282013265923-1946157056-1879048192352013265922684354564-1879048192-1811939328362684354563355443205-1811939328-1744830464373355443204026531846-1744830464-1677721600384026531844697620487-1677721600-1610612736394697620485368709128-1610612736-1543503872405368709126039797769-1543503872-14763950084160397977667108864010-1476395008-14092861444267108864073819750411-1409286144-13421772804373819750480530636812-1342177280-12750684164480530636887241523213-1275068416-12079595524587241523293952409614-1207959552-114085068846939524096100663296015-1140850688-1073741824471006632960107374182416-1073741824-1006632960481073741824114085068817-1006632960-939524096491140850688120795955218-939524096-872415232501207959552127506841619-872415232-805306368511275068416134217728020-805306368-738197504521342177280140928614421-738197504-671088640531409286144147639500822-671088640-6039797765414763950081543503872