哈希冲突（Hash Collision）是指不同的键（key）通过哈希函数计算后得到相同的哈希值（即相同的存储位置）。解决哈希冲突的方法主要有以下几种，每种方法各有优缺点，适用于不同场景：

1. 开放寻址法（Open Addressing）

核心思想：如果目标位置已被占用，就按照某种规则（探测序列）寻找下一个空闲位置。
常见探测方式：

线性探测（Linear Probing）
冲突时，顺序检查下一个位置（如 h(key)+1, h(key)+2, ...）。
缺点：容易导致“聚集”（Clustering），即连续占用位置，降低查找效率。
平方探测（Quadratic Probing）
冲突时，按平方步长探测（如 h(key)+1², h(key)+2², ...）。
减少聚集问题，但可能无法遍历所有位置（需保证表大小为质数）。
双重哈希（Double Hashing）
使用第二个哈希函数计算步长（如 h1(key) + i*h2(key)）。
探测序列更分散，冲突概率低，但计算成本略高。

优点：无需额外存储空间（如链表），适合数据量小、装载因子（load factor）低的场景。
缺点：删除操作需特殊标记（如“墓碑”标记），否则会中断探测序列。

2. 链地址法（Separate Chaining）

核心思想：每个哈希桶（bucket）维护一个链表（或其他数据结构），所有冲突的键值对存储在同一个桶的链表中。
优化变种：

链表 → 红黑树（如Java 8的HashMap）
当链表长度超过阈值时，转为红黑树，将查找时间从O(n)降至O(log n)。
动态可扩展链表：根据负载情况调整链表结构。

优点：实现简单，删除操作方便，适合高冲突场景。
缺点：需要额外指针空间，缓存不友好（链表节点非连续存储）。

其它概念

1. 装载因子（Load Factor）

定义：
装载因子是哈希表中已存储的键值对数量与哈希桶总数的比值，即：
$\text{Load Factor} = \frac{\text{已存储的元素数量}}{\text{哈希桶的数量}}$

作用：

衡量哈希表的空间利用率：装载因子越高，哈希表越拥挤，冲突概率越大。
触发扩容的阈值：当装载因子超过预设值（如Java HashMap默认为0.75），哈希表会触发扩容（resize），以减少冲突。

示例：

哈希表有10个桶（bucket），已存储7个元素，则装载因子为 ( \frac{7}{10} = 0.7 )。
若装载因子阈值设为0.75，插入第8个元素时会触发扩容（桶数量可能翻倍为20）。

影响：

高装载因子（接近1.0）：冲突频繁，查询/插入效率下降（接近O(n)）。
低装载因子（接近0）：空间浪费，但冲突少（接近O(1)）。

2. 哈希桶（Bucket）

定义：
哈希桶是哈希表中存储元素的基本单元，每个桶对应一个哈希值（或哈希值的子集）。

在开放寻址法中，每个桶直接存储一个键值对（或为空）。
在链地址法中，每个桶是一个链表（或树结构），存储所有哈希到该位置的键值对。

示例：

哈希函数 ( h(key) = key % 10 ) 将键映射到10个桶（编号0~9）：
键 23 → 桶 3（因为 ( 23 % 10 = 3 )）。
键 15 → 桶 5。
若 23 和 33 都映射到桶 3，则发生冲突，需通过冲突解决方法处理。

哈希桶的实现方式：

冲突解决方法	哈希桶的物理结构
开放寻址法	数组（每个位置是一个桶）
链地址法	数组 + 链表/树（每个桶是链表头）

3. 装载因子与哈希桶的关系

扩容机制：

当装载因子超过阈值，哈希表会增加桶的数量（如翻倍），并重新哈希所有元素到新桶中，以降低冲突概率。
例如：Java HashMap默认扩容后桶数量变为原来的2倍。

性能权衡：

桶数量多（装载因子低）：冲突少，但内存占用高。
桶数量少（装载因子高）：内存省，但冲突多。

动态调整：

现代哈希表（如Python dict、Java HashMap）会根据装载因子动态平衡时间与空间效率。

红黑树

[[红黑树：自平衡的二叉搜索树]]

其它哈希冲突解决方法：

3. 再哈希（Rehashing）

核心思想：当冲突发生时，使用另一个哈希函数重新计算位置（如 h2(key)）。

通常需要设计一组哈希函数，避免二次冲突。
适用于分布式哈希表等场景。

优点：减少聚集问题。
缺点：计算成本高，需精心设计哈希函数组。

4. 公共溢出区（Overflow Area）

核心思想：将冲突的键值对统一存放到一个独立的存储区域（溢出区）。

主表通过指针指向溢出区。
适用于静态哈希表或嵌入式系统。

优点：实现简单，主表结构紧凑。
缺点：溢出区可能成为性能瓶颈。

5. 动态扩容（Resizing）

核心思想：当哈希表装载因子（元素数量/桶数量）超过阈值时，扩容并重新哈希所有元素。

例如，Java HashMap默认装载因子为0.75，超过时容量翻倍。
渐进式扩容：如Redis的渐进式rehash，避免一次性扩容导致的性能抖动。

优点：从根本上减少冲突概率。
缺点：扩容时短暂性能下降。

方法对比

方法	时间复杂度（平均）	空间开销	适用场景
开放寻址法	O(1)	低	装载因子低、内存受限
链地址法	O(1)~O(n)	中	高冲突、频繁删除
再哈希	O(1)	低	需要避免聚集
公共溢出区	O(n)	高	静态数据或嵌入式系统
动态扩容	摊销O(1)	高	数据动态增长

实际应用示例

**Java HashMap**：链地址法 + 红黑树优化 + 动态扩容。
**Python dict**：开放寻址法（伪随机探测） + 动态扩容。
**Redis Hash**：链地址法 + 渐进式rehash。

[^1]: