java - Java String 哈希码溢出的后果

Question

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

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

Answer 1

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

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

虽然如果程序员不知道此属性，这可能会导致逻辑错误或其他困难，但这是 JVM 的指定行为。

在计算哈希码时，您无需担心 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 的信息中计算出来(但请参见上文)。当然，这会影响性能，因此您应该相应地设计您的程序。

• “自由”碰撞与 hashCode() 实现的质量有很大关系，而与字符串的大小关系不大。用于生成哈希码的算法应该能够产生良好的分布。什么是“好的散列函数”尚不清楚，但这是数学理论家的主题。幸运的是，定义一个“足够好”的哈希函数并不难，即使它可能不是“最先进的”(参见 Effective Java，第 2 版；J. Bloch)。