Hash

解决碰撞的方法

Chaining

把键相同的链起来。设 $n$ 表示键的个数，$m$ 表示槽的个数。$\alpha :=\frac{n}{m}$ 表示 load factor，平均每个槽里有多少个元素。

• 期望的查找时间：$\Theta (1+\alpha )$

开放寻址

• 线性寻址：$h(k,i):=(h^{\prime }(k)+i)\mathrm{mod}m$
• 双哈希：$h(k,i):=(h_1(k)+i\times h_2(k))\mathrm{mod}m$

哈希函数

1. $h(k):=k\mathrm{mod}m$
2. $h(k):=(Ak\mathrm{mod}{2}^w)\gg (w-r)$，即取 $Ak$ 模字长的高 $r$ 位
3. $h_a(k):={\sum }_{i=0}^r{a}_i{k}_i\mathrm{mod}m$，即取质数 $m$，把 $k$ 表示成 $m$ 进制数 $(k_r\cdots k_0{)}_m$，然后点乘一个随机向量