[数据结构与算法]Hash Table

Abstract：

在前面的学习过程中，我们的数据结构普遍采用的都是遍历的方式进行值查找，并且我们基于这种思想学习了一系列优秀的算法。现在，我们不妨换一种思路：我们而可不可以直接利用已知的索引，通过映射的方式在O(1)时间内直接获取我们想要的值呢？就像你可以直接通过身份证号，获取你的一些基本信息一样。下面，我们来介绍一种新的数据结构：Hash Table

正文：

下面我们可以给出Hash Table的简单概述：

对于所有数据，我们均采取键值对的形式进行值获取，并且不同于往常的二叉树结构，我们二叉树的值获取是利用键在二叉树中进行遍历比较获取目标数据，其本质仍然是以迭代的方式进行值获取。而我们的Hash Table，是将明文的一部分通过Hash算法获取索引值，然后给每个索引值标识唯一的存储地址，进而在存储地址中存储数据：

在这里，我们会产生疑问：这个Hash函数到底是什么？

这里的Hash可以描述为一种映射规则。比如，我们给出上图中Hash的一个法则：取明文数据最后两位正整数作为数据存储的索引：

也即是：

给出明文：202001180057，我们可以利用Hash函数，直接得到一块数组索引57，进而即可获取array[57]中的数据。

我们利用这个机制：

我们为每一个明文数据，都分配唯一的地址，通过Hash函数，都可以在O(1)时间内确定该明文所对应的地址。在这里，我们将上图中的明文数据可以称为关键码Key。图中数组的每一个存储单元称之为桶，桶中的数据称之为词条。一个个桶组成的数组（上图中为数组）我们称之为Hash Table。

建议：我们知道，通过Hash(Key)，我们可以获得hash的一个秩，也即是一个数组的下标。数组是用来存储数据的，我们将数组设计为结构体类型，其中一个成员用以存放对应Hash(Key)，另一个成员可以设计为一个结构体指针用以指向各种数据类型数据：

设计思想：

Hash Table的缺陷：

1. Hash Table桶单元个数过多，空间被浪费

hash表的这种思想即为空间换时间。不妨假设一下：如果我们hash(Key)得到的结果为正整数202001180057，那么我们必然要有一个索引202001180057与之对应，也必然存在arr[202001180057]，也即是数组arr的元素个数不低于202001180058个。如此巨大的空间开销是不可取的。我们再从另一个角度看：通常一个散列表的利用率并不是100%，就基于上方hash的法则，甚至可能利用率极低。假如我们的hash法则得到的结果只存在于202001180000~202001160099之间，我们开辟了如此多的空间，2k亿个空间却只使用了100个，这使得内存被大大地浪费！

2. Hash Table桶单元个数过少，Hash函数结果重复率高

例如我们有一个数据组（Key）：{100，201，302，403，504，605}

Hash函数为Hash(Key) = key % 5

数据组前5个数据的存储：

当我们存储第六个数据的时候，由于arr[0]已经被100指向，所以605的存储必然失败，这种情况我们称之为散列冲突。究其原因即是我们的hash函数的结果集重复率过高。

Hash函数设计：

我们通过上面可以感受到，Hash Table的检索效率是最高的，仅需O(1)，而其存在的问题又不可避免：内存浪费、重复率过高。所有的关键点实际上都集中于Hash函数。当然，我们想要的是内存浪费低且重复率低的Hash函数。下面，我们先来介绍几种常见的Hash函数：

金科玉律：随机性越强、规律性越弱的的散列函数越好

• 除余法

基本思想：将散列表的长度M作为素数，进而将关键码Key % M取余数。余数结果对应散列表的秩

• MAD法
• 数字分析法

从关键码Key特定的进制中抽取出特定的若干位，构成一个整型地址，

• 平方取中法

从关键码Key的平方的十进制或二进制展开中取居中的若干位，构成一个整型地址。

• 折叠法

将关键码的十进制、二进制展开分割成等宽的若干端，将每段视为独立的十进制、二进制数，再将其总和作为散列地址

• 位异或法

将关键码的二进制展开分割为若干等长独立的段，然后对这些段之间进行异或进而得到散列地址。当然，为了保证上述函数取值落在合法的散列地址以内，通常还要对异或结果根据散列表长度再来一次取余。

• 伪随机数法

将Hash函数直接用一个随机数代替：

Hash(Key) % M

冲突及其排解：

实际上，无论设计何种Hash函数，如若考虑其空间问题，必然不可避免Hash结果重复的情况发生。既然这是一种必然事件，下面我们不妨给出一些解决散列冲突的方案：

1、将桶设计为链表结构（独立链法）

既然我们无可避免Hash冲突，那么我们不妨对于重复的元素，将其组织为一个链表的结构。也即是：一个桶中可以存放多个Hash结果相同的词条。

2、多槽位法

在这里若桶平均高度较低，不建议我们使用数组的形式去设计桶（多槽位法）：

很显然，由于无法提前预知数组大小，这势必造成空间不必要的浪费，且如果桶平均层数较低，链表索引带来的时间效率的降低可以忽略不记。但如果桶平均层数较高，则应使用多槽位法。

3、公共溢出区法

我们前面的解决方案都是基于个散列表设计的。实际上，我们也可以设置两个（或者多个）散列表：

