散列

Redis 源码版本：Redis-6.0.9，本篇文章的代码均在 dict.h / dict.c 文件中。

散列类型可以存储一组无需的键值对，他特别适用于存储一个对象数据。

字典

• Redis 通常使用字典结构体存储用户散列数据。
• 字典是 Redis 的重要数据结构。除了散列类型，Redis 数据库也使用了字典结构。
• Redis 使用 Hash 表实现字典结构。分析 Hash 表，我们需要重点关注下面的问题：
  1. 使用什么 Hash 算法。
  2. Hash 冲突如何解决。
  3. Hash 表如何扩容。

定义

字典中键值对的定义如下：

typedef struct dictEntry {
    void *key; // 键
    union
    {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                    // 值
    struct dictEntry *next; // 下一个键值对的指针
} dictEntry;

C 语言 union 关键字用于声明联合体，联合体的所有属性共用同一空间，同一时间只能存储其中一个属性值。也就是说，dictEntry.v 可以存放 val，u64，s64，d 中的一个属性值。使用 sizeof 计算联合体的大小，结果不会小于联合体中的最大成员属性大小。

---

字典中哈希表的定义如下：

typedef struct dictht {
    dictEntry **table;      // 哈希表数组，负责存储哈希表中的数据。table 是一个指针数组，每个元素是一个指向 dictEntry 的指针
    unsigned long size;     // Hash 表数组长度
    unsigned long sizemask; // 哈希表大小的掩码值，通常为 size - 1，用于计算哈希值在哈希表中的索引位置。通过 sizemask 与哈希值进行按位与操作，可以快速计算出索引位置：index = hash & sizemask。这种计算方式比直接取模运算效率更高。
    unsigned long used; // 记录存储键值对的数量，在判断 Hash 表的扩容缩容时有很大作用
} dictht;

dictht 的结构如下图所示：

---

字典的定义如下：

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dict {
    dictType *type; // 指定操作数据的函数指针
    void *privdata; // 用户自定义数据指针。作用：传递给 dictType 中的函数，便于实现定制化操作。通常用于在操作过程中传递额外的上下文信息。
    dictht ht[2]; // 两个 dictht 结构体数组，分别表示哈希表的当前表和临时表。作用：在进行 rehash 操作（哈希表扩展或收缩）时，ht[0] 表示原始表，ht[1] 表示临时表。rehash 完成后，临时表将替代原始表。
    long rehashidx; // rehash 进度索引。作用：如果 rehash 正在进行，该值表示当前正在 rehash 的索引位置。如果值为 -1，则表示没有进行 rehash 操作。
    unsigned long iterators; // 当前正在运行的迭代器数量。作用：记录当前有多少个迭代器正在遍历该哈希表，以确保在 rehash 或修改哈希表时能够安全地处理迭代器。
} dict;

通过 dictType 指定操作数据的函数指针，字典就可以存放不同类型的数据啦。但在一个字典中，键和值之间可以是不同的类型，但键必须类型相同，值也必须类型相同。

Redis 为不同的字典定义了不同的 dictType，如数据库使用的 server.c / dbDictType，散列类型使用的 server.c/setDictType 等。

dictAddRaw

• 函数功能：向哈希表中添加一个 key。也可以在哈希表中查找一个 key。

• 参数：

  • dict *d：哈希表所在的字典。
  • void *key：需要添加的 key。
  • dictEntry **existing：输出型参数，如果参数 key 在哈希表中已经存在，则会添加失败。该参数可以将这个已经存在的 key 所属的 dictEntry 返回。

• 返回值：

  • NULL：哈希表中已经存在该 key，添加失败。
  • 非 NULL：添加成功，返回该 key 所在的 dictEntry 的首地址。

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // [1](见注解1)
    if (dictIsRehashing(d)) _dictRehashStep(d); // 如果处于 rehash 状态，尝试进行一次单步 rehash

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL; // 如果待插入的 key 在哈希表中已经存在，则直接返回 NULL

    // 走到这里说明待插入的 key 在哈希表中不存在，并且通过上一个代码块的 if 语句，我们已经计算出了该 key 应当插入到哈希表的哪个位置
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 根据哈希表是否处于 rehash 状态确定新节点应该插入到哪一个 Hash 表。如果处于 rehash 状态，肯定是插入到 d->ht[1] 因为该状态下 d->ht[0] 中的数据要全部迁移到 d->ht[1] 嘛。如果还往 d->ht[0] 中插入，是在不知道你怎么想的
    entry = zmalloc(sizeof(*entry)); // 开辟一个 dictEntry 节点
    entry->next = ht->table[index]; // 头插节点
    ht->table[index] = entry; // 覆盖哈希表中索引位置的指针
    ht->used++; // 更新哈希表中键值对的数量

    // 将 key 设置到 dictEntry 中
    dictSetKey(d, entry, key);
    return entry;
}

1. 为什么需要在字典插入函数中进行 rehash 操作呢？
   • 什么是 rehash？在 Redis 中，rehash 是将数据从旧的哈希表迁移到新的哈希表的过程。由于哈希表的大小是动态调整的，特别是在插入和删除元素时，哈希表可能会增长或缩小。当哈希表增长或缩小时，所有的元素需要从旧的哈希表重新哈希并搬移到新的哈希表中。这就是 rehash 过程。
   • 因为 Redis 是单线程的，如果在一个操作内将原哈希表中的数据 全部都迁移到新的哈希表，那么就可能引起线程长期阻塞。rehash 过程可能会非常耗时，尤其是当哈希表中有大量元素的时候。为了避免在单次操作中耗费过多时间，Redis 采取了增量 rehash (incremental rehashing)的策略，即每次操作时，只执行 rehash 过程的一小部分。这样做的好处是将 rehash 的开销分摊到多次操作中，从而避免了单次操作耗时过长的问题。
   • 这么做有什么好处？这样做的目的在于将 rehash 操作平滑地分摊到多个操作中，以避免单次操作的卡顿，确保 Redis 的高性能和低延迟。
   • 哪些操作可能会进行一次单步 rehash？dictAddRaw，dictGenericDelete，dictFind，dictGetRandomKey，dictGetSomeKeys 等函数都会调用 dictRehashStep 函数，从而逐步将数据迁移到新的 Hash 表中。

dictIsRehashing

宏功能：判断是否正在进行 rehash 操作。

#define dictIsRehashing(d) ((d)->rehashidx != -1)

_dictRehashStep

• 函数功能：进行一次单步 rehash。

• 参数：

  • dict* d：需要进行一次单步 rehash 的 dict 首地址。

• 返回值：无。

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1); // 只有原哈希表中没有迭代器正在遍历该哈希表，才会进行 rehash 操作。如果有迭代器正在遍历原哈希表，还去进行 rehash 很有可能会导致迭代器失效，引发不可预期的后果。
}

dictRehash

• 函数功能：进行 n 次单步 rehash 操作。

• 参数：

  • dict *d：一个 dict 的首地址。
  • n：惊醒多少次单步 rehash 操作。

• 返回值：

  • 0：当前的 dict 不处于 rehash 状态或者执行完该函数之后，rehash 完毕，退出 rehash 状态。
  • 1：还需要继续进行 rehash 操作。

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; // 从 rehashidx 允许出现的空索引位置的数量
    
    // 如果没有在进行 rehash 操作，直接返回 0 
    if (!dictIsRehashing(d)) return 0;

    // rehash 操作必须确保原哈希表中还有键值对嘛，至于 n 就是进行单步  rehash 的次数嘛
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++; // 更新 rehashidx，rehashidx 在原 hash 表中的索引加 1 
            if (--empty_visits == 0) return 1; // 出现空索引，empty_visits 需要减一
        }
        de = d->ht[0].table[d->rehashidx]; // 走到这说明找到了原哈希表中的一个非空索引
        
        // 将该索引下的全部节点移到新的哈希表中
        while(de) {
            uint64_t h;

            nextde = de->next; // 提前找到下一个节点
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask; // 获取当前节点在新哈希表中的索引
            de->next = d->ht[1].table[h]; // 头插到新的哈希表的对应索引处
            d->ht[1].table[h] = de; // 更新索引位置的 dictEntry 指针
            d->ht[0].used--; // 更新原哈希表中的键值对数量
            d->ht[1].used++; // 更新新哈希表中的键值对数量
            de = nextde; // 继续对下一个节点进行处理
        }
        d->ht[0].table[d->rehashidx] = NULL; // 原哈希表中的一个索引处理完成之后需要置为 NULL
        d->rehashidx++; // 更新原哈希表的 rehashidx 
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) { // 如果原哈希表中的键值对数量为 0，说明 rehash 操作已经完成啦
        zfree(d->ht[0].table); // 释放掉原哈希表
        d->ht[0] = d->ht[1]; // 让 ht[0] 指向 rehash 完成的哈希表
        _dictReset(&d->ht[1]); // 重置 ht[1] 的相关结构体成员
        d->rehashidx = -1; // 更新 dict 的 rehashidx
        return 0; // rehash 完毕
    }

    /* More to rehash... */
    return 1;
}

dictHashKey

宏功能：根据键计算其哈希值。

这是调用了 dictType.hashFunction 函数计算键的 Hash 值。

#define dictHashKey(d, key) (d)->type->hashFunction(key)

Redis 中字典基本都使用 SipHash 算法。该算法能有效防止 Hash 碰撞，并提供不错的性能。

Redis 4.0 之前使用的 Hash 算法是 MurmurHash。即使输入的键是有规律的，该算法计算的结果依然有很好的离散性，并且计算速度非常快。Redis 4.0 开始更换为 SipHash 算法，应该是出于安全的考虑。

_dictReset

• 函数功能：重置一个 dictht 的成员。
• 参数：
  • dictht *ht：需要重置的 dictht 的首地址。
• 返回值：无。

static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

_dictKeyIndex

• 函数功能：计算一个键在哈希表中的索引。
• 参数：
  • dict *d：哈希表所在的 dict 首地址。
  • const void *key：需要查找的键。
  • uint64_t hash：key 经过哈希算法得到的哈希值。
  • dictEntry **existing：输出型参数，如果查找的键在哈希表中已经存在，则通过该参数将这个键对应的 dictEntry 返回。
• 返回值：
  • -1：表示参数 key 在哈希表中已经存在。
  • 其他值：参数 key 在哈希表中的索引。

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL; // 置为 NULL 防止上一次的结果影响这次函数计算的结果

    // 判断哈希表是否需要进行扩容，如果需要的话，如果扩容失败直接返回 -1, 大概率是不可能在这里进行返回的
    if (_dictExpandIfNeeded(d) == DICT_ERR) 
        return -1;
    
    // 可能需要对两张表进行查找，因为如果原来的哈希表如果正处于 rehash 状态的话，原哈希表的一部分数据是在 新的哈希表中
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask; // hash 值在哈希表中的索引
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx]; // 找到哈希表中该索引下的第一个 dictEntry 节点
        while(he) { // 遍历这个链表 (哈希桶)
            // [1](见注解1)
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                // 如果参数的 key 已经在哈希表中存在了，通过输出型参数将这个存在的 dictEntry 节点返回出去
                if (existing) *existing = he;
                return -1;
            }
            he = he->next; // 继续比较下一个节点
        }
        if (!dictIsRehashing(d)) break; // 如果当前的哈希表没有处于 rehash 的状态说明另一个哈希表中是没有数据的，直接结束循环就行啦！
    }
    return idx;
}

