散列表（哈希）

相关定义

1. 散列表：有限连续的地址空间。
2. 冲突：不同关键字对应同一个散列地址。
   冲突是不可避免的。
3. 同义词：发生冲突的不同关键字。

构造散列函数

原则

1. 减少冲突。
2. 散列地址分布均匀。

常用方法

1. 直接定址
   1）条件：已知关键字每一位的数字分布情况。
   2）操作：从关键字中提取数字分布比较随机的若干位作为散列地址。
2. 平方取中
   取关键字平方后的中间几位，具体位数由表长决定。
3. 折叠
   将关键字分割成位数相同的多个部分，叠加求和，舍去进位，取与前面相同的位数。
   适用于散列地址位数少，关键字位数多。
   1）移位叠加：最低位对齐
   2）边界叠加：按照折叠绳子的方式叠加
4. 除留余数
   选择一个比表长小的最大素数取模。

处理冲突

1. 开放地址
   H0发生冲突时，基于H0用某方式计算得到下一个H，直到不发生冲突为止。
   1）线性探测法
   假想成一个循环表，先从冲突地址下一个位置进行寻找，如果到表尾也没找到位置，就从表头开始再找，如果还是找不到，做溢出处理。

2）二次探测法
每次从冲突位置的前后k²位置查找。
3）伪随机探测法
增量序列等于一个伪随机数序列。
2. 链地址
同义词链表：散列地址相同的关键词放进一个单链表。
一个数组存放头指针。

分析

1. 线性探测法

• 优点：只要表没满，总能找到合适的位置。
• 缺点：二次聚集（第一个散列地址不同的关键字在寻找后续散列地址的过程中再次冲突）。

2. 二次探测法/伪随机探测法

• 优点：没有二次聚集。
• 缺点：不一定找得到位置。

3. 链地址
   没有二次聚集。

散列表查找

算法分析

1. 装填因子α
   α = 表中填入记录数 / 散列表长度
   表示散列表的装满程度。α越大，冲突可能性越大，需要比较的关键字个数越多。
2. 影响平均查找长度的因素：处理冲突的方法和装填因子。
   平均查找长度与α有关，与n无关。

线性探测法 成功(1/2)(1+1/(1-α)) 失败(1/2)(1+(1-α)²)
二次探测法/伪随机探测法 成功(-ln(1-α)/α) 失败(1/(1-α))
链地址法 成功(1+α/2) 失败(α+exp(-α))