共计 7506 个字符，预计需要花费 19 分钟才能阅读完成。
散列（哈希）表总结
之前给大家介绍了 链表 ， 栈和队列 明天咱们来说一种新的数据结构散列（哈希）表，散列是利用十分宽泛的数据结构，在咱们的刷题过程中，散列表的出场率特地高。所以咱们快来一起把散列表的内些事给整明确吧。文章框架如下
脑图
说散列表之前，咱们先构想以下场景。
袁厨穿梭回了现代，凭借从古代学习的做饭手艺，开了一个袁记菜馆，正值停业初期，店里生意非常火爆，然而顾客结账时就犯难了，每当结账的时候，老板娘总是依照菜单一个一个找价格（遍历查找），每次都要找半天，所以结账的中央总是排起长队，顾客们示意用户体验不咋滴。袁厨一想这不是方法啊，让顾客老是等着，太影响客户体验啦。所以袁厨就先把菜单依照首字母排序（二分查找），而后查找的时候依据首字母查找，这样结账的时候就能大大提高检索效率啦！然而呢？工作日顾客不多，老板娘齐全应酬的过去，然而每逢节假日，还是会排起长队。那么有没有什么更好的方法呢？对呀！咱们把所有的价格都背下来不就能够了吗？每个菜的价格咱们都一目了然，结账的时候咱们只需简略相加即可。所以袁厨和老板娘加班加点的进行背诵。下次再结账的时候一说吃了什么菜，咱们立马就晓得价格啦。自此以后收银台再也没有呈现过长队啦，袁记菜馆开着开着一不小心就成了天下第一饭店了。
上面咱们来看一下袁记菜馆老板娘进化史。
image-20201117132633797
下面的前期结账的过程则模仿了咱们的散列表查找，那么在计算机中是如何应用进行查找的呢？
散列表查找步骤
散列表 ——- 最有用的根本数据结构之一。是依据关键码的值儿间接进行拜访的数据结构，散列表的实现经常叫做 散列（hasing）。散列是一种用于以 常数均匀工夫 执行插入、删除和查找的技术，上面咱们来看一下散列过程。
咱们的整个散列过程次要分为两步
（1）通过 散列函数 计算记录的散列地址，并按此 散列地址 存储该记录。就好比麻辣鱼咱们就让它在川菜区，糖醋鱼，咱们就让它在鲁菜区。然而咱们须要留神的是，无论什么记录咱们都须要用 同一个散列函数 计算地址，再存储。
（2)当咱们查找时，咱们通过 同样的散列函数 计算记录的散列地址，按此散列地址拜访该记录。因为咱们存和获得时候用的都是一个散列函数，因而后果必定雷同。
方才咱们在散列过程中提到了散列函数，那么散列函数是什么呢？
咱们假如某个函数为 f，使得
存储地位 = f (关键字)
输出：关键字 输入：存储地位(散列地址)
那样咱们就能通过查找关键字 不须要比拟 就可取得须要的记录的存储地位。这种存储技术被称为散列技术。散列技术是在通过记录的存储地位和它的关键字之间建设一个确定的对应关系 f , 使得每个关键字 key 都对应一个存储地位 f(key)。见下图
这里的 f 就是咱们所说的散列函数（哈希）函数。咱们利用散列技术将记录存储在一块间断的存储空间中，这块间断存储空间就是咱们本文的主人公 ——散列 (哈希) 表
上图为咱们形容了用散列函数将关键字映射到散列表，然而大家有没有思考到这种状况，那就是将关键字映射到同一个槽中的状况，即 f(k4) = f(k3) 时。这种状况咱们将其称之为 抵触 ，k3 和 k4 则被称之为散列函数 f 的 同义词，如果产生这种状况，则会让咱们查找谬误。侥幸的是咱们能找到无效的办法解决抵触。
首先咱们能够对哈希函数下手，咱们能够精心设计哈希函数，让其尽可能少的产生抵触，所以咱们创立哈希函数时应遵循以下规定
（1）必须是统一的 ，假如你输出辣子鸡丁时失去的是 在看 ，那么每次输出辣子鸡丁时，失去的也必须为 在看。如果不是这样，散列表将毫无用处。
（2）计算简略 ，假如咱们设计了一个算法，能够保障所有关键字都不会抵触，然而这个算法计算简单，会消耗很多工夫，这样的话就大大降低了查找效率，反而得失相当。所以咱们 散列函数的计算工夫不应该超过其余查找技术与关键字的比拟工夫，不然的话咱们干嘛不应用其余查找技术呢?
（3）散列地址散布平均 咱们方才说了抵触的带来的问题，所以咱们最好的方法就是让 散列地址尽量均匀分布在存储空间中，这样即保障空间的无效利用，又缩小了解决抵触而耗费的工夫。
当初咱们曾经对散列表，散列函数等常识有所理解啦，那么咱们来看几种罕用的散列函数结构规定。这些办法的共同点为都是将原来的数字按某种法则变成了另一个数字。
散列函数构造方法
间接定址法
如果咱们对盈利为 0 - 9 的菜品设计哈希表，咱们则间接能够依据作为地址，则 f(key) = key;
即上面这种状况。
有没有感觉下面的图很相熟，没错咱们常常用的数组其实就是一张哈希表，关键码就是数组的索引下标，而后咱们通过下标间接拜访数组中的元素。
另外咱们假如每道菜的老本为 50 块，那咱们还能够依据盈利 + 老本来作为地址，那么则 f(key) = key + 50。也就是说咱们能够依据线性函数值作为散列地址。
f(key) = a * key + b a,b 均为常数
长处：简略、平均、无抵触。
利用场景：须要当时晓得关键字的散布状况，适宜查找表较小且间断的状况
数字分析法
该办法也是非常简略的办法，就是剖析咱们的关键字，取其中一段，或对其位移，叠加，用作地址。比方咱们的学号，前 6 位都是一样的，然而前面 3 位都不雷同，咱们则能够用学号作为键，前面的 3 位做为咱们的散列地址。如果咱们这样还是容易产生抵触，则能够对抽取数字再进行解决。咱们的目标只有一个，提供一个散列函数将关键字正当的调配到散列表的各地位。这里咱们提到了一种新的形式，抽取，这也是在散列函数中常常用到的伎俩。
image-20201117161754010
长处：简略、平均、实用于关键字位数较大的状况
利用场景：关键字位数较大，晓得关键字散布状况且关键字的若干位较平均
折叠法
其实这个办法也很简略，也是解决咱们的关键字而后用作咱们的散列地址，次要思路是将关键字从左到右宰割成位数相等的几局部，而后叠加求和，并按散列表表长，取后几位作为散列地址。
比方咱们的关键字是 123456789，则咱们分为三局部 123，456，789 而后将其相加得 1368 而后咱们再取其后三位 368 作为咱们的散列地址。
长处：当时不须要晓得关键字状况
利用场景：适宜关键字位数较多的状况
除法散列法
在用来设计散列函数的除法散列法中，通过取 key 除以 p 的余数，将关键字映射到 p 个槽中的某一个上，对于散列表长度为 m 的散列函数公式为
f(k) = k mod p (p <= m)
例如，如果散列表长度为 12，即 m = 12，咱们的参数 p 也设为 12，那 k = 100 时 f(k) = 100 % 12 = 4
因为只须要做一次除法操作，所以除法散列法是十分快的。
由下面的公式能够看出，该办法的重点在于 p 的取值，如果 p 值选的不好，就可能会容易产生同义词。见上面这种状况。咱们哈希表长度为 6，咱们抉择 6 为 p 值，则有可能产生这种状况，所有关键字都失去了 0 这个地址数。
那咱们在选用除法散列法时选取 p 值时应该遵循怎么的规定呢？
- m 不应为 2 的幂，因为如果 m = 2^p，则 f(k) 就是 k 的 p 个最低位数字。例 12 % 8 = 4，12 的二进制示意位 1100，后三位为 100。
- 若散列表长为 m , 通常 p 为 小于或等于表长（最好靠近 m）的最小质数或不蕴含小于 20 质因子的合数。
合数：合数是指在大于 1 的整数中除了能被 1 和自身整除外，还能被其余数（0 除外）整除的数。
质因子：质因子（或质因数）在数论里是指能整除给定正整数的质数。
这里的 2，3，5 为质因子
还是下面的例子，咱们依据规定抉择 5 为 p 值，咱们再来看。这时咱们发现只有 6 和 36 抵触，相对来说就好了很多。
长处：计算效率高，灵便
利用场景：不晓得关键字散布状况
乘法散列法
结构散列函数的乘法散列法次要蕴含两个步骤
- 用关键字 k 乘上常数 A(0 < A < 1)，并提取 k A 的小数局部
- 用 m 乘以这个值，再向下取整
散列函数为
f (k) = ⌊ m(kA mod 1) ⌋
这里的 kA mod 1 的含意是取 keyA 的小数局部，即 kA – ⌊kA⌋。
长处：对 m 的抉择不是特地要害，个别抉择它为 2 的某个幂次（m = 2 ^ p ,p 为某个整数）
利用场景：不晓得关键字状况
平方取中法
这个办法就比较简单了，假如关键字是 321，那么他的平方就是 103041，再抽取两头的 3 位就是 030 或 304 用作散列地址。再比方关键字是 1234 那么它的平方就是 1522756，抽取两头 3 位就是 227 用作散列地址.
长处：灵便，适用范围宽泛
实用场景：不晓得关键字散布，而位数又不是很大的状况。
随机数法
故名思意，取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key)。这里的 random 是 随机函数。
长处：易实现
实用场景：关键字的长度不等时
下面咱们的例子都是通过数字进行举例，那么如果是字符串可不可以作为键呢？当然也是能够的，各种各样的符号咱们都能够转换成某种数字来看待，比方咱们常常接触的 ASCII 码，所以是同样实用的。
以上就是罕用的散列函数构造方法，其实他们的中心思想是统一的，将关键字通过加工解决之后变成另外一个数字，而这个数字就是咱们的存储地位，是不是有一种特务传递情报的感觉。
一个好的哈希函数能够帮忙咱们尽可能少的产生抵触，然而也不能完全避免产生抵触，那么遇到抵触时应该怎么做呢？上面给大家带来几种罕用的解决散列抵触的办法。
解决散列抵触的办法
咱们在应用 hash 函数之后发现关键字 key1 不等于 key2，然而 f(key1) = f(key2)，即有抵触，那么该怎么办呢？不急咱们缓缓往下看。
凋谢地址法
理解凋谢地址法之前咱们先构想以下场景。
袁记菜馆内，铃铃铃，铃铃铃 电话铃响了
大鹏：老袁，给我订个包间，我明天要去带几个客户去你那谈生意。
袁厨：大鹏啊，你罕用的那个包间被人订走啦。
大鹏：老袁你这不仗义呀，咋没给我留住呀，那你给我找个 空房间 吧。
袁厨：好滴老哥
哦，穿梭回现代就没有电话啦，那看来穿梭的时候得带着几个手机了。
下面的场景其实就是一种解决抵触的办法 —– 凋谢地址法
凋谢地址法 就是一旦发生冲突，就去寻找下一个空的散列地址，只有列表足够大，空的散列地址总能找到，并将记录存入，为了应用凋谢寻址法插入一个元素，须要间断地查看散列表，或称为 探查 ，咱们罕用的有 线性探测，二次探测，随机探测。
线性探测法
上面咱们先来看一下线性探测，公式：
f,(key) = (f(key) + di ) MOD m（di = 1,2,3,4,5,6….m-1）
咱们来看一个例子，咱们的关键字汇合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为 12，咱们再用散列函数 f(key) = key mod 12。
咱们求出每个 key 的 f(key)见下表
咱们查看上表发现，前五位的 f(key) 都不雷同，即没有抵触，能够间接存入，然而到了第六位 f(37) = f(25) = 1, 那咱们就须要利用下面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2，这其实就是咱们的订包间的做法。上面咱们看一下将下面的所有数存入哈希表是什么状况吧。
咱们把这种解决抵触的凋谢地址法称为 线性探测法。上面咱们通过视频来模仿一下线性探测法的存储过程。
另外咱们在解决抵触的时候，会遇到 48 和 37 尽管不是同义词，却抢夺一个地址的状况，咱们称其为 沉积。因为沉积使得咱们须要一直的解决抵触，插入和查找效率都会大大降低。
通过下面的视频咱们应该理解了线性探测的执行过程了，那么咱们考虑一下这种状况，若是咱们的最初一位不为 21，为 34 时会有什么事件产生呢？
此时他第一次会落在下标为 10 的地位，那么如果持续应用线性探测的话，则须要通过一直取余后失去后果，数据量小还好，要是很大的话那也太慢了吧，然而明明他的后面就有一个空房间呀，如果向前挪动只需挪动一次即可。不要焦急，前辈们曾经帮咱们想好了解决办法
二次探测法
其实了解了咱们的上个例子之后，这个一下就能整明确了，基本不用费脑子，这个办法就是更改了一下 di 的取值
线性探测：f,(key) = (f(key) + di ) MOD m（di = 1,2,3,4,5,6….m-1）
二次探测： f,(key) = (f(key) + di ) MOD m（di =1^2 , -1^2 , 2^2 , -2^2 …. q^2, -q^2, q<=m/2）
注：这里的是 -1^2 为负值 而不是（-1)^2
所以对于咱们的 34 来说，当 di = - 1 时，就能够找到空地位了。
二次探测法的目标就是为了不让关键字汇集在某一块区域。另外还有一种乏味的办法，位移量采纳随机函数计算失去，接着往下看吧.
随机探测法
大家看到这是不又有新问题了，方才咱们在散列函数结构规定的第一条中说
（1）必须是统一的 ，假如你输出辣子鸡丁时失去的是 在看 ，那么每次输出辣子鸡丁时，失去的也必须为 在看。如果不是这样，散列表将毫无用处。
咦？怎么又是 在看 哈哈，那么问题来了，咱们应用随机数作为他的偏移量，那么咱们查找的时候岂不是查不到了？因为咱们 di 是随机生成的呀，这里的随机其实是伪随机数，伪随机数含意为，咱们设置 随机种子 雷同，则一直调用随机函数能够生成 不会反复的数列 ，咱们在查找时， 用同样的随机种子 ， 它每次失去的数列是雷同的 ，那么雷同的 di 就能失去 雷同的散列地址。
随机种子（Random Seed）是计算机专业术语，一种以随机数作为对象的以真随机数（种子）为初始条件的随机数。个别计算机的随机数都是伪随机数，以一个真随机数（种子）作为初始条件，而后用肯定的算法不停迭代产生随机数
通过下面的测试是不是一下就秒懂啦，为什么咱们能够应用随机数作为它的偏移量，了解那句，雷同的随机种子，他每次失去的数列是雷同的。
上面咱们再来看一下其余的函数解决散列抵触的办法
再哈希法
这个办法其实也特地简略，利用不同的哈希函数再求得一个哈希地址，直到不呈现抵触为止。
f,(key) = RH,(key) (i = 1,2,3,4…..k)
这里的 RH, 就是不同的散列函数，你能够把咱们之前说过的那些散列函数都用上，每当发生冲突时就换一个散列函数，置信总有一个可能解决抵触的。这种办法能使关键字不产生汇集，然而代价就是减少了计算工夫。是不是很简略啊。
链地址法
上面咱们再构想以下情景。
袁记菜馆内，铃铃铃，铃铃铃电话铃又响了，那个大鹏又来订房间了。
大鹏：老袁啊，我一会去你那吃个饭，还是上回那个包间
袁厨：大鹏你下回能不能早点说啊，又没人订走了，这回是老王订的
大鹏：老王这个老东西啊，反正也是熟人，你再给我整个桌子，我拼在他前面吧
不好意思啊各位同学，信鸽最近太贵了还没来得及买。下面的情景就是模仿咱们的新的解决抵触的办法链地址法。
下面咱们都是遇到抵触之后，就换中央。那么咱们有没有不换中央的方法呢？那就是咱们当初说的链地址法。
还记得咱们说过得同义词吗？就是 key 不同 f(key) 雷同的状况，咱们将这些同义词存储在一个单链表中，这种表叫做同义词子表，散列表中只存储同义词子表的头指针。咱们还是用方才的例子，关键字汇合为 {12，67，56，16，25，37，22，29，15，47，48，21}，表长为 12，咱们再用散列函数 f(key) = key mod 12。 咱们用了链地址法之后就再也不存在抵触了，无论有多少抵触，咱们只需在同义词子表中增加结点即可。上面咱们看下链地址法的存储状况。
链地址法尽管可能不产生抵触，然而也带来了查找时须要遍历单链表的性能耗费，有得必有失嘛。
公共溢出区法
上面咱们再来看一种新的办法，这回大鹏又要来吃饭了。
袁记菜馆内 …..
袁厨：呦，这是什么风把你给刮来了，咋没开你的大奔啊。
大鹏：哎呀妈呀，别那么多废话了，我快饿死了，你快给我找个地位，我要吃点饭。
袁厨：你来的，太不巧了，咱们的店曾经满了，你先去旁边的小屋看会电视，等有空了我再叫你。小屋外面还有几个和你一样来晚的，你们一起看吧。
大鹏：电视？看电视？
下面得情景就是模仿咱们的公共溢出区法，这也是很好了解的，你不是抵触吗？那抵触的各位我先给你安顿个中央呆着，这样你就有中央住了。咱们为所有抵触的关键字建设了一个公共的溢出区来寄存。
那么咱们怎么进行查找呢？咱们首先通过散列函数计算出散列地址后，先于根本表比照，如果不相等再到溢出表去程序查找。这种解决抵触的办法，对于抵触很少的状况性能还是十分高的。
散列表查找算法(线性探测法)
上面咱们来看一下散列表查找算法的实现
首先须要定义散列列表的构造以及一些相干常数，其中 elem 代表散列表数据存储数组，count 代表的是以后插入元素个数，size 代表哈希表容量，NULLKEY 散列表初始值，而后咱们如果查找胜利就返回索引，如果不存在该元素就返回元素不存在。
咱们将哈希表初始化，为数组元素赋初值。
插入操作的具体步骤：
（1）通过哈希函数（除法散列法），将 key 转化为数组下标
（2）如果该下标中没有元素，则插入，否则阐明有抵触，则利用线性探测法解决抵触。具体步骤见正文
查找操作的具体步骤：
（1）通过哈希函数（同插入时一样），将 key 转成数组下标
（2）通过数组下标找到 key 值，如果 key 统一，则查找胜利，否则利用线性探测法持续查找。
上面咱们来看一下残缺代码
散列表性能剖析
如果没有抵触的话，散列查找是咱们查找中效率最高的，工夫复杂度为 O(1), 然而没有抵触的状况是一种现实状况，那么散列查找的均匀查找长度取决于哪些方面呢？
1. 散列函数是否平均
咱们在上文说到，能够通过设计散列函数缩小抵触，然而因为不同的散列函数对一组关键字产生抵触可能性是雷同的，因而咱们能够不思考它对均匀查找长度的影响。
2. 解决抵触的办法
雷同关键字，雷同散列函数，不同解决抵触形式，会使均匀查找长度不同，比方咱们线性探测有时会沉积，则不如二次探测法好，因为链地址法解决抵触时不会产生任何沉积，因此具备最佳的均匀查找性能
3. 散列表的装填因子
原本想在上文中提到装填因子的，然而起初发现即便没有阐明也不影响咱们对哈希表的了解，上面咱们来看一下装填因子的总结
装填因子 α = 填入表中的记录数 / 散列表长度
散列因子则代表着散列表的装满水平，表中记录越多，α 就越大，产生抵触的概率就越大。咱们下面提到的例子中 表的长度为 12，填入记录数为 6，那么此时的 α = 6 / 12 = 0.5 所以说当咱们的 α 比拟大时再填入元素那么产生抵触的可能性就十分大了。所以说散列表的均匀查找长度取决于装填因子，而不是取决于记录数。所以说咱们须要做的就是抉择一个适合的装填因子以便将均匀查找长度限定在一个范畴之内。
各位如果能感觉到这个文章写的很用心的话，能给您带来一丢丢帮忙的话，能麻烦您给这个文章点个赞吗？这样我就巨有能源写下去啦。
另外大家如果须要其余精选算法题的动图解析，大家能够微信关注下【袁厨的算法小屋】，我是袁厨一个热爱做饭所以本人考取了厨师证的菜鸡程序员，会始终用心写下去的，感激反对！
