知识卡片

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

双散列步长须与槽数互素

理解等级:中级

双散列用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是两个辅助哈希函数,它们与其他的哈希函数一样,