COMP4133AADS►练习复习

COMP4133AADS 课程练习复习：Lecture 2 Maps & Hash Tables（含答案）

Lecture 2 练习题复习（Maps & Hash Tables）— 含答案与思路

本讲核心：Map ADT（接口与复杂度）+ Hash Table 实现（哈希函数设计、压缩函数、冲突处理：链地址 / 线性探测 / 双哈希）
建议刷题顺序：Map 操作追踪 → 哈希函数思考题 → 线性探测（插入/查找/删除）→ 双哈希（为何要素数表长 + 计算探测序列）。

练习 0：Map ADT 操作追踪（Lecture2 p7）

题目（按顺序执行操作，填 Output，并写出每一步 Map 的内容）：

Operation Output Map（key→value）
isEmpty()
put(5, A)
put(7, B)
put(2, C)
put(8, D)
put(2, E)
get(7)
get(4)
get(2)
size()
remove(5)
remove(2)
get(2)
isEmpty()

解题思路（必背语义）

  • put(k,v)：
    • 若 k 不存在：插入并返回 null
    • 若 k 已存在：用新值替换旧值，返回旧值
  • get(k)：不存在返回 null
  • remove(k)：不存在返回 null；存在则删除并返回旧值
  • size()：当前 key 的个数（key 唯一）

标准答案（逐步追踪）

Operation Output Map（key→value）
isEmpty() true {}
put(5, A) null {5→A}
put(7, B) null {5→A, 7→B}
put(2, C) null {5→A, 7→B, 2→C}
put(8, D) null {5→A, 7→B, 2→C, 8→D}
put(2, E) C {5→A, 7→B, 2→E, 8→D}
get(7) B {5→A, 7→B, 2→E, 8→D}
get(4) null {5→A, 7→B, 2→E, 8→D}
get(2) E {5→A, 7→B, 2→E, 8→D}
size() 4 {5→A, 7→B, 2→E, 8→D}
remove(5) A {7→B, 2→E, 8→D}
remove(2) E {7→B, 8→D}
get(2) null {7→B, 8→D}
isEmpty() false {7→B, 8→D}

思考题 1：为什么把 hash function 拆成 hash code + compression function？（Lecture2 p22）

题目：
What is the advantage of separating the hash function into two components, namely, hash code and compression function? Why?

解题思路（抓住“职责分离 + 可复用”）

把哈希拆成两段，本质是把 “把 key 变成整数” 和 “把整数变成表下标” 分开，方便复用/扩容/优化分布。

参考答案（考试写 3~5 点）

  • 职责分离：h1（hash code）把任意类型 key 变成整数；h2（compression）把整数映射到 [0,N−1][0, N-1]。
  • 可复用性：同一个 h1 可以配不同表长 NN 的 h2；扩容/rehash 时主要调整 NN 与压缩。
  • 更易优化分布：针对 key 类型改 h1（如字符串多项式滚动），针对表长/范围改 h2（mod / MAD）。
  • 工程上更方便：很多语言对象自带 hashCode()（相当于 h1），你只需自定义压缩映射。

思考题 2：为什么要“disperse”（分散）？为什么要“random”（看起来随机）？（Lecture2 p23）

题目：

  • Why disperse?
  • Why random?

解题思路

哈希的目标不是“算得快”，而是“均匀”。分散与随机都是为了降低碰撞与聚集。

参考答案

  • Why disperse?（为什么分散）
    让 key 尽量均匀落到 NN 个槽位，减少 collision → get/put/remove 的平均代价更接近 O(1)O(1)。
  • Why random?（为什么要看起来随机）
    防止 key 自身存在规律（例如等差、同前缀/后缀）导致某些槽位被集中命中，从而产生 clustering（探测代价变大）。

自测 1：为什么 table size 选素数更好？（Lecture2 p27–28）

题目：

  • hash codes 序列：100,105,110,115,…100, 105, 110, 115, \ldots
  • 若 N=10N=10（非素数）会发生什么？
  • 若 N=11N=11（素数）会发生什么？
  • 用 gcd(N,d)\gcd(N, d) 解释：什么时候能遍历所有槽位？什么时候只落在少数槽位？

解题思路（等差数列 mod N）

若 hash code 是等差序列 a,a+d,a+2d,…a, a+d, a+2d, \ldots，取模后能访问多少槽位，取决于 gcd(N,d)\gcd(N, d)：

  • 若 gcd(N,d)=1\gcd(N, d)=1 → 会遍历全部 NN 个槽位
  • 若 gcd(N,d)>1\gcd(N, d)>1 → 只会访问 Ngcd(N,d)\frac{N}{\gcd(N,d)} 个槽位（其余槽位永远用不到）

