知识卡片
删除标记保留探查链连续性
开地址的空槽与删除过的槽含义不同:真正未占用的NULL可作为未找到的停止点;删除标记则表示这里曾被占用,目标可能被冲突推到后面,查询必须越过。插入可复用这类槽,但仍需先确认没有重复键。
本例vacated是指向静态char对象的一个哨兵地址,槽中存这个地址表示已删除。它不是保存多个删除位置的容器,也不是把槽地址加入一份列表。这个地址不可当普通用户数据传给match或destroy。
结构图:
stateDiagram-v2
[*] --> 未使用: 初始化为NULL
未使用 --> 有效成员: 插入数据地址
有效成员 --> 已删除: 移除并写哨兵地址
已删除 --> 有效成员: 复用槽插入
未使用允许查询结束,已删除要求继续探查;两种状态不能因当前都不含有效成员而合并。
139与02834 ohtbl_remove遇NULL即-1,遇vacated显式继续,普通有效槽才match;命中输出旧数据地址、写vacated、size–返回0。原文所谓将槽地址放进vacated不符实际赋值,应理解为槽中改存哨兵。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
指针vacated将被初始化来指向一个特殊的地址空间,来指明这个特殊地址上曾经删除一个元素;h1、h2、match、destroy是打包传入ohtbl_init的函数指针;size指明表中现有元素的数量;table是存储元素的数组。 这里需要稍微讨论一下指针vacated。它的存在主要是用来辅助删除
- · 查看原书依据
将data指向正在删除的数据,然后将表的大小减1。同时,将槽在哈希表中的地址放到数据结构vacated中。 考虑到我们尽量遵从了均匀散列的方法,ohtbl_remove的时间复杂度为O(1)。这是因为,为了找到删除元素的槽位,我们会探查1/(1-α)个槽(其中α是自从调用ohtbl_init以来哈希
参考来源
- 位置:《算法精解:C语言描述》第8章《开地址哈希表的实现与分析》(spine1278;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1245.html;u135-ch08-019)。
- 结论依据:135完整vacated解释与02832静态char/地址初始化、02834删除写哨兵实读;状态图区分查找终止规则,不假造额外删除表。
- 原始内容:指针vacated将被初始化来指向一个特殊的地址空间,来指明这个特殊地址上曾经删除一个元素;h1、h2、match、destroy是打包传入ohtbl_init的函数指针;size指明表中现有元素的数量;table是存储元素的数组。 这里需要稍微讨论一下指针vacated。它的存在主要是用来辅助删除
- 位置:《算法精解:C语言描述》第8章《ohtbl_remove》(spine1281;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1248.html;u139-ch08-019)。
- 结论依据:139与02834 ohtbl_remove遇NULL即-1,遇vacated显式继续,普通有效槽才match;命中输出旧数据地址、写vacated、size--返回0。原文所谓将槽地址放进vacated不符实际赋值,应理解为槽中改存哨兵。
- 原始内容:将data指向正在删除的数据,然后将表的大小减1。同时,将槽在哈希表中的地址放到数据结构vacated中。 考虑到我们尽量遵从了均匀散列的方法,ohtbl_remove的时间复杂度为O(1)。这是因为,为了找到删除元素的槽位,我们会探查1/(1-α)个槽(其中α是自从调用ohtbl_init以来哈希