java - 两个不同长度的字符串可以有相同的哈希码吗？

Question

虽然我知道两个不同的字符串可以返回相同的哈希码，但我一直无法找到有关两个不同长度这样做的任何信息。这是否可能，如果可以，将不胜感激。这是使用 java hashcode 函数，以防发生任何变化。

Answer 1

哈希码分布在 int 的空间中。 int 的可能值只有 2^32 = ~40 亿 个。可能的字符串远不止这个数量，因此根据鸽巢原理，必须存在多个具有相同哈希码的字符串。

但是，这并不能证明不同长度的字符串可能具有相同的哈希码，如下所述。 Java 使用公式 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 对字符串进行哈希处理。知道了这一点，就可以很容易地构造具有相同哈希码的不同长度的字符串:

令String s1 = "\001!"; 和String s2 = "@";。然后 s1.length() != s2.length() 但 s1.hashCode() == '\001' * 31 + '!' == 1 * 31 + 33 == 64 == s2.hashCode() == '@' == 64。

但是，让我再说一遍，int 的可能值有超过 4十亿 个，因此发生碰撞的概率很低，尽管没有你想象的那么低认为，因为 Birthday Paradox ，这表明在大约 77K 哈希值之后，您有大约 50% 的机会发生冲突(假设哈希值是随机分布的，这实际上取决于您的数据 - 如果您主要处理非常小的长度字符串，那么您将发生更频繁的冲突)。不过，每个使用哈希处理的数据结构都必须处理冲突(例如，常见的方法是在每个哈希位置使用链表)，或者处理数据丢失(例如在布隆过滤器中)。