7

在查看openjdk-1.6 的 java.lang.String 的源代码时，我看到 String.hashCode() 使用 31 作为素数并计算

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

现在我看这个的原因是我想到的问题是比较 String.equals 中的 hashCodes 是否会使 String.equals 显着更快。但是现在看hashCode，我想到了以下问题：

  • 更大的素数是否有助于更好地避免冲突，至少对于短字符串来说，例如“BC”与“Ab”具有相同的哈希值（因为 ascii 字母位于 65-122 区域，所以不会是素数比那个工作更好）？
  • 使用 31 作为素数是有意识的决定，还是只是因为它很常见而随机使用？
  • 给定固定字符串长度，哈希冲突的可能性有多大？这个问题的标题是原始问题，比较 hashCodes 和字符串长度有多好已经可以辨别字符串，以避免比较实际内容。
  • 有点离题，也许：String.equals 没有将 hashCodes 比较为额外的快捷方式有充分的理由吗？
  • 离题一点：假设我们有两个内容相同但实例不同的字符串：有没有办法在不实际比较内容的情况下断言相等？我猜不会，因为以某种方式进入字符串长度，空间会爆炸成大小，我们将不可避免地发生冲突，但是一些限制呢 - 只有某个字符集，最大字符串长度......以及我们需要限制多少字符串空间能有这样的散列函数吗？
4

1 回答 1

9

更大的素数是否有助于更好地避免冲突，至少对于短字符串来说，例如“BC”与“Ab”具有相同的散列（因为 ascii 字母位于 65-122 区域，所以不会是素数比那个工作更好）？

字符串中的每个字符可以取 65536 个值 (2^16)。因此，1 或 2 个字符的字符串集大于 1 或 2 个字符的字符串的数量，int并且任何哈希码计算方法都会对 1 或 2 个字符长的字符串产生冲突（我想这符合短字符串的条件）。

如果你限制你的字符集，你可以找到减少冲突次数的哈希函数（见下文）。

请注意，良好的散列还必须提供良好的输出分布。隐藏在此代码中的评论主张使用 33 并给出以下原因（强调我的）：

如果比较变体的 chi^2 值 [...]，则数字 33 甚至没有最好的值。但是数字 33 和其他一些同样好的数字，如 17、31、63、127 和 129，仍然比可能的乘法器中的剩余数字有很大的优势：它们的乘法运算可以用基于只需一个班次加上一个加法或减法运算。而且因为散列函数既要分布好，又要计算得非常快，所以应该首选这几个数字。

现在这些公式是不久前设计的。即使现在看起来它们并不理想，也无法更改实现，因为它记录在 String 类的合同中。

使用 31 作为素数是有意识的决定，还是只是因为它很常见而随机使用？

为什么 Java 的 String 中的 hashCode() 使用 31 作为乘数？

给定固定字符串长度，哈希冲突的可能性有多大？

假设每个可能的 int 值都有相同的概率成为哈希码函数的结果，那么冲突的概率是 1 in 2^32。

是否有充分的理由 String.equals 不将 hashCodes 作为附加快捷方式进行比较？

为什么String中的equals方法不使用hash？

假设我们有两个内容相同但实例不同的字符串：有没有办法在不实际比较内容的情况下断言相等？

没有对字符串的任何限制，就没有。您可以对字符串进行实习，然后检查引用相等性 ( ==)，但如果涉及许多字符串，则效率可能会很低。

我们需要多少限制字符串空间才能拥有这样的哈希函数？

如果您只允许使用小写字母（26 个字符），您可以设计一个散列函数，为长度为 0 到 6 个字符（包括）（sum(i=0..6) (26^i) = 3.10^8）的任何字符串生成唯一散列。

于 2013-07-17T09:30:17.447 回答