1. 在 Redis 中，使用 dict 存储散列元素，键（key）通常是使用 SDS (Simple Dynamic Strings) 来表示的，并且 Redis 在内部维护了一个 redisObject 共享池。redisObject 共享池是一个优化措施，它会缓存一些常用的 redisObject 对象，特别是在一些常见的操作中，如命令解析、客户端传输等。这些常用的 redisObject 对象会被缓存在共享池中，以减少内存分配和提高性能。

   因此，当在 Redis 的字典中进行键的比较时，如果两个键的 SDS 对象的指针相同（即它们指向了共享池中的同一个 SDS 对象），那么这两个键是相同的。在这种情况下，直接使用 == 操作符进行指针比较是一种快速有效的方法，因为它只需比较两个指针是否相等，而不需要比较 SDS 对象的内容。(并没有 SDS 共享池哈，实际上是 redisObject 共享池，但是呢，redisObject 的 ptr 指针可以指向一个 SDS 嘛，因此勉强说有 SDS 共享池也是没有啥大问题的，你觉得呢？)

   这种优化适用于那些频繁使用的 SDS 对象，尤其是在 Redis 内部的核心逻辑中，这些 SDS 对象可能被重复使用多次。通过使用 SDS 共享池和直接指针比较，Redis 可以在某种程度上提高比较操作的效率，并减少不必要的字符串内容比较的开销。

   需要注意的是，这种优化只适用于那些频繁使用的 SDS 对象，对于不在共享池中的 SDS 对象，仍然需要比较其内容来确定是否相等。因此，在字典中比较键时，Redis 会根据具体情况选择合适的比较方式，以提高性能。

   当 key==he->key 比较失败的时候，就会执行 dictCompareKeys 这个函数，使用 dict.type.keyCompare 进行比较。

   key==he->key 这个判断可以提供一些性能上的优化，因为它是一个非常快速的指针比较操作。而调用

   dictCompareKeys 可能会涉及更复杂的逻辑，具体取决于键的类型和比较函数的实现。因此，保留

   key==he->key 这个判断可以在某些情况下提高性能。

_dictExpandIfNeeded

• 函数功能：判断指定的 dict 中的哈希表是否需要进行 resize。如果需要 resize直接进行 resize哈！
• 参数：
  • dict *d：指定需要进行判断的 dict。
• 返回值：
  • DICT_ERR： resize失败。
  • DICT_OK： resize成功。
    • 当前哈希表正在进行 rehash。
    • 当前哈希表需要 rehash。

#define DICT_OK 0
#define DICT_ERR 1
#define DICT_HT_INITIAL_SIZE     4
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

static int _dictExpandIfNeeded(dict *d)
{
    // 如果正在进行 rehash 直接返回
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表是空的，则扩容到哈希表的初始大小
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // [1](见注解1)
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2); // 两倍扩容
    }
    return DICT_OK;
}

1. 哈希表的扩容操作需要满足两个条件：

   • d->ht[0].used >= d->ht[0].size：Hash 表存储的键值对数量大于或者等于 Hash 表数组的长度。
   • 开启了 dict_can_resize 或者负载因子大于 dict_force_resize_ratio。

   d->ht[0].used/d->ht[0].size，即 Hash 表存储的键值对数量除以 Hash 表数组的长度，称之为负载因子。dict_can_resize 默认开启，即负载因子等于 1 就扩容。负载因子等于 1 可能出现比较高的 Hash 冲突率，但这样可以提高 Hash 表的内存使用率。dict_can_resize 关闭时，必须等到负载因子大于

   dict_force_resize_ratio 时才强制扩容。用户不能通过配置关闭 dict_can_resize。

   以下是一些可能会修改 dict_can_resize 的场景：

   1. 持久化操作：在执行 RDB 保存或 AOF 重写等持久化操作期间，可能希望暂时禁用扩容以减少内存使用和避免性能抖动。
   2. 批量数据导入：在大量数据导入期间，可能希望禁用扩容以加快导入速度，然后在导入完成后手动调整字典大小。
   3. 内存限制：在接近内存使用上限时，可能希望禁用扩容以避免超出内存限制。

dictExpand

• 函数功能：对 dict 中的哈希表进行 resize (说是 resize 的准备也不错的，增量式的 resize 嘛)
• 参数：
  • dict *d：要进行 resize 的 dict。
  • unsigned long size：resize 之后的大小。这不一定是真的 resize 之后的哈希表大小。因为 Redis 要求哈希表的大小是 2 的整数次幂嘛！
