java - 更坏情况的时间复杂度 put/get HashMap

Question

当 Hashmap 的键的哈希码始终相等时，Hashmap 的最坏情况时间复杂度是多少。

在我的理解中:由于每个键都有相同的哈希码，它总是会进入同一个桶并循环遍历它以检查 equals 方法，所以对于 get 和 put 来说，时间复杂度应该是 O(n)，我说得对吗？

我在看这个HashMap get/put complexity但它没有回答我的问题。

也在这里 Wiki Hash Table他们说插入的最坏情况时间复杂度是O(1)，而获取 O(n) 为什么会这样？

Answer 1

是的，在最坏的情况下，您的 HashMap 将退化为链表，并且您将因查找以及插入和删除而遭受 O(N) 惩罚，这两者都需要查找操作(感谢评论指出我之前回答中的错误)。

有一些方法可以减轻最坏情况下的行为，例如使用自平衡树而不是桶溢出的链表 - 这将最坏情况下的行为减少到 O(logn) 而不是 O( n).