知识卡片
双散列步长须与槽数互素
双散列用h(k,i)=(h1(k)+i·h2(k)) mod m,使不同键可以有不同的探查步长。要在重复前走遍全部槽,h2(k)与m须互素:m为2的幂时取奇数步长;m为素数时取1至m−1的步长,都可满足这一条件。
本章h2=1+(k mod m′)示例需选合适m′并保证步长范围。m=1699、m′=1697、k=15385时,h1=94、h2=113,后续位置按113递增取模;原文中间的940与算例94不符,应为94。
02823采用模11和h2=1+k mod9,59由4探到10、25由3探到0、72由6探到7,和02822相同键的线性探查有不同分布。双散列改善某些聚集不等于保证所有键无冲突或所有探查序列均匀。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
双散列 最有效地探查开地址哈希表的方法之一,就是通过计算两个辅助哈希函数哈希编码的和来得到哈希编码。正式地表述为,如果i的大小在0和m之间(m为表中槽位个数),双散列的哈希函数定义为: h(k,i)=(h1(k)+ih2(k))mod m 函数h1与h2是两个辅助哈希函数,它们与其他的哈希函数一样,
参考来源
- 位置:《算法精解:C语言描述》第8章《冲突解决》(spine1276;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1243.html;u133-ch08-016)。
- 结论依据:133双散列全部规则/公式及02823完整阶段图实读;互素条件由MIT已读开地址课程第4页补证;数值按明确m′计算,不把940笔误复述成结果。
- 原始内容:双散列 最有效地探查开地址哈希表的方法之一,就是通过计算两个辅助哈希函数哈希编码的和来得到哈希编码。正式地表述为,如果i的大小在0和m之间(m为表中槽位个数),双散列的哈希函数定义为: h(k,i)=(h1(k)+ih2(k))mod m 函数h1与h2是两个辅助哈希函数,它们与其他的哈希函数一样,