知识卡片
乘法散列提取乘积小数部分
乘法散列先计算kA的小数部分,再放大到m个槽并向下取整:h(k)=⌊m·frac(kA)⌋,其中0。02802–02803补全正文缺失符号,常用A≈(√5−1)/2≈0.618。
按书中截断常数A=0.618的算例,k=6341得到3918.738,小数部分0.738,m=2000时映到1476。若改用更精确A,不能继续声称结果一定相同。方法可较灵活选择m,但实际分布仍需看键及计算精度。
后文容量例应保持同一分母:4500/2250=2,4500/2500=1.8;原句把2250与2500混写。无论哪一个,负载都是平均值,不是每桶绝对上限。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
乘法 与取余法不同的是乘法,它将整型键k乘以一个常数A(0<A<1);取结果的小数部分;然后乘以m取结果的整数部分。通常情况下,A取0.618,它由减1再除以2得到。这个方法称为乘法,正式的表述为: 这种方法有个优点是,对于表中槽位个数m的选择并不需要像取余法中那么慎重。例如:如果表有m=2000个
参考来源
- 位置:《算法精解:C语言描述》第8章《选择哈希函数》(spine1267;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1234.html;u122-ch08-008)。
- 结论依据:122乘法全部文字与02802根式/02803完整向下取整公式实际阅读,保留原算例常数精度和分母笔误的区别。
- 原始内容:乘法 与取余法不同的是乘法,它将整型键k乘以一个常数A(0<A<1);取结果的小数部分;然后乘以m取结果的整数部分。通常情况下,A取0.618,它由减1再除以2得到。这个方法称为乘法,正式的表述为: 这种方法有个优点是,对于表中槽位个数m的选择并不需要像取余法中那么慎重。例如:如果表有m=2000个