知识卡片
开地址接口需区分满表与重复
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