散列如何具有o（1）搜索时间？

季炯

2023-03-14

问题内容：

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

问题答案：

好吧，这只是个谎言-可能需要更长的时间，但通常不会。

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

因此，当我们在哈希表中插入内容时，我们使用哈希函数（将其称为 h
）来查找将其放置在何处并将其放置在其中。现在，我们插入另一件事，即哈希和存储。还有一个。每次插入数据时，都需要O（1）的时间来插入数据（因为哈希函数是O（1））。

查找数据是相同的。如果我们想找到一个值 x ，我们只需要找出 h （x）即可告诉我们 x
在哈希表中的位置。因此，我们也可以在O（1）中查找任何哈希值。

现在说谎：上面是一个很好的理论，但有一个问题：如果我们插入数据并且在数组的那个位置已经有东西该怎么办？没有什么可以保证哈希函数不会为两个不同的输入产生相同的输出（除非您具有完善的哈希函数，但是要产生这些棘手的代码）。因此，在插入时，我们需要采取以下两种策略之一：

在数组的每个位置存储多个值（例如，每个数组插槽都有一个链表）。现在，当您执行查找时，到达数组中的正确位置仍为O（1），但可能会在（希望较短的）链表中进行线性搜索。这称为“单独链接”。
如果发现已经有东西，请再次哈希并找到另一个位置。重复直到找到一个空白点，然后将其放在那里。查找过程可以遵循相同的规则来查找数据。现在它仍然是O（1）才能到达第一个位置，但是有一个潜在的（希望很短的）线性搜索可以在表格周围反弹，直到找到需要的数据为止。这称为“开放式寻址”。

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