更糟糕的案例时间复杂性放/获得HashMap

Question

当Hashmap的密钥的哈希码总是相等时,Hashmap的最坏情况时间复杂度是多少.

在我的理解中:由于每个密钥都具有相同的哈希码,它将始终转到同一个桶并循环通过它来检查equals方法,因此对于get和put,时间复杂度应为O(n),我是对的吗？

我正在看这个HashMap获取/放置复杂性,但它没有回答我的问题.

另外在这里Wiki Hash Table他们说明插入的最坏情况时间复杂度是O(1)而对于得到O(n)为什么会这样呢？

Answer 1

是的,在最坏的情况下,您的哈希映射将退化为链接列表,您将遭受查询以及插入和删除的O(N)惩罚,这两者都需要查找操作(感谢指出的注释)我之前的答案中的错误).

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

Answer 2

在 Java 8 的 HashMap 实现中（当键类型实现时Comparable）：

使用平衡树处理频繁的 HashMap 冲突：在高哈希冲突的情况下，这会将最坏情况下的性能从 O(n) 提高到 O(log n)。

从这里。

Answer 3

插入时，将其放在桶中的哪个位置并不重要，因此您可以将其插入到任何位置，因此插入的时间复杂度为 O(1)。

查找的时间复杂度为 O(n)，因为您必须循环遍历每个对象并验证它是否是您要查找的对象（如您所述）。