详解Redis如何处理Hash冲突

2024-09-29 19:24

短信预约 -IT技能 免费直播动态提醒

引言

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

Redis中的哈希表实现

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

哈希表结构

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

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

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

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的哈希表是一个带有头插法的链表。

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

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首先计算键的哈希值，并找到对应的哈希桶。然后在桶内的链表中进行遍历查找，直到找到对应的键或链表结束。

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

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的过程如下：

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

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

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

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