知识卡片

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

哈希增删查询区分状态与数据

理解等级:中级

本章chtbl_insert(CHTbl,const void)成功加入返回0,键已存在而未加入返回1,失败返回-1;它保存数据地址,不深复制对象。判等回调在实际代码中以非零为真、0为假,不能把三路大小比较器直接当相等谓词。

chtbl_lookup(const CHTbl*,void)与chtbl_remove(CHTbl*,void)成功0、未找到-1,都先从*data读取查找键,成功后将*data替换为实际存储的数据地址。lookup保留节点和成员,remove移除节点并减少数量但不自动销毁该数据对象。返回成功的含义是“找到/移除”,不代表调用方业务已完成。

查询给出的是仍由表保存的对象地址,使用方不能无约定地释放它;移除后则需按所有权约定处理对象。两者都应以合适的void*中间变量接收结果,不把void视为通用T。

127及02815 chtbl_insert用局部void* temp接收查找,命中return1;否则bucket=h(data)%buckets并list_ins_next(…,NULL,data),成功才size++,返回底层结果。size增长不表示桶数扩容,源码没有自动扩容步骤。

128及02816:prev从NULL起,遍历当前element;命中时调用list_rem_next(bucket,prev,data),成功才size–并返回0。prev实际是待删除节点的前驱,不是文字所称的待删节点本身;未命中返回-1。data改为已移除对象地址,并未调用destroy。

129及02816–02817 chtbl_lookup成功写*data=list_data(element),return0,未找到-1。开头“已删除元素”是文字笔误;实际lookup没有调用移除、释放或改size。const CHTbl*也不等于返回数据对象不可修改或永远有效,寿命仍受其他操作影响。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

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

    • · 查看原书依据

      先调用chtbl_lookup来确保表中没有重复的元素。如果散列表中的元素没有重复的键,将新元素的键散列,然后根据哈希编码将元素插入哈希表中相应位置的“桶”中。如果整个插入过程成功,表的容量将增大。 假设我们尽量遵从均匀散列的方法,chtbl_insert的时间复杂度为O(1)。这是由于chtbl_

    • · 查看原书依据

      prev必须维护一个指向待删除元素的指针。回想一下,在list_rem_next中,data用来指向从列表中删除的数据。如果在“桶”中没有找到匹配的键,那么表明哈希表中没有此元素。如果删除过程成功,将表的大小减一。 假设我们尽量遵从均匀散列的方法,chtbl_remove的时间复杂度为O(1)。这是

    • · 查看原书依据

      不会执行删除操作。 假设我们尽量遵从均匀散列的方法,chtbl_lookup的时间复杂度为O(1)。这是因为我们期望查找的元素数量等于哈希表的负载因子,这样所用的代价会更小。

    参考来源

    - 位置:《算法精解:C语言描述》第8章《链式哈希表的接口定义》(spine1268;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1235.html;u123-ch08-010)。 - 结论依据:123六项接口描述和02806–02811原型完整实读,02815–02817实现确认插入临时变量/三态、查找与移除的输入输出和判等真假;未运行。 - 原始内容:chtbl_insert 返回值 如果插入元素成功,返回0;如果哈希表已经包含此元素,返回1;否则,返回-1。 描述 向htbl指定的链式哈希表中插入一个元素。新元素包含一个指向data的指针,只要元素仍然存在于哈希表中,此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。 复杂度 O - 位置:《算法精解:C语言描述》第8章《chtbl_insert》(spine1271;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1238.html;u127-ch08-010)。 - 结论依据:127及02815 chtbl_insert用局部void* temp接收查找,命中return1;否则bucket=h(data)%buckets并list_ins_next(...,NULL,data),成功才size++,返回底层结果。size增长不表示桶数扩容,源码没有自动扩容步骤。 - 原始内容:先调用chtbl_lookup来确保表中没有重复的元素。如果散列表中的元素没有重复的键,将新元素的键散列,然后根据哈希编码将元素插入哈希表中相应位置的“桶”中。如果整个插入过程成功,表的容量将增大。 假设我们尽量遵从均匀散列的方法,chtbl_insert的时间复杂度为O(1)。这是由于chtbl_ - 位置:《算法精解:C语言描述》第8章《chtbl_remove》(spine1272;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1239.html;u128-ch08-010)。 - 结论依据:128及02816:prev从NULL起,遍历当前element;命中时调用list_rem_next(bucket,prev,data),成功才size--并返回0。prev实际是待删除节点的前驱,不是文字所称的待删节点本身;未命中返回-1。data改为已移除对象地址,并未调用destroy。 - 原始内容:prev必须维护一个指向待删除元素的指针。回想一下,在list_rem_next中,data用来指向从列表中删除的数据。如果在“桶”中没有找到匹配的键,那么表明哈希表中没有此元素。如果删除过程成功,将表的大小减一。 假设我们尽量遵从均匀散列的方法,chtbl_remove的时间复杂度为O(1)。这是 - 位置:《算法精解:C语言描述》第8章《chtbl_lookup》(spine1273;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1240.html;u129-ch08-010)。 - 结论依据:129及02816–02817 chtbl_lookup成功写*data=list_data(element),return0,未找到-1。开头“已删除元素”是文字笔误;实际lookup没有调用移除、释放或改size。const CHTbl*也不等于返回数据对象不可修改或永远有效,寿命仍受其他操作影响。 - 原始内容:不会执行删除操作。 假设我们尽量遵从均匀散列的方法,chtbl_lookup的时间复杂度为O(1)。这是因为我们期望查找的元素数量等于哈希表的负载因子,这样所用的代价会更小。