知识卡片
链式哈希先定位桶再查链
链式哈希把槽位组织成桶数组,每个桶是一条链表。插入先由键计算桶位置,再把新成员接入相应链;查找和删除也要先定位桶,然后逐项判等找实际键。冲突只是让多个成员共享一个桶,不代表已找到同一成员。
02801有5桶、7成员,桶长度分别为1、3、1、0、2:数组定位之后,查询成本仍取决于目标链有多长。链表允许每桶继续增长,避免了一个槽只能容一个对象的限制,但不表示机器内存无限,也不保证成员越多访问仍一样快。
127实际先查重再头插,所以不能用单独头插O(1)证明整次插入最坏常数。h与match必须相容:相等键要定位到同一桶,否则lookup可能查不到相等对象。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
然后遍历相应的链表,直到发现我们想要查找的元素。因为每个“桶”都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。 图 8-1 一个链式哈希表,含有5个桶,7个元素
- · 查看原书依据
相应位置的“桶”中。如果整个插入过程成功,表的容量将增大。 假设我们尽量遵从均匀散列的方法,chtbl_insert的时间复杂度为O(1)。这是由于chtbl_lookup散列键,并在链表头插入元素的操作都是运行固定时间的运算。
参考来源
- 位置:《算法精解:C语言描述》第8章《链式哈希表的描述》(spine1266;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1233.html;u120-ch08-004)。
- 结论依据:120全文及02801完整五桶图实际阅读,逐桶节点数核对为七个;未虚构CHTbl字段,实际结构留124。
- 原始内容:然后遍历相应的链表,直到发现我们想要查找的元素。因为每个“桶”都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。 图 8-1 一个链式哈希表,含有5个桶,7个元素
- 位置:《算法精解:C语言描述》第8章《chtbl_insert》(spine1271;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1238.html;u127-ch08-004)。
- 结论依据:127实际先查重再头插,所以不能用单独头插O(1)证明整次插入最坏常数。h与match必须相容:相等键要定位到同一桶,否则lookup可能查不到相等对象。
- 原始内容:相应位置的“桶”中。如果整个插入过程成功,表的容量将增大。 假设我们尽量遵从均匀散列的方法,chtbl_insert的时间复杂度为O(1)。这是由于chtbl_lookup散列键,并在链表头插入元素的操作都是运行固定时间的运算。