Question

1.综述

散表表仅支持 INSERT、SEARCH、DELETE 操作。

把关键字 k 映射到槽 h(k) 上的过程称为散列。

多个关键字映射到同一个数组下标位置称为碰撞。

好的散列函数应使每个关键字都等可能地散列到 m 个槽位中

2.散表函数

（1）若函数为 h(k)=k，就是直接寻址表

（2）除法散列法：h(k) = k mod m

（3）乘法散列法：h(k) = m (k A mod 1) (0<A<1)

（4）全域散列：从一组仔细设计的散列函数中随机地选择一个。（即使对同一个输入，每次也都不一样，平均性态较好）

3.冲突解决策略

（1）链接法

（2）开放寻址法

a.线性探测：h(k, i) = (h'(k) + i) mod m

b.二次探测：h(k, i) = (h'(k) + c1i + c2 i^2) mod m

c.双重散列：h(k, i) = (h1(k) + i * h2(k)) mod m

（3）完全散列：设计一个较小的二次散列表