知识卡片

普通读书笔记卡 · 5654.d.1.a.3.d.16 · 生成模型:未记录

开地址留空比例影响探查成本

理解等级:中级

开地址表α=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所述。

    参考来源

    - 位置:《算法精解:C语言描述》第8章《冲突解决》(spine1276;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1243.html;u133-ch08-017)。 - 结论依据:133完整负载/均匀探查段与02821表实读,公式条件和上界解释用官方课程相关分析页核验,不称真实测量。 - 原始内容:1/(1-α) 例如,对于一个处于半满状态的开地址哈希表来说(其负载系数为0.5),我们期望能够探查的槽位个数为1/(1-0.5)=2。表8-1显示了当哈希表的负载因子趋近于1(或100%,即表完全满)时,我们期望探查的槽位数量如何显著增大的。在一个对时间特别敏感的应用中,就可以通过增加哈希表的空间 - 位置:《算法精解:C语言描述》第8章《开地址哈希函数的接口定义》(spine1277;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1244.html;u134-ch08-017)。 - 结论依据:134增删查列O(1)应限定负载、探查分布和键处理成本;最坏可扫描全部m槽。初始化/带回调销毁按m个槽处理,size宏仅字段查询。 - 原始内容:复杂度 O(m),m是哈希表中槽的个数。 ohtbl_destroy 返回值 无 描述 销毁htbl指定的开地址哈希表。在调用ohtbl_destroy之后不再允许进行其他操作,除非再次调用ohtbl_init。ohtbl_destroy会删除哈希表中的所有元素,并同时释放ohtbl_init中参数 - 位置:《算法精解:C语言描述》第8章《问与答》(spine1284;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1251.html;u142-ch08-017)。 - 结论依据:142满表查询不存在键可探查m槽,通常控制负载如80%是本书经验建议而非固定普遍安全阈值;仍受探查序列与删除标记影响,不据此为任何应用保证响应时间。 - 原始内容:80%。如果我们选择一个近似于均匀散列的哈希函数,那么我们可以期望在一段固定时间内查找到元素,如表8-1所述。