data-structures - 哈希表中的渐近运行时间

Question

因为我们知道如果哈希函数均匀地分布条目，那么哈希表的查询时间为 O(1)。

什么是渐近运行时间：

(a) 在单独的链式哈希表中添加 n 个具有连续键的条目（插入所有的时间，而不是每一个）

(b) 搜索不在表中的键。

我的理解是，将一个键插入哈希表是 O(1)，因此插入这样的 n 个条目将是 O(n)。对于 b 部分，搜索表中不存在的键被认为是最坏的情况，因此搜索的渐近运行时间将为 O(n)，因为它需要搜索表中的所有 n 个值。

标签： data-structureshashtable

Answer 1

你是对的 a) - 它是 O(n)，其中 n 是要插入的新密钥的数量，因为每个都是 O(1) 相对于预先存在的密钥数量。

对于 b) - 你错了 - 它是 O(1)。搜索不在表中的键只需要穷举搜索该键散列到的桶，该桶的预期长度大致由负载因子给出：键与桶的比率。大多数哈希表旨在将负载因子保持在特定范围内，并在添加更多键时调整哈希表的大小。

例如，C++ 标准指定默认max_load_factor值为 1.0，因此如果您将第 129 个元素插入到具有 128 个存储桶的表中，它将调整整个事物的大小以拥有 256 个存储桶（MS Visual C++ 使用二次幂存储桶计数对于散列值到桶的快速按位掩码，GCC 使用素数来减少冲突）。无论如何，当负载因子保持在这样的范围内时——比如 ~0.5 到 1.0——你不太可能在存储桶中有超过几个元素，你会搜索实际上不在表中的键。

除了单独的链接之外，还有另一种将数据存储在哈希表中的方法，称为封闭哈希或开放寻址，其中 - 如果发生冲突 - 您可以使用其他存储桶。有很多方法可以选择这些桶：线性探测意味着您查看连续的桶，二次探测意味着您尝试从散列到桶中的 +1、+4、+9、+16。使用这些方法，当负载因子接近 1.0，或者如果哈希函数质量很差，您更有可能接近 O(N) 的最坏情况性能，但如果您是不会阻止这种情况并具有较低的负载因子或更好的散列函数 - 这将使性能保持在 O(1) 摊销水平。