知识卡片

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

取余散列依赖模数与键分布

理解等级:中级

对非负整数键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取模以约束回调结果,双散列还需对组合表达式取模。正模数与非负/合法算术是前提,仅补一个%并不能消除负下标、除零或组合整数溢出。 - 原始内容:对表取模后的值,这是为什么? 答:进行这种转换是为了确保哈希编码不会处于表的末尾。虽然哈希函数保证这一点,但通过哈希表本身的实现方式来保证这一点也是值得的,特别是当哈希函数是由函数调用者提供时。然而,在开地址哈希表中进行双散列时,进行取模的原因就不一样了。在这种情况下,双散列所产生的哈希编码可能超出