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

Question

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

一个。 该值是一个小于哈希表大小的int。因此，该值是它自己的哈希，所以没有哈希表。但即使有，也将是 O(1) 并且仍然效率低下。

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

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

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

维基百科的 article for hash tables始终引用恒定的查找时间并完全忽略哈希函数的成本。这真的是一个公平的衡量标准吗？

---

编辑:总结我学到的东西:

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

• 这在实践中是正确的，因为随着时间的推移，只要选择哈希函数和表大小以最大限度地减少冲突，它就会成功，即使这通常意味着不使用恒定时间哈希函数。

Answer 1

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

O(1) 查找性能声明至少有两个假设:

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

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

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

在实践中，虽然 O(1) 声明在技术上是错误的，但对于许多现实世界的情况，尤其是上述假设成立的情况，大约是正确的。