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

2023-12-15 07:58

本文主要是介绍科普:String hashCode 方法为什么选择数字 31 作为乘子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  点击上方 好好学java ,选择 星标 公众号

重磅资讯、干货,第一时间送达
今日推荐:牛人 20000 字的 Spring Cloud 总结,太硬核了~
作者:田小波
来源:https://www.cnblogs.com/nullllun/p/8350178.html

1. 背景

某天,我在写代码的时候,无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一个奇怪的数字,也就是本文的主角31。这个数字居然不是用常量声明的,所以没法从字面意思上推断这个数字的用途。后来带着疑问和好奇心,到网上去找资料查询一下。在看完资料后,默默的感叹了一句,原来是这样啊。那么到底是哪样呢?在接下来章节里,请大家带着好奇心和我揭开数字31的用途之谜。

2. 选择数字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 类型数组。这里我来简单推导一下这个公式:

假设 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]

上面的公式包括公式的推导并不是本文的重点,大家了解了解即可。接下来来说说本文的重点,即选择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,结果值相对于3210,510,100,501来说。是不是很nice,不大不小。

上面用了比较简陋的数学手段证明了数字31是一个不大不小的质数,是作为 hashCode 乘子的优选质数之一。接下来我会用详细的实验来验证上面的结论,不过在验证前,我们先看看 Stack Overflow 上关于这个问题的讨论,Why does Java's 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, 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));
}

结果如下:

从上图可以看出,使用较小的质数做为乘子时,冲突率会很高。尤其是质数2,冲突率达到了 55.14%。同时我们注意观察质数2作为乘子时,哈希值的分布情况。可以看得出来,哈希值分布并不是很广,仅仅分布在了整个哈希空间的正半轴部分,即 0 ~ 231-1。而负半轴 -231 ~ -1,则无分布。这也证明了我们上面断言,即质数2作为乘子时,对于短字符串,生成的哈希值分布性不佳。然后再来看看我们之前所说的 31、37、41 这三个不大不小的质数,表现都不错,冲突数都低于7个。而质数 101 和 199 表现的也很不错,冲突率很低,这也说明哈希值溢出并不一定会导致冲突率上升。但是这两个家伙一言不合就溢出,我们认为他们不是哈希算法的优选乘子。最后我们再来看看 32 和 36 这两个偶数的表现,结果并不好,尤其是 32,冲突率超过了了50%。尽管 36 表现的要好一点,不过和 31,37相比,冲突率还是比较高的。当然并非所有的偶数作为乘子时,冲突率都会比较高,大家有兴趣可以自己验证。

3.2 哈希值分布可视化

上一节分析了不同数字作为乘子时的冲突率情况,这一节来分析一下不同数字作为乘子时,哈希值的分布情况。在详细分析之前,我先说说哈希值可视化的过程。我原本是打算将所有的哈希值用一维散点图进行可视化,但是后来找了一圈,也没找到合适的画图工具。加之后来想了想,一维散点图可能不合适做哈希值可视化,因为这里有超过23万个哈希值。也就意味着会在图上显示超过23万个散点,如果不出意外的话,这23万个散点会聚集的很密,有可能会变成一个大黑块,就失去了可视化的意义了。所以这里选择了另一种可视化效果更好的图表,也就是 excel 中的平滑曲线的二维散点图(下面简称散点曲线图)。当然这里同样没有把23万散点都显示在图表上,太多了。所以在实际绘图过程中,我将哈希空间等分成了64个子区间,并统计每个区间内的哈希值数量。最后将分区编号做为X轴,哈希值数量为Y轴,就绘制出了我想要的二维散点曲线图了。这里举个例子说明一下吧,以第0分区为例。第0分区数值区间是[-2147483648, -2080374784),我们统计落在该数值区间内哈希值的数量,得到 <分区编号, 哈希值数量> 数值对,这样就可以绘图了。分区代码如下:

/*** 将整个哈希空间等分成64份,统计每个空间内的哈希值数量* @param hashs*/
public static Map<Integer, Integer> partition(List<Integer> hashs) {// step = 2^32 / 64 = 2^26final 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);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-208037478432067108864
1-2080374784-20132659203367108864134217728
2-2013265920-194615705634134217728201326592
3-1946157056-187904819235201326592268435456
4-1879048192-181193932836268435456335544320
5-1811939328-174483046437335544320402653184
6-1744830464-167772160038402653184469762048
7-1677721600-161061273639469762048536870912
8-1610612736-154350387240536870912603979776
9-1543503872-147639500841603979776671088640
10-1476395008-140928614442671088640738197504
11-1409286144-134217728043738197504805306368
12-1342177280-127506841644805306368872415232
13-1275068416-120795955245872415232939524096
14-1207959552-1140850688469395240961006632960
15-1140850688-10737418244710066329601073741824
16-1073741824-10066329604810737418241140850688
17-1006632960-9395240964911408506881207959552
18-939524096-8724152325012079595521275068416
19-872415232-8053063685112750684161342177280
20-805306368-7381975045213421772801409286144
21-738197504-6710886405314092861441476395008
22-671088640-6039797765414763950081543503872
23-603979776-5368709125515435038721610612736
24-536870912-4697620485616106127361677721600
25-469762048-4026531845716777216001744830464
26-402653184-3355443205817448304641811939328
27-335544320-2684354565918119393281879048192
28-268435456-2013265926018790481921946157056
29-201326592-1342177286119461570562013265920
30-134217728-671088646220132659202080374784
31-6710886406320803747842147483648

接下来,让我们对照上面的分区表,对数字2、3、17、31、101的散点曲线图进行简单的分析。先从数字2开始,数字2对于的散点曲线图如下:

上面的图还是很一幕了然的,乘子2算出的哈希值几乎全部落在第32分区,也就是 [0, 67108864)数值区间内,落在其他区间内的哈希值数量几乎可以忽略不计。这也就不难解释为什么数字2作为乘子时,算出哈希值的冲突率如此之高的原因了。所以这样的哈希算法要它有何用啊,拖出去斩了吧。接下来看看数字3作为乘子时的表现:

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

数字17作为乘子时的表现,明显比上面两个数字好点了。虽然哈希值在第32分区和第34分区有一定的聚集,但是相比较上面2和3,情况明显好好了很多。除此之外,17作为乘子算出的哈希值在其他区也均有分布,且较为均匀,还算是一个不错的乘子吧。

接下来来看看我们本文的主角31了,31作为乘子算出的哈希值在第33分区有一定的小聚集。不过相比于数字17,主角31的表现又好了一些。首先是哈希值的聚集程度没有17那么严重,其次哈希值在其他区分布的情况也要好于17。总之,选31,准没错啊。

最后再来看看大质数101的表现,不难看出,质数101作为乘子时,算出的哈希值分布情况要好于主角31,有点喧宾夺主的意思。不过不可否认的是,质数101的作为乘子时,哈希值的分布性确实更加均匀。所以如果不在意质数101容易导致数据信息丢失问题,或许其是一个更好的选择。

4.写在最后

经过上面的分析与实践,我想大家应该明白了 String hashCode 方法中选择使用数字31作为乘子的原因了。本文本质是一篇简单的科普文而已,并没有银弹。如果大家读完后觉得又涨知识了,那这篇文章的目的就达到了。最后,本篇文章的配图画的还是很辛苦的,所以如果大家觉得文章不错,不妨就给个赞吧,就当是对我的鼓励了。另外,如果文章中有不妥或者错误的地方,也欢迎指出来。如果能不吝赐教,那就更好了。最后祝大家生活愉快,再见。

这篇关于科普:String hashCode 方法为什么选择数字 31 作为乘子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/495708

相关文章

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

【北交大信息所AI-Max2】使用方法

BJTU信息所集群AI_MAX2使用方法 使用的前提是预约到相应的算力卡,拥有登录权限的账号密码,一般为导师组共用一个。 有浏览器、ssh工具就可以。 1.新建集群Terminal 浏览器登陆10.126.62.75 (如果是1集群把75改成66) 交互式开发 执行器选Terminal 密码随便设一个(需记住) 工作空间:私有数据、全部文件 加速器选GeForce_RTX_2080_Ti

cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈? cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte