1、Hash的概念

  • 散列方法的主要思想是根据结点的关键码值来确定其存储地址，按散列存储方式构造的存储结构称为散列表（hash table），散列表中的一个位置称为槽(slot)
  • 一般情况下，散列表的空间必须比结点的集合大，空间换时间的检索效率

  • 建立散列表时，若关键码与散列地址是一对一的关系，在检索时只需根据散列函数对给定值运算，即可得到待查结点的存储位置。但散列函数可能对不相等的关键码计算出相同的散列地址（冲突 collision）

    2、散列函数

  • 选取原则：

    • 运算尽可能简单
    • 函数的值域必须在散列表的范围内
    • 尽可能使得结点均匀分布，也就是尽量让不同的关键码具有不同的散列函数值

      （1）除余法

  • 用关键码 x 除以 M（往往取散列表长度），并取余数作为散列地址

  • 最简单的散列方法，散列函数为： h(x) ＝ x mod M

    （2）乘余取整法

  • 先让关键码 key 乘上一个常数 A (0< A < 1)，提取乘积的小数部分。再用整数 n 乘以该值，结果向下取整，做为散列地址

  • 散列函数为： hash ( key ) = LOW ( n × ( A × key % 1 ) )，LOW(X) 表示对 X 取下整

    （3）平方取中法

  • 整数相除的运行速度通常比相乘慢

  • 先求关键码平方值，扩大相近数差别，根据表长度取中间的几位数（往往取二进制的比特位）作为散列函数值。因为乘积的中间几位数与乘数的每一数位都相关，由此产生的散列地址较均匀 | 关键字 | 关键字的平方 | 哈希函数值 | | —- | —- | —- | | 1234 | 1522756 | 227 | | 2143 | 4592449 | 924 | | 4132 | 17073424 | 734 | | 3214 | 10329796 | 297 |

（4）数字分析法

  • 假设每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体，从中提取分布均匀的若干位或它们的组合作为地址
  • 取数据元素关键字中某些取值较均匀的数字位作为哈希地址，即当关键字位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位作为哈希值

  • 只适合于所有关键字值已知的情况，通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间

    （5）基数转换法

  • 将关键码值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址

    例：Hash (80127429) = (80127429) 13 = (502432641) 10

  • 如果取中间三位作为哈希值，得 Hash（80127429）= 432。为得良好哈希函数，可将几种方法联合使用，比如先变基，再折叠或平方取中等，只要散列均匀，就可随意拼凑

    （6）折叠法

  • 当关键码所含位数多，采用平方取中法计算复杂，可将关键码分割成位数相同的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去进位）作为散列地址

  • 移位叠加：将分割后的几部分低位对齐相加

  • 边界叠加：从一端沿分割界来回折叠，然后对齐相加

    3、冲突解决的策略

  • 冲突解决技术可以分为两类：

    • 开散列方法 (open hashing，拉链法，separate chaining)
    • 闭散列方法 (closed hashing，开地址方法，open addressing)

      不同之处：开散列法把冲突的关键码存储在散列表主表之外，闭散列法把冲突的关键码存储在表中另一个槽内

（1）开散列方法

a、拉链法

把散列表中的每个槽定义为一个链表的表头，散列到一个特定槽的所有记录都放到该槽的链表中
Hash算法 - 图1

