当 Hashmap 的键的哈希码始终相等时，它的最坏情况时间复杂度是多少。
根据我的理解：由于每个键都有相同的哈希码，因此它总是会进入同一个存储桶并循环遍历它以检查 equals 方法，因此对于 get 和 put 时间复杂度应该是 O(n)，我对吗？
我正在看这个HashMap 获取/放置复杂性 https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity但它没有回答我的问题。
也在这里维基哈希表 http://en.wikipedia.org/wiki/Hash_table他们指出插入的最坏情况时间复杂度是O(1)对于 get O(n) 为什么会这样呢？
是的，在最坏的情况下，你的哈希映射将退化为链表，并且你将遭受查找以及插入和删除的 O(N) 惩罚，这两者都需要查找操作（感谢指出的评论我之前的回答中的错误）。
有一些方法可以减轻最坏情况的行为，例如使用自平衡树而不是用于存储桶溢出的链表 - 这可以将最坏情况的行为减少到 O(logn) 而不是 O(n)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
