Redis遇到Hash冲突怎么办？

Redis遇到Hash冲突怎么办？

引用

CSDN

1.

https://blog.csdn.net/u012702547/article/details/143067861

本文将探讨Redis中Hash冲突的处理机制。首先介绍Hash冲突的基本概念和常见解决方案，然后详细说明Redis如何通过链地址法和渐进式rehash来保持高性能。

一 什么是 Hash 冲突

Hash冲突，也称为Hash碰撞，是指不同的关键字通过Hash函数计算得到了相同的Hash地址。Hash冲突在Hash表中是不可避免的，因为Hash表的地址空间有限，而可能的关键字数量是无限的。

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

1. 链地址法（Chaining）：这是最常用的方法之一，每个Hash表的桶（bucket）都维护一个链表，所有散列到同一个位置的元素都存储在这个链表中。当发生冲突时，新元素被添加到该链表的末尾。这种方法的优点是操作简单，插入、查找和删除的时间复杂度为O(1)，但当链表长度较长时，查找效率会降低，并且需要额外的内存空间来存储链表结构。

2. 开放寻址法（Open Addressing）：这种方法也称为闭散列，当发生Hash冲突时，会顺序地查找下一个可用的数组位置，直到找到一个空闲位置为止。开放寻址法有几种变体，包括线性探测、二次探测和伪随机探测。线性探测法是最简单的形式，它按顺序检查下一个空闲位置。二次探测法在发生冲突时，在表的左右进行跳跃式探测。伪随机探测法则使用伪随机数序列来确定下一个探查位置。

3. 再Hash法（Rehashing）：这种方法同时构造多个不同的Hash函数，当发生冲突时，使用第二个Hash函数计算地址，直到找到一个不发生冲突的位置。这种方法不易产生聚集，但增加了计算时间。

4. 建立公共溢出区：将Hash表分为基本表和溢出表，将发生冲突的元素都存放在溢出表中。这种方法可以减少冲突，但需要额外的存储空间。

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

• Python采用开放寻址。字典dict使用伪随机数进行探测。
• Java采用链式地址。自JDK1.8以来，当HashMap内数组长度达到64且链表长度达到8时，链表会转换为红黑树以提升查找性能。
• Go采用链式地址。Go规定每个桶最多存储8个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能。

熟悉这些解决方案很重要，因为Redis中的解决方案无外乎就是这四种方案中的某几种。

二 Redis 中的 Hash

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

1. 压缩列表（ziplist）：当Hash表中的元素数量较少，并且每个元素的值都小于特定阈值（例如，值的长度小于64字节）时，Redis会使用压缩列表来存储Hash表。压缩列表是一种内存高效的数据结构，它将所有的元素存储在一块连续的内存空间中，这样可以减少内存碎片和内存分配次数。但是，当元素数量增加或者单个元素的大小超过阈值时，压缩列表的性能会下降，因为它需要频繁地进行内存重新分配和数据复制。

2. Hash表（hash table）：当Hash表中的元素数量较多，或者元素的大小超过压缩列表的阈值时，Redis会使用一个普通的Hash表来存储数据。这个Hash表由数组和链表组成，每个数组的索引位置上可以存储多个元素，这些元素通过链表连接起来。当Hash表中的元素数量增加到一定程度时，Redis会进行rehash操作，即创建一个新的更大的Hash表，并将旧表中的所有元素重新映射到新表中。

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

从上面的介绍中可以看到，Redis在处理Hash冲突的时候，用到了两种不同的方案：

• 链地址法
• rehash

三 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冲突时能够有效地平衡性能和复杂度，确保在各种使用场景下都能提供高效的数据存储和检索服务。