Java中的String.hashCode()方法可能有問題,？

xkl135 2018-08-11

展開全文

過去幾天，我一直在瀏覽 Reddit 上的一篇文章,。這篇文章看得我要抓狂了,。文章指出，Java 中的 String.hashCode() 方法（將任意長度的字符串對象映射成 32 位 int 值）生成的哈希值存在沖突,。文章作者似乎對這個問題感到很驚訝,，并聲稱 String.hashCode() 的算法是有問題的。用作者自己的話說：

不管使用哪一種哈希策略,，沖突都是不可避免的,，但其中總有相對較好的哈希也有較差的哈希。你可以認為 String 中的哈希是比較差的那種,。

文章鏈接如下：

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

作者的措辭帶有相當強烈的意味,，并且已經(jīng)證明了很多奇怪的短字符串在生成哈希時會產(chǎn)生沖突。（文章中提供了很多示例，例如!~ 和'_）,。眾所周知,，32 位字符串哈希函數(shù)確實會發(fā)生很多沖突，但從經(jīng)驗來看,，在真實的場景中,，String.hashCode() 能夠很好地管理哈希沖突。

那么“差”的哈希是什么樣子的呢,？而“好”的哈希又是什么樣子的,？

一點理論

32 位哈希只能占用 2^32 = 4,294,967,296 個唯一值。因為字符串中可以包含任意數(shù)量的字符,，所以可能的字符串顯然要比這個數(shù)字多得多,。因此，根據(jù)鴿子原則,，必須會存在沖突,。

但沖突的可能性有多大？

著名的生日問題表明,，對于 365 個可能的“哈希值”,，在哈希沖突可能性達到 50％之前，必須計算出 23 個唯一哈希值,。如果有 2^32 個可能的哈希值,，那么在達到 50％的哈希沖突可能性之前，必須計算出大約 77,164 個唯一哈希值,。根據(jù)這個近似公式：

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

對于給定數(shù)量的獨立哈希,，預計會發(fā)生多少次沖突？所運的是,，維基百科提供了一個封閉式方程式：

def count(d, n):

    return n - d   d * ((d - 1) / d)**n

這種封閉式的解決方案可用于在實際的哈希函數(shù)表現(xià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 個哈希，出現(xiàn) 356 次沖突,。從理論上講,，“公平”的哈希函數(shù)應該只會產(chǎn)生 25.33 次沖突。因此,，String.hashCode() 產(chǎn)生的沖突是公平哈希函數(shù)的 14.05 倍：

356.0 / 25.33 ≈ 14.05

不過,，每 10,000 個哈希出現(xiàn) 8 次沖突的概率仍然是個不錯的成績。

那么長字符串值的結(jié)果怎樣,？使用莎士比亞全集中的句子（鏈接見文末）會產(chǎn)生以下輸出：

$ 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 個哈希，出現(xiàn) 1 次沖突?！肮健惫：瘮?shù)將在這些數(shù)據(jù)上產(chǎn)生 1.44 次沖突,，因此 String.hashCode() 優(yōu)于公平哈希函數(shù)，沖突可能性是公平哈希函數(shù)的 69.4％：

1 / 1.44 ≈ 0.694

也就是說,，每 100,000 個哈希產(chǎn)生不到 1 個沖突,，這個成績是極好的。

一點解釋

顯然,，String.hashCode() 不是唯一的,，但它不能變成唯一。對于短字符串,，它與理論平均值差得比較遠,，但它確實做得還不錯。對于長字符串,，它可以輕松打敗平均理論值,。

總得來看，它對于預期目的的字符串而言是具備唯一性的,，可以將字符串很好地發(fā)布在哈希表中,。

最后，我認為 String.hashCode() 是具備唯一性的,，至少它足夠“好”,。