知识卡片

操作参考卡 · 5654.d.1.a.3.d.17 · 生成模型:未记录

开地址接口需区分满表与重复

理解等级:中级

ohtbl_insert(OHTbl,const void)在接口表中约定0为新加入、1为已有、-1为失败;ohtbl_remove和ohtbl_lookup以void**读入键并在成功时交回实际数据地址,成功0、未找到-1。查询保留数据,移除后由调用方承担对象后续处置,存储仍不是深复制。

实际源码先检查size==positions并返回-1,然后才查询重复。因此表已满时,即使传入已有键也返回-1,不符合不加条件的“重复返回1”。调用方需知道该实现的优先顺序,不能把-1都归因于新键分配失败。

若希望接口始终以1表示已有,应先确定插入函数职责,再考虑将存在查询放到容量判断前。这里保留原代码行为与改进方向,没有修改或运行应用。

138及02833–02834 insert每轮计算(h1(data)+i*h2(data))%positions,最多positions次;空槽或哨兵槽可放入,size++返回0。没有自动扩容,文字“容量增大”实际是size增加。vacated是单个哨兵地址,不是槽地址收集结构。若哈希步长不覆盖全表,可能有空槽仍失败;实现也依赖算术不产生溢出或非法负下标。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      ohtbl_insert 返回值 如果插入元素成功,返回0;如果哈希表已经包含此元素,返回1;否则,返回-1。 描述 向htbl指定的开地址哈希表中插入一个元素。新元素包含一个指向data的指针,因此只要元素仍然存在于哈希表中,此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。 复杂

    • · 查看原书依据

      固定的大小,所以在插入新元素之前必须保证有足够的空间来放置元素。而且,因为相同的键不允许重复插入表中,所以在插入新元素时调用ohtbl_lookup来确保表中没有相同的元素存在。 一旦以上条件得到满足,就可以通过双散列法在表中寻找未占用的槽。如果一个槽的数据指向NULL或槽地址在vacated中(v

    参考来源

    - 位置:《算法精解:C语言描述》第8章《开地址哈希函数的接口定义》(spine1277;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1244.html;u134-ch08-018)。 - 结论依据:134六项接口表、02824–02829全部原型及02833完整insert先满后查顺序实读;明确代码与文档不一致,未制造不存在的分配分支。 - 原始内容:ohtbl_insert 返回值 如果插入元素成功,返回0;如果哈希表已经包含此元素,返回1;否则,返回-1。 描述 向htbl指定的开地址哈希表中插入一个元素。新元素包含一个指向data的指针,因此只要元素仍然存在于哈希表中,此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。 复杂 - 位置:《算法精解:C语言描述》第8章《ohtbl_insert》(spine1280;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1247.html;u138-ch08-018)。 - 结论依据:138及02833–02834 insert每轮计算(h1(data)+i*h2(data))%positions,最多positions次;空槽或哨兵槽可放入,size++返回0。没有自动扩容,文字“容量增大”实际是size增加。vacated是单个哨兵地址,不是槽地址收集结构。若哈希步长不覆盖全表,可能有空槽仍失败;实现也依赖算术不产生溢出或非法负下标。 - 原始内容:固定的大小,所以在插入新元素之前必须保证有足够的空间来放置元素。而且,因为相同的键不允许重复插入表中,所以在插入新元素时调用ohtbl_lookup来确保表中没有相同的元素存在。 一旦以上条件得到满足,就可以通过双散列法在表中寻找未占用的槽。如果一个槽的数据指向NULL或槽地址在vacated中(v