java - 什么是 Java 中用于文本字符串的好的 64 位散列函数？

Question

我正在寻找一个哈希函数:

1. 很好地散列文本字符串(例如，很少发生冲突)
2. 用 Java 编写，应用广泛
3. 奖励:适用于多个字段(而不是我将它们连接起来并在连接的字符串上应用哈希)
4. 奖励:有 128 位版本。
5. 奖励:不占用 CPU。

Answer 1

为什么不使用默认 String.hashCode() 的 long 变体(一些非常聪明的人肯定会努力提高效率 - 更不用说已经看过这段代码的成千上万的开发者的眼睛)？

// adapted from String.hashCode()
public static long hash(String string) {
  long h = 1125899906842597L; // prime
  int len = string.length();

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

如果您正在寻找更多位，您可能会使用 BigInteger 编辑:

正如我在对@brianegge 答案的评论中提到的那样，超过 32 位的哈希用例并不多，而且对于超过 64 位的哈希，很可能没有一个用例:

I could imagine a huge hashtable distributed across dozens of servers, maybe storing tens of billions of mappings. For such a scenario, @brianegge still has a valid point here: 32 bit allow for 2^32 (ca. 4.3 billion) different hash keys. Assuming a strong algorithm, you should still have quite few collisions. With 64 bit (18,446,744,073 billion different keys) your certainly save, regardless of whatever crazy scenario you need it for. Thinking of usecases for 128 bit keys (340,282,366,920,938,463,463,374,607,431 billion possible keys) is pretty much impossible though.

要组合多个字段的哈希值，只需进行 XOR 将一个与一个素数相乘并相加:

long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);

其中的小素数是为了避免切换值的哈希码相等，即 {'foo','bar'} 和 {'bar','foo'} 不相等，应该有不同的哈希码。 XOR 不好，因为如果两个值相等，它会返回 0。因此，{'foo','foo'} 和 {'bar','bar'} 将具有相同的哈希码。