散列表

约定不等于承诺〃 2023-01-01 02:49 136阅读 0赞

### 文章目录 ###

*   *  前言
     *  摘要
     *  思路介绍
     *  散列函数
     *   *  除法散列法
         *  乘法散列法
         *  全域散列法
     *  冲突解决
     *   *  链表法
         *  开放寻址法
     *  完全散列
     *  代码

## 前言 ##

[农夫山泉][Link 1]：我们不生产水，我们是大自然的搬运工。

大草如是说：我不生成知识点，我是书本的板运工。详细内容见《算法导论》第11章。

当年上《数据结构》的时候，由于课时原因，老师快速带过了9.3节哈希表的相关内容。后来，我偷闲看了[小甲鱼–数据结构–散列表][Link 2]的相关视频。从数据结构的角度来说，哈希表并没有什么难度。无非是，通过映射的方式来实现增删查的字典操作。但是从算法的角度，当看过[麻省理工学院公开课–算法导论–哈希表][Link 3]的相关视频，对于哈希表我一脸懵逼。由于算法课程原因，我翻看了《算法导论》第十一章散列表的相关内容。**下面将会抛开数学证明**，简单的整理下哈希表的相关内容，详细内容见书上。

这里不会介绍，为什么需要哈希表，哪些地方会用到哈希表，使用的时候需要如何设计等。因为，我也不知道这些^\_\_^ 。这里仅考虑哈希表是个什么啥。

## 摘要 ##

介绍了三种散列函数，用以完成映射：除法散列法、乘法散列法、全域散列法。

介绍了两种冲突解决办法：链表法、开放寻址法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center]

## 思路介绍 ##

我们可以把一组信息作为一个元素来存储。比如某个同学，他可能有学号，姓名，班级等信息。在设计数据结构的时候，我们可以将该同学的一组信息放在一个元素内。这个元素有个关键字，只有该元素拥有，而别的元素没有相同的内容，比如学号。

通过元素关键字，我们可以找到该元素的其他相关信息。那我们如何在设计的数据结构中快速得找到关键字呢？（目前，我们暂时仅考虑查找，不考虑增加和删除）

脱去元素信息和元素信息对应的数据结构，把问题抽出来，‘如何快速找到关键字？’。

顺便说下，计算机中的任何内容都是0和1组成。所以我们有理由相信，**可以将关键字转换成数字**。数字相对于其他字符，易于计算处理。后文，我们统一认为关键字是数字类型。这里留下了一个问题，有哪些转化方式，这些转换方式的适用场景与优缺点。

此时，我们拥有了一堆乱糟糟的关键字，我们如何快速定位我们需要的关键字呢？第一种方法是[排序][Link 4]。我们可以在有序的关键字集合中快速找到我们需要的内容。但是，排序是有代价的，不考虑线性时间排序，好的排序时间复杂度大约是`nlog(n)`。除了排序有没有什么好的办法呢？

有的。借鉴下[桶排序][Link 5]的思想，我们可以将关键字与下标建立起一对一的映射关系。（可以是一对多的关系，后面通过链表的方式解决冲突便是一对多关系）将关键字作为关键字数组存储位置下表的方式，是一对一映射关系的一种，可以在`O(1)`时间内找到关键字在数组中的位置。我们称这种方式为**直接寻址法**。

但是，直接寻址法，有很大的弊端。当关键字的全域比较大的时候，由于一对一关系，需要很大的存储空间。但是实际关键字的个数可能远远小于关键字的全域，导致大量的空间被浪费。

既然有一对一有许多空间被浪费，我们何不一对多呢？这里有两个问题：如何一对多？其造成冲突如何解决？

首先考虑第一个问题，一对多必然会有冲突，如何设计一对多以减少冲突。这里引入一个概念[哈希函数][Link 6]。通过哈希函数，将关键字的全域U映射到散列表的槽位上。好的哈希函数应(近似地)满足简单均匀散列假设：每个关键字都等可能的散列到m个槽位中的任何一个，与其他关键字已散列到那个位置无关。我们设计的哈希函数应当趋向于这个目标。

接着，考虑第二个问题，一对多必然会有冲突，如何解决冲突。借鉴下，通排序的思想，我们可以将在同一个槽位上冲突的关键字串联起来。或者，我们可以再次计算，将关键字放在表中的另一个位置。