• 返回值：
  • DICT_ERR：resize 失败。
    • 当前 dict 的哈希表正在进行 rehash 操作。
    • 指定的参数 size 太小。
  • DICT_OK：扩容成功。
    • 原哈希表不存在，该函数的功能就可以理解为创建哈希表啦。
    • 原哈希表存在，进行 resize。

int dictExpand(dict *d, unsigned long size)
{
    // 如果当前的 dict 正在进行 rehash 操作，或者键值对的数量大于 resize 之后的目标数组大小，直接返回
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; // 新的哈希表
    unsigned long realsize = _dictNextPower(size); // 获取哈希表的真实大小，因为参数的 size 并不一定满足 Redis 对哈希表大小的要求，resize 之后数组的大小需要进行手动计算

    // resize 之后的 size 不能与原来哈希表的 size 相等，否则直接返回，因为这并没有什么意义嘛
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize; // 初始化新的哈希表的 size 字段 (Hash 表数组的长度)
    n.sizemask = realsize-1; // 设置 Hash 表的 sizemask 字段，固定为 size 字段 - 1
    n.table = zcalloc(realsize*sizeof(dictEntry*)); // 开辟哈希表数组，并且初始化为 NULL，calloc 函数的功能嘛
    n.used = 0; // 设置新的哈希表的 used 字段，现在还没有任何键值对嘛，设置为 0 就行啦

    // 如果说原来的哈希表就是 NULL 说明就不是执行扩容操作啦，就是创建一个大小为 realsize 的哈希表啦
    if (d->ht[0].table == NULL) {
        d->ht[0] = n; // 结构体是直接允许赋值的，只是可能会带来效率上的消耗吧，其实效率问题不好说
        return DICT_OK; 
    } 

    // 增量式 resize 要提前准备一个哈希表来接收数据，就是 dictht->ht[1] 嘛
    d->ht[1] = n;
    d->rehashidx = 0; // 数据迁移的起始下标
    return DICT_OK;
}

_dictNextPower

• 函数功能：获取大于参数 size 的下一个可能的哈希表的大小。
• 参数：
  • unsigned long size：指定计算的 起点。
• 返回值：返回计算得到的大于等于 size 的哈希表的 size。

#define DICT_HT_INITIAL_SIZE     4

/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE; // 初始化 i 为哈希表的初始大小

    if (size >= LONG_MAX) return LONG_MAX + 1LU; // 这个 1LU 表示常量 1 他的类型是 unsigned long哈
    while(1) {
        if (i >= size) // 大于等于 size 的时候就返回
            return i;
        // [1](见注解1)
        i *= 2; // Redis 要求哈希表的大小是 2 的整数次幂
    }
}

1. 为什么要将 size 调整为 2 的整数次幂呢？为了能够使用位运算来计算哈希值在哈希表中的索引。
   • 在哈希表中，通过对键的哈希值进行模运算来确定键在哈希表中的索引位置，而模运算可以转化为位运算，即 hash & (size-1)。这种转化只有在哈希表的大小是 2 的整数次幂的情况下才成立，因为 (size-1) 的二进制表示形式是若干个连续的 1，这样做位与运算时可以更高效地确定哈希值在哈希表中的索引位置。
   • 如果哈希表的大小不是 2 的整数次幂，那么 (size-1) 的二进制表示形式就不再是若干个连续的 1，这样就无法通过位与运算来高效地计算哈希值在哈希表中的索引位置，而需要使用更为复杂的模运算。这会增加计算的时间复杂度，并且降低哈希表的性能。

dictCompareKeys

宏功能：比较哈希表中的两个键是否相等。

// 判断 dict.dictType.keyCompare 这个函数指针有没有初始化，如果初始化了，那么就调用这个函数来比较两个键否之直接使用 == 进行比较
#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d)->privdata, key1, key2) : \
        (key1) == (key2))

dictSetKey

宏功能：将 key 设置到指定的 dictEntry 中。

#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \ // 如果 (d)->type->keyDup 这个函数指针已经初始化了，那么调用该函数进行 key 的复制
        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        (entry)->key = (_key_); \ // 如果该函数指针没有初始化，那么直接使用 = 进行复制
} while(0)

dictAdd

