Map是很常用的数据结构, 而哈希表是 HashMap 等集合的底层实现之一，它通过将键的哈希值映射到数组中的位置来存储键值对。哈希冲突 (Hash Collision) 是指在使用哈希函数将数据映射到有限大小的哈希表时，不同的数据项被映射到了同一个哈希表位置上。
一、产生原因
哈希冲突是由于哈希函数的输出空间（即哈希值的可能取值范围）通常小于输入空间（即所有可能的数据项），因此无法保证每个数据项都对应一个唯一的哈希值。具体为：
- 哈希函数的设计
哈希函数的设计可能无法完全保证不同的输入一定产生不同的哈希值。即使是优秀的哈希函数，由于输入数据的多样性和哈希值空间的有限性，也存在发生冲突的可能性。 - 数据分布
当输入数据具有某种特定的分布特征时，更容易导致哈希冲突。例如，大量数据集中在某个特定的取值范围内，经过哈希函数计算后，可能会有更多的机会产生相同的哈希值。
二、哈希冲突的不良后果
- 降低查找效率
当哈希冲突较多时，查找数据需要在冲突的位置进行额外的比较和处理，从而降低查找效率。特别是在使用开放寻址法时，聚集现象可能会导致查找时间呈线性增长。 - 增加存储开销
了解决哈希冲突，可能需要使用额外的存储空间，如链表指针或更多的哈希表空间。这会增加存储开销，尤其是在处理大量数据时。 - 影响数据结构的性能
哈希冲突会影响哈希表等数据结构的性能，使其在存储和查找数据时的效率降低。哈希冲突会影响 Map 的查找、插入和删除操作的性能。如果冲突较少，HashMap 的操作复杂度接近 O(1)。但是如果冲突频繁，特别是当桶中存储的数据结构为链表时，查找操作可能会退化为 O(n)。当链表转换为红黑树后，性能会提升到 O(log n)。在一些对性能要求较高的应用中，哈希冲突可能会成为性能瓶颈。
三、解决哈希冲突
- 链地址法（Separate Chaining）
这是 HashMap 在发生冲突时的主要方法。在这种情况下，冲突的键值对会被存储在同一个桶（bucket）中。每个桶实际上是一个链表或红黑树。当多个键映射到同一个桶时，它们会以链表形式存储。当链表长度超过一定阈值时，链表会被转换成红黑树以提高效率。 - 开放地址法（Open Addressing）
这种方法不在桶中存储链表，而是通过寻找其他空闲的位置来存储冲突的键值对。具体的寻找方式可以是线性探测（Linear Probing）、二次探测（Quadratic Probing）或双重哈希（Double Hashing）等。优点是实现简单，不需要额外的数据结构。缺点是可能会出现聚集现象，降低查找效率。HashMap 默认不使用这种方法。 - 再哈希（Rehashing）
当发生哈希冲突时，使用另一个哈希函数重新计算哈希值，直到找到一个空闲位置。优点是可以减少冲突的发生概率。缺点是需要多个哈希函数，计算成本较高。 - 完美哈希（Perfect Hashing）
对于静态集合，可以构建一种特殊的哈希函数，确保没有哈希冲突。
完美哈希通常是两阶段的过程：第一阶段产生最小的冲突，第二阶段处理这些少量的冲突。
四、如何避免或减少哈希冲突
- 选择合适的哈希函数
理想的哈希函数应当尽量均匀地将键映射到哈希表的不同桶中，减少冲突的可能性。Java中 HashMap 使用 Object 类的 hashCode() 方法来生成哈希值，因此确保自定义对象的 hashCode() 方法设计得当至关重要。 - 使用足够大的初始容量
较大的初始容量可以减少冲突的发生。在初始化 HashMap 时，可以根据预计存储的键值对数量设置合适的容量和装载因子（load factor）。 - 避免不合适的键对象
使用不当的键（如大量相似字符串）可能导致大量的哈希冲突。选择合理的键值对象，确保它们的哈希值分布足够分散。
