更糟糕的案例时间复杂性放/获得HashMap
当Hashmap的密钥的哈希码总是相等时，Hashmap的最坏情况时间复杂度是多少。
在我的理解中：由于每个密钥都具有相同的哈希码，它将始终转到同一个桶并循环通过它来检查equals方法，因此对于get和put，时间复杂度应为O（n），我是对的吗？
我正在看这个HashMap get / put复杂性，但它没有回答我的问题。
另外在这里Wiki Hash Table他们说明插入的最坏情况时间复杂度是O（1）而对于得到O（n）它为什么会这样？
是的，在最坏的情况下，您的哈希映射将退化为链接列表，您将遭受查询的O（N）惩罚，以及插入和删除，这两者都需要查找操作（感谢指出的注释）我之前的答案中的错误）。
有一些方法可以减轻最坏情况的行为，例如通过使用自平衡树而不是桶溢出的链表 – 这可以将最坏情况的行为减少到O（logn）而不是O（n）。
在Java 8的HashMap实现中：
处理频繁的HashMap与平衡树的碰撞：在高哈希冲突的情况下，这将改善从O（n）到O（log n）的最坏情况性能。
从这里开始 。
在open hashing中，您将拥有一个链接列表来存储具有相同哈希码的对象。 所以：例如，你有一个大小为4的散列表.1）假设你想要存储一个hashcode = 0的对象。然后对象将被映射到索引（0 mod 4 =）0。2）然后你再次想要使用hashcode = 8放置另一个对象。这个对象将被映射到index（8 mod 4 =）0，因为我们记得索引0已经填充了我们的第一个对象，所以我们必须把第二个放在第一个对象旁边。
[0]=>linkedList{object1, object2} [1]=>null [2]=>null [3]=>null
3）搜索的步骤是什么？ 1，你必须散列关键对象并假设它的hashcode是8，所以你将被重定向到index（8 mod 4 =）0，然后因为在同一个索引中存储了多个对象，我们必须搜索逐个列出所有存储的对象，直到找到匹配的对象或直到列表的末尾。 因为该示例有2个对象存储在相同的哈希表索引0中，并且搜索到的对象位于链表的末尾，因此您需要遍历所有存储的对象。 这就是为什么O（n）是最坏的情况。 当所有存储的对象都在哈希表中的相同索引中时发生最坏的情况。 所以它们将被存储在一个链表中，我们可能需要遍历所有链接列表来查找我们搜索到的对象。
希望对此有所帮助。
插入时，放入桶中的位置并不重要，因此您可以将其插入任何位置，因此插入为O（1） 。
查找是O（n）因为你必须遍历每个对象并validation它是你正在寻找的那个（如你所说）。