redis 中的 HashTable 实现，是一个叫 dict 的结构体以及其相关的操作函数。本文将对 dict 中重要的结构体、操作方法进行介绍，阐述其实现逻辑，对于 redis 生命周期内对 dict 的其他操作，我会进一步的补充。另外，为了让源码能被更好的理解，我在必要的地方进行了改写，虽然这样可能使得源码不再可以正确运行，甚至无法通过语法检测。
一、重要的结构体
1. dict
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx;
unsigned long iterators;
} dict;
-
dict.dictType指定了该 dict 的实现方式。 -
dict.dictht是一个包含 2 个 dictht 的数组 -
dict.rehashidx表明了该 dict 进行 rehashing 的进度，-1：表示此时并没有在 rehashing。 -
dict.iterators表明现在正在操作该 dict 的迭代器数量。
2. dictType
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;
-
dictType.hashFunction计算 key 在 [0, dict.dictht.sizemask] 范围内的 hash 值，这个值是 value 存放到 dict.dictht.table 数组中的下标。 dictType.keyDup-
dictType.valDup如何将 value 放入 dictEntry 。可以对 value 的进行处理，默认 null 则表示不需要处理 -
dictType.keyCompare如何比较 key1 和 key2 是否相等，默认 null 表示 key1==key2 时相等 -
dictType.keyDestructor当释放 key 时的回调 -
dictType.valDestructor当需要释放 value 时的回调
3. dictht
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
-
dictht.table是一个 dictEntry 数组的起始指针，用来存在 value。 -
dictht.size记录了目前 dictht.table 的容量（即：数组长度）。 -
dictht.sizemaskdictht.table 容量的掩码。 -
dictht.used记录了 dict 中目前存放的 value 数量。
4. dictEntry
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
-
dictEntry.key存放 key -
dictEntry.v存放 value -
dictEntry.next是下一个 dictEntry 的指针。相同 dict.dictht.table 下标的 dictEntry 会以单向链表的方式存储，因此，dictEntry.next 是这个单向链表的头指针
二、重要的操作方法
1. dictCreate 用于创建一个空的 dict
dict *dictCreate(dictType *type, void *privDataPtr) {
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
int _dictInit(dict *d, dictType *type, void *privDataPtr){
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}
static void _dictReset(dictht *ht){
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
可以看到:
dictCreate 方法只是创建了一个空的 dict 实例，这个 dict 的各个属性都处于初始值，甚至连 dict.dictht[0].table 和 dict.dictht[1].table 都还是 null。
此时的 dict 用 javascript 对象表示，有点儿像：
{
"privdata": null,
"rehashidx": -1,
"iterators": 0,
"dictType": {
"hashFunction": function(key){return parse_int(key)%10;},
"keyDup": function(privdata, key){},
"valDup": function(privdata, value){return value;},
"keyCompare": function(privdata, key1, key2){return key1===key2;},
"keyDestructor": function(privdata, key){unset kye;},
"valDestructor": function(privdata, obj){unset obj;}
},
"dictht": [
{
"size": 0,
"sizemask": 0,
"used": 0,
"table": null,
},
{
"size": 0,
"sizemask": 0,
"used": 0,
"table": null,
}
]
}
2.dictExpand 对 dict 进行“扩容”
static int _dictExpandIfNeeded(dict *d){
if (dictIsRehashing(d)) return DICT_OK;
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
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;
}
int dictExpand(dict *d, unsigned long size){
if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR;
dictht n;
unsigned long realsize = _dictNextPower(size);
if (realsize == d->ht[0].size) return DICT_ERR;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
由源码可见：
① dict.dictht[0] 触发增加容量的条件是：
-
dict.dictht[0].size=0；意味着：刚初始化 dict，还没初始化dict.dictht[0].table时。 -
dict.dictht[0].used >= dict.dictht[0].size且dict_can_resize=1；当dict_can_resize=1并且dict.dictht[0]存放了dict.dictht[0].size以上个 value 时。 -
dict.dictht[0].used >= dict.dictht[0].size且dict.dictht[0].used是dict.dictht[0].size5倍以上时。
② dict.dictht[0] 增加容量到多少：
- 当初始化
dict.dictht[0].table时，会将容量增大到DICT_HT_INITIAL_SIZE，也就是4个。 - 其他情况，会将容量增大到
大于 dict.dictht[0].used 2倍的第一个 2^n
③ 扩容意外：
- 即使触发了增加容量的动作，但如果此时
dict 正在执行 rehashing，将放弃此次增加容量。
④ 当 dict 扩容成功后，dict 将开启 rehash
3. dictAdd 向 dict 中存入一对 key=>value
#define dictIsRehashing(d) ((d)->rehashidx != -1)
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
if (_dictExpandIfNeeded(d) == DICT_ERR) return -1;
for (table = 0; table <= 1; table++) {
idx = hash & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || d.dictType.keyCompare(d.privdata, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
if ((index = _dictKeyIndex(d, key, d.dictType.hashFunction(key), existing)) == -1) return NULL;
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
(entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
(entry)->v.val = (_val_); \
} while(0)
int dictAdd(dict *d, void *key, void *val){
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
由源码可以得到，在 dict 中存入一个键值对有两个步骤：
① 在 key 应该存放的位置，先放一个 v=null 的 dictEntry
- 如果需要
rehash，则先进行rehash - 使用
dict.dictType.hashFunction(key)，计算 key 应该存放的hash值 - 验证
dict.dictht.table中的hash位置能否存放 value。如果能，返回当前 key 的 hash 值应该存放在dict.dictht.table中的下标index - 在
dict.dictht.table中的index位置存放一个v=null 的 dictEntry，然后对dict中已经存放的 value 个数进行计数dict.dictht.used++
② 如果放置空 dictEntry 成功，再对 dictEntry 进行赋值
需要注意的是：如果
dict开启了 rehash，则 dictAdd 将会把 key=>value 存放到dict.dictht[1].table中
4. dictReplace 覆盖 key 的 value
int dictReplace(dict *d, void *key, void *val){
dictEntry *entry, *existing, auxentry;
if (entry) {
dictSetVal(d, entry, val);
return 1;
}
auxentry = *existing;
dictSetVal(d, existing, val);
dict.dictType.valDestructor(&auxentry);
return 0;
}
dictReplace 的实现和 dictAdd 的实现很相似，区别在于 dictReplace 会尝试调用 dict.dictType.valDestructor(&auxentry) 将被替换的值进行删除
5. dictRehash dictRehashMilliseconds 对 dict 进行 rehash
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
int dictRehash(dict *d, int n) {
int empty_visits = n*10;
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
while(de) {
uint64_t 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;
d->rehashidx++;
}
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
return 1;
}
由源码可知，redis rehash 的过程是：
- redis rehash 是将
dict.dictht[0].table中存储的dictEntry逐步 rehash 后存储到dict.dictht[1].table中的过程，这个过程往往是分成多次执行的，甚至支持现在先执行 100ms 的 rehash - 每次 rehash
dict.dictht[0].table 的 n 个下标或者访问了10n个下标都没能成功 rehashn 个下标时，退出 - 因为
dict.dictht[0].table中存储的dictEntry可能包含了一个dictEntry的单向链表（hash 冲突），因此：rehash n 个下标并不意味着 n 个 key，实际上 n 个下标可能包含大于 n 个 key - 对
dict的 rehash 是从 dict.rehashidx 开始的，每成功 rehash 一个下标dict.rehashidx++，每成功 rehash 一个 key，dict.dictht[0].used-- - 当
dict.dictht[0].used=0时，意味着dict的 rehash 操作完成了，此时只需要将dict.dictht[1].table赋值给dict.dictht[0].table，然后对dict.dictht[1].table进行初始化，同时将dict.rehashidx=1整个 rehash 过程就完成了
6. dictFind 在 dict 中查找指定 key
dictEntry *dictFind(dict *d, const void *key){
dictEntry *he;
uint64_t h, idx, table;
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
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 || dict.dictType.keyCompare(key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
在 dict 中查找的过程相对简单：
- 计算要查找的 key 的 hash 值 index（在 dict.dictht[0/1].table 中存储的下标）
- 在
dict.dictht[0].table[index]和dict.dictht[1].table[index]所对应的单向链表中，从链头开始向尾查找 - 查找的时间复杂度为
O(n)=m+n+1（m 和 n分别是dict.dictht[0].table[index]和dict.dictht[1].table[index]的长度）。因此查找的快慢取决于 dict 中 hash 冲突的多少，对dict的扩容和 rehash，正是为了减少hash 冲突，同时，选择更好的Hash Function，使得 hash 的结果更加均匀也能减少hash 冲突的频率
7. dictGenericDelete 从 dict 中删除 key
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
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 || dict.dictType.keyCompare(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 he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL;
}
在 dict 中删除 key 就是在找到 key 所在 dictEntry 单向链表的结点后，执行链表的删除，同时更新 dict.dictht[0/1].used--
8. dictUnlink 在链表中删除 key 但不释放内存
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
if (he == NULL) return;
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
dictEntry *dictUnlink(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
dictUnlink 和 dictDelete 的区别是：是否立即释放要删除的 dictEntry 内存（注意：在 dictUnlink 时，其实已经完成了 dictEntry 的链表删除）。dictUnlink 的意义在于：在真正释放 dictEntry 前，可以执行用户逻辑，比如：输出一下 key 的 value，再删除。
- 不使用
dictUnlink:
entry = dictFind(key);
print entry.v;
dictDelete(key)
- 使用
dictUnlink:
entry = dictUnlink(key);
print entry.v;
dictFreeUnlinkedEntry(entry);
两种写法的区别是：不使用 dictUnlink 时，在 dictFind 和 dictDelete 中分别执行了一次查询操作；使用 dictUnlink 时，只在 dictUnlink 中执行了一次查询操作。
9. dictRelease 删除并释放整个 dict
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
unsigned long i;
for (i = 0; i < ht->size && ht->used > 0; i++) {
dictEntry *he, *nextHe;
if (callback && (i & 65535) == 0) callback(d->privdata);
if ((he = ht->table[i]) == NULL) continue;
while(he) {
nextHe = he->next;
dict.dictType.keyDestructor(d, he);
dict.dictType.valDestructor(d, he);
zfree(he);
ht->used--;
he = nextHe;
}
}
zfree(ht->table);
_dictReset(ht);
return DICT_OK;
}
void dictRelease(dict *d){
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
zfree(d);
}
- 删除整个
dict的重点是需要释放dict.dictht[0].table和dict.dictht[1].table中的所有dictEntry，否则会造成内存泄漏。 - 在释放每个
dictEntry时，调用dict.dictType.keyDestructor和dict.dictType.valDestructor的意义在于：通知用户代码释放 key 和 value 的用户指针。
三、结论
- redis 中 HashTable 的实现是一个叫
dict的结构体及其相关的操作方法。 -
dict.dictType指定了dict的具体实现，它使得一个dict有别于另一个dict。 - key=>value 被存储到了
dictEntry中，dictEntry存储在dictht中。dict中有两个dictht，在没有开启 rehash 时，数据存放在dict.dictht[0].table中，一旦满足了 rehash 条件，数据将开始往dict.dictht[1].table中存储。 - 当
dict.dictht[0].used >= dict.dictht[0].size && dict_can_resize=1或者dict.dictht[0].used >= dict.dictht[0].size && dict.dictht[0].used / dict.dictht[0].size >=5时，将对dict进行扩容，扩容至大于 dict.dictht[0].used 2倍的第一个 2^n，扩容成功后，将开启dict的 rehash 过程。 -
dict的 rehash 过程是分多次完成的，具体过程是： 从dict.rehashidx开始，按照扩容后的dict.dictht[1].sizemask对dict.dictht[0].table中的每个dictEntry（如果 dict.dictht[0].table[dict.rehashidx] 产生过 hash 冲突，则会通过dictEntry.next指向链表头指针，遍历链表中的所有dictEntry）重新计算 hash 值（在dict.dictht[1].table中的下标），移动到dict.dictht[1].table中去。等到dict.dictht[0].table.used=0时，说明整个 rehash 过程完毕，会将dict.dictht[1]赋值给dict.dictht[0]，同时关闭dict的 rehash 标志（dict.rehashidx=-1）
四、设计问答
1. 为什么要对 dict 进行扩容？扩容后 rehash 的意义是什么？
dict.dictht.table 的默认大小是 4，当 key=>value 数据大于 4 时，必然出现多个 key 的 hash 值相同，在 dict.dictht[0].table 中的下标一致，从而导致 dict.dictht.table 其实是一个越来越长的链表，此时对 dict 的操作会退化为对链表的操作，即：时间复杂度从 O(1) 逐渐趋于 O(n)。对 dict 扩容后，使得存储相同数量 key=>value 时产生的 hash 冲突变少，从而链表长度变短，进而操作的 时间复杂度从 O(n) 逐渐趋于 O(1)
2. 为什么要 一次 rehash n 个下标，而不是一次性把所有下标都 rehash 完？
redis 是一个单线程（不考虑持久化线程）的应用，如果一次性 rehash 完所有下标，会导致 redis 在一定时间内无法提供服务，于是 redis 巧妙的将 这个一大段时间分摊到了每次操作这个 dict 都执行一部分的一小段时间，既保证了服务可用，又能完成 rehash 过程，提高性能。
3. 为什么扩容条件是 5 倍？为什么扩容到 大于 dict.dictht[0].used 2倍的第一个 2^n?
我猜测，5倍 应该是一个经验值，即避免了频繁扩容、hash导致的性能下降，又避免了 时间复杂度从 O(1) 逐渐趋于 O(n) 的可能。而扩容至 大于 dict.dictht[0].used 2倍的第一个 2^n 应该和选用的 Hash Function 有关，毕竟 redis 的 Hash Function 中大量使用了 << 和 '>>'
本来想在本篇中继续介绍
dict.iterator以及 redisdict相关命令的实现方式的，限于篇幅太长，会在redis 源码分析（一）HashTable 下篇中继续介绍，敬请期待。
另外，码字不易，喜欢的朋友点个赞，谢谢。
