6.3 Hash（哈希）表

1. 散列函数构造方法

• 直接定址法：H(key) = a * key + b
  这种方法计算最简单，而且不会产生冲突，但是如果关键字分布不连续，空位较多，浪费空间。适用于，关键字分布基本连续情况。

• 除留余数法：H(key) = key % p
  核心：选好p使得每一个关键字通过该函数转换后等概率地映射到散列空间的任一地址。
  p的选法：假定散列表表长为m取一个不大于m但最接近或等于m的质数p

• 数字分析法
  设关键字是r进制数，选取数字在上面出现频率比较均匀的若干位作为散列地址，这种方法适用于已知关键字集合。

• 平方取中法
  取关键字平方中间的几位作为散列地址，适用于关键字每一位取值都不够均匀或均小于散列地址所需位数。

• 折叠法
  把关键字分割成几个位数相同的部分，然后相加的和作为散列地址。适用于，关键字位数很多，每一位数字分布大致均匀。

2. 冲突处理

缺点：删除记录的时候不能把空间腾出，要留一个标记。因为因地址冲突的关键字寻址，需要寻得它前面一个冲突的关键字地址。

• 开放定址法
  H_i = (H(key) + d_i) % m
  d_i为增量序列

• 线性探测法：d_i = 1，2，3，4....,m - 1
  按顺序往后逐一保存，可能造成把一个区域的位置填满，导致很多关键字保存时出现冲突，只好往后移，大量元素在相邻的散列地址上“聚集”起来。

• 平方探测法：d_i = 1^2, -1^2, 2^2, -2^2,..., k^2, -k^2，其中k <= m / 2 ，m必须可表示成 4k + 3
  缺点：不能探测到所有单元，但是至少可以探测一半

• 再散列法：再用一个哈希函数求增量，d_i = Hash₂(key)

• 伪随机序列法：d_i 是已保存的伪随机序列

• 拉链法
  存储单元保存指针，指针指向链表，所有地址一样的关键字保存在链表上。

3. 散列查找

1. 使用哈希函数计算找到地址，地址为空则查找失败
2. 找到地址，出现冲突，通过处理冲突方法找到下一个地址，如果仍是冲突，重复上一步，直到找到或者存储单元为空

4. 性能分析

1. 平均查找长度是度量：根据散列表长度，元素个数，散列函数，解决冲突方法，计算查找成功的平均查找长度，查找不成功的平均查找长度。
2. 装填因子 = 表中记录数 / 散列表长度