过去几天，我一直在浏览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();
}
}