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

发表于 分类于 阅读次数： Disqus： 本文字数： 3.7k 阅读时长 ≈ 3 分钟

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

  • 更新

    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 个.
    • st1.png

  • 优化解

    • 虽然上面的方法可以得到 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$
      • $c_1 c_2$是为正的辅助常数.其取值和 HtSize 密切相关.
    • $c_1 c_2 HtSize$ 取值
      • 要尽量保证两点
        • 取值可以使得探查轨迹遍充满整个散列空间.
        • 第 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)$ 必须与 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..很多了…
相关文章