[数据结构与算法]408-数据结构-哈希表

哈希表是数据结构，特点是关键字与存储地址存在某种映射关系，通常关系由哈希函数表示addr = f(key)。

哈希表存在数据多于存储地址的情况。所以哈希函数在地址视角下是一对多的关系。也就是多个关键字可能对应着同一个存储地址。那么可能会产生冲突，也就是映射点已经存放了数据。

构造哈希表需要构造哈希函数，如果哈希函素构造好，可能会使得每一个数据都在哈希表中直接占据映射位置，也就是呈现出通过哈希函数的到地址直接就是数据。那么这样可以使得查找在O(1)复杂度下。如果产生冲突，就需要构建一定机制存放冲突数据，那么查找时间也会收到影响，所以构造哈希函数的目标是尽可能减少冲突的可能。

常见哈希函数：

1. 除留余数法
   就是f(key) = key%m。这里m通常取不大于表长的最大质数，这么做优点是可能减少冲突，因为如果是合数，在特殊数据情况下，这些数据都会映射到相同的值，例如m取8，数据都是2的倍数，但素数不会出现这种情况。缺点就是有一部分的哈希表完全就是浪费空间。
2. 直接定址法
   也就是线性方式 f(key) = a * key + b。
3. 平方取中法
   通常是取某几位然后平方来进行映射，因为关键字可能在某几位分布较为聚集，在某几位分布较为均匀。那么就取均匀几位再平方能够降低冲突可能。

处理冲突的方式：

1. 拉链法
2. 开放地址法

拉链法也就是将哈希表每一个单元作为一个链表头，同义词存储在相同链表下。计算查找长度通常计算比较关键字的次数，在链表判断那里通常不加入考虑。失败的ASL = 装填因子。也就是表中的记录数/哈希表长度。

开放地址法指的是空闲地址允许存储非同义词表项，也就是非空闲地址存储的不一定是哈希映射来的关键字。
通常通式可以表示为
$$H_i=(H(key)+d_i)modm$$
m表示表长。其中di针对不同方案取不同序列，通常有三种方式，线性探测法，平方探测法，伪随机序列法。

线性探测法 di = 0, 1, 2, 3 …
也就是在插入时候，如果发生冲突，就一直往右边走，如果碰壁从头继续，直到没有空闲地址为止。
查找时候，进行映射之后，就需要一直往右查找，直到遇到空闲块为止。空空闲块的判断也要算作一次比较关键词次数
删除需要注意，开放地址法不能直接将需要删除结点置空，因为查找算法是遇到空闲块为止，如果右侧还有同义词，置空该项会使得右侧同义词查找不到。所以只能假删除假置空。

平方探测法 di = 0, 1², -1²,2²,-2²…
其余类似。

伪随机数就是生成一个伪随机序列di。不是重点。