为什么哈希表平均具有恒定的访问时间？

Question

我不明白这个解释说明如果n是散列表中的元素数量而m是桶的总数,那么只有当n与theta(n)成比例时,散列表才具有平均的持续访问时间.为什么它必须成比例？

Answer 1

实际上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).