知识卡片

普通读书笔记卡 · 3620.c.1.d.2

双重哈希步长须互素

理解等级:高级

双重哈希在含 m 个槽的表中,令 i=0,1,… 表示第几次探测,并按 h(k,i)=(h₁(k)+i·h₂(k)) mod m 访问槽位:h₁(k) 决定起点,h₂(k) 决定每次向前跨多少槽,两者都随键 k 变化。

步长与表长 m 必须互素,探测才能遍历全部槽;若 m 是 2 的幂,让步长总为奇数即可。

否则可能在表未满时循环访问少数槽。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 .