写点什么

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

  • 2018-08-14
  • 本文字数:3179 字

    阅读完需:约 10 分钟

过去几天,我一直在浏览 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 个唯一哈希值。根据这个近似公式:

复制代码
from math import exp
def prob(x):
return 1.0 -exp(-0.5 * x * (x-1) / 2**32)
prob(77163) # 0.4999978150170551
prob(77164) # 0.500006797931095

那么对于给定数量的独立哈希,预计会发生多少次冲突?所运的是,维基百科为此提供了一个封闭式方程式:

复制代码
def count(d, n):
return n - d + d * ((d - 1) / d)**n

这种封闭式的解决方案可用于在实际的哈希函数中加入理论拟合。

一点实践

那么 String.hashCode() 符合标准吗?试着运行这段代码:

复制代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.nio.charset.StandardCharsets;
public class HashTest {
private static Map<Integer,Set> collisions(Collection values) {
Map<Integer,Set> result=new HashMap<>();
for(T value : values) {
Integer hc=Integer.valueOf(value.hashCode());
Set bucket=result.get(hc);
if(bucket == null)
result.put(hc, bucket = new TreeSet<>());
bucket.add(value);
}
return result;
}
public static void main(String[] args) throws IOException {
System.err.println("Loading lines from stdin...");
Set lines=new HashSet<>();
try (BufferedReader r=new BufferedReader(new InputStreamReader(System.in, StandardCharsets.UTF_8))) {
for(String line=r.readLine();line!=null;line=r.readLine())
lines.add(line);
}
// Warm up, if you please
System.err.print("Warming up");
for(int i=0;i<10;i++) {
System.err.print(".");
collisions(lines);
}
System.err.println();
System.err.println("Computing collisions...");
long start=System.nanoTime();
Map<Integer,Set> collisions=collisions(lines);
long finish=System.nanoTime();
long elapsed=finish-start;
int maxhc=0, maxsize=0;
for(Map.Entry<Integer,Set> e : collisions.entrySet()) {
Integer hc=e.getKey();
Set bucket=e.getValue();
if(bucket.size() > maxsize) {
maxhc = hc.intValue();
maxsize = bucket.size();
}
}
System.out.println("Elapsed time: "+elapsed+"ns");
System.out.println("Total unique lines: "+lines.size());
System.out.println("Time per hashcode: "+String.format("%.4f", 1.0*elapsed/lines.size())+"ns");
System.out.println("Total unique hashcodes: "+collisions.size());
System.out.println("Total collisions: "+(lines.size()-collisions.size()));
System.out.println("Collision rate: "+String.format("%.8f", 1.0*(lines.size()-collisions.size())/lines.size()));
if(maxsize != 0)
System.out.println("Max collisions: "+maxsize+" "+collisions.get(maxhc));
}
}

我们使用短字符串(words.txt,链接见文末)作为输入:

复制代码
$ cat words.txt | java HashTest
Loading lines from stdin...
Warming up..........
Computing collisions...
Elapsed time: 49117411ns
Total unique lines: 466544
Time per hashcode: 105.2793ns
Total unique hashcodes: 466188
Total collisions: 356
Collision rate: 0.00076306
Max collisions: 3 [Jr, KS, L4]

在这些英文短字符串中,总共有 466,544 个哈希,出现 356 次冲突。从理论上讲,“公平”的哈希函数应该只会产生 25.33 次冲突。因此,String.hashCode() 产生的冲突是公平哈希函数的 14.05 倍: 356.0 / 25.33 ≈ 14.05

不过,每 10,000 个哈希出现 8 次冲突的概率仍然是个不错的成绩。

那么长字符串值的结果怎样?使用莎士比亚全集中的句子(链接见文末)会产生以下输出:

复制代码
$ cat shakespeare.txt | java HashTest
Loading lines from stdin...
Warming up..........
Computing collisions...
Elapsed time: 24106163ns
Total unique lines: 111385
Time per hashcode: 216.4220ns
Total unique hashcodes: 111384
Total collisions: 1
Collision rate: 0.00000897
0.00076306
Max collisions: 2 [ There's half a dozen sweets., PISANIO. He hath been search'd among the dead and living,]

在这些较长的英语字符串中,总共有 111,385 个哈希,出现 1 次冲突。“公平”哈希函数将在这些数据上产生 1.44 次冲突,因此 String.hashCode() 优于公平哈希函数,冲突可能性是公平哈希函数的 69.4%: 1 / 1.44 ≈ 0.694

也就是说,每 100,000 个哈希产生不到 1 个冲突,这个成绩是极好的。

一点解释

显然,String.hashCode() 不具备唯一性,它也不可能具备唯一性。对于短字符串,它与理论平均值差得比较远,但其实做得还算不错。对于长字符串,它可以轻松打败平均理论值。

