散列表（Hash table，也叫哈希表），是根据 键（Key） 而直接访问在内存储存位置的数据结构。
散列表通过某一函数将键（Key） 转换为数组的下标，这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数的作用是将键（Key）映射到一个有限的整数空间上。
散列函数
@todo
冲突解决
如果对于不同的 K1、K2，经过散列函数计算出的散列值一样，就发生了散列冲突（碰撞）。
散列表解决冲突的方法主要有：
- 开放定址法
- 线性探测
- 平方探测
- 伪随机探测
- 再哈希法
- 链表法
- 建立公共溢出区
开放定址法：$$ H_i = ( hash(key) + d_i ) mod M , i = 1,2..k(k <= M-1)$$ 其中 hash 是散列函数，m 是散列表数组大小。根据 di 的取值不同，开放定制又分为：
- 线性探测法：di = 1,2 …
- 平方探测法：di = 1^2, 2^2 …
- 伪随机探测法：需要一个初始随机种子 seed，和一个随机数产生器，例如
di=random(seed)，产生一个随机数序列, 伪随机函数random()的特点是，如果种子相同，那么random()产生的随机数序列是一样的；
再散列法：建立多个不同的散列函数 $$ H_i = hash_i(key), i=1,2…k(k <= m-1) $$，若 Hash1 函数计算的散列值发生冲突, 再用 hash2 计算，直到没有冲突；
链表法：冲突的元素放入链表，将链表放入 table[i]（设 i= h(key) mod m）的位置；
建立公共溢出区：需要创建一个溢出区, 所有产生冲突的元素放入此溢出区；
➤ 几种冲突处理的比较：
开放定址法的缺点：
- 当冲突多的时候数据容易出现堆积（聚集），这时候对查找效率低，因为要多次处理冲突；（聚集：因为表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放，所以不可避免会造成聚集现象）
- 删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词（散列值相等）结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不能真正删除结点；
相比链表法的优点：
- 链表法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短（但如果冲突产生，则需要查找链表）；
开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多 table 数组的空间。
在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点较麻烦，参上