构造

冲突

1. 开放定址 $H[i]=(H(key)+d[i]) \ \mathrm{mod} , m$ $d[i]$ 为冲突后寻找新地址增量，因为可能冲突多次所以是一个序列
   1. 线性探测：$d[i]=1,2,\dots,m-1$
   2. 平方探测：$d[i]=\pm1^{2},\pm2^{2},\dots,\pm \lfloor \frac{m}{2} \rfloor^{2}$ 必须满足 $m = 4k+3$
   3. 双散列：$d[i]=i \cdot\mathrm{Hash}_{2}(key)$
   4. 伪随机：$d[i]=伪随机数列$
2. 拉链法 = 每个表项对应一个链表，冲突就放进链表里