知识卡片
取余散列依赖模数与键分布
对非负整数键k和正槽数m,取余法h(k)=k mod m把键映射到0至m−1。本书例25657 mod 1699=172。若m=2ᵖ,余数只取决于k低p位,低位模式明显的键可能大量聚集。
书中以不太靠近2的幂的素数作为选择启发,并同时考虑容量和负载;素数本身不保证任何键集都会均匀。若实现允许负整数键,还需明确得到合法非负下标的规则,不能不加处理就把C的负余数当数组下标。
142第一问在chtbl中再次对buckets取模以约束回调结果,双散列还需对组合表达式取模。正模数与非负/合法算术是前提,仅补一个%并不能消除负下标、除零或组合整数溢出。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 取余散列依赖模数与键分布
- · 问与答
原书出处 · 2 处
- · 查看原书依据
取余法 有一个整型键k,一种最简单地将k映射到m槽位的散列方法是计算k除以m的所得到的余数。我们称为取余法,正式的表述为: h(k)=k mod m 如果表有m=1699个位置,而要散列的键k=25 657,通过这种方法可以得到哈希编码为25 657 mod 1699=172。通常情况下,要避免m的
- · 查看原书依据
对表取模后的值,这是为什么? 答:进行这种转换是为了确保哈希编码不会处于表的末尾。虽然哈希函数保证这一点,但通过哈希表本身的实现方式来保证这一点也是值得的,特别是当哈希函数是由函数调用者提供时。然而,在开地址哈希表中进行双散列时,进行取模的原因就不一样了。在这种情况下,双散列所产生的哈希编码可能超出
参考来源
- 位置:《算法精解:C语言描述》第8章《选择哈希函数》(spine1267;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1234.html;u122-ch08-007)。
- 结论依据:122取余段、完整公式与1699例实读;末句是输入范围边界而非本书已给负键接口;MIT已读讲义除法方法支持选择启发,不写绝对最优规则。
- 原始内容:取余法 有一个整型键k,一种最简单地将k映射到m槽位的散列方法是计算k除以m的所得到的余数。我们称为取余法,正式的表述为: h(k)=k mod m 如果表有m=1699个位置,而要散列的键k=25 657,通过这种方法可以得到哈希编码为25 657 mod 1699=172。通常情况下,要避免m的
- 位置:《算法精解:C语言描述》第8章《问与答》(spine1284;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1251.html;u142-ch08-007)。
- 结论依据:142第一问在chtbl中再次对buckets取模以约束回调结果,双散列还需对组合表达式取模。正模数与非负/合法算术是前提,仅补一个%并不能消除负下标、除零或组合整数溢出。
- 原始内容:对表取模后的值,这是为什么? 答:进行这种转换是为了确保哈希编码不会处于表的末尾。虽然哈希函数保证这一点,但通过哈希表本身的实现方式来保证这一点也是值得的,特别是当哈希函数是由函数调用者提供时。然而,在开地址哈希表中进行双散列时,进行取模的原因就不一样了。在这种情况下,双散列所产生的哈希编码可能超出