知识卡片
线性探查会聚集连续占用槽
线性探查用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'是一个辅助哈希函数,就像任何哈希函数的选择方法一样,它会尽可能地将元素随机和均匀地