1.哈希表（HashTable）
（1）哈希表定义
又称散列表，是一种数据结构，数据元素的关键字与其存储地址直接相关
（2）同义词
若不同的关键字通过散列函数映射到同一个值，则称为“同义词”
（3）冲突
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”
（4）填装因子
装填因子=表中记录数/散列表长度
2.常见哈希函数
| 哈希函数 | 描述 | 公式 | 适用场景 |
|---|---|---|---|
| 除留余数法 | 散列表表长为m，取一个不大于m但最接近或等于m的质数p | H ( k e y ) = k e y % p H(key)=key\%p H(key)=key%p | 关键字范围相差较大的情况 |
| 直接定址法 | 通过取关键字或关键字的某个线性函数值为哈希值，从而确定数据在哈希表中的存储位置 | H ( k e y ) = k e y H(key)=key H(key)=key或 H ( k e y ) = a ∗ k e y + b H(key)=a*key+b H(key)=a∗key+b | 关键字的分布基本连续的情况 |
| 数字分析法 | 选取数码分布较为均匀的若干位作为散列地址 | 无 | 关键字集合已知，若更换了关键字，则需要重新构建新的哈希函数 |
| 平方取中法 | 取关键字的平方值的中间几位作为散列地址 | 无 | 关键字的每位取值都不够均匀或均小于散列地址所需的位数 |
3.常见处理冲突的方法
（1）开放定址法
指可存放新表项的空闲地址既向它的同义词表项开放，又向他的非同义词表项开放。其数学递推公式：
H
i
=
(
H
(
k
e
y
)
+
d
i
)
%
m
H_i=(H(key)+d_i)\%m
Hi=(H(key)+di)%m； i = 0,1,2,…,k(k<=m-1)；m表示散列表表长；
d
i
d_i
di为增量序列；i可理解为“第i次发生冲突”
| 开放定址法种类 | 增量序列 |
|---|---|
| 线性探测法 | d i = 0 , 1 , 2 , 3 , . . . , m − 1 d_i=0,1,2,3,...,m-1 di=0,1,2,3,...,m−1 |
| 平方探测法 | d i = 0 2 , 1 2 , ( − 1 ) 2 , 2 2 , ( − 2 ) 2 , . . . , k 2 , ( − k ) 2 d_i=0^2,1^2,(-1)^2,2^2,(-2)^2,...,k^2,(-k)^2 di=02,12,(−1)2,22,(−2)2,...,k2,(−k)2； k < = m / 2 k<=m/2 k<=m/2；注：散列表长度m必须是一个可以表示成4j+3的素数，才能探测到所有位置 |
| 伪随机序列法 | d i d_i di是一个伪随机序列 |
注：采用开放定址法解决冲突的时，删除结点不能简单地被删除结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，应进行逻辑删除
（2）再哈希法
除了原始的哈希函数之外，多准备几个哈希函数，当哈希函数冲突时，用下一个哈希函数计算新地址，直到不冲突为止
（3）拉链法
把所有同义词存储在一个链表里