java - 如何确保/强制在 HashMap 中平均分配？

Question

HashMap 数据结构根据 Key 的哈希码在其存储桶之间分配密钥。大多数情况下，如果散列算法非常好，所有密钥都将分布在不同的桶中。但是，如果所有键都返回相同的哈希码怎么办？插入/检索操作的顺序为 O(n)。

如果我正在实现自己的 HashMap，我将如何（或者我应该怎么做）确保桶之间的平等分配？有没有办法？

Answer 1

但是，如果所有键都返回相同的哈希码怎么办？

那么你就输掉了比赛，对此你无能为力。

不过不用担心，因为您的数据结构实际上并不关心——您的数据结构的用户hashCode可能会关心，但在第一种情况下，他们是负责病态实现的人。

从理论上讲，即使是恶意选择的输入值也可以通过通用散列合理均匀地分布，但在 Java 中，这确实不是一种选择。

Answer 2

在密钥上运行类似 DES 的东西来生成哈希。一个体面的加密算法可以保证结果看起来是随机的。