此时，顺其自然产生了第三个问题：一对多设计的不同哈希函数之间的对比；冲突解决策略的对比；在特定场景，两着的使用等

本文，复制书上的知识点，顺道借着这些问题思路看书上的点。

也可以阅读[这篇文章][Link 7]。

## 散列函数 ##

本节将讨论一些关于如何设计好的散列函数的问题,并**介绍三种具体方法**。其中的两种方法(用除法进行散列和用乘法进行散列)本质上属于启发式方法,而第三种方法(全域散列)则利用了随机技术来提供可证明的良好性能。

**一个好的散列函数应(近似地)满足简单均匀散列假设**:每个关键字都被等可能地散列到m个槽位中的任何一个,并与其他关键字已散列到哪个槽位无关。遗憾的是,一般无法检査这一条件是否成立,因为很少能知道关键字散列所满足的概率分布,而且各关键字可能并不是完全独立的。

有时,我们知道关键字的概率分布。例如,如果各关键字都是随机的实数k,它们独立均匀地分布于`0≤k<1`范围中,那么散列函数`h(k)=km`就能满足简单均匀散列的假设条件。

在实际应用中,常常可以运用启发式方法来构造性能好的散列函数。设计过程中,可以利用关键字分布的有用信息。例如,在一个编译器的符号表中,关键字都是字符串,表示程序中的标识符。一些很相近的符号经常会出现在同一个程序中,如pt和pts。好的散列函数应能将这些相近符号散列到相同槽中的可能性最小化

一种好的方法导出的散列值,在某种程度上应独立于数据可能存在的任何模式。例如,“除法散列”(113.1节中要介绍)用一个特定的素数来除所给的关键字,所得的余数即为该关键字的散列值。假定所选择的素数与关键字分布中的任何模式都是无关的,这种方法常常可以给出好的结果。

最后,注意到散列函数的某些应用可能会要求比简单均匀散列更强的性质。例如,可能希望某些很近似的关键字具有截然不同的散列值(使用11.4节中定义的线性探查技术时,这一性质特别有用)。113.3节中将介绍的全域散列( universal hashing)通常能够提供这些性质。

### 除法散列法 ###

在用来设计散列函数的除法散列法中,通过取k除以m的余数,将关键字k映射到m个槽中的某一个上,即散列函数为:  
 h ( k ) = k   m o d   m h(k)=k\\ mod\\ m h(k)=k mod m  
例如,如果散列表的大小为m=12,所给关键字k=100,则h(k)=4。由于只需做一次除法操作,所以除法散列法是非常快的。

当应用除法散列法时,要避免选择m的某些值。例如,**m不应为2的幂**,因为如果m=2p,则h(k)就是k的p个最低位数字。除非已知各种最低p位的排列形式为等可能的,否则在设计散列函数时,最好考虑关键字的所有位。

**一个不太接近2的整数幂的素数,常常是m的一个较好的选择**。例如,假定我们要分配张散列表并用链接法解决冲突,表中大约要存放n=2000个字符串,其中每个字符有8位。如果我们不介意一次不成功的査找需要平均检查3个元素,这样分配散列表的大小为择701这个数的原因是,它是一个接近2000/3但又不接近2的任何次幂的素数。把每个关键字k视为一个整数,则散列函数如下：h(k)=k mod 701

### 乘法散列法 ###

构造散列函数的乘法散列法包含两个步骤。第一步,用关键字k乘上常数A(0<A<1),并提取kA的小数部分。第二步,用m乘以这个值,再向下取整。总之,散列函数为

⌊ h ( k ) = m ( k A   m o d   1 ) ⌋ \\lfloor h(k)=m(k A\\ mod\\ 1)\\rfloor ⌊h(k)=m(kA mod 1)⌋  
这里 k A m o d 1 kAmod1 kAmod1是取足A的小数部分,即 k A − ⌊ k A ⌋ kA-\\lfloor kA \\rfloor kA−⌊kA⌋ 。

乘法散列法的一个优点是对m的选择不是特别关键，一般选择它为2的某个幂次。[Knuth认为][Knuth] :  A ≈ ( 5 − 1 ) / 2 A\\approx \\left (\\sqrt\{5\} -1 \\right ) / 2 A≈(5−1)/2

