• [高清组图]环广西赛:参赛车队赛前适应训练 2018-08-31
  • [高清组图]特谢拉复出吴曦失单刀 苏宁0-0平斯威 2018-08-31
  • [高清组图]潜水偶遇座头鲸 亲密互动玩起“水中击掌” 2018-08-31
  • [高清组图]法拉利拍定妆照 维特尔KIMI准备好了 2018-08-31
  • [高清组图]毛剑卿伤退莫雷诺捅射 申花1-0一方 2018-08-31
  • [高清组图]比埃拉双响巴坎布建功 国安5-1富力 2018-08-31
  • [高清组图]武磊世界波胡尔克点射 上港2-0胜申花 2018-08-31
  • [高清组图]武磊2球吕文君建功 上港3-1富力 2018-08-31
  • [高清组图]欧超杯-科斯塔2球 皇马加时赛2-4马竞 2018-08-31
  • [高清组图]格里芬赤膊骑行 休赛期享受二人世界 2018-08-31
  • [视频]【深化改革 重在实效】精准扶贫 四川彝区要拔掉“穷根” 2018-08-31
  • [视频]【深化改革 重在实效】破藩篱促合力 体制创新粘合“两张皮” 2018-08-31
  • [视频]【深化改革 重在实效】激发活力 实现市场准入全程便利化 2018-08-31
  • [视频]【深化改革 重在实效】打通简政放权的“最后一公里” 2018-08-31
  • [视频]【深化改革 重在实效】广东:户籍改革为外来工打开一扇门 2018-08-31
  • 手机版
    你好,游客 登录 注册 搜索
    背景:
    阅读新闻

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

    [日期:2018-08-17] 来源:infoq.com  作者:Andy ,译者 无明 [字体: ]

    奥门新萄京官方正版 www.arianalance.com 过去几天,我一直在浏览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),它深入探讨了哈希函数冲突的问题。

    重要链接:

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

    Linux公社的RSS地址:http://www.arianalance.com/rssFeed.aspx

    本文永久更新链接地址http://www.arianalance.com/Linux/2018-08/153544.htm

    linux
    相关资讯       String.hashCode() 
    本文评论   查看全部评论 (0)
    表情: 表情 姓名: 字数

           

    评论声明
    • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
    • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
    • 本站管理人员有权保留或删除其管辖留言中的任意内容
    • 本站有权在网站内转载或引用您的评论
    • 参与本评论即表明您已经阅读并接受上述条款