为什么Java中的String.hashCode（）有很多冲突？[已关闭]

string hashcode java

2022-09-01 08:04:01

为什么 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（）），但更少的冲突意味着更好的性能，而无需访问链表中的条目。

假设我们有两个字符，那么只要我们能找到两个匹配的字符串，那么我们将有相同的哈希码（）

a * 31 +b = c * 31 +d

很容易得出结论，举一个简单的例子是使a-c = 1和d-b = 31;所以我写了下面的代码用于简单测试(a-c) * 31 = d-b

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());        
}

它将在下面打印结果，这意味着所有字符串都具有相同的哈希码（），并且很容易在循环中执行此操作。

更糟糕的是，假设我们在字符串中有4个字符，根据算法，假设前2个字符产生a2，第2个2个字符产生b2;哈希码仍然是这样的，当a2和b2等于2个字符串之间时，我们将得到更多具有哈希码（）冲突的字符串。这样的例子是“AaAa”，“BBBB”等;那么我们将有6个字符，8个字符......a2 * 31^2 + b2

假设大多数时候我们在字符串中使用ascii表中的字符，这些字符将在哈希映射或哈希表中使用，那么这里选择的素数31肯定太小了;

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

以下是我的 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;
}

答案 1

我刚刚散列了58千个英语单词（在这里找到），都是全小写的，第一个字母也是大写的。知道有多少相撞了吗？二：“兄弟姐妹”和“德黑兰”（“德黑兰”的另一种拼写）。

就像你一样，我拿了一个可能字符串的子域（在我的情况下可能是一个），并分析了它的哈希码冲突率，并发现它是典型的。谁能说你的任意子域的可能字符串是比我的更好的优化选择？

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

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

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));

编辑

顺便说一句，如果你很好奇，与哈希函数的相同测试有13次碰撞，而's为1。String.hashCode

答案 2

很抱歉，我们需要对这个想法泼一些冷水。

你的分析太简单了。你似乎已经挑选了一个字符串子集，旨在证明你的观点。这并不能证明在所有字符串的域中，冲突次数（统计上）高于预期。
在他们正确的头脑中，没有人会期望String.hashCode是高度无冲突^的1。它根本没有考虑到这一点。（如果您想要高度无冲突的哈希，请使用加密哈希算法...并支付费用。String.hashCode（）被设计为在所有字符串的域中都相当不错...而且速度很快。
假设你可以陈述一个更强有力的案例，这不是陈述它的地方。您需要向重要的人提出这个问题 - Oracle的Java工程团队。
自 Java 1.2 以来，当前的算法一直是 javadoc 规范的一部分。（该算法几乎肯定可以追溯到Java 1.0及更早版本。如果更改了算法，则对于某些应用程序而言，这将是一个重大更改。这可能足以扼杀这个想法。String::hashCodeString
Java工程团队将权衡这种变化的优势与实现它的成本，对他们和每个Java用户来说都是如此。

用户的成本将包括处理各种潜在的性能和安全问题，以及迁移任何依赖于哈希码的存储数据。或者拥有更多无法实际移植到最新版本Java的旧式应用程序的成本。

^{1 - “高度无碰撞的哈希”，是一个想法/术语，我为了这个答案的目的从空中拉出来。不好意思。但是，要点是，2个字符串的哈希码冲突的概率应该与它们的相关性无关。例如，“AA”和“bz”由于具有相同的长度而相关。显然，这个想法需要更多的思考。同样明显的是，我所说的意义上的“相关性”是不可衡量的......有点像柯尔莫哥洛夫的复杂性。}