java - 为什么Java中的String.hashCode()会有很多冲突？

Question

为什么String.hashcode()会有这么多冲突？

我正在阅读jdk1.6中的String.hashCode()，下面是代码

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

这看起来让我很困惑，因为它有很多冲突；虽然它不需要是唯一的(我们仍然可以依赖equals())，但是更少的冲突意味着更好的性能，而无需访问链表中的条目。

假设我们有两个字符，那么只要我们能找到两个匹配下面等式的字符串，那么我们就会有相同的 hashcode()

a * 31 +b = c * 31 +d

很容易得出结论 (a-c) * 31 = d-b 举个简单的例子，让 a-c = 1 和 d-b = 31； 所以我写了下面的代码进行简单的测试

public void testHash() {
    System.out.println("A:" + (int)'A');
    System.out.println("B:" + (int)'B');
    System.out.println("a:" + (int)'a');

    System.out.println("Aa".hashCode() + "," + "BB".hashCode());
    System.out.println("Ba".hashCode() + "," + "CB".hashCode());
    System.out.println("Ca".hashCode() + "," + "DB".hashCode());
    System.out.println("Da".hashCode() + "," + "EB".hashCode());        
}

它将在结果下方打印，这意味着所有字符串都具有相同的 hashcode()，并且很容易在循环中完成。

A:65 
B:66
a:97
2112,2112
2143,2143
2174,2174
2205,2205

更糟糕的是，假设我们在字符串中有 4 个字符，根据算法，假设前 2 个字符产生 a2，第二个 2 个字符产生 b2； 哈希码仍然是 a2 * 31^2 + b2 因此，当 2 个字符串之间的 a2 和 b2 相等时，我们将获得更多与 hashcode() 冲突的字符串。 例如“AaAa”、“BBBB”等； 那么我们将有6个字符，8个字符......

假设大多数时候我们在字符串中使用 ascii 表中的字符，该字符串将用于 hashmap 或 hashtable，那么这里选择的素数 31 肯定太小了；

一个简单的解决方法是使用更大的素数(幸运的是，257 是素数)可以避免这种冲突。当然，如果字符串很长，选择一个太大的数字会导致返回的 int 值溢出，但我假设大多数时候用作键的字符串不是那么大？ 当然，它仍然可以返回一个 long 值来避免这种情况。

下面是我修改后的 Betterhash() 版本，可以轻松解决此类冲突 通过运行代码，它会打印出低于值的值，这可以有效地解决这个问题。

16802,17028
17059,17285
17316,17542
17573,17799

但是为什么 jdk 不修复呢？谢谢。

@Test
public void testBetterhash() {
    System.out.println(betterHash("Aa") + "," + betterHash("BB"));      
    System.out.println(betterHash("Ba") + "," + betterHash("CB"));
    System.out.println(betterHash("Ca") + "," + betterHash("DB"));
    System.out.println(betterHash("Da") + "," + betterHash("EB"));
}

public static int betterHash(String s) {
    int h = 0;
    int len = s.length();

    for (int i = 0; i < len; i++) {
        h = 257*h + s.charAt(i);
    }
    return h;
}

Answer 1

我刚刚散列了 58000 个英语单词(找到 here)，全小写，首字母大写。知道撞了多少？二:“ sibling ”和“德黑兰”(“德黑兰”的另一种拼写)。

就像你一样，我选取了一个可能的字符串的子域(在我的情况下可能是一个)，并分析了它的 hashCode 冲突率，并发现它具有示范性。谁说你的可能字符串的任意子域比我的更适合优化？

编写这个类的人必须知道他们无法预测(也因此优化)他们的用户将使用字符串作为键的子域。所以他们选择了一个散列函数，它在字符串的整个域上均匀分布。

如果你有兴趣，这是我的代码:

Map<Integer, List<String>> collisions = Files.lines(Paths.get(System.getProperty("user.home")+ "/corncob_lowercase.txt"))
    .flatMap(word -> Stream.of(word, word.substring(0, 1).toUpperCase() + word.substring(1)))
    .collect(Collectors.groupingBy(String::hashCode))
    .entrySet()
    .stream()
    .filter(e -> e.getValue().size() > 1)
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

System.out.printf("Number of collisions: %d%n", collisions.size());
collisions.forEach((hash, words) -> System.out.printf("%d: %s%n", hash, words));

编辑

顺便说一句，如果您好奇，与 String.hashCode 的 1 次相比，使用哈希函数的相同测试有 13 次冲突。