知识卡片
哈希增删查询区分状态与数据
本章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)。这是因为我们期望查找的元素数量等于哈希表的负载因子,这样所用的代价会更小。