答案（用本题数据）

  • 这里步长 d=5d=5。
  • N=10N=10：gcd(10,5)=5\gcd(10,5)=5 → 只能访问 10/5=210/5=2 个槽位。
    例如：100 \bmod 10 = 0，105 \bmod 10 = 5，110 \bmod 10 = 0……只在 {0,5}\{0,5\} 来回跳，大量槽位闲置，碰撞会很严重。
  • N=11N=11：gcd(11,5)=1\gcd(11,5)=1（11 是素数，且 5 不整除 11）→ 能遍历全部 11 个槽位，分布通常更均匀。

练习 1：线性探测（Linear Probing）插入（Lecture2 p31）

题目：

  • N=13N = 13
  • h(x) = x \bmod 13
  • 按顺序插入 keys：18, 41, 22, 44, 59, 32, 31, 73
  • 冲突处理：线性探测（冲突就 (i+1) \bmod N 继续找空位）
  • 要求：画出最终 hash table（0…12），并写出每个 key 的 probe 序列或 probe 次数。

解题思路（机械流程）

对每个 key：

  1. 先算 i=h(k)i = h(k)
  2. 若槽空 → 放入
  3. 若槽占用 → i = (i+1) \bmod 13 继续，直到找到空槽

标准答案（最终表）

索引 0..12：

idx 0 1 2 3 4 5 6 7 8 9 10 11 12
key 41 18 44 59 32 22 31 73

各 key 的 probe 序列（写到落位即可）

  • 18：h=5 → [5]（放 5）
  • 41：h=2 → [2]（放 2）
  • 22：h=9 → [9]（放 9）
  • 44：h=5 冲突 → [5, 6]（放 6）
  • 59：h=7 → [7]（放 7）
  • 32：h=6 冲突 → [6, 7, 8]（放 8）
  • 31：h=5 连续冲突 → [5, 6, 7, 8, 9, 10]（放 10）
  • 73：h=8 冲突 → [8, 9, 10, 11]（放 11）

记忆点：线性探测会形成连续“块”，越到后面 probe 越长 → primary clustering。

练习 2：线性探测查找过程（Lecture2 p32–34）

题目 A（概念题）：How to search with linear probing?
题目 B（手算题）：在练习 1 的表里，追踪查找 key=32 的 probe 过程，写出访问下标序列。

解题思路（查找规则）

从 i=h(k)i=h(k) 开始：

  • 若槽 空 → 直接失败（说明探测链断了）
  • 若槽 key 匹配 → 成功
  • 否则继续 i=(i+1) \bmod N
  • 最多 probe NN 次（防止死循环）

标准答案（查找 32）

  • h(32)=6h(32)=6
  • 访问序列：6(44) → 7(59) → 8(32)
  • 所以 probe 序列是：[6, 7, 8]

练习 3：线性探测删除（Lecture2 p35–36）

题目：How do you remove an element x?

解题思路（为什么不能直接置空）

线性探测的查找依赖“探测链”。如果你把中间某格直接清空：

  • 查找遇到空槽会判定“失败”
  • 但其实后面可能还有通过探测放进去的元素
    → 会把后面的元素“找丢”

标准答案（DEFUNCT / tombstone）

  • 删除时不要置空，而是标记为 DEFUNCT（墓碑）
  • get(k)：遇到 DEFUNCT 不能停，继续 probe；遇到真正空槽才停
  • put(k,v)：可以把 DEFUNCT 当作可插入位置（通常优先复用第一个遇到的 DEFUNCT）

小例子（理解用）
如果 44 在 idx=6，32 在 idx=8：

  • 直接把 idx=6 置空
  • 查找 32：从 6 开始，一看空槽就失败 → 错！
    所以必须用 DEFUNCT 维持探测链连续性。

练习 4：双哈希（Double Hashing）为什么要求 N 为素数？（Lecture2 p38）

题目：

  • probe 位置：(h(k) + j\,d(k)) \bmod N，j=0,1,…,N−1j=0,1,\ldots,N-1
  • 例：h(k)=1, d(k)=3h(k)=1,\ d(k)=3
    • 若 N=12N=12，会访问哪些 positions？
    • 若 N=13N=13，会访问哪些 positions？
  • 并解释为什么 NN 取素数更容易保证“覆盖全表”。

解题思路（等差序列 mod N）

探测序列是：1, 1+3, 1+2\cdot 3, \ldots\ (\bmod\ N)
能覆盖多少槽位取决于 gcd(N,d)\gcd(N, d)：

  • gcd(N,d)=1\gcd(N, d)=1 → 覆盖全部 NN 个槽位
  • gcd(N,d)>1\gcd(N, d)>1 → 只覆盖 Ngcd(N,d)\frac{N}{\gcd(N,d)} 个槽位，形成循环

