Redis遇到Hash冲突怎么办？

这是小伙伴之前遇到的一个面试题，感觉也是一个经典八股，和大伙分享下。

一什么是 Hash 冲突

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

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

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

链地址法（Chaining）：这是最常用的方法之一，每个 Hash 表的桶（bucket）都维护一个链表，所有散列到同一个位置的元素都存储在这个链表中。当发生冲突时，新元素被添加到该链表的末尾。这种方法的优点是操作简单，插入、查找和删除的时间复杂度为 O(1)，但当链表长度较长时，查找效率会降低，并且需要额外的内存空间来存储链表结构。
开放寻址法（Open Addressing）：这种方法也称为闭散列，当发生 Hash 冲突时，会顺序地查找下一个可用的数组位置，直到找到一个空闲位置为止。开放寻址法有几种变体，包括线性探测、二次探测和伪随机探测。线性探测法是最简单的形式，它按顺序检查下一个空闲位置。二次探测法在发生冲突时，在表的左右进行跳跃式探测。伪随机探测法则使用伪随机数序列来确定下一个探查位置。
再 Hash 法（Rehashing）：这种方法同时构造多个不同的 Hash 函数，当发生冲突时，使用第二个 Hash 函数计算地址，直到找到一个不发生冲突的位置。这种方法不易产生聚集，但增加了计算时间。
建立公共溢出区：将 Hash 表分为基本表和溢出表，将发生冲突的元素都存放在溢出表中。这种方法可以减少冲突，但需要额外的存储空间。

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

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

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

压缩列表（ziplist）：当 Hash 表中的元素数量较少，并且每个元素的值都小于特定阈值（例如，值的长度小于 64 字节）时，Redis 会使用压缩列表来存储 Hash 表。压缩列表是一种内存高效的数据结构，它将所有的元素存储在一块连续的内存空间中，这样可以减少内存碎片和内存分配次数。但是，当元素数量增加或者单个元素的大小超过阈值时，压缩列表的性能会下降，因为它需要频繁地进行内存重新分配和数据复制。
Hash 表（hash table）：当 Hash 表中的元素数量较多，或者元素的大小超过压缩列表的阈值时，Redis 会使用一个普通的 Hash 表来存储数据。这个 Hash 表由数组和链表组成，每个数组的索引位置上可以存储多个元素，这些元素通过链表连接起来。当 Hash 表中的元素数量增加到一定程度时，Redis 会进行 rehash 操作，即创建一个新的更大的 Hash 表，并将旧表中的所有元素重新映射到新表中。

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

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