如何在哈希冲突后检索值

Question

我在很多地方都读到过，在 Java 中发生哈希冲突后，它会根据哈希冲突的数量在内部使用链表/树。直到这很好，

但是如何使用“键”取回预期值

Answer 1

它只是迭代存储在该存储桶中的链表并检查使用的equals没有冲突的元素。

其运行时间是线性的，但仅与存储在该特定存储桶中的项目数量呈线性关系，因此只要存储桶保持足够的平衡就可以了。

看看这个插图（来源）：

所以实现将确保一个get操作，即使它有冲突，最终返回正确的结果。

请注意，JavasHashSet和HashMap不是如图所示的纯哈希表。在达到一定的阈值后，它们会在内部切换到红黑树。