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) 的可能性？
最佳答案
最坏的情况是 O(n)，因为放入 HashMap 中的每个条目可能会产生相同的哈希值(比方说 10)。这会对每个条目产生冲突，因为每个条目都放在 HashMap[10] 中。根据所实现的冲突解决策略，HashMap 要么在索引 10 处创建一个列表，要么将条目移动到下一个索引。
然而，当再次访问该条目时，哈希值将用于获取 HashMap 的初始索引。由于每种情况都是 10，HashMap 必须解决这个问题。
关于java - Big O中一般Hash表和java的HashMap的区别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20657399/