java - 为什么 String hashCode 没有大小限制？

Question

它困扰了我一段时间，但我还没有找到任何令人信服的答案，那么为什么 Java String 中的 hashCode 函数没有任何大小限制？下面是我发现的实现 here :

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

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

首先，我了解临时变量 h 的用法，这在多线程中使用 String 时很有意义。其次我们都知道上面的实现不能避免散列冲突(没有hashCode实现可以)，所以基本上我们应该把这个功能当作“性能改进”而已，这对哈希表或类似结构很有用.

如果是这样，那为什么允许我们有例如100 MB 字符串，我们根据所有 字符计算哈希？增加一些限制不是更有意义吗？ 32/128 甚至可能是 1024 个字符但不是整个 value.length？是的，如果我们有两个不同的字符串，它们的前缀与我们的限制一样长，那么我们就会发生哈希冲突，但是无论如何我们都无法避免冲突，所以从性能的角度来看，我个人会将 for 循环更改为类似以下内容:

int limit = value.length > 32 ? 32 : value.length;
for (int i = 0; i < limit; i++) {
    h = 31 * h + val[i];
}

你怎么看？

Answer 1

我想到了几个可能的原因:

1. 字符串仅在开头或结尾处变化是很常见的，例如所有 StackOverflow 问题 URL 都以“https://stackoverflow.com/questions/”开头。因此，将 hashCode 限制为仅字符子集会导致不必要的冲突，并且对于某些字符串集会导致许多冲突。您提出的算法会导致每个 stackoverflow 问题 URL 都具有相同的 hashCode!

2. hashCode 速度快且可内存，目前尚不清楚将 hashCode 限制为某个常量长度是否会带来显着的性能改进，尤其是因为它总是先于创建字符串(O(n) 操作)，并且通常随后调用 equals(也为 O(n))。

3. 遗留原因。 String.hashcode指定使用特定算法。现有应用程序依赖于此规范。即使现在认为有必要进行这种优化，也无法在不破坏向后兼容性的情况下进行。