java - 大O中普通Hash表和java的HashMap的区别

Question

Hash table wiki 条目将其 Big O 列为:

搜索:O(n)
插入:O(n)
删除:O(n)

当一个 java HashMap 被 Big O 列为:

得到:O(1)
放:O(1)
移除:O(1)

有人能解释一下为什么 Big O 在概念和实现之间存在差异吗？我的意思是，如果有一个最坏情况为 O(1) 的实现，那么为什么这个概念中有 O(n) 的可能性？

Answer 1

最坏的情况是 O(n)，因为您放入 HashMap 的每个条目都可能产生相同的哈希值(假设为 10)。这会为每个条目产生冲突，因为每个条目都放在 HashMap[10] 中。根据实现的冲突解决策略，HashMap 要么在索引 10 处创建一个列表，要么将条目移动到下一个索引。

然而当再次访问条目时，哈希值用于获取HashMap的初始索引。由于在每种情况下都是 10，因此 HashMap 必须解决这个问题。