哈希表（散列表）详解
基本概念
散列方法（hashing）：一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法。以最基本的向量作为底层支撑结构，通过适当的散列函数在词条的关键码与向量单元的秩之间建立起映射关系。散列表（hashtable）：逻辑上由一些列可存放词条（或者其引用）的单元（称作桶（bucket）或桶单元）组成。各桶单元按照其逻辑次序在物理上连续排列。通常直接使用数组进行排列，这时散列表也称作桶数组（bucket array）地址空间（address space）：如果桶数组的容量为R，则其中合法秩的区间[0,r)也称作为地址空间。
散列函数（hash function）：用来描述散列方法，是从关键码空间到桶数组地址空间的函数。比如下面的hash()：
1 | hash() : key -> hash(key) |
key的散列地址（hashing address）：也就是上面的hash(key) 。
完美散列（perfect hashing）：在时间和空间性能方面均达到最优的散列，也就是没有空余，没有重复的散列。
装填因子（load factor）：散列表中非空桶的数目与桶单元总数的比值。是散列表的空间利用率度量方法。
散列冲突（collision）：关键码不同的词条映射到同一个散列地址的情况。
词条的聚集（clustering）：词条集中到散列表内少数若干桶中（或附近）的现象。
综上散列表的基本构思概括为：
开辟物理地址连续的桶数组hba[],借助散列函数hash(),将词条关键码key映射为桶地址hash(key),从而快速确定待操作的词条的位置。
散列函数
好的散列函数应该具备的条件：
- 确定性 ：也就是说词条E的映射地址hash(E.key)必须完全取决于E.key。
- 简单性 ：映射过程不能过于复杂
- 所有关键码经过映射后应该尽量覆盖整个地址空间。也就是说hash()最好是满射。
- 均匀性 ：最重要的原则，关键码映射到各个桶的概率是同等的，应该尽量为1/R ，R为散列表长度或容量。
直接定址法
直接定址法：关键码就可以直接用作为散列地址
1 | hash(key)=key |
除余法（devision method）
除余法：选择一个适当的正整数R,用R去除关键码去除关键码,余数作为 散列地址.这个方法的关键是选取适当的R。一般R为素数，采用素数表长是是降低聚集发生概率的捷径。
1 | hash(key)=key mod R //R为散列表长度或容量。一般R为素数。 |
缺点：残留有某种连续性，比如相邻关键码所对应的散列的地址，总是彼此相邻。
MAD法（multiply-add-divide method）乘加除法
乘加除法：需要依次执行乘法，加法，和除法运算得名。
解决的问题：用来克服除余法的连续性缺陷。
1 | hash(key)=(a * key + b)mod R //a>0，b>0，且(a mod R) !=0 |
数字分析法（selecting digits）
数字分析法：从关键码key中特定进制的展开中抽出特定的若干位，构成一个整型地址。对关键码的各位进行分析（多种方法），丢下分布不均匀的位，留下均匀的位作为地址。
数字分析法举例：
- 平方取中法（mid-square）
- 折叠法（folding）
- 一般折叠
- 往复折返式折叠
- 异或法（xor）
- 一般异或
- 往复折返式异或
伪随机数法
越是随机，越是没有规律的就是好的散列函数。
1 | hash(key)=rand(key) mod R //R为散列表长度或容量。 |
冲突及其排解
开散列策略/封闭定址
开散列（open hashing）或封闭定址（closed addressing）：
- 开放基本的散列表结构，引入次级关联结构。
- 散列表中的地址只对特定的词条开放（每个桶可以只能能存放特定的一组词条）。
多槽位法（multiple slots）
多槽位法：将每个桶细分为更小的称作槽位（slot）的若干单元，每一组槽位可以组织为向量或列表。//类似于二维数组
独立链法（separate chaining)（拉链法）
拉链法：某些哈希地址可以被多个关键字值共享，这样可以针对每个哈希地址建立一个单链表。//引入链表
先计算哈希地址，然后搜索该地址的单链表。
公共溢出区法（overflow）
在原有散列表hashA之外再设置一个公共溢出区（散列表hashB），如果抽入词条发生冲突，就将该词条转存至公共溢出区（散列表hashB）中。 //引入新的散列表
可以说是一种递归形式的散列表。
闭散列策略/开放定址
闭散列（open hashing）或开放定址（closed addressing）：
- 仅仅依靠基本的散列表结构，就地排解冲突。
- 散列表中的地址对所有的词条开放（每个桶可以都有可能存放任一词条）。
- 一个桶冲突了，只允许在散列表内部为其寻找另一空桶。
线性试探法（linear probing）
线性试探法：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
被尝试的桶依次为：
1 | [(hash(key) + i)mod R ] ,i=1,2,3,... |
平法试探法（二次探测法）
被尝试的桶依次为：
1 | [(hash(key) + i^2)mod R ] ,i=1,2,3,... |
伪随机试探法
被尝试的桶依次为：
1 | [rand(i)mod R ] ,rand(i)为系统定义的第i个随机数。 |
再散列法（rehashing）
再散列法：使用哈希函数去散列一个输入的时候，如果输出是同一个散列地址就再次散列，直至不发生冲突为止。
缺点：每次冲突都要重新散列，计算时间增加。
被尝试的桶依次为：
1 | //hash2为二级散列函数 |
本文许可证
本文遵循 CC BY-NC-SA 4.0（署名 - 非商业性使用 - 相同方式共享） 协议，转载请注明出处，不得用于商业目的。
#
散列表