05_散列表

什么是散列表（Hash Table）

• 根据键（Key）直接访问在内存存储位置的数据结构。
• 通过一个计算键值的函数，将所需查询的数据映射到表中的一个位置来访问记录，加快了查找速度。
• 散列表是普通数组概念的推广。借鉴于普通数组可以直接寻址，在O(1)时间访问数组的任意位置。

相关概念

• 散列函数：将key值计算为散列值的函数。
• 例：H(key) = key mod 13
• 散列冲突：不同关键字，根据散列函数，计算得到相同的散列值。

直接寻址表

• 适用场景：当关键字的全域(要存储的数据量)比较小的时候，直接寻址表是一种比较有效的方法。
• 实现方式：将key值直接作为要存入hash表的索引地址。
  • 可以视为特殊的散列表，散列函数 H(key) = key
• 优势：
  • 所有字典操作（增删改查）都只需要O(1)的时间。
• 缺点：
  • 空间浪费。比如，存一个关键字序列为[1, 3, 5, 8, 10086]共5个元素，按直接寻址方式，hash表的空间需要开到1w+。

散列表

基于直接寻址表的劣势的改进：

• 当关键字集合K << 全域 U时，希望将存储空间降低，并保持元素查找性能的优势。
• 散列函数
  • 定义域 ==> 包含全部关键字
  • 值域 ==> 依赖于散列表的大小或地址范围
  • 函数特性 ==> 尽量简单，在较短时间内计算出任意一个关键字的散列地址。
• 冲突的思考
  • 理想的散列函数，避免所有冲突。
  • 另一个想法：函数尽可能随机，从而避免冲突或是冲突次数最小化。
• 相关定义
• 散列表查找性能的衡量：装填因子 α ， 表元素个数n，表长度m
  

常见散列函数

    编程语言实现的Hash是很复杂的，这里只是选一些典型的 hash构造方法。

直接定址法

根据关键字的某个线性函数值。

%20%3D%20a%20*%20key%20%2B%20b%0A#card=math&code=H%28key%29%20%3D%20a%20%2A%20key%20%2B%20b%0A)

除留余数法

定义

散列表长度为 m，取一个最接近且不大于 m 的质数 p，利用如下公式求散列地址。

%20%3D%20key%20%5Cmod%20p%0A#card=math&code=H%28key%29%20%3D%20key%20%5Cmod%20p%0A)

• 除留余数法，关键在于选择质数 p，使得key值经过该函数，等概率应色号到散列空间。

示例

表长为 20， 关键字63被散列到的地址

h(63) = 63 % 19 = 6

数字分析法

定义

关键字是一个r进制的数，r个数码在各个位置上出现的频率不一定相同（某些位数分布均匀，某些位分布不均匀），将分布均匀的值用作散列地址。

示例

手机号序列。

明显结尾的数码是比较均匀杂乱的，可以作为散列地址。

平方取中法

定义

取关键字平方值中间的几位作为散列地址。

示例

1234 = 15 227 56 ==> 227 作为散列地址

2345 = 54 990 25 ==> 990 作为散列地址

折叠法

定义

关键字分为数位相同的几部分（最后一部分可能短一些），取几个部分折叠求和，作为散列地址。

示例

关键字 123 456 789 0，散列表长为3位， 可将关键字分为4组，每组三位。

h(key) = 123 + 456 + 789 + 0 = 1368

取三位 368 即位散列值。

乘法散列法

定义

%20%3D%20%5Clfloor%20m%20%20(key%20%20A%20%5Cmod%201)%20%5Crfloor%0A#card=math&code=H%28key%29%20%3D%20%5Clfloor%20m%20%2A%20%28key%20%2A%20A%20%5Cmod%201%29%20%5Crfloor%0A)

① 关键字 key 乘上常数A(0 < A < 1)，并提取k * A的小数部分；

② m乘上这个值，再向下取整。

分析

• 对m的选择不是特别关键，一般取m为 2，2的整数次幂。
• Knuth[211]认为
  A = ( - 1) / 2 = 0.618 033 988 7…是个理想值。
