哈希冲突（Hash Collision），也称为哈希碰撞，是指两个或多个不同的输入数据（键）经过哈希函数计算后，得到了相同的哈希值，从而被映射到哈希表（或散列表）的同一个存储位置上。
简单来说，就是不同的“钥匙”（键）打开了同一把“锁”（哈希地址）。
为什么会产生哈希冲突？
哈希冲突是不可避免的，主要原因如下：
- 输入空间无限，输出空间有限：哈希函数的输入（即可能的键）可以是无限多的（例如，任意长度的字符串、数字），而哈希表的大小是固定的，其地址空间是有限的。根据鸽巢原理（Pigeonhole Principle），当把无限多的“鸽子”放进有限的“鸽巢”里时，至少有一个“巢”里会有多于一只“鸽子”，即必然会发生冲突。
- 哈希函数的压缩性：哈希函数的本质是将一个大范围的数据压缩到一个小范围的索引。这种压缩过程本身就可能导致不同的输入被压缩到同一个输出。
- 哈希函数设计或数据分布：如果哈希函数设计得不够好（例如，不够均匀、随机），或者输入数据的分布本身就有规律（例如，大量键的尾数相同），也可能增加冲突发生的概率。
举个例子
假设我们有一个简单的哈希函数：hash(key) = key % 10，并且哈希表的大小为10。
- 当
key = 5时，hash(5) = 5 % 10 = 5，数据存放在索引5的位置。 - 当
key = 15时，hash(15) = 15 % 10 = 5，它也想存放在索引5的位置。 - 当
key = 25时，hash(25) = 25 % 10 = 5，它同样想存放在索引5的位置。
此时，键 5、15 和 25 虽然不同，但都映射到了索引5，这就发生了哈希冲突。
如何解决哈希冲突？
为了解决冲突，确保所有数据都能被正确存储和查找，主要有以下几种方法：
链地址法 (Chaining / Separate Chaining)
- 原理：将哈希表的每个槽位（bucket）都设计成一个链表（或其他数据结构，如红黑树）的头指针。当发生冲突时，新的元素不是替换旧元素，而是以链表节点的形式链接到该槽位已有的元素后面。
- 优点：实现简单，增删改查逻辑清晰，对哈希函数要求相对较低。
- 缺点：当链表过长时，查找效率会下降（接近O(n)）。为了解决这个问题，Java 8 的
HashMap在链表长度超过一定阈值（默认为8）时，会将链表转换为红黑树，将查找时间复杂度优化到O(log n)。 - 应用：Java 的
HashMap、LinkedHashMap、ConcurrentHashMap（在一定条件下）都使用了链地址法。
开放地址法 (Open Addressing)
- 原理：当发生冲突时，不使用额外的链表结构，而是在哈希表内部寻找下一个“空”的槽位来存放发生冲突的元素。查找时，如果目标位置不是要找的元素，也需要沿着相同的探测序列继续查找。
- 常见的探测方法：
- 线性探测 (Linear Probing)：如果
hash(key)位置被占用，则尝试(hash(key) + 1) % table_size，如果还被占用，再尝试+2，依此类推。 - 二次探测 (Quadratic Probing)：探测序列为
hash(key),(hash(key) + 1²) % table_size,(hash(key) + 2²) % table_size, ...，旨在减少“聚集”现象。 - 双重哈希 (Double Hashing)：使用第二个哈希函数
hash2(key)来计算探测步长，序列为hash(key),(hash(key) + hash2(key)) % table_size,(hash(key) + 2*hash2(key)) % table_size, ...，能更均匀地分布元素。
- 线性探测 (Linear Probing)：如果
- 优点：避免了指针的开销，数据存储更紧凑，缓存局部性好。
- 缺点：容易产生“聚集”（Clustering），即连续的被占用槽位，导致查找效率下降。删除操作比较复杂（通常需要标记为“已删除”而非真正删除）。当哈希表快满时，性能急剧下降，需要及时扩容。
再哈希法 (Rehashing)
- 原理：当发生冲突时，使用另一个不同的哈希函数重新计算哈希地址，直到找到一个空的槽位为止。
- 优点：理论上可以减少冲突。
- 缺点：需要设计多个高质量的哈希函数，计算开销可能增大。
建立公共溢出区 (Overflow Area)
- 原理：将哈希表分为基本表和溢出表两部分。凡是发生冲突的元素，都统一放到溢出表中。
- 查找：先在基本表中查找，如果没找到再去溢出表中查找。
- 缺点：查找效率依赖于溢出表的大小和查找方式，实现相对复杂，不常用。
归纳：哈希冲突是哈希表机制中不可避免的现象。链地址法和开放地址法是最主流的两种解决方案。像Java HashMap这样的广泛应用，就采用了链地址法结合红黑树优化的策略来高效地处理哈希冲突。