Why does Java‘s hashCode() in String use 31 as a multiplier?
HashCode 为什么使用 31 作为乘数?
- 1. 固定乘积 31 在这用到了
- 2. 来自 stackoverflow 的回答
- 3. Hash 值碰撞概率统计
- 3.1 读取单词字典表
- 3.2 Hash 计算函数
- 3.3 Hash 碰撞概率计算
- 封装碰撞统计信息的类
- 3.4 针对一组乘数,分别计算碰撞率
- 3.5 碰撞结果可视化
- 3.6 Main方法
- 3.7 测试结果
问题如上:
☞hashCode 的计算逻辑中,为什么是 31 作为乘数。
1. 固定乘积 31 在这用到了
在获取 hashCode 的源码中可以看到,有一个固定值 31,在 for 循环每次执行时进行乘积计算,循环后的公式如下:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
那么这里为什么选择 31 作为乘积值呢?
2. 来自 stackoverflow 的回答
在 stackoverflow 关于为什么选择 31 作为固定乘积值,有一篇讨论文章,Why does Java’s hashCode() in String use 31 as a multiplier?
这是一个时间比较久的问题了,摘取两个回答点赞最多的:
这段内容主要阐述的观点包括;
- 31 是一个奇质数,如果选择偶数会导致乘积运算时数据溢出。
- 另外在二进制中,2 个 5 次方是 32,那么也就是
31 * i == (i << 5) - i
。这主要是说乘积运算可以使用位移提升性能,同时目前的 JVM 虚拟机也会自动支持此类的优化。
- 这个回答就很有实战意义了,告诉你用超过 5 千个单词计算 hashCode,这个 hashCode 的运算使用 31、33、37、39 和 41 作为乘积,得到的碰撞结果,31 被使用就很正常了。
- 他这句话就就可以作为我们实践的指向了。
3. Hash 值碰撞概率统计
接下来要做的事情并不难,只是根据 stackoverflow 的回答,统计出不同的乘积数对 10 万个单词的 hash 计算结果。
103976个英语单词库已通过资源绑定,将在文章顶部展示,可自行下载测试。
3.1 读取单词字典表
/*** 读取单词表文件,提取每行的第一个单词** @param filePath 文件路径* @return 单词列表*/public static List<String> readWordList(String filePath) {List<String> words = new ArrayList<>();try (BufferedReader reader = new BufferedReader(new FileReader(filePath))) {String line;while ((line = reader.readLine()) != null) {// 1. 跳过空行line = line.trim();if (line.isEmpty()) {continue;}// 2. 按空格或制表符分割行内容String[] parts = line.split("\\s+"); // 使用正则匹配连续空白符if (parts.length >= 2) {// 3. 提取第一个单词(索引为 1,因为首项是行号)String word = parts[1];words.add(word);}}} catch (IOException e) {e.printStackTrace();}return words;}
3.2 Hash 计算函数
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;}
3.3 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();int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());double collisionRate = (collisionCount * 1.0) / hashCodeList.size();return new RateInfo(multiplier, minHash, maxHash, collisionCount, collisionRate);}
封装碰撞统计信息的类
public class RateInfo {private int multiplier;private int minHash;private int maxHash;private int collisionCount;private double collisionRate;public RateInfo(int multiplier, int minHash, int maxHash, int collisionCount, double collisionRate) {this.multiplier = multiplier;this.minHash = minHash;this.maxHash = maxHash;this.collisionCount = collisionCount;this.collisionRate = collisionRate;}public int getMultiplier() {return multiplier;}public void setMultiplier(int multiplier) {this.multiplier = multiplier;}public int getMinHash() {return minHash;}public void setMinHash(int minHash) {this.minHash = minHash;}public int getMaxHash() {return maxHash;}public void setMaxHash(int maxHash) {this.maxHash = maxHash;}public int getCollisionCount() {return collisionCount;}public void setCollisionCount(int collisionCount) {this.collisionCount = collisionCount;}public double getCollisionRate() {return collisionRate;}public void setCollisionRate(double collisionRate) {this.collisionRate = collisionRate;}@Overridepublic String toString() {return String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 = %6d, 碰撞率 = %.4f%%",multiplier, minHash, maxHash, collisionCount, collisionRate * 100);}
3.4 针对一组乘数,分别计算碰撞率
public static List<RateInfo> collisionRateList(List<String> words, int[] multipliers) {List<RateInfo> rateInfoList = new ArrayList<>();for (int m : multipliers) {// 对所有单词计算 hash 值(使用传入的 m)List<Integer> hashCodeList = words.stream().map(word -> hashCode(word, m)).collect(Collectors.toList());// 传递 m 而非计算出的某个 hash 值RateInfo rate = hashCollisionRate(m, hashCodeList);rateInfoList.add(rate);}return rateInfoList;}
3.5 碰撞结果可视化
public static void printBarChart(List<RateInfo> rateInfoList) {// 求出所有记录中碰撞率的最大值,用于归一化条形长度double maxRate = rateInfoList.stream().mapToDouble(RateInfo::getCollisionRate).max().orElse(1.0);// 设定条形图最大宽度(字符数)int maxBarWidth = 50;System.out.println("==== 横向条形图展示各乘数下的碰撞率 ====");for (RateInfo rate : rateInfoList) {// 当前碰撞率归一化后的条形长度计算int barLength = (int) ((rate.getCollisionRate() / maxRate) * maxBarWidth);String bar = new String(new char[barLength]).replace('\0', '#');System.out.printf("乘数 %4d | %s (碰撞率: %.4f%%)%n",rate.getMultiplier(), bar, rate.getCollisionRate() * 100);}}
3.6 Main方法
// 指定需要测试的乘数列表List<String> words = FileUtil.readWordList("D:\\英语单词库.txt");List<RateInfo> rateInfoList = collisionRateList(words, new int[]{2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199});System.out.println("读取单词总数: " + words.size());// 输出各乘数下的碰撞统计信息System.out.println("============ 哈希碰撞统计 ============");for (RateInfo rate : rateInfoList) {System.out.println(rate.toString());}System.out.println();printBarChart(rateInfoList);
3.7 测试结果
以上就是不同的乘数下的 hash 碰撞结果图标展示,从这里可以看出如下信息;
- 乘数是 2 时,hash 的取值范围比较小,基本是堆积到一个范围内了。
- 乘数是 3、5、7、17 等,都有较大的碰撞概率
- 乘数是 31 的时候,碰撞的概率已经很小了,基本稳定。
- 顺着往下看,你会发现 199 的碰撞概率更小,这就相当于一排奇数的茅坑量多,自然会减少碰撞。但这个范围值已经远超过 int 的取值范围了,如果用此数作为乘数,又返回 int 值,就会丢失数据信息。
相关文章:
Why does Java‘s hashCode() in String use 31 as a multiplier?
HashCode 为什么使用 31 作为乘数? 1. 固定乘积 31 在这用到了2. 来自 stackoverflow 的回答3. Hash 值碰撞概率统计3.1 读取单词字典表3.2 Hash 计算函数3.3 Hash 碰撞概率计算封装碰撞统计信息的类3.4 针对一组乘数,分别计算碰撞率3.5 碰撞结果可视化3…...
如何将一个8s的接口优化到500ms以下
最近换了个工作,刚入职就接了个活--优化公司自营app的接口性能,提升用户体验。 刚开始还以为是1s优化到500ms这种,或者500ms优化到200ms的接口,感觉还挺有挑战的。下好app体验了一下。好家伙,那个慢已经超过了我的忍耐…...
如何保证本地缓存和redis的一致性
1. Cache Aside Pattern(旁路缓存模式) 核心思想:应用代码直接管理缓存与数据的同步,分为读写两个流程: 读取数据: 先查本地缓存(如 Guava Cache)。若本地未命中&…...
30天学Java第十天——反射机制
反射机制 反射机制是 Java 语言中的一个重要特性,它允许程序在运行时动态地获取类的信息(如类的属性、方法和构造器等),并且可以操作这些信息。 反射机制在某些情况下非常有用,例如开发框架、库,或者需要进…...
Nodejs Express框架
参考:Node.js Express 框架 | 菜鸟教程 第一个 Express 框架实例 接下来我们使用 Express 框架来输出 "Hello World"。 以下实例中我们引入了 express 模块,并在客户端发起请求后,响应 "Hello World" 字符串。 创建 e…...
视频设备轨迹回放平台EasyCVR打造货运汽车安全互联网视频监控与管理方案
一、背景介绍 随着互联网发展,货运中介平台大量涌现,行业纠纷也随之增多。尽管当前平台APP具备录音和定位功能,但货物交易流程的全方位监控仍无法实现。主流跟踪定位服务大部分聚焦货物轨迹与车辆定位,尚未实现货物全程可视化监控…...
玩转Docker | 使用Docker部署Docmost文档管理系统
玩转Docker | 使用Docker部署Docmost文档管理系统 前言一、Docmost介绍Docmost 简介Docmost 特点二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署Docmost服务下载镜像编辑部署文件创建容器检查容器状态检查服务端口安全设置四、访问Docmost服务访问Docmos…...
docker方式项目部署(安装容器组件+配置文件导入Nacos+dockerCompose文件创建管理多个容器+私有镜像仓库Harbor)
基于docker的部署 服务器主机ip 192.168.6.131 安装组件 安装redis docker pull redis:7.0.10#在宿主机上/var/lib/docker/volumes/redis-config/_data/目录下创建一个redis配置文件 vim redis.conf#内容如下 appendonly yes #开启持久化 port 6379 #requirepass 1234 #密码…...
基于OpenCV与PyTorch的智能相册分类器全栈实现教程
引言:为什么需要智能相册分类器? 在数字影像爆炸的时代,每个人的相册都存储着数千张未整理的照片。手动分类不仅耗时,还容易遗漏重要瞬间。本文将手把手教你构建一个基于深度学习的智能相册分类系统,实现:…...
C++中string库常用函数超详细解析与深度实践
目录 一、引言 二、基础准备:头文件与命名空间 三、string对象的创建与初始化(基础) 3.1 直接初始化 3.2 动态初始化(空字符串) 3.3 基于字符数组初始化 3.4 重复字符初始化 四、核心函数详解 4.1 字符串长度相关 4.1.1 …...
数据结构(3)
实验步骤: 任务:要求使用自定义函数来实现 输入一段文本,统计每个字符出现的次数,按照字符出现次数从多到少,依次输出,格式如下: 字符1-个数 字符2-个数 ...... 解题思路: 构建结构体…...
【C++教程】使用printf语句实现进制转换
在C语言中,printf 函数可以直接实现部分进制转换功能,通过格式说明符(format specifier)快速输出不同进制的数值。以下是详细使用方法及示例代码: 一、printf 原生支持的进制转换 1. 十进制、八进制、十六进制转换 #…...
el-dialog设置append-to不生效;el-dialog设置挂载层级
文章目录 一、场景二、注意点1. append-to-body何时为true2.设置层级,遮罩层大小不生效3.相关代码 三、ElMessageBox遮罩层 效果: 一、场景 正常情况下,el-dialog的弹框是挂载在body下的,导致我们会有修改样式或者修改弹框的遮罩…...
互联网软件开发自动化平台 的多维度对比分析,涵盖架构、功能、适用场景、成本等关键指标
以下是关于 互联网软件开发自动化平台 的详细解析,涵盖其核心概念、主流平台的功能、架构设计、适用场景及对比分析: 一、自动化平台的定义与核心目标 自动化平台(如CI/CD平台)是用于 持续集成(CI) 和 持续…...
UE5 制作方块边缘渐变边框效果
该效果基于之前做的(https://blog.csdn.net/grayrail/article/details/144546427)进行修改得到,思路也很简单: 1.打开实时预览 1.为了制作时每个细节调整方便,勾选Live Update中的三个选项,开启实时预览。…...
深入探究 GRU 模型:梯度爆炸问题剖析
在深度学习领域,循环神经网络(RNN)及其变体在处理序列数据时展现出了强大的威力。其中,门控循环单元(GRU)作为 RNN 的一种进阶架构,备受关注。今天,咱们就来深入聊聊 GRU 模型&#…...
生成对抗网络(GAN)原理详解
生成对抗网络(GAN)原理详解 1. 背景 生成对抗网络(Generative Adversarial Network, GAN)由 Ian Goodfellow 等人于 2014 年提出,是一种通过对抗训练生成高质量数据的框架。其核心思想是让两个神经网络(生…...
CFD中的动量方程非守恒形式详解
在计算流体力学(CFD)中,动量方程可以写成守恒形式和非守恒形式,两者在数学上等价,但推导方式和应用场景不同。以下是对非守恒形式的详细解释: 1. 动量方程的守恒形式 首先回顾守恒形式的动量方程ÿ…...
AIoT 智变浪潮演讲实录 | 刘浩然:让硬件会思考:边缘大模型网关助力硬件智能革新
4 月 2 日,由火山引擎与英特尔联合主办的 AIoT “智变浪潮”技术沙龙在深圳成功举行,活动聚焦 AI 硬件产业的技术落地与生态协同,吸引了芯片厂商、技术方案商、品牌方及投资机构代表等 700 多位嘉宾参会。 会上,火山引擎边缘智能高…...
4.B-树
一、常见的查找方式 顺序查找 O(N) 二分查找 O(logN)(要求有序和随机访问) 二叉搜索树 O(N) 平衡二叉搜索树(AVL树和红黑树) O(logN) 哈希 O(1) 考虑效率和要求而言,正常选用 平衡二叉搜索树 和 哈希 作为查找方式。 但这两种结构适合用于数据量相对不是很大,能够一次性…...
怎么看英文论文 pdf沉浸式翻译
https://arxiv.org/pdf/2105.09492 Immersive Translate Xournal打开...
计算机三级第一章:信息安全保障概述(以时间节点推进的总结)
淡蓝色为必背内容 第一阶段:电讯技术的发明19世纪30年代:电报电话的发明 1835年:莫尔斯(Morse)发明了电报 1837年:莫尔斯电磁式有线电报问世 1878年:人工电话交换局出现 1886年:马可尼发明了无线电报机 1876年:贝尔(Bell)发明了电话机 1892年,史瑞桥自动交换…...
车载软件架构 ---单个ECU的AUTOSAR开发流程
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 周末洗了一个澡,换了一身衣服,出了门却不知道去哪儿,不知道去找谁,漫无目的走着,大概这就是成年人最深的孤独吧! 旧人不知我近况,新人不知我过…...
【场景应用7】在TPU上使用Flax/JAX对Transformers模型进行语言模型预训练
在本笔记本中,我们将展示如何使用Flax在TPU上预训练一个🤗 Transformers模型。 这里将使用GPT2的因果语言建模目标进行预训练。 正如在这个基准测试中所看到的,使用Flax/JAX在GPU/TPU上的训练通常比使用PyTorch在GPU/TPU上的训练要快得多,而且也可以显著降低成本。 Fla…...
C++运算符重载全面总结
C运算符重载全面总结 运算符重载是C中一项强大的特性,它允许程序员为自定义类型定义运算符的行为。以下是关于C运算符重载的详细总结: 一、基本概念 1. 什么是运算符重载 运算符重载是指为自定义类型(类或结构体)重新定义或重…...
PTA | 实验室使用排期
目录 题目: 输入格式: 输出格式: 输入样例: 输出样例: 样例解释: 代码: 无注释版: 有注释版: 题目: 受新冠疫情影响,当前大家的活动都…...
3.7 字符串基础
字符串 (str):和列表用法基本一致 1.字符串的创建 -str转换(字符串,可用于将其他字符类型转换为字符串) -单引号 双引号 三引号 2.索引 3.字符串的切片 4.字符串的遍历 5.字符串的格式化 6.字符串的运算符 7.字符串的函数 #…...
《 C++ 点滴漫谈: 三十三 》当函数成为参数:解密 C++ 回调函数的全部姿势
一、前言 在现代软件开发中,“解耦” 与 “可扩展性” 已成为衡量一个系统架构优劣的重要标准。而在众多实现解耦机制的技术手段中,“回调函数” 无疑是一种高效且广泛使用的模式。你是否曾经在编写排序算法时,希望允许用户自定义排序规则&a…...
16bit转8bit的常见方法(图像归一化)
文章目录 16-bit转8-bit的常用方法一、数据类型转换:image.astype(np.uint8) —— 若数值 x 超出 0-255 范围,则取模运算。如:x 600 % 256 88二、截断函数:np.clip().astype(np.uint8) —— 若数值 x 超出 0-255 范围࿰…...
消息中间件kafka,rabbitMQ
在分布式系统中,消息中间件是实现不同组件之间异步通信的关键技术。Kafka 和 RabbitMQ 是两个非常流行的消息中间件系统,它们各自有着不同的特点和应用场景。下面将分别介绍 Kafka 和 RabbitMQ,并讨论它们在消息队列中的使用。 一、Kafka (Apache Kafka) 主要特点: 高吞吐…...
C语言编译预处理3
条件编译:是对源程序的一部分指定编译条件,满足条件进行编译否则不编译。 形式1 #indef 标识符 程序段1 #else 程序段2 #endif 标识符已经被定义用#ifdef #include <stdio.h>// 可以通过注释或取消注释下面这行来控制是否定义 DEBUG 宏 // …...
数据结构·树
树的特点 最小连通图 无环 有且只有 n − 1 n-1 n−1 条边 树的建立方式 顺序存储 只适用于满n叉树,完全n叉树 1<<n 表示结点 2 n 2^n 2nP4715 【深基16.例1】淘汰赛 void solve() {cin >> n;for (int i 0; i<(1<<n); i) {cin >&g…...
队列的各种操作实现(数据结构C语言多文件编写)
1.先创建queue.h声明文件(Linux命令:touch queue.h)。编写函数声明如下(打开文件 Linux 操作命令:vim queue.h): //头文件 #ifndef __QUEUE_H__ #define __QUEUE_H__ //队列 typedef struct queue{int* arr;int in;int out;int cap;int size; }queue_t;…...
48V/2kW储能电源纯正弦波逆变器详细设计方案-可量产
48V/2kW储能电源纯正弦波逆变器详细设计方案 1.后级驱动电路图 2.前级驱动电路图 3.功率表电路原理图 4.功率板BOM: 5.后级驱动BOM 6.前级驱动BOM...
[redis进阶二]分布式系统之主从复制结构(2)
目录 一 redis的拓扑结构 (1)什么是拓扑 (2)⼀主⼀从结构 (3)⼀主多从结构 (4)树形主从结构 (5)三种拓扑结构的优缺点,以及适用场景 二 redis的复制原理 (1)复制过程 (2)数据同步psync replicationid/replid (复制id)(标注同步的数据来自哪里:数据来源) offset (偏移…...
Playwright多语言生态:跨Python_Java_.NET的统一采集方案
一、问题背景:爬虫多语言割裂的旧时代 在大规模数据采集中,尤其是学术数据库如 Scopus,开发者常遇到两个经典问题: 技术语言割裂:Python开发人员使用Selenium、requests-html等库;Java阵营使用Jsoup或Htm…...
day30 第八章 贪心算法 part04
452. 用最少数量的箭引爆气球 先排序,再算重叠区间 class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points)0:return 0points.sort(keylambda x:x[0])result 1for i in range(1, len(points)):if points[i][0] > point…...
java操作redis库,开箱即用
application.yml spring:application:name: demo#Redis相关配置redis:data:# 地址host: localhost# 端口,默认为6379port: 6379# 数据库索引database: 0# 密码password:# 连接超时时间timeout: 10slettuce:pool:# 连接池中的最小空闲连接min-idle: 0# 连接池中的最…...
clickhouse中的窗口函数
窗口函数 边界核心参数 窗口边界通过 ROWS、RANGE 或 GROUPS 模式定义,语法为: ROWS BETWEEN AND 基于 物理行位置 定义窗口,与排序键的实际值无关,适用于精确控制窗口行数 – 或 RANGE BETWEEN AND 基于 排序键的数值范围 定义窗口,适用于时间序列或连续数值的场景(…...
YZ系列工具之YZ02:字典的多功能应用
我给VBA下的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。我的教程一共九套一部VBA手册,教程分为初级、中级、高级三大部分。是对VBA的系统讲解,从简单的…...
金山科技在第91届中国国际医疗器械博览会CMEF 首发新品 展现智慧装备+AI
4月8日—11日,国家会展中心(上海),第91届中国国际医疗器械(春季)博览会(以下简称“CMEF 2025”)举办。金山科技在盛会上隆重推出年度新品——全高清电子内镜光学放大镜与肛肠测压系统…...
STM32 BOOT设置,bootloader,死锁使用方法
目录 BOOT0 BOOT1的配置含义 bootloader使用方法 芯片死锁解决方法开发调试过程中,由于某种原因导致内部Flash锁死,无法连接SWD以及JTAG调试,无法读到设备,可以通过修改BOOT模式重新刷写代码。修改为BOOT01,BOOT10…...
机器学习:让数据开口说话的科技魔法
在人工智能飞速发展的今天,「机器学习」已成为推动数字化转型的核心引擎。无论是手机的人脸解锁、网购平台的推荐系统,还是自动驾驶汽车的决策能力,背后都离不开机器学习的技术支撑。那么,机器学习究竟是什么?它又有哪…...
PDF解析示例代码学习
以下是结合多种技术实现的PDF解析详细示例(Python实现),涵盖文本、表格和扫描件处理场景: 一、环境准备与依赖安装 # 核心依赖库 pip install pdfplumber tabula-py pytesseract opencv-python mysql-connector-python 二、完整…...
【云平台监控】安装应用Ansible服务
安装应用Ansible服务 文章目录 安装应用Ansible服务资源列表基础环境一、安装Ansible1.1、部署Ansible1.2、配置主机清单1.2.1、方法11.2.2、方法2 二、Ansible命令应用基础2.1、ping模块2.2、command模块2.3、user模块2.4、group模块2.5、cron模块2.6、copy模块2.7、file模块2…...
项目执行中的目标管理:从战略到落地的闭环实践
——如何让目标不“跑偏”、团队不“掉队”? 引言:为什么目标管理决定项目成败? 根据PMI研究,47%的项目失败源于目标模糊或频繁变更。在复杂多变的项目环境中,目标管理不仅是制定KPI,更是构建“方向感-执行…...
如何优雅地处理 API 版本控制?
API 会不断发展,而用户的需求也会随之变化。那么,如何确保你的 API 在升级时不会影响现有用户?答案就是:API 版本控制。就像你更新了一个应用程序,引入了新功能,但旧功能仍然保留,让老用户继续愉…...
如何通过Radius认证服务器实现虚拟云桌面安全登录认证:安当ASP身份认证系统解决方案
引言:虚拟化时代的安全挑战 随着云计算和远程办公的普及,虚拟云桌面(如VMware Horizon、Citrix)已成为企业数字化办公的核心基础设施。然而,传统的用户名密码认证方式暴露了诸多安全隐患:弱密码易被暴力破…...
自然语言处理spaCy
spaCy 是一个流行的开源 自然语言处理(NLP) 库,专注于 高效、易用和工业化应用。它由 Explosion AI 开发,广泛应用于文本处理、信息提取、机器翻译等领域。 zh_core_web_sm 是 spaCy 提供的一个小型中文预训练语言模型࿰…...
大语言模型(LLMs)中的强化学习(Reinforcement Learning, RL)
第一部分:强化学习基础回顾 在深入探讨LLMs中的强化学习之前,我们先快速回顾一下强化学习的核心概念,确保基础扎实。 1. 强化学习是什么? 强化学习是一种机器学习范式,目标是让智能体(Agent)…...