Java String上散列码溢出的后果

Question

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

另外,既然我可能有30k到80k之间的字符串,也许更多,那么通常的String hashcode是否足够无冲突？

Answer 1

(我知道会发生溢出,但作为哈希键,会发生什么)？

在Java中,原始类型的算术溢出和下溢不会引发运行时错误或异常.结果溢出的部分就完全丢失了.

如果程序员不知道此属性,则会导致逻辑错误或其他困难,但这是JVM的指定行为.

int计算哈希码时,您无需担心类型的溢出或下溢.溢出的位简直就丢失了.

这不会影响计算的哈希值的正确性或其分配给哈希桶的能力.

另外,既然我可能有30k到80k之间的字符串,也许更多,那么通常的String hashcode是否足够无冲突？

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

• Java字符串是不可变的.因此,String实例的哈希值只计算一次.之后,结果将缓存在实例中,以便后续调用hashCode()不会导致重复计算.这是有效的,因为字符串是不可变的,重新计算的值每次都是相同的.

• 实际上应该根据实例中的所有有意义的信息来计算哈希码.这意味着如果你的String包含20k的信息,那么哈希码应该从它的所有20k中计算出来(但参见上文).当然,有性能影响,所以你应该相应地设计你的程序.

• 碰撞'free'-ness与实现的质量有很大关系,hashCode()而与你的字符串大小关系不大.用于生成哈希码的算法应该能够产生良好的分布.什么是"好的散列函数"并不是精确已知的,而是数学理论家的主题.幸运的是,定义一个"足够好"的哈希函数并不难,即使它可能不是"最先进的"(参见Effective Java,2nd ed .; J. Bloch).

Answer 2

你误解了什么hashCode().它计算一个32位数,对于不同的值应该是不同的,但不保证是这样.怎么可能,那么哈希可能有超过2 ^ 32个不同的值.

对于a String,hashCode与字符串长度无关.任何hashCode都是任何字符串的有效hashCode,只要你总是得到相同String 的相同 hashCode,即hashCode()对同一个字符序列多次调用必须返回相同的值.

作为示例,这里是字符串的一些哈希码.

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)的字符串.