算法 – 为什么散列表平均访问时间不变？
发布时间：2020-12-14 05:04:45 所属栏目：Java 来源：网络整理
导读：我不明白这个解释,如果n是哈希表中的元素数,m是桶的总数,那么只有在n与n(n)成比例时,哈希表的平均访问时间是平均的.为什么要成比例？ 解决方法 实际上m应该与n成正比.否则,你可以,例如,只有一个桶,它将像一个未排序的集合. 更准确地说,如果m与n成比例,即m =
|
我不明白这个解释,如果n是哈希表中的元素数,m是桶的总数,那么只有在n与n(n)成比例时,哈希表的平均访问时间是平均的.为什么要成比例？
解决方法
实际上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))(我假设你不要在bucket中粘贴另一个哈希表,或者我们在该哈希表上有相同的参数),所以在这种情况下不会是O(1). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |