酷应用

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

百家作者：聊聊架构 2018-08-11 14:55:02

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

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

文章链接如下：

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

作者的措辞带有相当强烈的意味，并且已经证明了很多奇怪的短字符串在生成哈希时会产生冲突。（文章中提供了很多示例，例如!~ 和"_）。众所周知，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 collisions(Collection values) {

        Map 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 collisions=collisions(lines);

        long finish=System.nanoTime();

        long elapsed=finish-start;



        int maxhc=0, maxsize=0;

        for(Map.Entry 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/

现在区块链概念如火如荼的传播，但是区块链技术和实现稍显冷门，技术人才也依然十分紧缺。

为了让大家可以跟快速上手区块链技术，国内开源共有链项目元界的 CTO 陈浩将用通俗易懂的语言从 0 开始讲起，帮你系统而准确的学习区块链知识，专栏中还会手把手教你搭建一个属于自己的迷你区块链。

现在订阅，享双重福利：

福利一：拼团价只需要¥58（仅限今日），原价¥68

福利二：订阅成功后，每邀请一位好友订阅，你可获得 12 元返现，好友可获得 6 元返现，多邀多得，上不封顶，立即提现。