知识卡片

结构图卡 · 5654.d.1.a.3.d.18 · 生成模型:未记录

删除标记保留探查链连续性

理解等级:中级

开地址的空槽与删除过的槽含义不同:真正未占用的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以来哈希