知识卡片
开地址留空比例影响探查成本
开地址表α=n/m越接近1,可用空槽通常越难找到。无删除标记的均匀探查模型中,未成功查询/插入新键寻找空槽的期望探查次数上界可写1/(1−α),要求α;这是期望界,不是每次的精确值,也不是所有探查方法的无条件保证。
02821对应α=0.5、0.8、0.9、0.95时上界数值为2、5、10、20,说明保持空位可换取较短探查。线性聚集和删除标记会使简单模型不适用,α=1时也不能套公式取得有限保证。
补充依据:MIT 6.006开地址讲义,第4–5页(2026-11-06核验模型与期望界)。
134增删查列O(1)应限定负载、探查分布和键处理成本;最坏可扫描全部m槽。初始化/带回调销毁按m个槽处理,size宏仅字段查询。
142满表查询不存在键可探查m槽,通常控制负载如80%是本书经验建议而非固定普遍安全阈值;仍受探查序列与删除标记影响,不据此为任何应用保证响应时间。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 开地址留空比例影响探查成本
- · 开地址哈希函数的接口定义
- · 问与答
原书出处 · 3 处
- · 查看原书依据
1/(1-α) 例如,对于一个处于半满状态的开地址哈希表来说(其负载系数为0.5),我们期望能够探查的槽位个数为1/(1-0.5)=2。表8-1显示了当哈希表的负载因子趋近于1(或100%,即表完全满)时,我们期望探查的槽位数量如何显著增大的。在一个对时间特别敏感的应用中,就可以通过增加哈希表的空间
- · 查看原书依据
复杂度 O(m),m是哈希表中槽的个数。 ohtbl_destroy 返回值 无 描述 销毁htbl指定的开地址哈希表。在调用ohtbl_destroy之后不再允许进行其他操作,除非再次调用ohtbl_init。ohtbl_destroy会删除哈希表中的所有元素,并同时释放ohtbl_init中参数
- · 查看原书依据
80%。如果我们选择一个近似于均匀散列的哈希函数,那么我们可以期望在一段固定时间内查找到元素,如表8-1所述。