Hash Table
基本概念
- 散列函数：一个把查找表中的关键字映射成该关键字对以韩国的地址的函数，记为
Hash(key) = Addr，其中Addr可以是数组下标、索引或者内存地址等。 - 散列表：根据关键字而直接进行访问的数据结构。
冲突：散列函数可能把两个或者两个以上的不同关键字映射到统一地址； 同义词：在冲突中发生碰撞的不同关键词；
散列表建立了关键字和存储地址之间的一种直接映射关系。
理想情况下，对散列表进行查找的时间复杂度为O(1),即与表中元素的个数无关。
散列函数构造方法
首先我们要注意以下几点：
- 定义域必须包含全部需要存储的关键字，至于的范围依赖于散列表的大小或地址范围；
- 散列函数计算出来的地址应该等概、均匀地分布在整个地址空间中，从而减少冲突的发生；
- 散列函数尽量简洁：较短的时间内计算出任一关键字对应的散列地址。
常见的散列函数
选用不同方法的目的：尽量降低产生冲突的可能性
直接定址法
- 直接取关键字的某个线性函数值为散列地址；
- 散列函数
H(key) = key or H(key) = a * key + b; - 最简单，不会产生冲突；
- 适合关键字的分布基本连续的情况；否则空位较多，浪费存储空间。
除留余数法
- 散列表表长
m，一个不大于m但最接近或等于m的质数p； - 散列函数：
H(key) = key % p； - 最简单，最常用；
- 此方法的关键为选好p，使得每个关键字通过该函数转化后等概率地映射到散列空间上的任一地址，尽可能减少冲突的可能性。
数字分析法
- 设关键字为
r进制，而r个数码在各位上出现的频率不一定相同。选取数码较为均匀的若干位作为散列地址； - 适用于已知关键字集合（如果更换了关键字，需要重新构造新的散列函数）。
平方取中法
- 取关键字的平方值的中间几位作为散列地址；
- 具体取多少位视具体情况而定；
- 特点：散列地址分布比较均匀(因为得到散列地址的过程与关键字的每位都有关系)；
- 适用于每位关键字都不够均匀或均小于散列地址所需的位数。
处理冲突的方法
开放定址法
可存放新表项的空闲地址向它的同义词表项和非同义词表项开放。
递推公式：
式子里面H(key)为散列函数；i = 0,1,2,...,k；m表示散列表表长，为增量序列。
增量序列确定之后，对应的处理方法就是确定的。通常有4种取法：
- 线性探测法：冲突发生时，顺序查看表中下一个单元(
m-1的下一个为0)，直到找出一个空闲单元。增量序列的范围为0,1,2,…,m-1。后果：会造成大量元素在相邻的散列地址上“聚集/堆积”起来，降低了查找效率。 - 平方探测法：
,其中
。散列长度
m为可以表示为4k+3的素数，也称为二次探测法；可以避免出现堆积问题，缺点是不能探测到散列表上的所有单元，但至少可以探测到一半单元。 - 再散列法：
，也成为双散列法。通过第一个散列函数H(key)得到的地址发生冲突时，利用第二个散列函数Hash2(key)计算该关键字的的地址增量 -
，
i为冲突次数，初始为0。在散列法，最多经过m-1次探测就会遍历表中的所有位置，回到H0。 - 伪随机序列法:
=伪随机序列。
开放定址法的情况下，不能随便物理删除表中已有元素(如果删除元素，就会截断其他具有相同散列地址的元素的查找地址)。处理方法是给要删除的元素做一个删除标记，进行逻辑删除(这样做的副作用：执行多次删除操作之后，表面上看起来散列表很满，实际上有许多位置未利用，故而定期维护散列表，把有删除标记的元素物理删除)。
拉链法
也叫：链接法，chaining
把所有的同义词存储到一个线性链表中，此线性链表由其散列地址唯一标识。
散列地址为i的同义词链表的头指针存放在散列表的第i个单元。
查找、插入和删除操作主要在同义词链表中进行。
链表法适用于经常进行插入和删除操作的情况。
散列查找以及性能分析
查找过程与构造散列表的过程基本一致：
- 初始化：
Addr = Hash(key) - 检测查找表中地址为
Addr的位置上是否有记录：若无记录，则查找失败；若有，则比较它与key的值，如果相等，返回查找成功标志，否则执行步骤3； - 用给定的处理冲突方法计算“下一个散列地址”，并把
Addr置为此地址，转入步骤2。
总结
虽然散列表在关键字与记录的存储位置之间建立了直接映像，但是由于“冲突”的产生，使得散列表的查找过程仍是一个给定值和关键字进行比较的过程。因此仍需以平均查找长度作为衡量散列表的查找效率的度量。
散列表的平均查找效率取决定于三个因素：散列函数、处理冲突的方法和填装因子。
填装因子：定义一个表的装满程度，
，其中n为表中记录数，m为散列表长度。 散列表的平均查找长度依赖于散列表的填装因子。填装因子越大，表示填装的记录越满，发生冲突的可能性越大；反之，越小。