Redis如何处理Hash冲突？

发表于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

你好，我是猿java。

在 Redis 中，哈希表是一种常见的数据结构，通常用于存储对象的属性，对于哈希表，最常遇到的是哈希冲突，那么，当 Redis遇到Hash冲突会如何处理？这篇文章，我们将详细介绍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

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

rehashing过程

rehashing的过程如下：

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

渐进式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

性能分析

Redis的哈希表在负载因子较低时性能优越，但在负载因子较高时，链表的长度会增加，从而导致查找性能下降。为了解决这个问题，Redis通过渐进式rehashing保持哈希表的负载因子在合理范围内。

总结

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

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

学习交流

如果你觉得文章有帮助，请帮忙转发给更多的好友，或关注公众号：猿java，持续输出硬核文章。

drawing