带你一文搞懂Hash算法解决冲突的四种方法

桃扇骨 2023-03-03 13:29 1阅读 0赞

**Hash算法解决冲突的方法一般有以下几种常用的解决方法**  
**1， 开放定址法：**

> 所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 公式为：fi(key)  
> = (f(key)+di) MOD m (di=1,2,3,……,m-1)
> 
> ※  
> 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者  
> 碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表  
> 中无待查的关键字，即查找失败。
> 
> 比如说，我们的关键字集合为\{12,67,56,16,25,37,22,29,15,47,48,34\},表长为12。  
> 我们用散列函数f(key) = key mod l2 当计算前S个数\{12,67,56,16,25\}时，都是没有冲突的散列地址，直接存入：

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

> 计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。 于是我们应用上面的公式f(37) = (f(37)+1)  
> mod 12 = 2。于是将37存入下标为2的位置：

![在这里插入图片描述][20200731170940618.png]  
**2， 再哈希法：**

> 再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数  
> 计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

**3， 链地址法：**

> 链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向  
> 链表连接起来，如：  
> 键值对k2, v2与键值对k1, v1通过计算后的索引值都为2，这时及产生冲突，但是可以通道next指针将k2, k1所在的节点连接起来，这样就解决了哈希的冲突问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70 1]  
**4， 建立公共溢出区：**

> 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70]: /images/20230208/60c647197e544c8d8440b5a3d76b187f.png
[20200731170940618.png]: /images/20230208/41e00f2c3159443b800f941c6ec6b637.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70 1]: /images/20230208/44e9e9e0ea8e4139b1491c10f90886bb.png