前言

全篇无代码,讲的都是思路奥awa。


理解哈希表(HashTable)的原理是关键。

首先要明白,我们用哈希表来干什么?

存储并且查找数据。


哈希函数

假设有$n$个数值最大为$k$的数字,$m$次查询是否存在某个数字。

Round 1

先想一想常规操作。当$n,k,m$都比较小的时候我们会怎么实现?

直接开数组存啊!然后查找直接暴力$for$就好了。

Round 2

这时我们把$n$的范围调大一点,让上面的暴力做法只能够$TLE$,该怎么办呢?

我们就开一个$bool$数组判断每个数是否有出现。

Round 3

但是如果数据不多,但是数值很大呢?比如$1≤n,m≤1000,1≤k≤1e12$。

在这样的条件下,我们不能开出这么大的数组,怎么办呢?可以通过一个$map<long long,bool>$来解决。或者通过离散化也可以达到同样的效果。

Round 4

但是,$3$中的映射读取的时间复杂度为$O(logn)$,总时间复杂度达到了$O(mlogn)$,数据更强一点会被卡掉。

此时,就需要引入我们的hash表了。

hash表所需要的,是一个足够使用的哈希函数(散列函数),在关键字($key$)与数值之间建立一个映射(非map),让我们可以进行双向查找。并且这个查找的时间需要尽量的短。

基本思路是:为这$n$个数据开一个$len$大的数组($len≥n$),然后用我们的哈希函数为每个值算出一个下标,并且这个计算过程需要是可逆的。存起来就好了。

哈希函数的实现一般都是通过取模来完成的。比如下面这个例子。

现在有四个数,$13,7,14,11$,假设我们设计的哈希函数为$hash(i)=i%5$。

hash(13)=13%5=3,h[3]=13;
hash(7)=7%5=2,h[2]=7;
hash(14)=14%5=4,h[4]=14;
hash(11)=11%5=1,h[1]=11;

哈希的方便之处,是在查询的时候体现的。这个时候,加入我要查询数字14是否在数组中,不需要循环,只需要算出14对应的关键字为14%5=4,确认h[4]=14,返回即可。查询的理论时间复杂度为$O(1)$。

而这里的模数5,在实际问题中可以替换为适当的值,但一定要是质数


哈希冲突

在具体的例子中,可能会出现哈希冲突。即a[i]!=a[j]但hash(a[i])==hash(b[i])的情况,下面就来讲讲如何解决哈希冲突。

对于上面的例子,很幸运的,没有出现一例哈希冲突。但如果我们再在这个哈希表中加入数字8,经过计算应该把h[3]=8,但是我们发现,这个位置已经被使用了,怎么办?

这个时候我们就需要让这个hash函数不再只会像我一样无脑%%%,需要给它添加上一个尽量避免哈希冲突的功能。

常用的分为两种,分别是链地址法(开链法,拉链法,哈希桶)开放地址法

链地址法

所谓链地址法,就是当发生hash冲突的时候,将冲突的数据作为链表的形式存储。

这样操作虽然让分散的几次哈希冲突影响不那么大,但如果多次冲突都聚集在同一个位置,链表的位置就会过长,浪费时间。

具体实现类比前向星,就不放代码了。


开放地址法

在这种方法中,如果一个位置发生了哈希冲突,那么就另外寻找一个位置放下。寻找的方式常用的分三种:线性探测法二次探测散列法双哈希法


线性探测法

法如其名,这种方法就是开放地址法中的暴力。它的思想是如果当前位置发生了哈希冲突,那就尝试后一个位置,直到成功为止。这样虽然暴力,但是如果有连续的哈希冲突,会在插入和查询上都花费过多的时间来进行循环。

线性探测的查找:先通过键值定位到数组下标位置,然后将这个位置上数据的值和你要查找数据的值对比,如果相等就直接找到了,如果不相等则继续判断下个元素,所有元素遍历完都没找到的话,则不存在。

这种方法不推荐使用,一旦数据刚好在你设定的模数下在相同位置发生大量冲突,直接$T$上天!


二次探测散列法

这个名字看起来很高级,实际上只是对线性探测法进行了一些优化。

线性探测法把每一步的步长$d[i]$都设定为1,而二次探测散列法则是设定$d[]={1^2,-1^2,2^2,-2^2...}$,依次类推。

简单来说,就是以发生冲突的位置为中心点,左右横跳直到找到一个合适的位置。这样的话就避免发生一个区间都被占满的情况发生。但是经过研究,数列长度是质数&&剩余空间>50%的时候,新的项一定能被插入,并且一个位置不会被探测两次,所以双倍空间&&质数长度数列就很有用啦。


双哈希法(再哈希法)

虽然二次探测散列法能够很大程度上避免原始聚集问题,但是又不可避免地产生了新的二次聚集问题。问题发生的原因是,不管是线性探测还是二次探测,对于不同的原始值,产生的步长是一定的。

而双哈希法则不同。第一次哈希和原来没有区别,第二次哈希的模数就需要较小,用来生成对应的步长。设一个比列表长度小的质数为$cons$,则比较好的二次哈希函数形式为:step=cons-(ket%cons)。

需要注意的是,输出一定不能为0并且不与第一次哈希相同。上面的形式完全符合。

双哈希法的核心思想是,第二次哈希生成一个随机的步长。


ov.

最后修改:2020 年 04 月 10 日 05 : 47 PM