字典的实现
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;
table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
sizemask 属性的值总是等于 size-1 。下图展示了一个大小为 4 的空哈希表 （没有包含任何键值对）。
redis通过hash函数和sizemask决定元素的索引值：
- 使用字典设置的哈希函数，计算键 key 的哈希值： hash = dict->type->hashFunction(key);
- 使用哈希表的 sizemask 属性和哈希值，计算出索引值： index = hash & dict->ht[x].sizemask;
哈希表节点
哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
next 属性是指向另一个哈希表节点的指针，redis采用链地址法来解决键冲突（collision）的问题。
举个例子， 下图就展示了redis解决键冲突的问题。
字典
Redis 中的字典由 dict.h/dict 结构表示：
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict;
type 属性和 privdata 属性是针对不同类型的键值对。type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
ht 属性是一个包含两个项的数组，一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。
typedef struct dictType { // 计算哈希值的函数 unsigned int (*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;
下图展示了一个普通状态下（没有进行 rehash）的字典：
渐进式rehash
redis渐进式rehash步骤
- 分配h[1]空间，此时字典同时持有h[0]和h[1]两个哈希表
- 在rehash期间，每次对字典执行添加、删除、查找或者更新操作时，会将
ht[0]哈希表在rehashidx索引上的所有键值对 rehash 到ht[1] - rehash结束，
rehashidx属性的值设为-1， 表示 rehash 操作已完成。
int dictRehash(dict *d, int n) { // 只可以在 rehash 进行中时执行 if (!dictIsRehashing(d)) return 0; // 进行 N 步迁移 // T = O(N) while(n--) { dictEntry *de, *nextde; // 如果 0 号哈希表为空，那么表示 rehash 执行完毕 if (d->ht[0].used == 0) { // 释放 0 号哈希表 zfree(d->ht[0].table); // 将原来的 1 号哈希表设置为新的 0 号哈希表 d->ht[0] = d->ht[1]; // 重置旧的 1 号哈希表 _dictReset(&d->ht[1]); // 关闭 rehash 标识 d->rehashidx = -1; // 返回 0 ，向调用者表示 rehash 已经完成 return 0; } // 确保 rehashidx 没有越界 assert(d->ht[0].size > (unsigned)d->rehashidx); // 略过数组中为空的索引，找到下一个非空索引 while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; // 指向该索引的链表表头节点 de = d->ht[0].table[d->rehashidx]; // 将链表中的所有节点迁移到新哈希表 while(de) { unsigned int h; // 保存下个节点的指针 nextde = de->next; // 计算新哈希表的哈希值，以及节点插入的索引位置 h = dictHashKey(d, de->key) & d->ht[1].sizemask; // 插入节点到新哈希表 de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; // 更新计数器 d->ht[0].used--; d->ht[1].used++; // 继续处理下个节点 de = nextde; } // 将刚迁移完的哈希表索引的指针设为空 d->ht[0].table[d->rehashidx] = NULL; // 更新 rehash 索引 d->rehashidx++; } return 1; }
下面给出部分字典更新操作代码，可以看到在字典更新操作是会进行一步的rehash，同时操作要在两个哈希表上进行
dictEntry *dictGetRandomKey(dict *d) { ... // 进行单步 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 如果正在 rehash ，那么将 1 号哈希表也作为随机查找的目标 if (dictIsRehashing(d)) { // T = O(N) do { h = random() % (d->ht[0].size+d->ht[1].size); he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] : d->ht[0].table[h]; } while(he == NULL); // 否则，只从 0 号哈希表中查找节点 } else { do { h = random() & d->ht[0].sizemask; he = d->ht[0].table[h]; } while(he == NULL); } }