algorithm - 哈希表总是查找 O(n) 时间？

Question

如果存储桶的数量是恒定的，我不明白哈希表是如何进行恒定时间查找的。假设我们有 100 个桶和 1,000,000 个元素。这显然是 O(n) 查找，这就是复杂点，以了解对于非常大的 n 值事物的行为方式。因此，哈希表永远不是常量查找，它总是 O(n) 查找。

为什么人们说它的平均查找时间为 O(1)，最坏情况下仅为 O(n)？

Answer 1

使用散列的目的是能够像数组一样直接索引到表中。在理想情况下，每个桶只有一个项目，我们很容易实现 O(1)。

实际的哈希表的桶数多于元素数，因此每个桶只有一个元素的可能性很高。如果插入表中的元素数量过多，将调整表的大小以增加桶的数量。

总是有可能每个元素都具有相同的哈希值，或者所有事件的哈希值都将分配给同一个桶；在那种情况下，查找时间确实是 O(n)。但是一个好的哈希表实现将被设计成将这种情况发生的可能性降到最低。