哈希表真的可以是 O(1) 吗？

哈希表可以实现 O(1) 似乎是常识，但这对我来说从来没有意义。有人可以解释一下吗？我想到了以下两种情况：

A. 该值是一个小于哈希表大小的 int。因此，该值是它自己的哈希值，因此不存在哈希表。但即使有，也会是 O(1) 并且效率仍然很低。

B. 您必须计算该值的哈希值。在这种情况下，所查找数据的大小的顺序是 O(n)。在完成 O(n) 工作后，查找可能是 O(1)，但在我看来仍然是 O(n)。

除非您有完美的哈希或大型哈希表，否则每个桶可能有多个项目。因此，无论如何，它在某个时刻都会演变为小型线性搜索。

我认为哈希表很棒，但我没有得到 O(1) 指定，除非它只是理论上的。

维基百科的哈希表的文章 http://en.wikipedia.org/wiki/Hash_table始终引用恒定的查找时间并完全忽略哈希函数的成本。这真的是一个公平的措施吗？

Edit:总结一下我学到的东西：

• 从技术上讲这是正确的，因为散列函数不需要使用密钥中的所有信息，因此可以是恒定时间，并且因为足够大的表可以将冲突降低到接近恒定时间。

• 在实践中确实如此，因为随着时间的推移，只要选择哈希函数和表大小以最小化冲突，它就会起作用，即使这通常意味着不使用恒定时间哈希函数。

这里有两个变量，m 和 n，其中 m 是输入的长度，n 是哈希中的项目数。

O(1) 查找性能声明至少做出两个假设：

• 您的对象可以在 O(1) 时间内比较相等。
• 哈希冲突很少。

如果您的对象大小可变，并且相等性检查需要查看所有位，那么性能将变为 O(m)。然而，哈希函数不必是 O(m) - 它可以是 O(1)。与加密哈希不同，字典中使用的哈希函数不必查看输入中的每一位来计算哈希。实现可以自由地仅查看固定数量的位。

对于足够多的项目，项目的数量将变得大于可能的散列数量，然后您将遇到冲突，导致性能上升到 O(1) 以上，例如，对于简单的链表遍历，O(n)（或 O(n *m) 如果两个假设都是假的)。

在实践中，尽管 O(1) 声明在技术上是错误的，但大约对于许多现实世界的情况都是如此，特别是上述假设成立的情况。