总得来看,它对于预期字符串而言是具备唯一性的,可以将字符串很好地分布在哈希表中。

最后,我还是认为 String.hashCode() 是具备唯一性的,至少它足够“好”。

延伸阅读

如果你对这个问题感兴趣,我强烈建议你看一看 Stack Overflow 上的答案( https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed#answer-145633 ),它深入探讨了哈希函数冲突的问题。

重要链接:

Reddit 文章: https://www.reddit.com/r/coding/comments/967hci/stringhashcode_is_not_even_a_little_unique/

相关测试: https://vanilla-java.github.io/2018/07/26/Stringhash-Code-is-not-even-a-little-unique.html

生日问题: https://en.wikipedia.org/wiki/Birthday_problem

words.txt: http://sigpwned.com/wp-content/uploads/2018/08/words.txt

莎士比亚长句: http://sigpwned.com/wp-content/uploads/2018/08/shakespeare.txt

查看英文原文: http://sigpwned.com/2018/08/10/string-hashcode-is-plenty-unique/

2018-08-14 06:068526
用户头像

发布了 731 篇内容, 共 468.2 次阅读, 收获喜欢 2006 次。

关注

评论

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

在线文本交集计算工具

入门小站

工具

Redis之Geospatial,助你轻松实现附近的xx功能

李子捌

redis geospatial 签约计划第二季

限流系列文章——令牌桶限流

李子捌

redis 限流 签约计划第二季

[Pulsar] 消息从Producer到Broker的历程

Zike Yang

Apache Pulsar 11月日更

为什么我的 C4C Service Request 没办法 Release 到 ERP?

汪子熙

Cloud SAP abap C4C 11月日更

云原生训练营作业--部署k8s集群

好吃不贵

跟小师妹一起学JVM-系列文章

程序那些事

Java JVM JIT 内容合集 签约计划第二季

限流系列文章——漏斗限流

李子捌

redis 限流 签约计划第二季

Linux 调优之:调整 bond hash 策略提升网络吞吐能力

卫智雄

巧用代理设计模式(Proxy Design Pattern)改善前端图片加载体验

汪子熙

设计模式 web开发 代理模式 Proxy 11月日更

LRU经常被吐槽,要不试试LFU?本文详述LFU(Least Frequently Used)

李子捌

redis 签约计划第二季

Redis高可用的绝对的利器——持久化(RDB和AOF)

李子捌

redis redis持久化 签约计划第二季

SAP Cloud for Customer Price 计价简介

汪子熙

Cloud SAP C4C 11月日更 pricing

数据分析从零开始实战,Pandas读写Excel/XML数据

老表

Python 数据分析 Excel pandas 11月日更

linux双向重定向之tee命令

入门小站

Linux

HyperLogLog这里面水很深,但是你必须趟一趟

李子捌

redis 签约计划第二季

Skip List(跳跃列表)它到底好在哪?今天我们不仅只聊为什么,还手写一个玩玩

李子捌

redis skiplist 签约计划第二季

限流系列文章——滑动窗口限流

李子捌

redis 限流 签约计划第二季

Prometheus Exporter (十三)Elasticsearch Exporter

耳东@Erdong

elasticsearch Prometheus exporter 11月日更

李子捌 Redis精通系列文章 研究分享| 内容合集

李子捌

redis 内容合集 签约计划第二季 技术专题合集

Redis集群模式,你若还是一知半解,试试仔细阅读一遍这篇文章

李子捌

redis redis cluster 签约计划第二季

签到功能怎么做?Bitmaps助你一臂之力

李子捌

redis bitmaps 签约计划第二季

CSS之盒模型

Augus

CSS 11月日更

URL URI傻傻分不清楚,dart告诉你该怎么用

程序那些事

flutter dart 程序那些事 11月日更

ES6, Angular, React 和 ABAP 中的 String Template(字符串模板)

汪子熙

JavaScript angular React abap 11月日更

都在用MQ,Redis的Pub/Sub也可以试着了解下

李子捌

redis MQ 签约计划第二季

【高并发】如何使用Java7提供的Fork/Join框架实现高并发程序?

冰河

Java 并发编程 多线程 高并发 异步编程

k8s statefulset controller源码分析

良凯尔

源码 Kubernetes 源码分析 #Kubernetes#

Redis的LRU(Least Recently Used)算法你了解多少?

李子捌

redis 签约计划第二季

数据库不能没有事务,今天他来了——Redis事务详述

李子捌

redis 事务 签约计划第二季

听说你的服务经常被打崩?试试布隆过滤器(Bloom Filter)

李子捌

redis 布隆过滤器 签约计划第二季

Java中的String.hashCode()方法可能有问题?_Java_Andy_InfoQ精选文章