知识卡片

问题卡 · 5654.d.1.a.3.d.21 · 生成模型:未记录

查询必须先跳过删除哨兵

理解等级:中级

开地址查询只有遇真正空槽NULL才可宣告未找到;遇删除哨兵应继续探查,不能把哨兵当用户数据判等。

本章完整ohtbl_lookup源码只检查NULL,随后直接调用match(table[position],*data),漏掉ohtbl_remove已经具备的vacated分支。若探到删除槽,传入的是静态char哨兵地址,不是原用户对象;按用户类型解引用的回调可能访问无效对象或错误匹配。

修正该示例的控制顺序应为:NULL则未找到;vacated则继续;有效槽才判等,命中后交回地址。返回0仍只表示查找成功,不表示删除。这里明确记录源码缺陷和修正逻辑,未把原实现当正确模板,也未声称已编译或测试修复。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      不会执行删除操作。 考虑到我们尽量遵从了均匀散列的方法,ohtbl_lookup的时间复杂度为O(1)。其原因与ohtbl_remove操作相同。这是因为我们希望探查1/(1-α)个槽位,这是一个很小的常数,其中α是自从调用ohtbl_init以来哈希表的最大负载因子。性能依赖于自从调用ohtbl_

    参考来源

    - 位置:《算法精解:C语言描述》第8章《ohtbl_loopup》(spine1282;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1249.html;u140-ch08-022)。 - 结论依据:140原说明和02834末尾至02835完整lookup实读,直接对照同图remove的显式哨兵分支;哨兵对象为02832 static char,错误回调实参是实际代码可核验事实。 - 原始内容:不会执行删除操作。 考虑到我们尽量遵从了均匀散列的方法,ohtbl_lookup的时间复杂度为O(1)。其原因与ohtbl_remove操作相同。这是因为我们希望探查1/(1-α)个槽位,这是一个很小的常数,其中α是自从调用ohtbl_init以来哈希表的最大负载因子。性能依赖于自从调用ohtbl_