为什么哈希表平均具有常数访问时间？

Question

为什么哈希表平均具有常数访问时间？

algorithmdata-structureshashtable

12

我不理解这个解释，它说如果n是哈希表中元素的数量，而m是桶的总数量，那么只有当n与theta(n)成比例时，哈希表才具有平均恒定的访问时间。为什么必须成正比呢？

- phoenix

5个回答

2

严格来说，哈希表访问的平均时间复杂度实际上是Ω(n^1/3)。信息无法超过光速，这是一个常数。由于空间具有三个维度，因此存储n位数据需要将一些数据定位在距CPU大约为n^1/3的距离处。

更多详细信息请参阅我的博客。

- Daniel Lubarov

2

对于纯组合电路，这可能是一个问题（当我们进入三维全息存储器时，这将更加成为问题），但现代计算机是顺序的：内部时钟的存在保证了所有内存访问在相同的时间内执行。 - Jeff

1

@Jeff，说实话，我认为我们只能增加有限的内存，否则延迟（每次访问的周期数或时钟周期）就必须增加。实际上，我认为我们可以从寄存器、L1-L3缓存和主内存的相对延迟中看到距离的影响（尽管还有其他限制，如成本和热量）。 - Daniel Lubarov

1

对我来说，将内存访问视为常量似乎类似于将字长操作视为常量——这是一种非常合理和有用的简化，但从技术上讲忽略了多项式对数因子。当然，如果我们使用64位计算机，我们不会看到这些因子，但在理论上，如果我们使用针对问题规模进行优化的硬件，它们将很重要。 - Daniel Lubarov

2

我理解你的观点，你说得完全正确，但是我现在看到了问题所在。渐进算法复杂度分析（大O/Ω/Θ符号）纯粹是理论上的。如果你谈论任何与原子、电子、微秒或空间（或任何形式的物理学）有关的事情，那么大O/Ω/Θ符号在讨论中就没有地位。任何理论上的哈希表查找都是O(1)，即使任何实现的哈希表查找可能需要任意数量的墙钟时间。算法和算法实现（以及它们运行的架构）处于完全不同的领域。 - Jeff

1

计算机科学家使用“常数时间”这个词语是可以理解的。我们之间明白它指的是在理论意义下的O(1)：从上方被一个常数函数有界渐进地限制。对于外部观察者来说，可能会认为我们在谈论实际的墙钟时间，但事实并非如此。大O/Ω/Θ符号表示一个无单位的抽象时间，只有与其他算法相比才有意义。 - Jeff

0

碰撞的概率更高，因此需要扫描具有相同哈希键的项目列表的发生率也更高。

- BJ Safdie

0

访问时间是恒定的，因为访问是基于哈希值的计算和常量查找以找到适当的桶。假设哈希函数在桶之间均匀分配项目，则访问任何单个项目所需的时间将等于访问其他项目所需的时间，而不管n的大小。

恒定并不一定意味着始终很低。平均访问时间与哈希函数的均匀分布和桶的数量有关。如果你有数千个项目均匀分布在少量的桶中，你会快速找到桶，但然后需要遍历桶中的许多项目。如果你有良好的桶与项目比例，但是一个糟糕的哈希函数使得某些桶中的项目比其他桶中的项目多得多，那么较大桶中的项目的访问时间将比其他桶中的项目慢。

- Samuel Neff

0

一个大小适中的哈希表，其中有足够的插槽来存储每个元素和充足的额外空间，将使哈希函数大部分工作是选择插槽并且很少发生冲突，即不同的元素具有相同的哈希。一个非常拥挤的哈希表会有很多冲突，并且会退化为基本上是线性搜索，几乎每次查找都会是一个错误项，它具有相同的哈希值，你必须继续搜索正确的项（哈希表查找仍然必须在选择第一个插槽后检查键，因为正在查找的键可能在存储时发生了冲突）。

确定命中-冲突比的是项目数量与哈希表大小的比率（即随机选择插槽被填充的百分比）。

- Mu Mind

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Larry Watanabe · Accepted Answer

实际上，m 应该与 n 成比例。否则，例如，您可能只有一个桶，它就像未排序的集合一样。

更准确地说，如果 m 与 n 成比例，即 m = c * n，则每个桶中的项数将是 n/m = 1/c，这是一个常数。进入任何桶都是 O(1) 操作（只需计算哈希码），然后通过桶进行搜索是常量级别的（可以在桶中的项上执行线性搜索，这是一个常量）。

因此，如果 m = c * n，则算法的顺序为 O(1)。

举个反例，假设我们有一个固定大小的表，大小为 tableSize。那么每个桶中预期的项数是 n/tableSize，它是 n 的线性函数。对于树来说，通过桶进行任何类型的搜索最好是 O(log(n))（我假设您没有将另一个哈希表放在桶内，否则我们就需要对该哈希表进行相同的论证），因此在这种情况下它不是 O(1)。