数据结构-搜索(三) 散列表

发表于 2019-04-08 分类于计算机基础，数据结构阅读次数： Disqus：本文字数： 4.4k 阅读时长 ≈ 4 分钟

数据结构散列表(哈希表)的原理/代码.暂时没有证明(涉及大量随机情况分析,概率,我去补了)
更新
1
19.04.08 初始

参考资料
维基百科
算法第四版,算法导论

导语

散列表的证明部分,暂时忽略,涉及大量概率的内容,必须补上了…
其他内容主要是散列表的原理/代码.主要内容参考了算法导论.
代码开源在 Gitbub
- 拉链法
- 线性探测

散列表

在涉及散列表的概念之前,先总结一下前文.
- 对于我们的符号表(ST),基本操作定义为查找/插入/删除.
- 由数组/链表实现的符号表ST,基本操作时间复杂度为 $O(n)$
- 二叉搜索树/红黑树实现则即使在最坏情况下,基本操作的时间复杂度为 $O(\lg n)$
- 但对于超大型的数据集,还是不够,有没有可以将基本操作的时间复杂度降低为 $O(1)$ 的数据结构呢?
直接寻址表
- 当key可以直接作为索引,且值域不大时,可以直接将key作为索引,存入数组.
- 基本操作查找/插入/删除,直接对节点进行,时间复杂度为 $O(1)$ .
- 但计算机的内存是有限的,不可能直接存入key过大的情况.虽然大部分情况下,key的值域范围很大,但是实际上我们需要处理的键值对的数量有限,我们可以对 key 进行处理后再映射到内存地址.这就是散列表的原理.
散列表又称哈希表,是根据键值(key)直接访问内存的数据结构.而将键值映射为内存地址的函数即为散列函数.存放键值对的表称为散列表(哈希表)
散列函数要保证的是对输入随机均分分布的键值,转换后得到的索引(散列值),也是随机均匀分布.(下文统称映射得到的索引为散列值)
即使散列值是随机均匀分布,但还是有可能存在不同的 key 值,映射得到的散列值相同.这种情况成为碰撞.
处理碰撞
- 拉链法
- 开放寻址,最常用的是线性探测法
我们将键值对的数目 N 和哈希表长度 M 的比值成为装载因子,用字母 $\alpha$ 表示.

散列函数

因键有N多不同的类型,在进行散列值的计算前,需要提前对键值进行处理.
键值处理
- 正整数: 可以直接使用
- 浮点数:
  - 0~1 之间,直接 * HtSize ,得到一个 $[1,M]$ 之间的散列值.
  - 更为通用方式: 使用浮点数的二进制表示.
- 字符串
  - 转换为 UTF-8 对应编码,再处理.
  - 纯 ASCII 字符串,也可以直接当作整数使用.
- 组合键(例如: xx年xx月xx日)
  - 定义一个转换到数值的约束.保证转换后得到的数值也是随机均匀分布
散列函数
- 一致性,相同的键必定产生相同的散列值.
- 高效性,必须方便计算.
- 均匀性,这是保证散列表高效的前提.
糟糕的散列函数,通常是性能的罪魁祸首.

除法散列法

步骤
- 对输入的 k 取 m 的余数.
散列函数
- $h(k) = k \; mod \; m$
特点
- 通常非常方便计算,但散列值的分布非常依赖m的取值.
m取值
- 这里对 m 的取值有额外要求,必须保证将散列值均匀的散布在 $[1,m-1]$ 例如不能是 $2^n$ ,m 通常取值为素数.
- 具体的取值与键值对的数量有关,例如: 键值对数量在100左右,可以选择97,而键值对数量接近 2000,701又是一个选择.

乘法散列法

步骤
- 输入的 k 乘上常数A,取 $kA$ 的小数部分.
- m 乘上小数值,向下取整.
散列函数
- $h(k) = [m(kA \; mod \; 1)]$
特点
- 并不依赖对m的取值,一般将 m = $2^n$ ,对应二进制的表示.
- A的取值有通用方法,但也有优化解.
A 的取值通用方法:
- 计算机的字长为 w 位,而k恰好可以使用w位表示,定义 $A = \frac{s}{2^w} s \in [0,2^w]$ .
- $k*A$ ,可以得到 2w 长度的一个数值 t ,假设我们取 p 位的散列值,就是在 t 的后 w 位,取前 p 个.
优化解
- 虽然上面的方法可以得到 N 多的 A 值,但某些取值效果最好.
- 算法导论上提到Knuth建议 $A \approx \frac{\sqrt5 -1 }{2} = 0.6180039887...$
- 即在 $A = \frac{s}{2^w} s \in [0,2^w]$ 中取最接近 $\frac{\sqrt5 -1 }{2}$ 的数值

全域散列法

步骤
- 对键值处理前,随机选取一个预先载入的散列函数.
- 其他相同.
特点
- 针对某个特定的散列函数,可以精确设计输入的键值,使得哈希表退化到最坏情况(链表).
- 而随机选取散列函数,大大降低了这种攻击成功的可能性.以全域散列建立哈系表,即使相同的键值,两次建表得到的散列值也不一定相同.
- ps: 针对精心构造数据攻击,相同的防御原理的,快速排序的随机化.
详细的证明涉及大量概率,略.(我在补了)

拉链法

