哈希如何实现O(1)的搜索时间？

Question

当我们使用 HashTable 存储数据时，搜索时间为o(1)。我很困惑，能有人解释一下吗？

- algo-geeks

---

在哈希表中查找成本是摊销常数O(1) - 大多数情况下，我们只做恒定的工作，但偶尔（当发生冲突时）我们会进行一些直接比较，这些比较可以再次是二进制或线性搜索。 - RBT

Answer 1

这有点夸张——实际上可能需要更长时间，但通常也不会太久。

基本上，哈希表是一个包含所有要搜索的键的数组。每个键在数组中的位置由哈希函数决定，它可以是任何总是将相同输入映射到相同输出的函数。我们假设哈希函数为O(1)。

因此，当我们向哈希表插入东西时，我们使用哈希函数（称其为 h ）找到要放置它的位置，并将其放在那里。现在我们再插入另一件事情，再次进行哈希和存储。每次插入数据时，它都需要O(1)时间来插入它（因为哈希函数为O(1)）。

查找数据也是相同的。如果我们想要查找值x，我们只需找到h(x)，就能知道x在哈希表中的位置。所以我们也可以在O(1)的时间内查找任何哈希值。

现在来说谎言：以上是一个非常好的理论，但有一个问题：如果我们插入数据，而该数组的那个位置已经有其他数据了怎么办？除非你有一个完美哈希函数，否则没有任何保证哈希函数不会为两个不同的输入产生相同的输出（但这些很难生成）。因此，在插入时我们需要采取以下两种策略之一：

• 在数组的每个位置存储多个值（例如，每个数组槽都有一个链接列表）。现在当您进行查找时，到达正确的数组位置仍然是O(1)，但可能需要在线性时间内搜索（希望很短）链接列表。这称为“分离链接”。
• 如果你发现已经有值存在，再次进行哈希并找到另一个位置。重复此过程直至找到空闲的位置，将其放入其中。查找过程可以遵循相同的规则来查找数据。现在访问第一个位置仍然是O(1)，但是可能需要（但愿很短的）线性搜索来在散列表中跳转，直到找到所需的数据。这被称为“开放寻址”。

基本上，这两种方法仍然大多数情况下是O(1)，但会涉及到一些短暂的线性搜索。我们可以假设对于大多数情况来说，它仍然是O(1)。如果散列表变得太满，那么这些线性搜索可能会变得越来越长，此时就需要“重新哈希”，也就是创建一个更大的新散列表，并将所有数据插入其中。

- mgiuca

---

感谢您的解释。 - algo-geeks

感谢美丽地解释，还有其他避免冲突的技术，例如字典中基本使用的“链式法”、双散列等。+1 - TalentTuner

@user531802 没问题。如果您对这个答案感到满意，能否勾选“接受的答案”复选框呢？ - mgiuca

如果哈希表变得过于拥挤，线性搜索的时间会越来越长，那么就需要“重新哈希”，也就是创建一个更大的新哈希表。可以参考这个网站：https://dev59.com/THE95IYBdhLWcg3wSsGD，以获得更好的解释。 - RBT

从技术上讲，在位级别上，哈希或地址至少具有log(N)位，因此它的访问时间至少为O(log(N))。复杂性理论通常忽略位操作成本，以固定成本来保持分析的简单性。 - Real

Answer 2

如果哈希表中没有冲突，搜索只需O(1)时间，因此说在哈希表中搜索需要O(1)或恒定时间是不正确的。

查看MSDN上Hashtable的工作原理?

编辑

mgiuca很好地解释了它，我只想再添加一种避免冲突的技术，称为链接法（Chaining）。

在这种技术中，我们在每个位置维护一个值的链接列表，因此当发生冲突时，您的值将添加到该位置的链接列表中，因此当您搜索值时，可能需要在整个链接列表中搜索，因此在这种情况下，搜索将不是O(1)操作。

- TalentTuner