6、Redis系统-数据结构-04-Hash

四、哈希表（Hashtable）

哈希表是一种高效的键值对数据结构，通过散列函数将键映射到表中的位置，实现快速的插入、删除和查找操作。Redis 广泛使用哈希表来实现 Hash 对象和数据库的键值存储。以下将从结构设计、哈希冲突与链式哈希、rehash、渐进式哈希和哈希触发条件等角度详细介绍 Redis 中的哈希表。

1. 结构设计

在 Redis 中，哈希表（dict）由两个哈希表数组（dictht）组成，用于实现渐进式 rehash，以应对数据量增大时的性能问题。每个哈希表数组包含一个哈希表节点（dictEntry）的指针数组。哈希表节点用于存储实际的键值对，并通过链地址法处理哈希冲突。

哈希表结构

typedef struct dictht {
    dictEntry **table;    // 哈希表数组
    unsigned long size;   // 哈希表大小
    unsigned long sizemask;  // 哈希表大小掩码，用于计算索引值
    unsigned long used;   // 哈希表中已使用的节点数量
} dictht;
 
typedef struct dict {
    dictType *type;       // 类型特定函数
    void *privdata;       // 私有数据
    dictht ht[2];         // 哈希表，支持渐进式 rehash
    long rehashidx;       // rehash 索引，-1 表示没有进行 rehash
    unsigned long iterators;  // 当前正在运行的安全迭代器数量
} dict;
 
typedef struct dictEntry {
    void *key;            // 键
    union {
        void *val;        // 值
        uint64_t u64;     // 无符号整数值
        int64_t s64;      // 有符号整数值
        double d;         // 双精度浮点值
    } v;
    struct dictEntry *next;  // 指向下一个哈希表节点，解决冲突
} dictEntry;

主要字段介绍

1. table：指向哈希表节点指针数组的指针。
2. size：哈希表的大小，即哈希表数组的长度。
3. sizemask：哈希表大小掩码，用于计算键的索引值。
4. used：哈希表中已使用的节点数量。
5. rehashidx：rehash 的索引，表示当前进行到哪个位置，-1 表示没有进行 rehash。
6. type：指向哈希表类型特定函数的指针，用于实现不同类型的哈希表。
7. privdata：指向私有数据的指针，可以用于存储与哈希表相关的额外信息。

2. 哈希冲突及链式哈希

哈希冲突

哈希冲突是指不同的键通过哈希函数计算得到相同的索引值，从而映射到哈希表数组的同一位置。哈希冲突是哈希表的一种常见问题，需要有效的处理机制来解决。

链式哈希

链式哈希是一种解决哈希冲突的常用方法。它通过链表的形式，将所有哈希值相同的键值对连接在一起。每个哈希表数组的元素（dictEntry）都指向一个链表的头节点，当发生哈希冲突时，新节点被插入到链表的头部。

typedef struct dictEntry {
    void *key;            // 键
    union {
        void *val;        // 值
        uint64_t u64;     // 无符号整数值
        int64_t s64;      // 有符号整数值
        double d;         // 双精度浮点值
    } v;
    struct dictEntry *next;  // 指向下一个哈希表节点，解决冲突
} dictEntry;

插入操作

在哈希表中插入键值对时，Redis 首先计算键的哈希值，并将其映射到哈希表数组中的一个位置。如果该位置已经有其他节点，则通过链地址法将新节点插入到链表的头部。

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

查找操作

在哈希表中查找键对应的值时，Redis 通过计算键的哈希值来确定其在哈希表数组中的位置，然后遍历链表查找对应的键值对。

dictEntry *dictFind(dict *d, const void *key) {
    if (d->ht[0].size == 0) return NULL;
    dictEntry *he = dictFindRaw(d, key);
    if (he == NULL) return NULL;
    return he;
}

删除操作

在哈希表中删除键值对时，Redis 同样通过计算键的哈希值来确定其位置，然后遍历链表找到对应的节点并将其删除。

int dictDelete(dict *d, const void *key) {
    if (dictSize(d) == 0) return DICT_ERR;
    if (dictDeleteRaw(d, key) == DICT_OK) {
        if (d->ht[0].used == 0) _dictReset(&d->ht[0]);
        return DICT_OK;
    }
    return DICT_ERR;
}

3. rehash

rehash 的必要性

随着哈希表中元素数量的增多，哈希表的负载因子（load factor）会不断增大，从而影响性能。为了维持哈希表的性能，Redis 需要进行 rehash 操作，即重新分配哈希表的大小，并将原有的键值对重新分布到新的哈希表中。

rehash 过程

1. 初始化新哈希表：当需要进行 rehash 时，首先为哈希表分配新的哈希表数组，并调整新哈希表的大小。
2. 迁移节点：将旧哈希表的所有节点逐个迁移到新哈希表中。迁移过程中，计算每个节点的新哈希值，并将其插入到新哈希表的对应位置。
3. 完成 rehash：当所有节点都迁移完成后，释放旧哈希表的内存，将新哈希表替换为当前哈希表。

void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d, 1);
}

4. 渐进式 rehash

渐进式 rehash 的基本思想

渐进式 rehash 的基本思想是：将哈希表的扩容操作分摊到多次操作中完成，而不是一次性完成，从而避免一次性 rehash 带来的性能问题。通过渐进式 rehash，Redis 可以在保证高效操作的同时，平滑地完成哈希表的扩容。

渐进式 rehash 的具体实现

1. 分阶段迁移：在每次对哈希表进行增删查改操作时，逐步将旧哈希表的节点迁移到新哈希表中。每次操作迁移一部分节点，直到旧哈希表的所有节点都迁移完成。
2. 维护 rehash 状态：在进行 rehash 过程中，Redis 维护一个 rehash 索引（rehashidx），表示当前迁移到哪个位置。每次操作完成后，rehash 索引会相应更新，直到所有节点迁移完成。
3. 完成 rehash：当所有节点迁移完成后，释放旧哈希表的内存，将新哈希表替换为当前哈希表。

void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d, 1);
}

渐进式 rehash 的优点

1. 平滑过渡：通过逐步迁移节点，避免了一次性 rehash 带来的性能波动。
2. 低延迟：每次操作只迁移一部分节点，保证了每次操作的时间复杂度不会过高，从而降低延迟。

5. 哈希触发条件

哈希表的 rehash 触发条件主要有两个：

1. 负载因子：当哈希表的负载因子超过一定阈值时，触发 rehash 操作。负载因子等于已使用的节点数量除以哈希表的大小。Redis 的默认阈值是 1，当负载因子超过 1 时，会触发 rehash。
2. 内存使用情况：当 Redis 内存使用情况达到

一定水平时，也会触发 rehash 操作，以保证内存的高效使用。

通过这两个条件，Redis 可以在适当的时候进行哈希表的 rehash，从而维持哈希表的性能和内存利用率。

结论

通过上述解析，我们可以更好地理解哈希表的设计思想和实现原理，从而在实际开发中更好地利用哈希表提供的优势。在 Redis 中，哈希表通过高效的键值对存储和渐进式 rehash 机制，实现了高性能和低延迟的操作，适用于多种场景如键值存储、缓存等。了解这些优化策略，可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。