知识卡片
负载因子是平均链长非上限
设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是表示哈希表范围的某个常数。选择一个好的哈希函数能够保证这种最坏情况不会发生。如果哈希表中的元素能够近似于均匀散列的分布,那么我们