知识卡片
双重哈希步长须互素
双重哈希在含 m 个槽的表中,令 i=0,1,… 表示第几次探测,并按 h(k,i)=(h₁(k)+i·h₂(k)) mod m 访问槽位:h₁(k) 决定起点,h₂(k) 决定每次向前跨多少槽,两者都随键 k 变化。
步长与表长 m 必须互素,探测才能遍历全部槽;若 m 是 2 的幂,让步长总为奇数即可。
否则可能在表未满时循环访问少数槽。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
the value h2(k) must be relatively prime to the hash-table size m.
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.4 节(`OEBPS/chapter011.xhtml`,文本字符 [49500, 53500);图 11.5/Art_P395)。
- 结论依据:原文给出双重哈希公式、互素要求及表长为 2 的幂时取奇数步长的例子。
- 原始内容:the value h 2 ( k ) must be relatively prime to the hash-table size m .