• 函数功能：向哈希表中添加一个键值对。
• 参数：
  • dict *d：哈希表所属的 dict。
  • void *key：待插入的键。
  • void *val：待插入的值。
• 返回值：
  • DICT_ERR：键已存在，添加失败。
  • DICT_OK：添加成功。

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL); // 先向哈希表中添加一个键，通过接受返回值确定添加的结果

    if (!entry) return DICT_ERR; // entry == NULL 说明这个键在哈希表中已经存在了，添加失败，返回 DICT_ERR
    // 走到这里说明键已经添加成功啦
    dictSetVal(d, entry, val); // 将值设置到 dictEntry 中，添加值
    return DICT_OK;
}

dictSetVal

宏功能：将 val 设置到指定的 dictEntry 中。

#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \ // 如果 (d)->type->valDup 这个函数指针已经初始化了，那么调用该函数进行 val 的复制
        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        (entry)->v.val = (_val_); \ // 如果该函数指针没有初始化，那么直接使用 = 进行复制
} while(0)

dictReplace

• 函数功能：替换或者插入键值对。
• 参数：
• 返回值：

int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    /* Try to add the element. If the key
     * does not exists dictAdd will succeed. */
    entry = dictAddRaw(d,key,&existing); // 先尝试向哈希表中添加一个键，通过接受返回值确定添加的结果
    if (entry) { // 如果添加成功了
        dictSetVal(d, entry, val); // 直接设置 val 就行啦
        return 1;
    }

    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    // 走到这里说明哈希表中已经存在这个键啦
    auxentry = *existing; // 保存这个存在的键所在的 dictEntry 浅拷贝，保存了旧的 val 地址
    dictSetVal(d, existing, val); // 将 val 设置到这个 dictEntry 中
    dictFreeVal(d, &auxentry); // 释放点旧的 val 空间
    // [1](见注解1)
    return 0;
}

1. 如果先释放旧值，然后再设置新值，那么有可能在释放旧值的过程中，新值的内存被错误地释放掉，从而导致潜在的内存错误。

   引用计数和内存管理的潜在问题

   在 Redis 中，值对象（value）通常是通过引用计数进行内存管理的。这意味着每次使用一个对象时，会增加其引用计数，而每次不再使用时，会减少其引用计数。当引用计数降为零时，对象的内存才会被释放。

   错误释放新值的可能性

   1. 旧值和新值是同一个对象：
      • 如果 val 是一个引用计数对象，并且此时 existing 指向的旧值恰好与 val 是同一个对象（例如同一个字符串或其他共享对象），先释放旧值会导致其引用计数减少。
      • 如果此时引用计数减少到零，该对象就会被释放。
      • 之后，再尝试设置新值 val 时，由于 val 已经被释放，会导致访问无效内存，进而引发未定义行为或程序崩溃。
   2. 引用计数的安全性：
      • 在设置新值之前，如果旧值与新值是同一个对象，立即减少引用计数可能会错误地认为对象不再被使用，从而释放它。
      • 为了避免这种情况，正确的顺序应该是先增加引用计数（通过设置新值），然后再减少引用计数（通过释放旧值）。这样可以确保在整个过程中对象不会被错误地释放。

dictFreeVal

• 宏功能：释放一个 dictEntry 中 val 的空间。

#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d)->privdata, (entry)->v.val) // 只有初始化了 valDestructor 这个函数指针，才会调用该函数来释放 val 的空间

dictDelete

• 函数功能：删除哈希表中的一个键值对。
• 参数：
  • dict *ht：哈希表所属的 dict。
  • const void *key：待删除的键。
• 返回值：

/* Remove an element, returning DICT_OK on success or DICT_ERR if the
 * element was not found. */
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR; // 根据 dictGenericDelete 函数的返回值，判断 Delete 操作是否成功
}

dictGenericDelete

