散列表

作者: 丹丘生___ | 来源:发表于2018-09-02 10:28 被阅读0次

散列表
散列表
散列表
散列表
散列表
散列表
散列表
散列表
散列表
散列表

基本概念(非严谨）

散列表：按照思考事物本质以及理想状态的思路，那么散列表从本质来讲就是一个表，而理想的散列表应该是一个包含关键字的具有固定大小的数组。

散列函数：本质上是一个映射函数，将关键字映射成(0~tableSize-1)这个范围内的某个数。而理想情况下的散列函数，应有这两点特征：

运算简单。
保证任意不同的两个关键字映射到不同的单元中。（让键本身的分布特性不影响它在哈希表中分布的均匀性）

碰撞：当一个记录要被插入到散列表时，却被散列到一个已经被占用的槽，称为发生‘碰撞’(collision).

碰撞处理：解决上述“碰撞”引发的问题，主要有：拉链法和开放寻址法。

散列和散列函数构成了散列的基本想法。

学习一项知识，我们要考虑这项知识的第一原则是什么，而对散列函数而言，它的第一原则是“尽可能的将两个不同关键字映射到不同的单元中”。为了坚守这个原则，面对不同类型的关键字时，就要设计不同的散列函数。而关键字往往可以分为三种类型：正整数、字符串以及浮点数。每种类型的关键字又有多种类型的散列方法。

直接寻址表

学习散列表之前，有必要了解直接寻址表。表本身存储的是<key, value>对，而最直观的直接寻址表就是一个普通的数组，将数组下标作为key,进而获得value。

下图中是一个较为严谨的直接寻址表的图形化描述⁽¹⁾，其中表T[0..m-1]记为直接寻址表，表中的每一个位置称为槽，槽在描述散列表的过程中将经常被使用。
集合U是一些键值的集合，有些键值在T中有元素(内部白色部分)，有些键值没有。

直接寻址表：T中每一个槽内包含指向元素的指针，而某些应用是直接将对象放在槽中

缺点：如果U很大，或者其中有很大的数字，比如 $x = 2^{64}，x\in{U}$ ,那么直接寻址表将大的无法接受，并且有许多空间不能被利用，非常浪费。
因此，我们需要散列函数和散列表。

多种散列方法

1. 除数留余法

将整数散列最常用的方法是除留余数法。先回顾一下求余的数学特性：当K%M = R, 那么R的取值范围为（0~M-1)，正好满足将键值散列到大小为M的数组中的要求。但考虑均匀分布的问题，还需加上一个条件，就是M必须是一个素数。否则，通过特例法演示可知，散列后的值将等于键值的后K位，那么必然分布的很不均匀。
举例: 0110100110是一个二进制数，依次对2ⁿ形式的数取余
0110101110 % 2 = 0000
0110101110 % 4 = 0010
0110101110 % 8 = 0110
0110101110 % 16 = 1110
…
由此可见，某数K % 2ⁿ 相当于取K二进制数的后n位。二进制数是如此，十进制数也是类似的道理。
总结来说，如果想用除留余数法将其散列,那么散列表的大小要慎重选择，比如不应为2ⁿ，最好是一个素数。

2. 乘法散列法

优点：只有乘法操作，而处理器做乘法效率更高。
描述：
$m = 2^r$ , 假设计算机的字长为w-bits,有
$h(k) = (A * K\ mod\ 2^w) rsh\ (w - r),其中A为奇数， 2^{w-1}<= A <= 2^w ， rsh为向右移位之意$
两点：

A的取值不要太接近 $2^{w-1}$ 和 $2^w$
这是一个快速算法，因为与A相乘后再对2^w取余，相比直接做除法，其运算要更快(处理器的特点？）

这一大段，我基本抄的MIT算法导论公开课的板书，看得我是云山雾罩。
拿老师的栗子来看看：
$\begin{array}{r} 1011001\\ 1101011 \\ \hline 10010100110011 \end{array}$
这是A*K的式子，A = 1011001,K = 1101011,相乘结果为：10010100110011
该结果对2^w取余，就相当于保留其最后w位二进制位，然后向右移位w-r，相当于除以2^w-r(r为m的幂数),其结果必然不大于2^r,也就是m的值。因此，该哈希函数最后的结果是一个最大不超过m的数。

假设m=23，字长w是7-bit ，看示意图⁽²⁾：

m = 8时，哈希函数最后结果为：011

把A看作一个数的小数部分，用车轮法考虑那个乘法过程，如图⁽³⁾：

车轮法.png

把A看作一个数的小数部分，假设A的整数部分是T, 那么 $T.A*K\ mod\ 2^w$ 实际上取的是 $T.A*K$ 最后的w位小数部分。
而车轮法的思考过程是：
当K = 1时， $T.A*1\ mod\ 2^w$ 结果就是A,而A rsh (w-r)就相当于绕着最大刻度为r的车轮走了一个A的长度。
当K = 100时，相当于绕轮盘走了100个A的长度
...

碰撞处理方法

拉链法

处理碰撞问题的一个很直接的方法就是，把哈希值相同的的记录放到一个链表中存储。拉链法如下图⁽⁴⁾所示：

拉链法散列表示意图

特点：
如果有N个键，用M条链表保存元素，那么链表长度平均为N/M,哪怕是最坏情况下也满足

最坏情况分析：
最坏情况下，所有元素hash到表中的同一个槽中，那么使用拉链法后形成的哈希表：只有一个槽包含指向一个长长的链表的指针，其他槽都为空。
这种情形下，访问某个元素需要： $\theta(n)$ 的时间复杂度, n为链表长度。

平均情况分析：
前文中说过，链表的平均长度是N/M，查找一个元素可能要遍历整个链表，因此访问一个元素的时间复杂度为： $\theta(1+N/M)$ ，其中‘1’是把键用哈希函数映射到槽所花费的时间，当N/M为一个常数时，即 $N = O(M)$ ，那么访问一个元素的时间复杂度为 $\theta(1)$ ,这要求N和M以同等规模增长，或M的增长率高于N。