DICT

简介

Redis是一个键值型（Key-Value Pair）的数据库，可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。查找、插入和删除操作的时间复杂度均为 O(1)。

具体实现

Dict由三部分组成，从外到内分别是：字典（Dict）、哈希表（DictHashTable）、哈希节点（DictEntry）

Dict结构定义如下：

1
2
3
4
5
6
7
8
typedef struct dict {
    dictType *type; // dict类型，内置不同的hash函数
    void *privdata;     // 私有数据，在做特殊hash运算时用
    dictht ht[2]; // 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用
    long rehashidx;   // rehash的进度，-1表示未进行
    int16_t pauserehash; // rehash是否暂停，1则暂停，0则继续
} dict;

DictHashTable结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictht {
    // entry数组
    // 数组中保存的是指向entry的指针
    dictEntry **table; 
    // 哈希表大小
    unsigned long size;     
    // 哈希表大小的掩码，总等于size - 1
    unsigned long sizemask;     
    // entry个数
    unsigned long used; 
} dictht;

DictEntry结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    // 下一个Entry的指针（哈希冲突时使用链地址法）
    struct dictEntry *next; 
} dictEntry;

整体结构图示如下：
image-20250219215955989

扩容缩容机制

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

  • 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
  • 哈希表的 LoadFactor > 5 ；

扩容代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
static int _dictExpandIfNeeded(dict *d){
    // 如果正在rehash，则返回ok
    if (dictIsRehashing(d)) return DICT_OK;    // 如果哈希表为空，则初始化哈希表为默认大小：4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // 当负载因子（used/size）达到1以上，并且当前没有进行bgrewrite等子进程操作
    // 或者负载因子超过5，则进行 dictExpand ，也就是扩容
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){
        // 扩容大小为used + 1，底层会对扩容大小做判断，实际上找的是第一个大于等于 used+1 的 2^n
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩。

rehash实现

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。

过程是这样的：

  • 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

    • 如果是扩容，则新size为第一个大于等于ht[0].used + 1的2^n
    • 如果是收缩，则新size为第一个大于等于ht[0].used的2^n （不得小于4）

  • 按照新的realeSize申请内存空间，创建dictht，并赋值给ht[1]

  • 设置dict.rehashidx = 0，标示开始rehash

  • 将ht[0]中的每一个dictEntry都rehash到ht[1]

  • 将ht[1]赋值给ht[0]，给ht[1]初始化为空哈希表，释放原来的ht[0]的内存

  • 将rehashidx赋值为-1，代表rehash结束

  • 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在ht[0]和ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

image-20250219220911902

image-20250219220944439

__END__