大概看起来是，m是槽的个数，m乘上一个\[0,1)的数字。

上课的时候在走绳，我不知道这个公式是如何理解的。但是运行的时候，公式的乘法可以用位移来实现。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 1]

### 全域散列法 ###

如果让某个与你作对的人来选择要散列的关键字，那么他会选择全部散列到同一槽位的n个关键字，使得`平均检索时间`为`O(n)`，任何一个特定的散列函数都无法避免这种最坏情况的发生。唯一有效的改进方法是`随机的选择散列函数`，使之独立于要存储的关键字，这便是全域散列(universal hashing)，无论对手如何选择关键字，平均性态都很好。

我也不明白，可以参考书上，或者[这里][Link 8]

## 冲突解决 ##

因为是是一对多映射，所以必然会产生冲突。本文介绍两种解决冲突的办法：链表法，开放寻址法。

### 链表法 ###

在链表法中，把散列到同一个槽的所有元素都放在一个链表中。

在简单均匀散列的假设下，对于用链表法解决冲突的散列表，一次成功查找所需的平均时间为 Θ ( 1 + α ) \\Theta \\left ( 1+\\alpha \\right ) Θ(1\+α) 。其中， α \\alpha α = 元素个数n / 槽个数m。

关于这个方法的代码实现，见[这里][Link 9]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 2]

> 拉链法的优点:
> 
>  *  拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
>  *  由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
>  *  在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
> 
> 拉链法的缺点：
> 
>  *  指针需要额外的空间

### 开放寻址法 ###

当哈希碰撞发生时，从发生碰撞的那个单元起，按照一定的次序，从哈希表中**寻找**一个空闲的单元，然后把发生冲突的元素存入到该单元。

这个寻找过程有线性探查、二次探查、双重散列。方法有一个通用的再散列函数形式：

**线性探查**。给定一个普通的散列函数h: U→(0,1, …,m-1\},称之为辅助散列函数( auxiliary hash function),性探查( linear probing)方法采用的散列函数为：  
 h ( k , i ) = ( h ′ ( k ) + i )   m o d   m , i = 0 , 1 , ⋯   , m − 1 h(k, i)=\\left(h^\{\\prime\}(k)+i\\right) \\bmod m, \\quad i=0,1, \\cdots, m-1 h(k,i)=(h′(k)\+i)modm,i=0,1,⋯,m−1  
给定一个关键字k,首先探査槽T\[h’(k)\],即由辅助散列函数所给出的槽位。再探査槽T\[h’(k)+1\]，依此类推,直至槽T\[m-1\]。**然后,又绕到槽**T\[0\],T\[1\], …，直到最后探查到槽T\[h’(k)-1\]。在线性探査方法中,初始探査位置决定了整个序列,故只有m种不同的探査序列。

线性探査方法比较容易实现,但它存在着一个问题,称为一次群集( primary clustering)。随着连续被占用的槽不断增加,平均査找时间也随之不断增加。群集现象很容易出现,这是因为当二个空槽前有个满的槽时,该空槽为下一个将被占用的概率是(+1)/m。连续被占用的槽就会变得越来越长,因而平均查找时间也会越来越大。代码实现在[这里][Link 10]

**二次探查**。次探查( quadratic probing)采用如下形式的散列函数：  
 h ( k , i ) = ( h ′ ( k ) + c 1 i + c 2 i 2 )   m o d   m h(k, i)=\\left(h^\{\\prime\}(k)+c\_\{1\} i+c\_\{2\} i^\{2\}\\right) \\bmod m h(k,i)=(h′(k)\+c1i\+c2i2)modm  
其中h‘是一个辅助散列函数,c1和c2为正的辅助常数初始的探查位置为T\[h’(k)\],后续的探査位置要加上一个偏移量,该偏移量以二次的方式依赖于探査序号i。这种探査方法的效果要比线性探査好得多,但是,为了能够充分利用散列表, a1、c2和m的值要受到限制。思考题11-3给出了一种选择这几个参数的方法。此外,如果两个关键字的初始探査位置相同,那么它们的探查序列也是相同的,这是因为h(k1, 0)=(k2, 0)蕴涵着h(k1, i)=h(k2, i)。这一性质可导致一种轻度的群集,称为二次群集( secondary clustering)。像在线性探査中一样初始探查位置决定了整个序列,这样也仅有m个不同的探查序列被用到。

