哈希表及哈希冲突解决办法

旧城等待， 2021-12-05 05:15 320阅读 0赞

# 哈希表及哈希冲突解决办法 #

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

## 目录 ##

1.  什么是哈希表？
2.  哈希表的数据结构
3.  哈希冲突
4.  哈希冲突解决办法

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

### 1. 什么是哈希表？ ###

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

当使用哈希表hashtable(key，value) 进行查询的时候，就是使用哈希函数将关键码key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

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

### 2. 哈希表的数据结构 ###

数组的特点是：寻址容易，插入和删除困难；  
而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

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

### 3. 哈希冲突 ###

1.  哈希冲突：即不同key值产生相同的地址，即发生了哈希冲突。一般来说，哈希冲突是无法避免的，所以就有了解决方案。

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

### 4. 哈希冲突解决办法 ###

#### （一）链地址法 ####

1.  HashMap，HashSet其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来去存取发生哈希冲突的输入域的关键字（也就是被哈希函数映射到同一个位桶上的关键字）。首先来看使用拉链法解决哈希冲突的几个操作：
    
    1.  插入操作：在发生哈希冲突的时候，我们输入域的关键字去映射到位桶（实际上是实现位桶的这个数据结构，链表或者红黑树）中去的时候，我们先检查带插入元素x是否出现在表中，很明显，这个查找所用的次数不会超过装载因子（n/m:n为输入域的关键字个数，m为位桶的数目），它是个常数，所以插入操作的最坏时间复杂度为O(1)的。
    2.  查询操作：和插入操作一样，在发生哈希冲突的时候，我们去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是O(1)的
    3.  删除操作：如果在拉链法中我们想要使用链表这种数据结构来实现位桶，在删除一个元素x的时候，需要更改x的前驱元素的next指针的属性，把x从链表中删除。这个操作的时间复杂度也是O(1)的。

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

1.  与开放定址法相比，拉链法有如下几个优点：  
    ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
    
    ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
    
    ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
    
    ④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
2.  拉链法的缺点
    
    指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
    
    使用例子：HashMap

#### （二）开发地址法 ####

开发地址法的做法是，当冲突发生时，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。按照探测序列的方法，一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。

这里为了更好的展示三种方法的效果，我们用以一个模为8的哈希表为例，采用除留余数法，往表中插入三个关键字分别为26，35，36的记录，分别除8取模后，在表中的位置如下：  
![在这里插入图片描述][20190717214556360.png]  
这个时候插入42，那么正常应该在地址为2的位置里，但因为关键字26已经占据了位置，所以就需要解决这个地址冲突的情况，接下来就介绍三种探测方法的原理，并展示效果图。

1） 线性探查法：

fi=(f(key)+i) ％ m ，0 ≤ i ≤ m-1

探查时从地址 d 开始，首先探查 T\[d\]，然后依次探查 T\[d+1\]，…，直到 T\[m-1\]，此后又循环到 T\[0\]，T\[1\]，…，直到探查到有空余的地址或者到 T\[d-1\]为止。

插入42时，探查到地址2的位置已经被占据，接着下一个地址3，地址4，直到空位置的地址5，所以42应放入地址为5的位置。  
![在这里插入图片描述][2019071721462623.png]

缺点：需要不断处理冲突，无论是存入还是査找效率都会大大降低。

2） 二次探查法

fi=(f(key)+di) ％ m，0 ≤ i ≤ m-1

探查时从地址 d 开始，首先探查 T\[d\]，然后依次探查 T\[d+di\]，di 为增量序列1^2 ， -1^2， 2^2， -2^2，……， q^2， -q^2 且q≤1/2 (m-1) ,直到探查到 有空余地址或者到 T\[d-1\]为止。

缺点：无法探查到整个散列空间。

所以插入42时，探查到地址2被占据，就会探查T\[2+1^2\]也就是地址3的位置，被占据后接着探查到地址7，然后插入。**(文章说是地址7位置上，但是照上面运算我觉得是T(2±1=1))，是1位置上添加。**  
![在这里插入图片描述][20190717214850158.png]

3） 伪随机探测  
di=伪随机数序列；具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），生成一个位随机序列，并给定一个随机数做起点，每次去加上这个伪随机数++就可以了。

#### （三）再散列法 ####

fi=(f(key)+i\*g(key)) % m (i=1，2，……，m-1)

其中，f(key) 和 g(key) 是两个不同的哈希函数，m为哈希表的长度

步骤：

1.  双哈希函数探测法，先用第一个函数 f(key) 对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数 g(key) 确定移动的步长因子，最后通过步长因子序列由探测函数寻找空的哈希地址。
2.  比如，f(key)=a 时产生地址冲突，就计算g(key)=b，则探测的地址序列为 f1=(a+b) mod m，f2=(a+2b) mod m，……，fm-1=(a+(m-1)b) % m，假设 b 为 3，那么关键字42应放在 “5” 的位置。

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

> 文章内容引用博客：  
> 数据结构：哈希表以及哈希冲突的解决方案： [https://blog.csdn.net/yeyazhishang/article/details/82533211][https_blog.csdn.net_yeyazhishang_article_details_82533211]  
> 解决hash冲突的三种方法：[https://www.cnblogs.com/kaleidoscope/p/9588151.html][https_www.cnblogs.com_kaleidoscope_p_9588151.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211205/05267ba2b40a4a1ab4545420ec01e024.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211205/8620254abeb04d0ebd6c24ba2b60c16e.png
[20190717214556360.png]: /images/20211205/b2cad9b1c56e4153a645158be435c795.png
[2019071721462623.png]: /images/20211205/1c87d58d2d724beba2552181440dea5e.png
[20190717214850158.png]: /images/20211205/a29d0780be654336ba839995b6e6b36b.png
[https_blog.csdn.net_yeyazhishang_article_details_82533211]: https://blog.csdn.net/yeyazhishang/article/details/82533211
[https_www.cnblogs.com_kaleidoscope_p_9588151.html]: https://www.cnblogs.com/kaleidoscope/p/9588151.html