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

Question

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

如果我正在实现自己的 HashMap，我将如何(或我应该做什么)来确保桶之间的平等分配？有办法吗？

Answer 1

But what if all keys return the same hashcode?

那你就输了，对此你无能为力。

不过不用担心，因为您的数据结构真的不在乎 – 您的数据结构的 用户 可能会在意，但他们才是对病态的 hashCode 负责的人第一种情况下的实现。

理论上，即使是恶意选择的输入值也可以使用 universal hashing 合理均匀地分配。 ，但在 Java 中，这确实不是一个选项。