如何在哈希冲突后检索值

Question

我在很多地方都读到，在 Java 中发生哈希冲突后，它在内部使用链接 list/tree，基于哈希的数量 collisions.Till 这很好，

但是如何使用 'key'

取回期望值

Answer 1

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

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

看看这张图 (source):

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

---

请注意，Javas HashSet 和 HashMap 并不是如图所示的纯哈希表。他们将在特定阈值后切换到内部 red-black tree。