散列表

散列表是根据关键字而直接进行访问的数据结构，它建立了关键字和存储地址之间的一种直接映射关系：

$$\mathrm{Hash}(\mathrm{key})=\mathrm{Addr}$$

散列函数的构造方法

• 直接定址法
• 除留余数法
• 数字分析法
• 平方取中法

处理冲突的方法

开放定址法（发生冲突时按某种探测序列寻找下一个空位置）：

• 线性探测法
• 平方探测法
• 再散列法
• 伪随机序列法

此外还有拉链法（链地址法），将同义词存储在一个链表中。

散列查找及性能分析

散列表的查找效率主要取决于散列函数、处理冲突的方法和装填因子 $\alpha$（表中记录数与表长的比值）。装填因子越大，冲突越多，查找效率越低。