在 Redis 中，哈希冲突（Hash Collision）是指多个不同的键在哈希计算后映射到同一个哈希槽（Hash Slot）或同一个桶（Bucket）。虽然哈希表在大多数情况下都能快速定位键值对，但哈希冲突可能导致性能下降，尤其是在哈希表的负载因子较高时。Redis 通过几种机制来处理哈希冲突，确保性能的稳定性。

Redis 哈希表的结构

• Redis 内部使用哈希表（Hash Table）来存储键值对。
• 哈希表的每个位置称为一个“桶”（Bucket）。
• 通过哈希函数，将键映射到哈希表中的某个桶中。

处理哈希冲突的常见方法

1. 链地址法（Separate Chaining）

链地址法是哈希冲突处理的常见方法之一。在这种方法中，每个哈希表的桶不仅存储一个元素，而是存储一个指向链表的指针。链表中包含了所有哈希到同一个桶中的键值对。

机制:

• 当多个键被哈希到同一个桶中时，这些键值对将被存储在一个链表中。
• 插入时，新元素将插入到链表中。
• 查找时，需要遍历链表中的所有节点，查找目标键。

优点:

• 链表可以动态增长，因此哈希表在负载因子较高时也能继续工作。
• 解决了冲突问题，避免了哈希表的扩展频繁触发。

缺点:

• 在链表较长时，查找、插入和删除操作的性能会下降（时间复杂度为 O(n)）。
• 链表需要额外的内存来存储指针。

2. 开放地址法（Open Addressing）

在开放地址法中，所有的元素都存储在哈希表本身，而不是外部的链表中。当发生哈希冲突时，算法会探测其他位置，直到找到一个空位置为止。

常见的探测策略:

• 线性探测（Linear Probing）: 当冲突发生时，向后一个位置依次探测，直到找到空闲的桶。
• 二次探测（Quadratic Probing）: 采用二次函数的形式探测下一位置，避免“堆积”现象。
• 双重哈希（Double Hashing）: 使用第二个哈希函数来计算探测的步长，进一步减少冲突。

优点:

• 所有元素都存储在哈希表中，节省了指针的内存开销。
• 在负载因子较低时，查找效率较高。

缺点:

• 当负载因子较高时，探测链会变长，导致查找性能下降。
• 需要处理删除操作时的特殊情况（如伪删除标记）。

3. Redis 的渐进式 rehash

Redis 使用链地址法来处理哈希冲突，同时为了避免哈希表过度增长带来的性能问题，Redis 采用了渐进式 rehash（rehashing）机制。

机制:

• Redis 在需要扩展或收缩哈希表时，不会一次性进行 rehash 操作，而是将 rehash 操作分布到多个请求中渐进完成。
• 在渐进式 rehash 过程中，Redis 会同时维护两个哈希表：旧表和新表。每次处理一个操作时，会将一部分键值对从旧表迁移到新表中。
• 这种渐进式的处理方式，避免了因 rehash 带来的集中性能损耗，保证了 Redis 在高并发环境中的性能稳定性。

优点:

• 渐进式 rehash 使得 Redis 的响应时间稳定，不会因为表的扩展或收缩而造成性能突降。
• 保证了 Redis 在高并发访问场景下的稳定性和高性能。

总结

Redis 主要通过链地址法和渐进式 rehash 机制来处理哈希冲突。链地址法在处理冲突时，通过将多个键值对存储在同一个链表中，保证了哈希表的稳定性。而渐进式 rehash 则通过分阶段地扩展或收缩哈希表，避免了性能的剧烈波动。这两种机制结合，使得 Redis 在处理哈希冲突时既能保持高效，也能在负载变化时提供稳定的性能。