特别提醒，本文所涉及的代码是redis3.0，由《Redis设计与实现》作者所注释的版本：地址

与字典相关的文件在dict.h和dict.c两个文件中

数据结构

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

dictEntry是字典中的单个节点，即一个k-v对，注意到这里的值是一个union联合体，键值对中的值可以是一个指向实际值的指针即val，或者是一个无符号的 64 位整数u64或有符号的 64 位整数s64。

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

dictht是一个哈希表，其中存放了很多个链表节点，每个链表是一个dictEntry

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; 
    // 目前正在运行的安全迭代器的数量
    int iterators; 
} dict;

dict是redis中真正提供给外面使用的字典，其中有多个字段，这里只关注核心的两个字段dictht ht[2]和int rehashidx。这里要创建两个哈希表是为了方便rehash，rehashidx主要用于渐进式哈希。

可能第一眼看上面有三个相关的数据结构，有点不太好理解，下面画一个图来描述三者的关系：

image-20231027153704840

下面介绍学习一下dict的一些增删改查的源码

查找

在字典dict中查找key在哪个链表中，如果存在该key则返回-1，不存在则返回哈希值，即应该在哪个链表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    // 计算 key 的哈希值
    h = dictHashKey(d, key);
    // T = O(1)
    for (table = 0; table <= 1; table++) {
        // 计算索引值
        idx = h & d->ht[table].sizemask;
        // 查找 key 是否存在
        // T = O(1)
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key
        // 如果这时 rehahs 正在进行，那么继续对 1 号哈希表进行 rehash
        if (!dictIsRehashing(d)) break;
    }
    // 返回索引值
    return idx;
}

  • 首先调用函数_dictExpandIfNeeded(d)判断当前字典是否需要进行扩容
  • 先遍历ht[0]中的链表，然后计算key的哈希值，如果该链表中查询到则直接返回
  • 如果在ht[0]的链表中没找到，则要先判断该字典是否处在rehash中，如果不在，则直接返回前面计算到的idx，否则还要去ht[1]对应的链表中查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int _dictExpandIfNeeded(dict *d)
{
    // 渐进式 rehash 已经在进行了，直接返回
    if (dictIsRehashing(d)) return DICT_OK;
    // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表
    // T = O(1)
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // 一下两个条件之一为真时，对字典进行扩展
    // 1）字典已使用节点数和字典大小之间的比率接近 1：1
    //    并且 dict_can_resize 为真
    // 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        // 新哈希表的大小至少是目前已使用节点数的两倍
        // T = O(N)
        return dictExpand(d, d->ht[0].used*2);
    }

    return DICT_OK;
}
  • 如果字典还未初始化，则进行初始化操作，初始化链表数组大小为4
  • 满足两个条件之一，则需要进行扩容操作：字典已使用节点数和字典大小之间的比率接近 1:1并且 dict_can_resize 为真，或者已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio，该值为5。
  • 扩容时有个小细节，就是它调用dictExpand(d, d->ht[0].used*2)，传入的大小为已经存在的k-v对的两倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int dictExpand(dict *d, unsigned long size)
{
    // 新哈希表
    dictht n;
    // 根据 size 参数，计算哈希表的大小
    // T = O(1)
    unsigned long realsize = _dictNextPower(size);
    // 不能在字典正在 rehash 时进行
    // size 的值也不能小于 0 号哈希表的当前已使用节点
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    // 为哈希表分配空间，并将所有指针指向 NULL
    n.size = realsize;
    n.sizemask = realsize-1;
    // T = O(N)
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    // 如果 0 号哈希表为空，那么这是一次初始化：
    // 程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }
    // 如果 0 号哈希表非空，那么这是一次 rehash ：
    // 程序将新哈希表设置为 1 号哈希表，
    // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}
  • 首先会根据传入的size大小，找到第一个大于等于size的2的幂次方
  • 如果ht[0]为空，则说明这是一次初始化操作
  • 如果非空，则说明这是一次rehash操作，需要打开rehash标识，让字典在进行增删改查的时候进行渐进式哈希。

添加

往一个字典dict中添加一个k-v对，如果key已经存在字典当中，则添加失败，否则插入该k-v对

1
2
3
4
5
6
7
8
9
10
11
12
13
int dictAdd(dict *d, void *key, void *val)
{
    // 尝试添加键到字典，并返回包含了这个键的新哈希节点
    // T = O(N)
    dictEntry *entry = dictAddRaw(d,key);
    // 键已存在，添加失败
    if (!entry) return DICT_ERR;
    // 键不存在，设置节点的值
    // T = O(1)
    dictSetVal(d, entry, val);
    // 添加成功
    return DICT_OK;
}
  • 首先调用dictAddRaw函数，判断字典d中是否存在key
  • 如果已经存在则直接返回错误
  • 不存在，则插入，并且返回成功
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    // 如果条件允许的话，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 计算键在哈希表中的索引值
    // 如果值为 -1 ，那么表示键已经存在
    // T = O(N)
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;
    // T = O(1)
    // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
    // 否则，将新键添加到 0 号哈希表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为新节点分配空间
    entry = zmalloc(sizeof(*entry));
    // 将新节点插入到链表表头
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 更新哈希表已使用节点数量
    ht->used++;
    // 设置新节点的键
    // T = O(1)
    dictSetKey(d, entry, key);
    return entry;
}
  • 首先判断字典是否处在rehash中，如果是，则顺带执行单步rehash
  • 首先使用_dictKeyIndex(d, key)获取到插入到哪个链表的索引
  • 如果当前正在rehash则应该插入到ht[1]表中，否则是ht[0]表中
  • 插入到链表的头部（时间复杂度是O(1)）