• 举例：当m = 2 = 32, A = ( - 1) / 2时，以下关键字序列对应hash值，没有冲突，分散均匀。 | key | 26 | 36 | 41 | 38 | 44 | 15 | 68 | 12 | 6 | 51 | 25 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | Hash | 2 | 7 | 10 | 15 | 6 | 8 | 0 | 13 | 22 | 16 | 14 |

全域散列法

定义

从一组精心设计的散列函数中，随机选择一个散列函数，使得hash值独立于要存储的关键字。

冲突问题解决办法

链接法

散列到同一个槽中的元素，放到槽指向的一个链表中。

示例

关键字序列为 {26, 36, 41, 38, 44, 15, 68, 12, 6, 51, 25}

用链接法解决冲突，装载因子 α = 0.75，散列函数

%20%3D%20key%20%5Cmod%20p%0A#card=math&code=H%28key%29%20%3D%20key%20%5Cmod%20p%0A)

• 构造出散列函数
  α = 记录数n / 表长m = 11 / m = 0.75 ==> m = 15
  m为不大于表长的最大质数，所以m = 13。
  散列函数为 H(key) = key mod 13

• 散列情况 | addr | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | key | p0 | ^ | p1 | p4 | ^ | p5 | p6 | ^ | ^ | ^ | p10 | ^ | p12 | | | 26 | | 41 | 68 | | 44 | 6 | | | | 36 | | 38 | | | ^ | | 15 | ^ | | ^ | ^ | | | | ^ | | 12 | | | | | ^ | | | | | | | | | | 51 | | | | | | | | | | | | | | | 25 | | | | | | | | | | | | | | | ^ |

  • key这一行引出链接法指向链表的指针。
  • ^ 代表空指针
• 分别计算出等概率情况下，成功 / 失败 的平均查找长度（失败情况，只将与关键字比较次数计算在内即可）
  • 平均查找长度（成功）
    • = (1 7 + 2 2 + 3 1 + 4 1) / 11 = 18 / 11
  • 平均查找长度（失败）
    • = (1 + 2 + 1 + 1 + 1 + 1 + 4 ) / 13 = 11 / 13

开放定址法

将冲突的hash值作为自变量，通过冲突解决函数得到一个新的hash地址。主要方法如下：

1. 线性探测

• 冲突发生，顺序查找hash表的下一个单元（到达表尾时，继续从表头开始找）

示例

• 元素列表：{9, 10, 11, 19, 27}
• 散列函数： H(key) = key mod 8

• 散列情况 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | key | | 9 | 10 | 11 | 19 | 27 | | | |

• 劣势分析

  • 造成大量元素在散列地址附近聚集（总是访问下一个单元）
  • 降低查找效率
    • 元素 19 需计算 2 次( 3 —> 4)
    • 元素 27 需计算 3 次( 3 —> 4 —> 5)

2. 平方探测法

• 冲突的地址为d，则新的地址从 d + , d - , d + , d - …中查找。找到非空的即作为新地址。

示例

• 元素列表：{9, 10, 11, 19, 27}
• 散列函数： H(key) = key mod 8

• 散列情况 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | key | | 9 | 10 | 11 | 19 | | | 27 | |

• 优劣分析

  • 优点：避免堆积
  • 缺点：不能探测所有单元，至少探测一半。

3. 再散列法（双散列法）

• 两个散列函数，第一个发生计算散列值，第二个在冲突时候计算其增量。

示例

• 元素列表：{9, 10, 11, 19}
• 散列函数：
  • H(key) = key mod 8
  • 增量：H2(key) = key mod 2

• 散列情况 | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | key | | 9 | 10 | 11 | 19 | | | | |

  • 当计算元素 19 的散列值时候
    H(19) = 19 mod 8 = 3 发生冲突，
    增量 H2(19) = 19 mod 2 = 1，所以散列值应该是 3 + 1 = 4；

4. 伪随机序列法

增量为伪随机序列。