← 返回刚才阅读的位置

知识卡片

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

线性探查会聚集连续占用槽

理解等级:中级

线性探查用h(k,i)=(h′(k)+i) mod m,i从0开始逐次增加,遇到表尾再回到开头。例如m=1000、h′(2998)=998时,序列从998、999、0继续,步长1可覆盖全部槽。

连续占用段会让落在这段上的新键都向段尾寻找,从而更易延长已有段,形成基本聚集。02822中11槽先放37、83、97、78、14,再放59需查4、5,放25需查3、4、5、6、7,放72需查6、7、8。聚集使探查更长,并不表示固定表容量自动变大。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      线性探查 开地址哈希表中一种简单的探查方法就是探查表中连续的槽位。正式地表述为,如果i大于0小于m-1(m为表中的槽位个数),那么一个线性探查方法的哈希函数定义为: h(k,i)=(h'(k)+i)mod m 函数h'是一个辅助哈希函数,就像任何哈希函数的选择方法一样,它会尽可能地将元素随机和均匀地

    参考来源

    - 位置:《算法精解:C语言描述》第8章《冲突解决》(spine1276;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1243.html;u133-ch08-015)。 - 结论依据:133线性全部段落、公式和02822四阶段实际图完整实读,按槽号与给定模11逐项核对;未执行。 - 原始内容:线性探查 开地址哈希表中一种简单的探查方法就是探查表中连续的槽位。正式地表述为,如果i大于0小于m-1(m为表中的槽位个数),那么一个线性探查方法的哈希函数定义为: h(k,i)=(h'(k)+i)mod m 函数h'是一个辅助哈希函数,就像任何哈希函数的选择方法一样,它会尽可能地将元素随机和均匀地