• 函数功能：在哈希表中查找并删除一个 dictEntry。
• 参数：
  • dict *d：哈希表所属的 dict。
  • const void *key：待删除的键。
  • nofree：在哈希表中存在待删除的键的前提下，决定删除该 dictEntry 之后是否释放其空间。引入 nofree 参数的主要目的是提供灵活性，让调用者能够控制在删除字典节点时是否立即释放节点所占用的内存。这种设计考虑了性能优化、内存管理、并发安全和特定业务逻辑需求等多方面因素。在具体使用时，需要根据实际需求和场景来决定是否使用 nofree 参数。
• 返回值：
  • NULL：待删除的键在哈希表中不存在，删除失败。
  • 非 NULL：待删除的键在哈希表中存在。无论是否释放这个 dictEntry 返回值都一定不为 NULL。

/* Search and remove an element. This is an helper function for
 * dictDelete() and dictUnlink(), please check the top comment
 * of those functions. */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    // 如果两个哈希表中的键值对数量均为 0，那么没有键值对会被删除，直接返回 NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    // 如果当前哈希表处于 rehash 状态，那么执行一次单步的 rehash 操作
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 根据键计算其哈希值
    h = dictHashKey(d, key);

    // 当前的哈希表可能处于 rehash 状态，该状态下键值对数据可能存在与 dict 下的两个哈希表中，因此可能需要遍历两个哈希表
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask; // 计算这个哈希值在哈希表中的索引
        he = d->ht[table].table[idx]; // 找到该索引下的链表(哈希桶)的第一个节点
        prevHe = NULL;
        while(he) { // 遍历这个链表(哈希桶)
            if (key==he->key || dictCompareKeys(d, key, he->key)) { // 如果这个键存在
                /* Unlink the element from the list */
                if (prevHe) // prevHe 不为 NULL 说明待删除的 dictEntry 不是链表(哈希桶)的头结点
                    prevHe->next = he->next; // 直接进行节点的链接就行啦
                else // prevHe 为 NULL 说明待删除的 dictEntry 是链表(哈希桶)的头结点
                    d->ht[table].table[idx] = he->next; // 更新该索引下的头结点地址
                if (!nofree) { // 如果 nofree == 0 即需要释放掉 dictEntry
                    dictFreeKey(d, he); // 释放键
                    dictFreeVal(d, he); // 释放值
                    zfree(he); // 释放 dictEntry
                }
                d->ht[table].used--; // 哈希表中的键值对数量减 1
                // [1](见注解1)
                return he; // 因为哈希表中不可能出先两个相同的键，那么一旦找到了待删除的键值对，删除之后就可以直接返回了
            }
            prevHe = he; // 更新 prevHe
            he = he->next; // 更新 he 
        }
        if (!dictIsRehashing(d)) break; // 如果当前的哈希表不处于 rehash 状态，那么另一个哈希表一定没有数据退出循环
    }
    return NULL; // 返回 NULL 代表删除成功
}

1. 在 dictGenericDelete 函数中，如果 nofree 为 0，则会释放字典项中的键和值，并且释放 dictEntry 本身的内存。然而，在这种情况下，函数仍然返回已经被释放的 dictEntry 指针。这会导致返回一个无效的指针，这种情况下访问返回的指针将导致未定义行为。

   在 Redis 中，dictGenericDelete 函数的设计可能有以下几个原因：

   1. 一致的接口：函数总是返回 dictEntry 指针，无论是否释放内存。这使得调用者在处理结果时有一个一致的接口，虽然需要调用者小心处理 nofree 为 0 的情况。

   2. 特定使用场景：在 Redis 的使用场景中，调用 dictGenericDelete 时，如果 nofree 为 0，调用者需要特别注意不要使用返回的指针。这可能是由 Redis 开发者内部约定的，并且通过代码审查和测试来确保正确使用。

   3. 性能考虑：Redis 是一个高性能的内存数据库，设计中非常注重性能。在一些性能关键的代码路径中，避免额外的判断和复杂的逻辑可以提高性能。通过约定来管理内存和指针可能是权衡性能和代码安全性的一种选择。

      dictGenericDelete 函数只是作为 dictDelete 和 dictUnlink 的子函数，只要在这两个函数中正确使用

      dictGenericDelete 函数的返回值，就不会出现任何问题啦！

dictFind

