知识卡片
查询必须先跳过删除哨兵
开地址查询只有遇真正空槽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_