哈希如何有一个o（1）的搜索时间？

Question

当我们使用HashTable来存储数据时，据说搜索需要o（1）次。我很困惑，有人可以解释吗？

Answer 1

嗯，这是一个小位谎言 - 它可能需要更长的时间，但它通常不会。

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

所以当我们在散列表中插入一些东西时，我们使用散列函数（我们称之为h）来找到放置它的位置，并放在那里。现在插入另一个东西，哈希和存储。另一个。每次插入数据时，都需要O（1）次插入（因为散列函数是O（1）

查找数据是一样的如果我们想要查找一个值，x，我们只有找出^h（x）的，它告诉我们哪里X位于哈希表。因此，我们可以看一下在O（1），以及任何哈希值。

我们的谎言：上面是一个非常好的理论，有一个问题：如果我们插入数据，并且数组中已经存在某些东西？没有什么能保证散列函数不会为两个不同的输入产生相同的输出（除非你有一个perfect hash function，但这些都很难制作）。因此，当我们插入时，我们需要采取以下两种策略之一：

• 在数组中的每个点上存储多个值（比如说，每个数组插槽都有一个链接列表）。现在，当你进行查找时，它仍然是O（1）到达数组中的正确位置，但可能是一个线性搜索（希望是短的）链表。这被称为“分离链接”。
• 如果您发现某些东西已经存在，请再次散列并找到其他位置。重复，直到你找到一个空的地方，并把它放在那里。查找过程可以遵循相同的规则来查找数据。现在它仍然是O（1）到达第一个位置，但是有一个可能的（希望是短的）线性搜索在桌子上反弹，直到你找到你之后的数据。这被称为“开放寻址”。

基本上，两种方法都仍然大多 O（1）但具有希望-短的线性序列。我们可以为大多数目的假设它是O（1）。如果散列表变得太满，那些线性搜索可能变得越来越长，然后是“重新散列”的时候，这意味着要创建一个更大尺寸的新散列表并将所有数据重新插入到它中。

Answer 2

如果散列表中没有collisons，搜索需要O（1）时间，所以对于sya来说，在散列表中搜索需要O（1）或常量时间，这是不正确的。

See how Hashtable works on MSDN?

编辑

mgiuca精美解释它，我只是多加一个Collosion避免技术被称为链接。

在这项技术中，我们维护每个位置的值链接列表，因此当您发生爆炸时，您的值将被添加到该位置的链接列表中，因此当您搜索某个值时可能会出现需要的场景在整个链接列表中搜索值，因此在这种情况下搜索不会是O（1）操作。