Java中用于文本字符串的64位散列函数是什么?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (20)

我正在寻找一个散列函数:

  1. 很好地扫描文本字符串(例如很少碰撞)
  2. 用Java编写,并且被广泛使用
  3. Bonus:在几个字段上工作(而不是我连接它们并在连接字符串上应用散列)
  4. Bonus:有一个128位的变种。
  5. Bonus:不占用CPU。
提问于
用户回答回答于

为什么不使用long默认的变体String.hashCode()(一些真正聪明的人肯定会努力使其高效 - 而不是提及已经看过这些代码的成千上万的开发人员的眼睛)?

// 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 Edit:

正如我在@brianegge的回答中所提到的那样,对于超过32位的哈希,没有太多的用例,对于超过64位的哈希,很可能没有单一的哈希。

我可以想象一个巨大的散列表分布在数十台服务器上,可能会存储数百亿的映射。对于这种情况,@brianegge在这里仍然有一个有效的点:32位允许2 ^ 32(大约43亿)不同的散列键。假设一个强大的算法,你应该仍然有很少的碰撞。使用64位(18,446,740.73亿不同的密钥),无论你需要什么疯狂的场景,你都可以保存。想想128位密钥的使用情况(340,282,366,920,938,463,463,374,674,347,431亿个可能的密钥)几乎是不可能的。

要将几个字段的散列组合起来,只需执行XOR乘以一个素数并添加它们即可:

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

这个小素数是为了避免开关值相同的哈希码,即{'foo','bar'}和{'bar','foo'}不相等,并且应该有不同的哈希码。XOR不好,因为如果两个值相等,它将返回0。因此,{'foo','foo'}和{'bar','bar'}将具有相同的哈希码。

用户回答回答于

扫码关注云+社区