Hash冲突解决详细方法 原创

在哈希表存储中，当不同关键字通过哈希函数计算得到相同存储地址时，就会发生哈希冲突。《软件设计师教程（第五版）》中介绍了四种常用的冲突解决方法，以下是详细整理。

一、开放地址法（闭散列法）

开放地址法是在哈希表的线性存储空间内，当发生冲突时，通过特定的探测规则寻找下一个空闲位置存储数据。核心公式为：hash′(key)=(hash(key)+dᵢ)%m，其中hash(key)是原哈希函数，dᵢ是增量序列，m是哈希表长度。根据增量序列的不同，分为以下四种类型：

1. 线性探测法

原理：增量序列dᵢ=1,2,...,m-1，即冲突发生后，依次探测下一个相邻地址。

示例：已知关键字组(14,36,42,38,40,15)，哈希表长m=15，哈希函数hash(key)=key%13。

• hash(14)=14%13=1（地址1空闲，存入14）

• hash(40)=40%13=1（地址1冲突，探测d₁=1：(1+1)%15=2，地址2空闲，存入40）

• hash(15)=15%13=2（地址2冲突，探测d₁=1：(2+1)%15=3，地址3存入42仍冲突，继续d₂=2：(2+2)%15=4，地址4空闲，存入15）

特点：实现简单，但易产生“堆积现象”（非同义词争夺同一地址），降低查找效率。

2. 二次探测法

原理：增量序列dᵢ=±1²,±2²,...,±k²（k≤m/2），通过平方数调整探测地址，减少堆积。

示例：关键字25，哈希函数hash(key)=key%13=12（地址12冲突）。

• d₁=1²：(12+1)%15=13（冲突）

• d₂=-1²：(12-1)%15=11（空闲，存入25）

特点：堆积现象较线性探测弱，但当哈希表接近满时，可能无法找到空闲地址。

3. 随机探测法

原理：增量序列dᵢ为随机数，需保证探测序列能覆盖哈希表所有地址。

特点：避免系统性堆积，但随机数需预先设定，实现稍复杂。

4. 再哈希法（双哈希法）

原理：使用多个哈希函数，当第一个函数冲突时，依次调用后续函数计算地址，直到找到空闲位置。公式为Hᵢ=RHᵢ(key)（i=1,2,...,k）。

示例：第一个哈希函数hash₁(key)=key%13冲突后，调用第二个函数hash₂(key)=key%11计算新地址。

特点：无堆积现象，但增加了哈希函数的计算时间。

二、链地址法（开散列法）

原理：将哈希表每个地址视为一个链表头节点，冲突的关键字按顺序链接到同一链表中。

示例：关键字组(14,40,15,12,51)，哈希函数hash(key)=key%13。

哈希地址	链表结构
1	14 → 40
2	15
12	12 → 51
特点：处理冲突效率高，无堆积现象；哈希表装满时仍可插入，但需额外存储链表指针。

三、建立公共溢出区

原理：将哈希表分为“基本表”和“溢出表”两部分，基本表存储无冲突的关键字，所有冲突的关键字统一存入溢出表。

示例：基本表地址0-12，溢出表独立存储。

基本表（地址）	存储内容	溢出表
1	14	40（与14冲突）、15（与40冲突）
12	38	12（与38冲突）、51（与12冲突）
特点：结构简单，适用于冲突较少的场景；溢出表规模增大时，查找效率会下降。

四、方法对比总结

开放地址法：适用于哈希表装填因子较小（通常≤0.7）的场景，空间利用率高但易堆积。

链地址法：适用于冲突频繁的场景，扩展性好，是实际开发中最常用的方法。

公共溢出区：适用于小规模数据或冲突较少的场景，实现简单但溢出表易成为性能瓶颈。