过去几天, 我一直在浏览 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()是具备唯一性的, 至少它足够 "好".
来源: http://www.tuicool.com/articles/i6zqA3v