修改

如果键不存在，则将给定的键值对添加到字典中，如果键已经存在，那么删除旧有的键值对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, auxentry;
    // 尝试直接将键值对添加到字典
    // 如果键 key 不存在的话，添加会成功
    // T = O(N)
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;
    // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点
    // T = O(1)
    entry = dictFind(d, key);
    // 先保存原有的值的指针
    auxentry = *entry;
    // 然后设置新的值
    // T = O(1)
    dictSetVal(d, entry, val);
    // 然后释放旧值
    // T = O(1)
    dictFreeVal(d, &auxentry);
    return 0;
}
  • 首先调用dictAdd(d, key, val)判断是否成功，如果成功说明是添加操作，否则要进行修改操作
  • 调用dictFind(d, key)找到该key对应的节点，修改其中的值

删除

查找并删除包含给定键的节点，成功删除返回DICT_OK，没找到则返回DICT_ERR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;
    // 字典（的哈希表）为空
    if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
    // 进行单步 rehash ，T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 计算哈希值
    h = dictHashKey(d, key);
    // 遍历哈希表
    // T = O(1)
    for (table = 0; table <= 1; table++) {
        // 计算索引值 
        idx = h & d->ht[table].sizemask;
        // 指向该索引上的链表
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 遍历链表上的所有节点
        // T = O(1)
        while(he) {
            if (dictCompareKeys(d, key, he->key)) {
                // 超找目标节点
                // 从链表中删除
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                // 释放调用键和值的释放函数？
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                // 释放节点本身
                zfree(he);
                // 更新已使用节点数量
                d->ht[table].used--;
                // 返回已找到信号
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        // 如果执行到这里，说明在 0 号哈希表中找不到给定键
        // 那么根据字典是否正在进行 rehash ，决定要不要查找 1 号哈希表
        if (!dictIsRehashing(d)) break;
    }
    // 没找到
    return DICT_ERR; /* not found */
}
  • 如果当前正在rehash，则协同进行单步的rehash操作
  • 首先遍历ht[0]，如果在该链表中没找到，则取遍历ht[1]找到则直接删除