• 函数功能：查找键值对。
• 参数：
  • dict* d：哈希表所属的 dict。
  • const void *key：查找的键。
• 返回值：
  • NULL：哈希表中不存在该键。
  • 非 NULL：找到的键所在的 dictEntry。

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (dictSize(d) == 0) return NULL; // dict 是空的，找啥呢？直接返回
    if (dictIsRehashing(d)) _dictRehashStep(d); // 如果当前的哈希表处于 rehash 状态，那么执行一次单步 rehash 的操作
    h = dictHashKey(d, key); // 键的哈希值
    
    // 遍历两个哈希表
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask; // 在哈希表中的索引值
        he = d->ht[table].table[idx]; // 该索引下的头结点
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) // 如果找到了直接返回
                return he; // 返回找到的 dictEntry
            he = he->next; // 下一个节点
        }
        if (!dictIsRehashing(d)) return NULL; // 不处于 rehash 状态直接跳出循环
    }
    return NULL; // 遍历完哈希表都没找到
}

dictSize

• 宏功能：计算 dict 中哈希表的键值对数量。

#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)

dictResize

• 函数功能：哈希表的缩容。
• 参数：
  • dict* d：哈希表所属的 dict。
• 返回值：
  • DICT_ERR：缩容失败。
  • DICT_OK：缩容成功。

#define DICT_HT_INITIAL_SIZE     4

int dictResize(dict *d)
{
    unsigned long minimal;

    // dict_can_resize 详见 _dictExpandIfNeeded 函数的注解
    // 如果哈希表不允许 resize 或者 当前哈希表已经在进行 rehash 操作了，直接返回 DICT_ERR
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht[0].used; // 记录 ht[0] 中键值对的数量
    if (minimal < DICT_HT_INITIAL_SIZE) // 缩容之后的最小值不能小于 4 
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal); // 尝试缩容哈，目标容量：minimal
}

htNeedsResize

• 函数功能：判断哈希表是否需要缩容。
• 参数：
  • dict* d：哈希表所属的 dict。
• 返回值：
  • 1：哈希表需要缩容。
  • 0：哈希表不需要缩容。

#define DICT_HT_INITIAL_SIZE     4
#define HASHTABLE_MIN_FILL        10 

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict); // dict 的两个哈希表数组的总长度
    used = dictSize(dict); // dict 的两个哈希表中存储的键值对的总数量
    // 这就是需要进行缩容的条件啦，原哈希表的长度至少为 4 并且 负载因子小于 0.1
    // [1](见注解1)
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

1. 执行删除操作后，Redis 会检查字典是否需要缩容，当 Hash 表长度大于 4 且负载因子小于 0.1 时，会执行缩容操作，以节省内存。缩容实际上也是通过 dictExpand 函数完成的，只是函数的第二个参数 size 是缩容后的大小

dictSlots

• 宏功能：计算 dict 下两个哈希表数组的总长度

#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)

编码

散列类型有 OBJ_ENCODING_HT 和 OBJ_ ENCODING_ ZIPLIST 两种编码，分别使用 dict、ziplist 结构存储数 (redisObject.ptr 指向 dict、ziplist 结构)。Redis 会优先使用 ziplist 存储散列元素，使用一个 ziplist节点存储键，后驱节点存放值，查找时需要遍历 ziplist。 使用 dict 存储散列元素，字典的键一般是 sds 类型。

散列类型使用 OBJ_ENCODING_ZIPLIST 编码，需满足以下条件：

1. 散列中所有键或值的长度小于或等于 server.hash_max_ziplist_value，该值可通过 hash-max-ziplist-value 配置项调整。
2. 散列中键值对的数量小于 server.hash_max_ziplist_entries，该值可通过 hash-max-ziplist-entries 配置项调整。

总结

• Redis 字典使用 SipHash 算法计算 Hash 值，并使用链表法处理 Hash 冲突。
• Redis 字典使用增量式扩容方式， 在每次数据操作中都执行一次扩容单步操作，直到扩容完成。
• 散列类型的编码格式可以为 OBJ_ ENCODING_HT、OBJ_ENCODING_ ZIPLIST。