HashTable
存储数据时,搜索时间为o(1)。我很困惑,能有人解释一下吗?这有点夸张——实际上可能需要更长时间,但通常也不会太久。
基本上,哈希表是一个包含所有要搜索的键的数组。每个键在数组中的位置由哈希函数决定,它可以是任何总是将相同输入映射到相同输出的函数。我们假设哈希函数为O(1)。
因此,当我们向哈希表插入东西时,我们使用哈希函数(称其为 h )找到要放置它的位置,并将其放在那里。现在我们再插入另一件事情,再次进行哈希和存储。每次插入数据时,它都需要O(1)时间来插入它(因为哈希函数为O(1))。
查找数据也是相同的。如果我们想要查找值x,我们只需找到h(x),就能知道x在哈希表中的位置。所以我们也可以在O(1)的时间内查找任何哈希值。
现在来说谎言:以上是一个非常好的理论,但有一个问题:如果我们插入数据,而该数组的那个位置已经有其他数据了怎么办?除非你有一个完美哈希函数,否则没有任何保证哈希函数不会为两个不同的输入产生相同的输出(但这些很难生成)。因此,在插入时我们需要采取以下两种策略之一:
基本上,这两种方法仍然大多数情况下是O(1),但会涉及到一些短暂的线性搜索。我们可以假设对于大多数情况来说,它仍然是O(1)。如果散列表变得太满,那么这些线性搜索可能会变得越来越长,此时就需要“重新哈希”,也就是创建一个更大的新散列表,并将所有数据插入其中。
如果哈希表中没有冲突,搜索只需O(1)时间,因此说在哈希表中搜索需要O(1)或恒定时间是不正确的。
编辑
mgiuca很好地解释了它,我只想再添加一种避免冲突的技术,称为链接法(Chaining)。
在这种技术中,我们在每个位置维护一个值的链接列表,因此当发生冲突时,您的值将添加到该位置的链接列表中,因此当您搜索值时,可能需要在整个链接列表中搜索,因此在这种情况下,搜索将不是O(1)操作。