拉链法是将散列值相同的元素放在对应位置的链表中.每次在表头插入新元素.且链表为双向链表.
装载因子 $\alpha$ 在拉链法中的意义相当与链表的平均长度.
基本操作
- 查找: 计算散列值,进入对应链表查找
- 插入: 计算散列值,直接在头节点插入.
- 删除: 计算散列值,进入对应链表,找到节点并删除.
基于拉链法的时间复杂度
- 插入 $O(1)$ ,因为在链表头插入,计算哈希值和插入的消耗时间都是 $O(1)$ .
- 查找 $O(1+ \alpha)$ (假设散列值).
- 删除这里有一些变动.
  - 算法导论中 API 定义为直接传入了待删除的节点.从双向链表直接删除节点,时间复杂度为 $O(1)$
  - 而在我们的符号表(ST)的定义中,直接传入待删除的键值,所以这里是 $O(1+ \alpha)$ 与查找相同.

开放寻址

拉链法确实简单易用,但并非没有缺点.额外的指针浪费了内存空间.
开放寻址,没有多余的指针和链表,所有元素均存储在散列表中,因此散列表有可能填满,所以使用开放寻址的散列表的装载因子 $\alpha$ 值不能超过 1.
这里要对散列函数有一点变形,已适应对碰撞的处理.
- 散列函数增加一个探查号 $i i \in [0,HtSize-1]$ .初始值为0.
- 插入时,返回的散列值对应位置不为空(碰撞发生),探查号+1,重复计算散列值,直到对应位置不为空,
- 查找时,如果遇到空值,都未找到对应键值节点,认为散列表中不存在对应键值对.
线性探查
- 线性探查,顾名思义,直接将探查号 i + 散列值上.随着 i++的变化,原相同的散列值,轨迹是由原散列值位置开始的一段连续内存空间.
- $h(k,i) = (h'(k)+i) \; mod \; HtSize$
- 由于取模的存在,轨迹可能又重新绕到散列表的开头,直到 $h'(k)$ 前一位停止.
- 线性探测在装载因子较大时,非常容易导致一次集群的出现,即出现连续的内存空间被大块占用,使得查询的平均时间变得越来越长.
- 应对一次集群
  - 控制装载因子在 $[\frac18 , \frac12 ]$
  - 改用其他开放寻址.
二次探查
- 为应对一次集群,二次探查改为如下形式.
- $h(k,i) = (h'(k)+ c_{1}i + c_{2}i^2 ) \; mod \; HtSize$ $h (k, i) = (h^{'} (k) + c_{1} i + c_{2} i^{2}) m o d H t S i z e$
  - $c_1 c_2$ 是为正的辅助常数.其取值和 HtSize 密切相关.
- $c_1 c_2 HtSize$ $c_{1} c_{2} H t S i z e$ 取值
  - 要尽量保证两点
    - 取值可以使得探查轨迹遍充满整个散列空间.
    - 第 i 次和第 j 次查询的偏移量不能相同.
  - 一些建议值
    - 对于 $HtSize = 2^n$ , $c1 = c2 = 1/2$ .
    - 对于 HtSize 为大于2的素数, $c1 = c2 = 1/2, c1 = c2 = 1, c1 = 0, c2 = 1$
- 对 HtSize 限制
  - (具体证明未看懂),留白.参考
双重探查
- 双重探查是开放寻址最好的方法之一,双重探查产生的排列完全随机.
- $h(k,i) = (h_{1}(k)+ ih_{2}(k)) \; mod \; HtSize$
- 初始的探查位置为 $h_{1}(k)$
- 为探查整个散列表, $h_{2}(k)$ $h_{2} (k)$ 必须与 HtSize 互素(互质,最大公约数为1).有两种通用方式:
  - 取 $HtSize = 2^n$ ,而 $h_{2}(k)$ 总是产生奇数.
  - 取 HtSize 为素数,而 $h_{2}(k)$ 总是返回小于 HtSize 的正整数.
开放寻址的基本操作中,查找/插入都是比较好实现的,不佳赘述.麻烦一点的是删除.
删除
- 不能简单的将待删除节点置为空值,直接置空会导致之后的元素无法被探查.有两种方式
  - 线性探测中,我们需要将被删除键的右侧开始的连续内存空间,直到遇到空值为止,内所有节点重新插入.
  - 不将节点置为空值,而是在存储结构中,增加空槽的指示位,删除即将置为空槽,查找时直接跳过,插入时,直接返回该节点位置.
  - 第二种更为常用.
在实现中,算法第四版选择的是线性探查,故这里仅实现了线性探查.

动态调整

如果可以提前预估键值对的数量,并不建议进行动态调整.
拉链法实现的散列表要求装载因子要求在 $[2,8]$ ,即链表的平均长度在 $[2,8]$ 之间.
开放寻址实现的散列表,要求装载因子在 $[\frac18,\frac12]$ 之间.
动态调整步骤…删除原散列表,在将元素插入新调整容量后的散列表.

完全散列

完全散列实际上是两级散列表,对 key 进行两次取散列值.使得即使关键词集合为静态,碰撞几乎不可能发生.最坏情况下也可以在 $O(1)$ 完成操作.
即使第一次散列值碰撞,但精心选择的二次散列函数,使得再次碰撞的几率几乎为0.
初看完全散列的空间复杂度为 $O(n^2)$ ,但精心挑选第一级散列函数可以将总体的存储空间限制在 $O(n)$ …(努力补证明中…)

结语

散列表这一章,第80篇日志,几乎是写的最干巴巴的一章,证明几乎看不懂…接下来要将在计划中加入算法导论的概率部分了.
下一篇可能是搜索部分的总结,或者红黑树,看内容多少了.
本篇的证明一定会补全的…en…flag…很多了…