你好，我是猿java。

在 Redis 中，哈希表是一种常见的数据结构，通常用于存储对象的属性，对于哈希表，最常遇到的是哈希冲突，那么，当 Redis遇到Hash冲突会如何处理？这篇文章，我们将详细介绍Redis如何处理哈希冲突，并探讨其性能和实现细节。

Redis中的哈希表实现 {#Redis中的哈希表实现}

在Redis中，哈希表被用于实现多个内部数据结构，包括数据库的键空间（key space）和哈希类型（hash type）。Redis的哈希表实现基于一个称为 dict 的数据结构。dict 结构内部使用了两个哈希表，以支持渐进式rehashing。

哈希表结构 {#哈希表结构}

Redis的哈希表结构定义如下：

|---------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 | typedef struct dictht { dictEntry **table; // 哈希表数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引 unsigned long used; // 已使用的哈希表节点数量 } dictht; |

dictEntry 是哈希表的节点，定义如下：

|------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 | typedef struct dictEntry { void *key; // 键 union { void *val; // 值 uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; // 指向下一个哈希表节点，形成链表 } dictEntry; |

每个哈希表节点包含一个键和值，以及一个指向下一个节点的指针。这个指针用于解决哈希冲突。

哈希冲突解决策略 {#哈希冲突解决策略}

在Redis中，哈希冲突通过链地址法（Chaining）来解决。具体来说，当多个键映射到同一个哈希桶时，这些键会被存储在一个链表中。链地址法的优点是实现简单，且在哈希表负载因子较低时性能较好。

链地址法实现 {#链地址法实现}

当插入一个键值对时，Redis首先计算键的哈希值，并根据哈希值找到对应的哈希桶。如果该桶为空，则直接插入；如果该桶不为空，则在链表的头部插入新节点。因此，Redis的哈希表是一个带有头插法的链表。

以下是插入操作的伪代码：

|-------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 | function dictAdd(dict, key, value): index = hashFunction(key) & dict.sizemask if dict.table[index] == NULL: dict.table[index] = new dictEntry(key, value) else: newEntry = new dictEntry(key, value) newEntry.next = dict.table[index] dict.table[index] = newEntry |

查找操作 {#查找操作}

查找操作时，Redis首先计算键的哈希值，并找到对应的哈希桶。然后在桶内的链表中进行遍历查找，直到找到对应的键或链表结束。

以下是查找操作的伪代码：

|-------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 | function dictFind(dict, key): index = hashFunction(key) & dict.sizemask entry = dict.table[index] while entry != NULL: if entry.key == key: return entry.value entry = entry.next return NULL |

渐进式rehashing {#渐进式rehashing}

为了保持哈希表的性能，Redis需要在哈希表过于拥挤时进行扩容，或在哈希表过于空闲时进行缩容。Redis采用渐进式rehashing策略，以避免在rehash过程中阻塞服务。

rehashing过程 {#rehashing过程}

rehashing的过程如下：

创建一个新的哈希表，大小为当前哈希表的两倍或一半。
将旧哈希表中的数据逐渐迁移到新哈希表中。
迁移完成后，释放旧哈希表的内存。

渐进式rehashing通过分批次将旧哈希表的数据迁移到新哈希表来实现。具体来说，每次增删改查操作都会顺便迁移一定数量的哈希表节点，直到迁移完成。

以下是渐进式rehashing的伪代码：

|------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | function rehashStep(dict): if dict.rehashidx == -1: return for i = 0 to REHASH_BATCH_SIZE: if dict.rehashidx >= dict.size: dict.rehashidx = -1 break while dict.table[dict.rehashidx] == NULL: dict.rehashidx += 1 entry = dict.table[dict.rehashidx] while entry != NULL: nextEntry = entry.next index = hashFunction(entry.key) & dict.new_ht.sizemask entry.next = dict.new_ht.table[index] dict.new_ht.table[index] = entry entry = nextEntry dict.table[dict.rehashidx] = NULL dict.rehashidx += 1 |