查找--理解哈希算法并实现哈希表

朱雀 2022-05-29 09:05 254阅读 0赞

[查找--理解哈希算法并实现哈希表][--]

我们喜欢使用数组进行数据的查找，就是因为数组是一种“随机存取”的数据结构，我们根据数组的起始地址和数组元素的下标值就可以直接计算出每一个数组元素的存储位置，所以它的查找时间是O(1)，而与数组的个数无关。

我们在这个思想的基础上，可以联想到，如果有一种数据结构，让我们在进行关键字查找的时候，也可以像数组一样，进行随机存储，使其时间复杂度从O(n)降到O(1)，那就可以大大提高查找的效率。我们的前辈们基于这种想法发明了散列方法，也就是哈希或关键字地址计算方法。

--------------------

## 基本思想 ##

我们试图寻找一种关系，可以根据我们要存储的关键字（key）然后使用这种关系直接计算出它应该存储的位置（p），一旦建立起这种关系，那么我们在之后一旦需要查找此关键字的话，只需计算此对应关系所产生的值就可以直接得到关键字所在的地址，那么查找的时间复杂度也就降到了O(1)，我们将刚才所说的转换为一种数学关系：

> p（位置）= H（key）

其中H就是对应关系，我们称之为哈希函数，p被成为散列地址。因此，哈希算法的核心就是找到哈希函数（H），通过这个函数来组织存储并进行查找。

--------------------

## Hash函数的构造方法 ##

我们先来看一个问题：   
假如我们现在有一些单词（关键字）：and，cell，do，flag … … 等等，如果我们的哈希函数取值为关键字的第一个字母在字母表中的字典顺序，那么关键字会依次分布在散列地址中。然而当我们还使用这套规则进行and，ant，apple，cell，do … …等等字母的存储，那么就会产生“地址冲突”的问题，因为前三个单词在字母表中的顺序是一样的。

由于Hash函数是一个压缩映像，因此在实际应用中，很少存在不产生冲突的hash函数，因此，如何构造恰当的Hash函数，使得节点“均匀分布”，尽量少的产生冲突就是我们必须要解决的问题之一了。

hash函数的构造原则为简单和均匀：

>  *  hash函数本身运算简单，便于计算；
>  *  hash函数值必须在散列地址范围内，且分布均匀，地址冲突尽可能少。

有几种常用的hash函数的构造方法：

#### 1.除留余数法 ####

该方法是最为简单常用的一种方法，假设表长为m（散列地址的长度），p为小于等于表长m的最大素数，则hash函数为H（key）= key % p。H就是在散列地址中位置。

p的取值应该是一个质因子，这样才能减少“地址冲突”的可能性。

--------------------

#### 2.数字分析法 ####

假设关键字集合中的每个关键字都是由s位数字组成（k1, k2, … , kn），如果可以预先估计出全体关键字的每一位上各种数字出现的频度时，分析关键字集中的全体，并从中提取出分布均匀的若干位或它们的组合作为hash地址。

例如：   
H（49646542）= 465， H（49673242）= 732 … …

经过分析，各个关键字中第4~6位中的取值比较均匀，则hash函数为H（key）= d4d5d6。

--------------------

#### 3.平方取中法 ####

由于整数相除的运行速度通常比相乘要慢，所以我们需要有意识的避免使用除余法可以提高散列算法的运行时间。平方取中法：首先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为hash函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，因此由此产生的散列地址较为均匀。

--------------------

#### 4.分段叠加法 ####

有时关键字所含的位数很多，采用平方取中法计算太复杂，则可将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分进行叠加，叠加和（舍去进位）作为散列地址。

具体的叠加方式有移位叠加和折叠叠加。

--------------------

#### 5.基数转换法 ####

首先将关键字看做是另一种进制的数，然后在转换成原来进制的数，再选择其中几位作为散列地址。

例如：   
把十进制（362081）看做13进制的数，最后结果再转换为十进制（1289744），假设散列长度是10000，则可取低四位9744作为散列地址。

--------------------

一般来说我们还是应该根据实际情况采用恰当的哈希算法，并测试它的性能，一般考虑下列因素：

>  *  计算hash函数所需的时间；
>  *  关键字的长度；
>  *  散列表的大小；
>  *  关键字分布的情况；
>  *  记录查找的频率。

--------------------

## 处理冲突的方法 ##

