我不明白如果存储桶的数量恒定，那么哈希表如何进行恒定时间查找。假设我们有 100 个桶和 1,000,000 个元素。这显然是 O(n) 查找，这就是理解非常大的 n 值时事物的行为方式的复杂性所在。因此，哈希表永远不是常量查找，它始终是 O(n) 查找。
为什么人们说平均查找时间为 O(1)，而最坏情况下查找时间仅为 O(n)？
使用哈希的目的是能够像数组一样直接对表进行索引。在理想情况下，每个桶只有一个项目，我们可以轻松实现 O(1)。
实际的哈希表的存储桶数量将多于其元素数量，因此每个存储桶仅包含一个元素的可能性很高。如果插入表中的元素数量过多，则将调整表的大小以增加存储桶的数量。
总是有可能每个元素都具有相同的哈希值，或者所有活动哈希值将被分配到同一个存储桶；在这种情况下，查找时间确实是 O(n)。但良好的哈希表实现将被设计为最大限度地减少发生这种情况的可能性。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
