← 返回刚才阅读的位置

知识卡片

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

负载因子是平均链长非上限

理解等级:中级

设n个成员、m个桶,α=n/m表示平均每桶成员数;它不限制最长桶,也不保证每个桶都不超过α。即使α,多个键仍可能落在同一桶;02801的平均值为7/5=1.4,却已有长度3的桶。

均匀散列是关于分布的假设,不是“每个桶一样长”的确定保证。本书3198/1699写成2是粗略/错误等号,实际约1.882;“每桶不超过两个”也不能由该平均值推出。增大n而不增加m会提高平均链长,偏斜还可能造成远长于平均值的链。

在简单均匀散列、常数哈希与判等成本下,链式搜索期望成本为Θ(1+α);α受常数控制才得到期望O(1),所有键落入一桶时最坏可到Θ(n)。MIT 6.006讲义,第4–5页(2026-11-06核验)。

123各表项的O(1)不是无条件最坏保证:操作需哈希并搜索桶,期望常数依赖散列、常数负载及键处理成本。销毁还需遍历所有桶和成员,后续126按实际代码展开。

142链式最坏同桶O(n)。原答“选择好函数保证最坏不会发生”过强:近似均匀是期望分析条件,不能对任意键集提供确定不碰撞保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      负载因子,其定义为: α=n/m 其中,n是表中元素的个数,m是“桶”的个数。在均匀散列的情况下,链式哈希表的负载因子告诉我们表中的“桶”能装下元素个数的最大值。 例如,有一个链式哈希表,其“桶”的数量m=1699,元素的数量n=3198,其负载因子α=3198/1699=2。所以在这种情况下,当查

    • · 查看原书依据

      复杂度 O(m),m是哈希表中“桶”的个数。 chtbl_destroy 返回值 无 描述 销毁htbl指定的链式哈希表。在调用chtbl_destroy之后不再允许进行其他操作,除非再次调用chtbl_init。chtbl_destroy会删除哈希表中的所有元素,并同时释放chtbl_init中参

    • · 查看原书依据

      所有元素散列到同一个“桶”中时,链式哈希表的性能最差。在这种情况下,查找一个元素的复杂度是O(n),其中n是表中元素的个数。会产生如此糟糕性能的函数是h(k)=c,其中c是表示哈希表范围的某个常数。选择一个好的哈希函数能够保证这种最坏情况不会发生。如果哈希表中的元素能够近似于均匀散列的分布,那么我们

    参考来源

    - 位置:《算法精解:C语言描述》第8章《解决冲突》(spine1266;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1233.html;u121-ch08-005)。 - 结论依据:121完整定义、均匀散列解释及两个数量示例实读;120图直接反驳最大桶深上限,期望条件和最坏界由MIT原始课程讲义相关页补充核验。 - 原始内容:负载因子,其定义为: α=n/m 其中,n是表中元素的个数,m是“桶”的个数。在均匀散列的情况下,链式哈希表的负载因子告诉我们表中的“桶”能装下元素个数的最大值。 例如,有一个链式哈希表,其“桶”的数量m=1699,元素的数量n=3198,其负载因子α=3198/1699=2。所以在这种情况下,当查 - 位置:《算法精解:C语言描述》第8章《链式哈希表的接口定义》(spine1268;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1235.html;u123-ch08-005)。 - 结论依据:123各表项的O(1)不是无条件最坏保证:操作需哈希并搜索桶,期望常数依赖散列、常数负载及键处理成本。销毁还需遍历所有桶和成员,后续126按实际代码展开。 - 原始内容:复杂度 O(m),m是哈希表中“桶”的个数。 chtbl_destroy 返回值 无 描述 销毁htbl指定的链式哈希表。在调用chtbl_destroy之后不再允许进行其他操作,除非再次调用chtbl_init。chtbl_destroy会删除哈希表中的所有元素,并同时释放chtbl_init中参 - 位置:《算法精解:C语言描述》第8章《问与答》(spine1284;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1251.html;u142-ch08-005)。 - 结论依据:142链式最坏同桶O(n)。原答“选择好函数保证最坏不会发生”过强:近似均匀是期望分析条件,不能对任意键集提供确定不碰撞保证。 - 原始内容:所有元素散列到同一个“桶”中时,链式哈希表的性能最差。在这种情况下,查找一个元素的复杂度是O(n),其中n是表中元素的个数。会产生如此糟糕性能的函数是h(k)=c,其中c是表示哈希表范围的某个常数。选择一个好的哈希函数能够保证这种最坏情况不会发生。如果哈希表中的元素能够近似于均匀散列的分布,那么我们