赞
踩
大家好,我是大明哥,一个专注「死磕 Java」系列创作的硬核程序员。
本文已收录到我的技术网站:https://www.skjava.com。有全网最优质的系列文章、Java 全栈技术文档以及大厂完整面经
在使用 hash 表时, hash 冲突是一个非常常见的问题,该问题出现的主要原因是两个不同的输入值,通过 hash 函数计算得到了相同的 hash 值,尝试存储在 hash 表的同一个位置。解决 hash 冲突主要有如下几种方式:
h1(x)
导致冲突时,系统将尝试第二个 hash 函数 h2(x)
,如果仍然冲突,将继续尝试第三个 hash 函数 h3(x)
,依此类推,直到找到一个空闲槽位为止。链地址法是解决 hash 冲突最经典方法,Java 中的 HashMap 使用的就是它。它是通过将具有相同 hash 值的所有元素存储在同一个索引位置的链表中来解决冲突。这种方法允许多个条目存在于 hash 表的同一个位置,从而避免了冲突直接导致的存储问题。其结构如下:
其工作原理如下:
查询和删除操作和插入步骤一直,先计算 hash 值得到索引位置,然后根据链表来查询或删除。
优缺点
性能优化
开放定址法与链地址法不同,它是在 hash 表的数组本身中找到一个空闲的槽位来存储冲突的元素。它的核心思想是:当发生 hash 冲突时,按照某种探测技术来探测下一个空闲的槽位。其工作原理如下:
开放定址法主要通过以下三种探测技术解决冲突。
一、线性探测
当发生冲突时,顺序探查下一个槽位,直到找到一个空槽位。这种方法简单,但可能导致"聚集"现象,即连续的槽位被占用,从而影响后续插入和查找操作的效率。
比如我们使用大小为 8 的 hash 表,一次添加 5、10、2、4、18,如下:
详细过程如下:
h(5) = 5 % 8 = 5
,位置 5 是空的,所以 5 插入位置 5。h(10) = 10 % 8 = 2
,位置 2 是空的,所以 10 插入位置 2。h(2) = 2 % 8 = 2
,但位置 2 已被 10 占用,因此我们线性探测下一个位置,即位置 3,位置 3 是空的,所以 2 插入位置 3。h(4) = 4 % 8 = 4
,位置 4 是空的,所以 4 插入位置 4。h(18) = 18 % 8 = 2
,位置 2 已被 10 占用,位置 3 被 2 占用,继续线性探测到位置 4,但位置 4 被4 占用,再次线性探测到位置 5,位置 5 已被 5 占用。继续探测到位置 6,位置 6 是空的,所以 18 插入位置 6。二、二次探测
在发生冲突时,不是简单地检查下一个槽位,而是使用二次函数来计算探测的间隔。在二次探测中,如果第一个计算得到的 hash 地址已经被占用,将会尝试一个二次方程式来计算下一个地址,直到找到空位置。
二次探测减少了线性探测的“聚集”现象,但可能仍存在二次聚集问题。
如果我们的 hash 函数是 h(key) = key % table_size
,那么在遇到冲突时,二次探测的探测序列会是这样的:
h(key) + 1^2 % table_size
h(key) + 2^2 % table_size
h(key) + 3^2 % table_size
所以,使用上面的例子,二次探测结果如下:
详细过程如下:
h(5) = 5 % 8 = 5
,位置 5 空,放入 5。h(10) = 10 % 8 = 2
,位置 2 空,放入 10。h(2) = 2 % 8 = 2
,位置 2 已占,进行二次探测:2 + 1^2 = 3
,位置 3 空,放入 2。h(4) = 4 % 8 = 4
,位置 4 空,放入 4。h(18) = 18 % 8 = 2
,位置 2 已占,进行二次探测:2 + 1^2 = 3
,位置 3 已占,2 + 2^2 = 6
,位置 6 空,放入 18。三、双重 hash
使用两个 hash 函数。当第一个 hash 函数导致冲突时,使用第二个 hash 函数计算探测步长。这种方法通常能够更均匀地分布 hash 冲突,减少“聚集”现象,提高 hash 表的整体性能。其原理如下:
双重 hash 使用两个 hash 函数,记为 h1(x)
和 h2(x)
。当在 hash 表中插入一个元素时,首先使用第一个 hash 函数 h1(x)
确定元素的初始位置。如果该位置没有被占用,则直接插入。如果该位置已被占用(发生了冲突),则使用第二个 hash 函数 h2(x)
来计算探测序列的步长,然后按此步长在 hash 表中进行探测,直到找到空槽或目标元素。
具体公式如下:
p i = ( h 1 ( x ) + i ⋅ h 2 ( x ) ) m o d M p_{i}=\left(h_{1}(x)+i \cdot h_{2}(x)\right) \bmod M pi=(h1(x)+i⋅h2(x))modM
M 表示 hash 表的大小,h1(x) 表示第一个 hash 函数,h2(x) 表示第二个 hash 函数,i 表示探测的次数。
我们继续上面的例子:
h1(x) = x % 8
h2(x) = 5 - (x % 5)
:一般第二个 hash 函数最好能确保它产生的步长是非零的,且与表的大小互质(假设表的大小为 8,那么步长应该是与 8 互质的数)。详细过程如下:
h1(5) = 5 % 8 = 5
,位置 5 是空的,所以 5 被直接插入到位置 5。h1(10) = 10 % 8 = 2
,位置 2 是空的,因此 10 被直接插入到位置 2。h1(2) = 2 % 8 = 2
,位置 2 已被 10 占用。h2(2) = 5 - (2 % 5) = 3
,因此新位置计算为 (2 + 1*3) % 8 = 5
,位置 5 已被 5 占用。(2 + 2*3) % 8 = 0
,位置 0 是空的,2 被插入到位置 0。h1(4) = 4 % 8 = 4
,位置 4 是空的,因此 4 被直接插入到位置 4。h1(18) = 18 % 8 = 2
,位置 2 已被 10 占用。h2(18) = 5 - (18 % 5) = 2
,因此新位置计算为 (2 + 1*2) % 8 = 4
,位置 4 已被 4 占用。(2 + 2*2) % 8 = 6
,位置 6 是空的,18 被插入到位置 6。优点
缺点
再哈希法与开放定址法中的双重 hash 差不多。再哈希法依赖多个 hash 函数来寻找空闲槽位,其思想是:当第一个 hash 函数 h1(x)
导致冲突时,系统将尝试第二个 hash 函数 h2(x)
,如果仍然冲突,将继续尝试第三个 hash 函数 h3(x)
,依此类推,直到找到一个空闲槽位为止。
继续上面例子,比如我们有如下三个 hash 函数:
h1(x) = x % 8
h2(x) = 7 - (x % 7)
h3(x) = 5 - (x % 5)
h1(5) = 5 % 8 = 5
,位置 5 空,放入 5。h1(10) = 10 % 8 = 2
,位置 2 空,放入 10。h1(2) = 2 % 8 = 2
,位置 2 已占h2(2) = 7 - (2 % 7) = 5
,位置 5 已占h3(2) = 5 - (2 % 5) = 3
,位置 3 空,放入 2h(4) = 4 % 8 = 4
,位置 4 空,放入 4。h1(18) = 18 % 8 = 2
,位置 2 已占h2(18) = 7 - (18 % 7) = 4
,位置4 已占h3(18) = 5 - (18 % 5) = 2
,位置 2 已占,直接选择其他 hash 算法,比如这里大明哥就直接穷举了,从 hash 表 0 位置开始,位置 0 空,放入 18。优点
缺点
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。