**双重散列**。双重散列( double hashing)是用于开放寻址法的最好方法之一,因为它所产生的排列具有随机选择排列的许多特性。双重散列采用如下形式的散列函数：  
 h ( k , i ) = ( h 1 ( k ) + i h 2 ( k ) )   m o d   m h(k, i)=\\left(h\_\{1\}(k)+i h\_\{2\}(k)\\right) \\bmod m h(k,i)=(h1(k)\+ih2(k))modm  
其中h1和h2均为辅助散列函数。初始探査位置为T\[h1(k)\],后续的探查位置是前一个位置加上偏移量h2(k)模m。因此,不像线性探查或二次探查,这里的探査序列以两种不同方式依赖于关键字k,因为初始探查位置、偏移量或者二者都可能发生变化。

为了能査找整个散列表,值h2(k)必须要与表的大小m互素。有一种简便的方法确保这个条件成立,就是取m为2的幂,并设计一个总产生奇数的h2。另种方法是取m为素数,并设计一个总是返回较m小的正整数的函数h2。

看到这里，我们会好奇，使用开放寻址法的时候，当哈希表的空间不足的时候，该如何处理？

如果我们将原表扩容，m的值变化，会导致无法查询到之前插入的值。

我google下没找见答案，不知道为啥。

## 完全散列 ##

当关键字是静态的时候，通过完全散列能提供出色的最坏情况下，用O(1)次访存完成。

完全散列将关键字通过一级散列函数h1和二级散列函数h2后映射到二级散列中，其中，关键字个数等于槽数(n=m)，二级散列的大小等于映射在同一槽位置关键字个数的平方。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 3]

## 代码 ##

[这里][Link 11]

[Link 1]: http://www.nongfuspring.com/
[Link 2]: https://www.bilibili.com/video/BV1os41117Fs?p=84
[Link 3]: https://www.bilibili.com/video/BV1Ex411T773?p=7
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/12d214f98b1d4e748d0170d65867d257.png
[Link 4]: https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[Link 5]: https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
[Link 6]: https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
[Link 7]: http://www.james-wu-shanghai.com/wordpress/?tag=%E5%BC%80%E6%94%BE%E5%AF%BB%E5%9D%80%E6%B3%95
[Knuth]: https://books.google.com.ph/books?hl=zh-CN&lr=&id=cYULBAAAQBAJ&oi=fnd&pg=PR12&dq=sort+and+searching+Donald+E.+knuth&ots=KLvBIkQt-B&sig=EiVmkFuxHBWhc9zxOUIK8stOfws&redir_esc=y#v=onepage&q=sort%20and%20searching%20Donald%20E.%20knuth&f=false
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b4292060f25947fdb3fa611dc08dc6d7.png
[Link 8]: http://alexyyek.github.io/2014/12/11/hash/#%E5%85%A8%E5%9F%9F%E6%95%A3%E5%88%97
[Link 9]: https://github.com/da1234cao/data_structure/tree/master/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA/%E7%AC%AC%E4%B8%89%E9%83%A8%E5%88%86_%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%AC%AC%E5%8D%81%E4%B8%80%E7%AB%A0_%E6%95%A3%E5%88%97%E8%A1%A8/%E9%93%BE%E8%A1%A8%E6%96%B9%E5%BC%8F%E8%A7%A3%E5%86%B3%E5%86%B2%E7%AA%81
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201230180246267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0,size_16,color_FFFFFF,t_70#pic_center
[Link 10]: https://github.com/da1234cao/data_structure/tree/master/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA/%E7%AC%AC%E4%B8%89%E9%83%A8%E5%88%86_%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%AC%AC%E5%8D%81%E4%B8%80%E7%AB%A0_%E6%95%A3%E5%88%97%E8%A1%A8/%E5%BC%80%E6%94%BE%E5%AF%BB%E5%9D%80%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201230180258155.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzM4ODE2OTI0,size_16,color_FFFFFF,t_70#pic_center
[Link 11]: https://github.com/da1234cao/data_structure/tree/master/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA/%E7%AC%AC%E4%B8%89%E9%83%A8%E5%88%86_%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%AC%AC%E5%8D%81%E4%B8%80%E7%AB%A0_%E6%95%A3%E5%88%97%E8%A1%A8