一、什么是 Hash 冲突

Hash 冲突，也称为 Hash 碰撞，是指不同的关键字通过 Hash 函数计算得到了相同的 Hash 地址。

Hash 冲突在 Hash 表中是不可避免的，因为 Hash 表的地址空间有限，而可能的关键字数量是无限的。

为了解决 Hash 冲突，有几种常见的方法：

不同的编程语言在面临这个问题时也都采取了不同策略，例如：

小伙伴们需要先熟悉这些解决方案，因为 Redis 中的解决方案无外乎就是这四种方案中的某几种。

二、Redis 中的 Hash

Redis 中的 Hash 数据结构在底层使用了两种不同的数据结构来存储键值对：

Redis 会根据 Hash 表的大小和元素的数量自动在这两种数据结构之间进行切换，以保证性能和内存效率。这种动态的数据结构选择机制使得 Redis 的 Hash 数据结构既灵活又高效。

从上面的介绍中小伙伴们其实能看到，Redis 在处理 Hash 冲突的时候，用到了两种不同的方案：

三、Redis 如何解决 Hash 冲突

根据前面的介绍，小伙伴们已经明白了 Redis 在处理 Hash 冲突的时候，用到了两种不同的方案：链地址法和 rehash。

第一种链地址法大家应该是比较熟悉的，我们 Java 里边早期的 HashMap 就是这样的，具体数据结构如下图：

不过链地址法有一个弊端，就是如果出现大量的 key 冲突导致链表过长，此种情况下会导致数据的检索效率变慢，这不符合 Redis 高性能的人设，那怎么办呢？

为了保持高效，Redis 会对 Hash 表做 rehash 操作，也就通过增加 Hash 桶来减少冲突。为了 rehash 更高效，Redis 还默认使用了两个全局 Hash 表，一个用于当前使用，称为主 Hash 表，一个用于扩容，称为备用 Hash 表。

具体来说，在 Hash 表扩容时，Redis 首先会创建一个新的 Hash 表，该 Hash 表的大小是原有 Hash 表的两倍，然后将原有 Hash 表中的键值对逐一迁移到新的 Hash 表中。

在迁移过程中，Redis 会为每个被迁移的键值对计算出其在新 Hash 表中的位置，并将其插入到相应的位置上。在迁移完成后，Redis 会将新 Hash 表作为当前 Hash 表，用于存储新的键值对，同时释放旧 Hash 表的内存。

由于迁移过程是逐步进行的，因此在迁移过程中，既可以对新 Hash 表进行写入操作，也可以对旧 Hash 表进行读取操作，从而保证了 Redis 服务的正常运行。

四、小结

Redis 通过链地址法解决 Hash 冲突，并通过渐进式 rehash 保持 Hash 表的性能。

链地址法实现简单且在负载因子较低时性能较好，但在负载因子较高时性能会下降。渐进式 rehash 通过分批次迁移数据，避免了 rehash 过程中的服务阻塞，从而保持了系统的高性能和高可用性。

通过以上机制，Redis 在处理 Hash 冲突时能够有效地平衡性能和复杂度，确保在各种使用场景下都能提供高效的数据存储和检索服务。