Java 字符串哈希码溢出的后果

Question

我最近在这里阅读了一些关于 Java String class' hashcode 的内容，但我没能找到这个信息：当字符串的长度大于 32 时会发生什么（我知道会发生溢出，但作为哈希键，会发生什么）？例如，我需要散列长度在 20 到 120 个字符之间的字符串，以将它们用作散列键。我需要使用 BigInteger 实现我自己的算法吗？

此外，由于我可能有 30k 到 80k 之间的字符串，也许更多，通常的字符串哈希码是否足够无冲突？

Answer 1

字符串没有溢出。只要您的进程的内存可以容纳，字符串就可以。任何 String 的 hashCode 都是一个 32 位整数。碰撞频率不应与字符串的长度相关。您不需要重新实现它。

Answer 2

(I know an overflow then happens, but as a hash key, what happens)?

在Java中，原始类型的算术上溢和下溢不会引发运行时错误或异常。结果溢出的部分直接丢失了。

虽然如果程序员没有意识到这一点，这可能会导致逻辑错误或其他困难属性，但这是 JVM 的指定行为。

计算hashcode时无需担心int类型的上溢或下溢。溢出的位只是丢失了。

这不会影响计算出的哈希值的正确性或其很好地分发到哈希桶的能力。

Also, since I might have between 30k and 80k strings, maybe more, is usual String hashcode collision-free enough?

一些可以方便记住的事情：

Java 字符串是不可变的。因此，String 实例的哈希值只计算一次。之后，结果被缓存在实例中，这样 hashCode() 的后续调用就不会导致重复计算。这是有效的，因为字符串是不可变的，每次重新计算的值都是相同的。
哈希码确实应该从一个实例中所有有意义的信息中计算出来。这意味着如果您的字符串包含 20k 的信息，则哈希码应该从所有 20k 的信息中计算出来（但请参见上文）。当然，这会影响性能，因此您应该相应地设计您的程序。
Collision 'free'-ness 与 hashCode() 实现的质量有很大关系，而与字符串的大小关系不大。用于生成哈希码的算法应该能够产生良好的分布。 "good hash function" 是什么并不确切知道，但它是数学理论家的主题。幸运的是，定义一个 "good enough" 的散列函数并不难，即使它可能不是 "state of the art"（参见 Effective Java，第二版；J. Bloch）。

Answer 3

您误解了 hashCode() 的作用。它计算出一个 32 位数字，应该对于不同的值是不同的，但不保证如此。怎么可能，那么可能有超过 2^32 个不同的值需要哈希。

对于String，hashCode与字符串长度无关。任何 hashCode 都是任何字符串的有效 hashCode，只要您始终获得相同字符串的 same hashCode，即为相同的字符序列多次调用 hashCode() 必须return相同的值。

例如，这里有一些字符串的哈希码。

0x00000000 = "".hashCode()
0x00000061 = "a".hashCode()
0x00000041 = "A".hashCode()
0x042628b2 = "Hello".hashCode()
0x6f8f80f1 = "Goodbye".hashCode()
0xdbacdd53 = "The quick brown fox jumps over the lazy dog".hashCode()
0x99eecd2e = "The quick brown fox jumps over the lazy dog!".hashCode()

注意最后两个是很长的 (>32) 字符串。

Java 字符串哈希码溢出的后果

Consequences of hashcode overflow on Java String

java

string

collision

hashcode