Java中的String.hashCode()方法可能有问题?

2018 年 8 月 14 日

过去几天,我一直在浏览 Reddit 上的一篇文章。这篇文章看得我要抓狂了。文章指出,Java 中的 String.hashCode() 方法(将任意长度的字符串对象映射成 32 位 int 值)生成的哈希值存在冲突。文章作者似乎对这个问题感到很惊讶,并声称 String.hashCode() 的算法是有问题的。用作者自己的话说:

不管使用哪一种哈希策略,冲突都是不可避免的,但其中总有相对较好的哈希也有较差的哈希。你可以认为 String 中的哈希是比较差的那种。

作者的措辞带有相当强烈的意味,并且已经证明了很多奇怪的短字符串在生成哈希时会产生冲突。(文章中提供了很多示例,例如!~ 和"_)。众所周知,32 位字符串哈希函数确实会发生很多冲突,但从经验来看,在真实的场景中,String.hashCode() 能够很好地管理哈希冲突。

那么“差”的哈希是什么样子的呢?而“好”的哈希又是什么样子的?

一点理论

32 位哈希只能占用 2^32 = 4,294,967,296 个唯一值。因为字符串中可以包含任意数量的字符,所以可能的字符串显然要比这个数字多得多。因此,根据鸽子原则,必然会存在冲突。

但冲突的可能性有多大?

著名的生日问题表明,对于 365 个可能的“哈希值”,在哈希冲突可能性达到 50%之前,必须计算出 23 个唯一哈希值。如果有 2^32 个可能的哈希值,那么在达到 50%的哈希冲突可能性之前,必须计算出大约 77,164 个唯一哈希值。根据这个近似公式:

原文链接:【 https://www.infoq.cn/article/2018/08/java-stringhashcode-plenty 】。未经作者许可,禁止转载。

登录后可解锁全站优质内容

免费畅享技术公开课、顶尖技术团队访谈、一线互联网大厂技术实践

文章
视频
电子书
研究报告
立即登录
2018 年 8 月 14 日 06:06 4615
用户头像

发布了 5 篇内容,共 4081 次阅读,收获喜欢 0 次。

关注

评论

发布
暂无评论
发现更多内容

Go: Go 调度器的任务窃取(Work-Stealing)

陈思敏捷

go golang 源码分析 原理 队列

重装Oracle11g

阡陌r

oracle 踩坑 oracle重装

推荐几款有意思的小众App(06.06)

静陌

像运营公司一样去做产品

胖鱼2号

创业 产品 产品经理 企业

Spring 源码学习 - 单例bean的实例化过程

公众号:好奇心森林

内存屏障的来历

HackMSF

cpu 并发

test

PQY

JDK 8,该离开的时候,请别留恋!

范学雷

Java 架构 编程语言 Java 25 周年

彻底搞懂 etcd 系列文章(一):初识 etcd

aoho

架构 云原生 etcd

Spark学习笔记一之为什么Spark这么牛逼

Shockang

大数据 spark

缓存一致性协议的工作方式

HackMSF

缓存 并发

中小型城市商业银行数字化转型实践(四)业务中台建设思路和路径

泡菜小仙

银行业务中台 银行数字化转型

游戏夜读 | 终端设备之争?

game1night

Pycharm社区版安装教程(永久免费,随时升级)

早睡蟒

ARTS Week2

时之虫

ARTS 打卡计划

ARTS|Week 02:体会刷算法题的快乐,同时开启Ubuntu 20.04备用系统

MiracleWong

算法 ARTS 打卡计划

Trie 字典树

12583

LeetCode Trie

当代社畜在维权中成长 | 记初次打官司

张鸱鸺

个人成长 随笔杂谈 维权 民事诉讼

奈学教你五分钟学会分布式事务

奈学教育

分布式系统

听说用 Lombok 可以早点下班?

武培轩

Java 程序员 工具 后端 IDEA

做正确的事情什么时候都不晚

Neco.W

学习 学习方法 导师

Spark Launcher Java API提交Spark算法

杨仪军

spark spark launcher

彻底搞懂 etcd 系列文章(三):etcd 集群运维部署

aoho

架构 云原生 etcd

原创 | TDD工具集:JUnit、AssertJ和Mockito (十九)编写测试-依赖注入\测试接口\重复测试

编程道与术

Java 编程 TDD 单元测试 JUnit

单例模式详解

章小传

Java 单例模式

C/C++:const常量真的可以用指针修改吗

韩小非

c c++ 指针 常量 编译器优化

愿你也能穿越熊熊烈火,飞往你的山

Janenesome

读书笔记 思考

GitLab CI/CD

xgqfrms

ES2020 new features / ES11

xgqfrms

ES2020 new features ES11 ES2020

某二手交易平台大数据平台从 0 到 1 演进与实践

奈学教育

线上故障处理实践

心平气和

故障分析 故障定位

众安黑客马拉松大赛总决赛-InfoQ小编探班

众安黑客马拉松大赛总决赛-InfoQ小编探班

Java中的String.hashCode()方法可能有问题?-InfoQ