哈希如何有o(1)搜索时间？

Question

当我们使用a HashTable来存储数据时,据说搜索需要o(1)时间.我很困惑,任何人都可以解释一下吗？

Answer 1

嗯,这有点谎言 - 它可能需要更长的时间,但通常不会.

基本上,哈希表是包含要搜索的所有键的数组.数组中每个键的位置由散列函数确定,散列函数可以是始终将相同输入映射到同一输出的任何函数.我们假设散列函数是O(1).

因此,当我们在哈希表中插入一些东西时,我们使用哈希函数(让我们称之为h)来找到放置它的位置,并将其放在那里.现在我们插入另一个东西,哈希和存储.而另一个.每次插入数据时,插入数据都需要O(1)时间(因为散列函数是O(1)).

查找数据是一样的.如果我们想要找到一个值x,我们只需要找出h(x),它告诉我们x在哈希表中的位置.所以我们也可以在O(1)中查找任何哈希值.

现在说谎:上面是一个非常好的理论,有一个问题:如果我们插入数据并且数组的那个位置已经有了什么呢？没有什么可以保证哈希函数不会为两个不同的输入产生相同的输出(除非你有一个完美的哈希函数,但这些都很难产生).因此,当我们插入时,我们需要采取以下两种策略之一:

在数组中的每个点存储多个值(例如,每个数组槽都有一个链表).现在当你进行查找时,它仍然是O(1)到达数组中的正确位置,但可能是一个线性搜索(希望很短的)链表.这被称为"单独链接".
如果您发现某些内容已经存在,请再次哈希并找到其他位置.重复,直到找到一个空位,并将其放在那里.查找过程可以遵循相同的规则来查找数据.现在它仍然是O(1)到达第一个位置,但是有一个潜在的(希望很短的)线性搜索在桌子周围反弹,直到找到你想要的数据.这称为"开放寻址".

基本上,这两种方法仍然主要是 O(1),但有一个希望短的线性序列.在大多数情况下,我们可以假设它是O(1).如果哈希表变得太满,那些线性搜索会变得越来越长,然后是时候"重新哈希"了,这意味着要创建一个更大的新哈希表并将所有数据插回其中.

Answer 2

如果哈希表中没有collisons,则搜索需要O(1)时间,因此sya在哈希表中搜索需要O(1)或恒定时间是不正确的.

编辑

mgiuca很好地解释了它,我只是添加了一种叫做Chaining的Collosion Avoidance技术.

在这种技术中,我们在每个位置都维护一个值的链接列表,所以当你有一个崩溃时,你的值将被添加到该位置的链接列表中,所以当你搜索一个值时,你可能需要搜索值.在整个链接列表中,所以在这种情况下搜索将不是O(1)操作.