闭散列策略：

上面介绍的三种处理散列冲突的方案都是通过引入散列表外部的存储单元来进行解决的。尽管就逻辑结构而言，独立链等策略便捷而紧凑，但这绝非上策。比如，因需要引入次级关联结构，实现相关算法的代码自身的复杂程度和出错概率都大大增加。反过来，又因为不能保证物理上的连续性，对于稍大规模的词条集，查找过程中将需要进行更多的IO操作。（如果是多槽位法，势必造成大量空间的浪费）

实际上，若能仅仅依靠基本的散列结构，且就地排解冲突，而不是在引入协助的链表、数组、甚至哈希表反而是更好的选择。

也即是：若新词条与已有词条冲突，则只允许在散列表内部为其寻找一个空桶

等等！！我们前面知道：我们设计的哈希算法是为了给每一个key指定唯一的内存地址，这样就可以在O(1)时间内直接获取对应的数据，但是如果我们这样做，那么这不就意味着每个Key可以存放在任何一个桶中？那我们还如何保证查找的高效率？

在回答上面的疑问之前，我们先了解一些基本概念：

封闭定址：对于任一key，Hash(Key)只能有唯一的地址与之对应。

开散列：若Hash(Key)存在重复，则可以借助散列表外部的存储空间进行冲突排解。

开放定址：对于任一Key，Hash Table中的任一桶地址都有可能与之对应。

闭散列：若Hash(Key)存在重复，则不允许借助Hash Table外部的存储空间进行冲突排解，而是在内部进行冲突排解。

开放定址策略的冲突排解方法：

• 线性排解法

插入：

在进行值插入的时候，若对应的Hash(Key)已经存在，则我们去相邻的下一个索引位置寻找，如此反复直到遇到空桶：

为了保证查找能称为一个循环，我们应该对Hash(Key)+1再进行一次取模操作：

查找：

执行插入操作逻辑上并无任何难点，问题是我们进行插入操作以后对于具有相同Hash的Key1、Key2，我们怎么知道Key1和Key2哪个是直接Hash(Key)得到的？哪个是进行多次移动操作取得的？

实际上查找操作可以分为一下三种基本情况：

? (1)、在当前桶单元命中目标关键码，则成功返回

? (2)、当前桶单元非空，但其中关键码与目标关键码不相等，则转入下一桶单元继续试探

? (3)、当前桶单元为空，返回查找失败

删除

在学习删除操作之前，我们发现，查找操作的一个判断条件是：若当前桶单元为空，则返回查找失败。问题是：若Hash(Key)位置的Key对应的数据被删除，而与之相同Key的数据由于移动到了其他桶中，那根据第三条（在该位置插入新值之前）我们岂不是无法继续删除后续元素了？

为了解决这个问题，我们引入一种方法：懒惰删除法，所谓懒惰删除法，实际上就是对每一个桶再设一个标志位，用以标志该桶曾存放过数据。进行数据查询的时候，即使桶中为空，但若该标志表示曾经存在过数据，就可以进入下一个桶中继续查询。

• 平方探测法

前面学习的线性排解法逻辑十分简单，且代码实现难度也不大但实际存在一个问题：数据分布较为集中。因为当一个数据的Hash(Key)位置不为空的话，待插入数据会移动到下一个位置插入，当数据量过于庞大的时候，这样极其容易导致数据分布变得集中，进而使得一系列数据操作的时间复杂度上升。为了使数据的分布变得更加分散，我们将原来的移动一步转化为移动2^n步。

散列码转换：

我们前面进行举例说明的时候，对于关键码都是默认采用整数或者长整数。而实际中的关键码通常都是以字符型数据存储的，也就是我们直接通过Hash(Key)可能并不能得到一个规范的正整数以供我们使用。

为了解决这个问题，我们通常采取下面的策略：

即：

1. 利用某一种散列码转换函数HashCode()，将关键码统一转化为整数—该整数称为散列码
2. 利用散列函数Hash()，将散列码转换映射为散列地址（Hash Address）

HashCode()的设计是学东西Hash Table的十分重要的一环，但是其设计也应根据需求去具体设计，下面我们给出HashCode()设计的一些必要条件的说明：

1. 为支持后续尺度不同的散列空间，以及种类各异的散列函数，作为中间桥梁的散列码，取值范围应该覆盖系统所支持的最大整数范围。
2. 各关键码经HashCode()映射后得到的散列码相互之间的冲突应尽可能的少。否则这一阶段出现的冲突，后续的Hash()函数注定无法消除。
3. 被判等器判定为相等的词条，应为两种可能：词条内容一致（散列码必一致）；词条内容不一致（但散列码一致）。

*散列应用：

1、桶排序

若Hash的映射法则与Key本身就有大小对应的关系，则每执行一次插入操作，即附加排序效果

例如，对于关键码集合：{1,2,3,4,5,6}

Hash() = Key % 7

则散列表内容为：

也即是：插入即排序

如果我们出现冲突该如何解决？我们插入即排序基本根据点就是基于关键码到秩的唯一映射，因此桶排序算法要求的Hash Table应该是一种封闭定址开散列表，而其中我们不妨使用独立链法：

上图内容只需经过6次插入，遍历的时候也是O(n)时间。遍历结果：