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

Question

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

哈希表可以实现O(1)，这似乎是常识，但这对我来说从来没有意义。谁能解释一下吗？以下是脑海中浮现的两种情况：

一个。该值小于哈希表的大小。因此，该值是它自己的散列，因此没有哈希表。但如果有，它将是O(1)，仍然是低效的。

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

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

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

维基百科散列表项目始终引用常量查找时间，并完全忽略哈希函数的成本。这真的是一个公平的措施吗？

---

编辑：总结一下我学到的东西：

• 从技术上讲，这是正确的，因为哈希函数不需要使用键中的所有信息，因此可以是常数时间，而且一个足够大的表可以将冲突降到几乎恒定的时间。

• 这在实践中是正确的，因为随着时间的推移，只要选择哈希函数和表大小来最小化冲突，它就能计算出来，尽管这通常意味着不使用固定时间哈希函数。

Answer 1

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

O(1)查找性能索赔至少有两个假设：

• 在O(1)时间内，您的对象可以是相等的。
• 会有很少的散列冲突。

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

对于足够多的项，条目的数量将大于可能的散列数，然后会出现冲突，从而导致性能高于O(1)，例如，对于简单的链表遍历(或者如果这两个假设都是错误的，则O(n*m)。

实际上，虽然O(1)的说法在技术上是错误的，但却是约对于许多真实世界的情况，尤其是上述假设成立的情况。

Answer 2

您必须计算哈希，所以查找的数据大小的顺序是O(N)。在你做O(N)工作后，查找可能是O(1)，但在我看来，这仍然是O(N)。

什么？散列单个元素需要恒定的时间。为什么还会有其他东西？如果你要插入n元素，那么是的，您必须计算n哈希，这需要线性时间.。要查找元素，只需计算要查找的内容的一个散列，然后使用该方法查找适当的桶。您不会重新计算哈希表中已经存在的所有内容的散列。

而且，除非您有一个完美的散列或一个大型哈希表，否则每个桶中可能有几个项，所以无论如何，它都会变成一个小的线性搜索。

不一定。桶不一定是列表或数组，它们可以是任何容器类型，比如平衡的BST。这意味着O(log n)最坏的情况。但这就是为什么选择一个好的散列函数以避免将太多的元素放入一个桶中是很重要的。正如KennyTM所指出的，平均来说，你仍然会得到O(1)时间，即使偶尔你要挖一个水桶。

当然，哈希表的权衡是空间复杂性。你用空间来交换时间，这似乎是计算科学中常见的情况。

---

您提到在其他注释中使用字符串作为键。您担心计算字符串的散列所需的时间，因为它由几个字符组成？正如其他人再次指出的那样，您不一定需要查看所有的字符才能计算哈希，尽管如果您这样做了，它可能会产生更好的哈希。在这种情况下，如果平均m键中的字符，您使用所有这些字符来计算散列，那么我想您是对的，这种查找将需要O(m)..如果m >> n那你可能有麻烦了。在这种情况下，你最好还是买个BST吧。或者选择更便宜的哈希功能。

Answer 3

散列是固定大小的-查找适当的散列桶是一个固定的成本操作。这意味着它是O(1)。

计算哈希不一定是一个特别昂贵的操作-这里我们不是在谈论加密散列函数。但那是顺便说的。哈希函数计算本身不依赖于数字。n元素；虽然它可能取决于元素中数据的大小，但这不是n指的是。因此，哈希的计算不依赖于n也是O(1)。