5.散列表

散列表的基本概念

• 散列表（哈希表，Hash Table)：是一种数据结构。特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址
• 散列函数（哈希函数）：Addr=H(key)建立了“关键字”$\to$“存储地址”的映射关系。

散列函数的构造方法

直接定址法

直接取关键字的某个线性函数值为散列地址

除留余数法

最简单，最常用。选取一个不大于表长但是接近或等于表长的质数

数据分析法

选取数码分布较为均匀的若干位作为散列地址。

平方取中法

取关键字的平方值的中间几位作为散列地址。适合关键字每位取值都不均匀

处理冲突的方法

开放定址法

线性探测法

冲突时顺序查看一下个单元

平方探测法

查看$0^2,1^2,-1^2,2^2,-2^2\dots$

这种方法可以避免出现“堆积”，但是没法探测到每一个单元

双散列表

使用两个散列函数，第一个散列函数得到的地址冲突时，第二个散列函数计算增量

伪随机序列法

注意

在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此,可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

拉链法（链接法）

散列查找及性能分析

散列表的查找效率取决于：散列函数、处理冲突的方法和装填因子。

装填因子

$$\displaystyle \alpha = \frac{\text{表中记录}n}{\text{散列表长度}m}$$

散列表的平均查找长度依赖于散列表的装填因子，而不直接依赖$m,n$