哈希表

词汇

撒开、碰撞、化解

哈希函数 hash function 把键映射到桶：$h(k) = k \bmod 13$ 把 $4, 17, 30, 43$ 全送进 $4$ 号桶——冲突 collision。链地址法 chaining 在每个桶挂一条链；开放寻址法 open addressing 走到下一个空位。

{exercise:uni-cs0503-buckets}

练习

在 h(k) = k mod 13 下，键 4、17、30、43 都落在——

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

$m$ 个桶、$n$ 个键时，负载因子 load factor $\alpha = n/m$ 也是平均链长：固定键集 $[4, 17, 30, 43, 12, 25, 38]$ 给出 $\alpha = 7/13 \approx 0.54$——$4$ 号桶四把钥匙，$12$ 号桶三把，十个桶空着。
链地址下成功查找约 $1 + \alpha/2$ 次比较；让 $m$ 随 $n$ 增长，期望代价保持 $O(1)$——字典快，靠的就是这个扩容。

{exercise:uni-cs0503-load}

练习

13 个桶装 7 把钥匙，负载因子是——

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

对 $4, 17, 30, 43$ 线性探测：$4$ 落 $4$ 号位；$17$ 探 $4 \to 5$；$30$ 探 $4, 5 \to 6$；$43$ 探 $4, 5, 6 \to 7$。合计 $1 + 2 + 3 + 4 = 10$ 次探测插入四把钥匙。
聚集 clustering 让探测串越长，所以实用表把 $\alpha$ 压在约 $0.75$ 以下。键的低位相同时别对 2 的幂取模（选素数）；键在表里时绝不要改它。