哈希表

• 位数大的时候可以分组然后求和
• 可以除余
• 随机数法

冲突处理：

• 开放地址法 $H_i=(H_{i-1}+d_i)(\mathrm{mod}m)$
  • 线性探测：$d_i=c\times i$ 分散性不行
  • 平方探测再散列： $1^1,-1^1,2^2,-2^2$ 可能很难找到
  • 随机探测：$d_i$ 是一组随机数列，或者 $d_i=i\times H_i(key)$ 双散列函数探测 相对效果好，但是计算量大
• 再哈希法：设计 n 个不同的哈希函数，解决冲突的可能性更高
• 链地址法：将关键字发生冲突的记录记载同一个线性链表里，查找性能最优
• 公共溢出区：将和基本表中的关键字发生冲突的所有记录都存在溢出表中