java - HashMap 中的 LinkedList 搜索性能

Question

我几乎可以肯定我在某处看到过这样的问题，但我找不到它。如果为了在 LinkedList 上执行等于迭代来查找键，那么 HashMap 的性能是 O(1) 的，而这个过程是 O(n)。

编辑:

我发现 get() 的性能实际上介于没有碰撞时的 O(1) 和每个键都发生碰撞时的 O(n) 之间。这样对吗？

Answer 1

get 的预期性能是O(1)。预期性能是在 hashCode 方法将键均匀分布在 HashMap 的桶中的假设下计算的，因此每个链表的平均大小(即平均数每个桶中的条目数)非常小，因此我们可以假设每个这样的列表都可以在一个小常数的时间范围内遍历。

在最坏的情况下，如果错误的 hashCode 将所有键映射到同一个存储桶，get 将花费 O(n) .