在上面我们说过，实际情况中我们是不可能不产生地址冲突的，所以，一旦我们有地址冲突，我们应该怎么办？我们自然而然的想到，那就为产生冲突的地址寻找下一个散列地址。

--------------------

### 开放定址（再散列）法 ###

基本思想：   
当关键字key的初始散列地址h0=H（key）出现冲突时，以h0为基础查找下一个地址h1，如果h1仍然冲突，再以h0为基础，产生另一个散列地址h2… … 直到找出一个不冲突的地址hi，将相应元素存入其中，这种方法有一个通用的再散列函数形式：

> hi=（（H（key）+ di）% m

其中h0=H（key），m为表长，di为增量序列。增量序列的取值方式不同，对应不同的再散列方式：

#### 1.线性探测再散列 ####

> di = c × i

最简单的情况：c = 1

特点：冲突放生时，顺序查看表中下一个单元，直到找到一个空单元或查遍全表。值得注意的是：由于使用的是%（取余）运算符，所以它和循环队列有点相似，表尾的后边是表头，表头的前边是表尾。

--------------------

#### 2.二次探测再散列 ####

> di = 1^2，-1^2，2^2，-2^2, … … ，k^2，-k^2 （k<=(m/2)）

特点：冲突发生时分别在表的右，左进行跳跃式探测，较为灵活，不易产生聚集，缺点是不能探查到整个散列地址空间。

--------------------

#### 3.随机探测再散列 ####

> di = 伪随机数

特点：建立一个随机数发生器，并给定一个随机数作为起始点。

--------------------

### 链地址法 ###

基本思想：

把所有具有地址冲突的关键字链在同一个单链表中。   
若哈希表的长度是m，则可以将哈希表定义为一个有m个头指针组成的指针数组。散列地址为i的记录，均插到以指针数组第i个单元为头指针的单链表中。

--------------------

## 性能指标 ##

衡量查找效率的主要性能指标就是平均查找长度（ASL）。

> ASL（succ）=（比较次数之和）/（关键字个数）

比较次数代表的是关键字放入散列地址中为避免地址冲突需要跟当前散列地址中是否已经有值而进行判断的次数。

ASL越小，性能越好。

--------------------

## 哈希表 ##

有了前面的基础，我们来试着自己构建一个哈希表，并实现哈希表的插入，查找和删除。

--------------------

### 哈希表的创建 ###

1.首先将表中各节点的关键字置空；   
2.使用插入算法将给定的关键字序列一次插入哈希表中。

--------------------

### 哈希表的插入 ###

1.通过查找算法找到待插记录在表中的位置；   
2.若在表中找到待插记录，则不必插入；若没有找到，查找算法给出一个单元空闲的散列地址，并插入到该地址单元中。

--------------------

### 哈希表的查找 ###

1.根据待查找记录的关键字和建表时的哈希函数计算散列地址；   
2.若该地址单元为空，则查找失败；若不为空，则将该单元中的关键字与待查记录的关键字进行比较：   
　　如果相等，则查找成功；   
　　如果不等，则按建表时设定的处理冲突的方法找下一个地址。   
3.重复上述步骤2，直至某个单元为空，则查找失败或者与待查记录的关键字进行比较，相等则查找成功。

--------------------

### 哈希表的删除 ###

基于开放地址法的哈希表不能实现真正的删除，只能给被删除节点设置删除标志，以免在删除后找不到比它晚插入的节点且发生过冲突的节点，也就是说，如果执行真正的删除操作，会中断查找路径，如果必须对哈希表做真正的删除操作，最好采用链地址法处理冲突的哈希表。

--------------------

## 哈希表的装填因子 ##

> α = 哈希表中已存入的元素个数 / 哈希表的长度

α越小，冲突的可能性就越小，但空间利用率就越低；   
α越大，冲突的可能性就越大，但空间利用率就越高。

--------------------

## 哈希表的存储效率为何一般只有50% ##

根据上面的装填因子我们可以得知，α越大，产生冲突的的几率也就越大，查找的次数就会变多，然后我们可以看一下查找的时间复杂度计算公式：

> 1/( 1 - n/m )

n/m就是上面所说的装填因子，我们可以发现，当装填因子大于1/2的时候，查找的时间复杂度就会大于二，所以我们一般会说哈希表的存储效率只有50%。