标准答案

  • N=12N = 12：gcd(12,3)=3\gcd(12,3)=3 → 只覆盖 12/3=412/3=4 个槽位
    探测：
    • j0: (1+0) \bmod 12 = 1
    • j1: (1+3) \bmod 12 = 4
    • j2: (1+6) \bmod 12 = 7
    • j3: (1+9) \bmod 12 = 10
    • j4: (1+12) \bmod 12 = 1（开始重复）
      所以 positions：{1,4,7,10}\{1,4,7,10\}。
  • N=13N = 13（素数）：gcd(13,3)=1\gcd(13,3)=1 → 覆盖全部 13 个槽位
    探测序列（按 j=0…12）：
    1,4,7,10,0,3,6,9,12,2,5,8,111,4,7,10,0,3,6,9,12,2,5,8,11（13 个都出现）

结论：素数 NN 下，只要 d(k)d(k) 不是 0 且不被 NN 整除，就更容易满足 gcd(N,d)=1\gcd(N,d)=1，从而探测覆盖全表。

练习 5：双哈希插入整套演算（Lecture2 p39–40）

题目：

  • N=13N = 13
  • h(k) = k \bmod 13
  • d(k) = 7 - (k \bmod 7)
  • 按顺序插入 keys：18, 41, 22, 44, 59, 32, 31, 73
  • probe：(h(k) + j\,d(k)) \bmod 13，j=0,1,2,…j=0,1,2,\ldots
  • 要求：画出最终表，并为每个 key 写出 probe 序列（至少写到落位为止）。

解题思路（每个 key 都要算两件事）

  1. 算 h(k)h(k)
  2. 算 d(k)d(k)
  3. 从 j=0j=0 开始生成探测位置直到找到空槽

标准答案（逐个 key）

记号：pos(j) = (h + j\,d) \bmod 13

  1. 18
  • h=18 \bmod 13=5
  • d=7-(18 \bmod 7)=3
  • j0: pos=5 空 → 放 5
  • probe：[5][5]
  1. 41
  • h=2h=2
  • d=7-(41 \bmod 7)=1
  • j0: 2 空 → 放 2
  • probe：[2][2]
  1. 22
  • h=9h=9
  • d=7-(22 \bmod 7)=6
  • j0: 9 空 → 放 9
  • probe：[9][9]
  1. 44
  • h=5h=5
  • d=7-(44 \bmod 7)=5
  • j0: 5 被 18 占 → j1: (5+5)=10 空 → 放 10
  • probe：[5,10][5, 10]
  1. 59
  • h=7h=7
  • d=7-(59 \bmod 7)=4
  • j0: 7 空 → 放 7
  • probe：[7][7]
  1. 32
  • h=6h=6
  • d=7-(32 \bmod 7)=3
  • j0: 6 空 → 放 6
  • probe：[6][6]
  1. 31
  • h=5h=5
  • d=7-(31 \bmod 7)=4
  • j0: 5 被 18 占
  • j1: (5+4)=9 被 22 占
  • j2: (5+8)=13 mod13=0 空 → 放 0
  • probe：[5,9,0][5, 9, 0]
  1. 73
  • h=8h=8
  • d=7-(73 \bmod 7)=4
  • j0: 8 空 → 放 8
  • probe：[8][8]

最终 hash table（0…12）

idx 0 1 2 3 4 5 6 7 8 9 10 11 12
key 31 41 18 32 59 73 22 44

复习要点（考试一句话总结）

  • 双哈希比线性探测更能“打散”探测路径，通常 clustering 更弱。
  • 要想探测覆盖全表，需要 gcd(N,d(k))=1\gcd(N, d(k))=1；取素数 NN 更容易满足。

一页速记（考前 60 秒）

  • Map ADT：get/put/remove 语义要清楚（存在/不存在返回什么）。
  • List-based map：get/remove/put 最坏都 O(n)O(n)（因为要找 key）。
  • Hash table：期望 O(1)O(1)，最坏 O(n)O(n)（全碰撞）。
  • Hash function：h(x)=h2(h1(x))h(x)=h_2(h_1(x))；目标：分散、看起来随机。
  • Compression：\bmod\ N 常用；N 选素数通常更均匀。
  • Collision：
    • Chaining：简单，但额外内存。
    • Linear probing：primary clustering；删除要 DEFUNCT。
    • Double hashing：(h + j\,d) \bmod N；d≠0d\ne 0，NN 常取素数确保覆盖全表。