（2）闭散列方法

  • 把所有记录直接存储在散列表中
  • 每个记录关键码 key 有一个由散列函数计算出来的基位置，即 h(key)。插入一个关键码，而另一记录已占据 R 的基位置（发生碰撞），把 R 存储在表中其它地址，由冲突解决策略确定地址

  • 基本思想：

    • 冲突时，使用某种方法为关键码 K 生成一个散列地址序列 d0，d1，d2，… di ，…dm-1。其中 d0 = h(K) 称 K 的基地址地置 (home position)；所有 di (0< i< m) 是后继散列地址。插入 K 时，若基地址上结点被别的数据元素占用，按上述地址序列依次探查，将找到的第一个开放空闲位置 di 作为 K 的存储位置；若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出
    • 检索 K 时，按同值的后继地址序列依次查找，检索成功时返回该位置 di；若遇到开放的空闲地址，说明表中无待查关键码
    • 删除 K 时，按同值的后继地址序列依次查找，查找到某个位置 di 具有该 K 值，删除该位置 di 上的数据元素（删除操作实际上只对该结点加以删除标记）；若遇到开放的空闲地址，说明表中无待删关键码

      a、线性探测法

      将散列表看成是一个环形表，若在基地址 d 发生冲突，依次探查下述地址单元：d+1，d+2，……，M-1，0，1，……，d-1，直到找到一个空闲地址或查找到关键码为 key 的结点为止。若沿该探查序列检索一遍后又回到地址 d，插入和检索操作都失败

  • 用于简单线性探查的探查函数： p(K,i) = i

    例：已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散列表长度 M = 15，用线性探查法解决冲突构造这组关键码的散列表。

n = 11，利用除余法构造散列函数，选取小于 Ｍ 的最大质数 P = 13，散列函数为：
h(key) = key % 13
按顺序插入各结点：
h(26) = 0，h(36) = 10， h(41) = 2，h(38) = 12， h(44) = 5，插入15时，其散列地址为 2，已被关键码 41 的元素占用，进行探查。按顺序探查法，3 为开放空闲地址，将其放在 3 单元。类似地，68 和 12 可分别放在 4 和 13 单元中

b、二次探查法

基本思想：生成的后继散列地址不连续，是跳跃式的，以便为后续数据元素留下空间而减少聚集

探查序列依次为：12，-12，22 ，-22，… 等，冲突时，将同义词来回散列在第一个地址的两端。求下一个开放地址的公式为：
Hash算法 - 图2

c、随机探查法

理想的探查函数应当在探查序列中随机地从未访问过的槽中选择下一位置。但实际上不能实现，在检索关键码时不能建立起同样的探查序列。可以做一些类似伪随机探查 (pseudo-random probing) 的事。在伪随机探查中，探查序列中的第 i 个槽是 (h(K) + ri) mod M，其中 ri 是 1 到 M - 1 之间数的“随机”数序列。所有插入和检索都使用相同的“随机”数

  • 探查函数是：p(K,i) = perm[i - 1]，perm 是一个长度为 M - 1的数组，包含从 1 到 M – 1 的随机序列

    例：已知哈希表长度 m = 11，哈希函数为：H(key) = key % 11，则 H(47) = 3，H(26) = 4，H(60) = 5，假设下一个关键字为 69，则 H(69) = 3，与 47 冲突。

  • 用线性探测再散列处理冲突：下一个哈希地址为 H1= (3 + 1) % 11 = 4，仍冲突，下一个哈希地址为 H2 = (3 + 2) % 11 = 5，还冲突，下一个哈希地址为 H3 = (3 + 3) % 11 = 6，不冲突，69 填入 5 号单元

  • 用二次探测再散列处理冲突，下一个哈希地址为 H1=（3 + 12）% 11 = 4，仍然冲突，下一个哈希地址为 H2 =（3 - 12）% 11 = 2，此时不再冲突，将 69 填入 2 号单元
  • 用伪随机探测再散列处理冲突，伪随机数序列为：2，5，9，……..，下一个哈希地址为 H1 = (3 + 2) % 11 = 5，仍冲突，下一个哈希地址为 H2 = (3 + 5) % 11 = 8，不冲突，69 填入 8 号单元

Hash算法 - 图3

d、双散列探查法

伪随机探查和二次探查都能消除基本聚集，即基地址不同的关键码，其探查序列的某些段重叠在一起的问题。若两个关键码散列到同一基地址，采用这两种方法还是会产生聚集。因为伪随机探查和二次探查产生的探查序列只是基地址函数，而不是原来关键码值的函数（二级聚集 secondary clustering），避免二级聚集，需使探查序列是原来关键码值的函数，而不是基位置的函数，可以利用第二个散列函数作为常数，每次跳过常数项，做线性探查