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

Question

我一直很困惑，但是我还没有找到令人信服的答案，那么为什么Java中的String的hashCode函数没有任何大小限制？以下是我在这里找到的实现：

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时很有意义。其次，我们都知道上述实现无法避免哈希冲突（没有哈希码实现可以避免），所以基本上我们应该将此函数视为仅用于“性能改进”，这对于哈希表或类似结构很有用。

如果是这样，那么为什么我们要允许计算基于所有字符的哈希值，例如100MB的字符串？难道不限制一下吗？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];
}

你觉得怎么样？

- LLL

---

如果你在谷歌上搜索URL的历史，会发现Java以前的hashCode是有限制的 :) - dehasi

通过限制用于创建哈希码的字符数量，您试图解决的问题是什么？ - Ankit Deshpande

@dehasi，从你分享的文章中并不是很清楚，因为它更像是一个URL问题，可能只使用了hashCode而没有后续的equals检查，但我已经理解了你的意思，谢谢！ - LLL

最终我找到了关于Java字符串哈希和URL的故事。这本书是Kernighan＆Pike的《编程实践》第2.9章“哈希表”。 - dehasi

@dehasi 谢谢，我已经检查过了，确实提到了URL示例。 - LLL

Answer 1

有几个可能的原因：

1. 字符串通常只在开头或结尾处有所不同，例如所有 StackOverflow 问题的 URL 都以 "https://stackoverflow.com/questions/" 开头。将 hashCode 限制为仅使用字符子集将导致不必要的碰撞，对于某些字符串集会导致许多碰撞。你提出的算法将导致每个 stackoverflow 问题 URL 具有相同的 hashCode ！

2. hashCode 是快速并且是记忆化的，不清楚将 hashCode 限制为某个恒定长度是否会带来明显的性能改进，特别是它总是先创建 String（一个 O(n) 操作），然后经常跟随一个调用 equals （也是 O(n)）。

3. 历史原因。 String.hashcode 的使用要求采用特定算法。现有应用程序依赖此规范。即使现在认为这种优化是必要的，也不能进行改变而不破坏向后兼容性。

- MikeFHay

---

谢谢回答。对于＃1，我明白了，尽管我认为一些合理的限制，例如1024，应该足以解决大多数此类问题。或者可能是一些花哨的代码，它总是会得到32个字符，但不总是前32个。对于更大的字符串，它可以获取第1个，第1000个，第2000个等（可以使用模运算完成）。对于＃2，我并不是说它会带来明显的好处，但由于哈希码是惰性计算的，即使创建字符串是O（n），为什么不具有潜在的更好的hashCode实现呢？至于＃3，我同意现在更改可能会有问题，但我只是好奇。 - LLL

无论如何，你总结了几个可能的原因，所以我会接受你的答案，谢谢！ - LLL