知识卡片

普通读书笔记卡 · 5654.d.1.a.3.d.3 · 生成模型:未记录

链式哈希先定位桶再查链

理解等级:中级

链式哈希把槽位组织成桶数组,每个桶是一条链表。插入先由键计算桶位置,再把新成员接入相应链;查找和删除也要先定位桶,然后逐项判等找实际键。冲突只是让多个成员共享一个桶,不代表已找到同一成员。

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散列键,并在链表头插入元素的操作都是运行固定时间的运算。