Redis中内部数据结构dict的作用是什么

共计 8365 个字符，预计需要花费 21 分钟才能阅读完成。

本篇文章为大家展示了 Redis 中内部数据结构 dict 的作用是什么，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

dict 的数据结构定义

为了实现增量式重哈希（incremental rehashing），dict 的数据结构里包含两个哈希表。在重哈希期间，数据从第一个哈希表向第二个哈希表迁移。

dict 的 C 代码定义如下（出自 Redis 源码 dict.h）：

typedef struct dictEntry {
 void *key;
 union {
 void *val;
 uint64_t u64;
 int64_t s64;
 double d;
 } v;
 struct dictEntry *next;
} dictEntry;
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;
/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
 dictEntry **table;
 unsigned long size;
 unsigned long sizemask;
 unsigned long used;
} dictht;
typedef struct dict {
 dictType *type;
 void *privdata;
 dictht ht[2];
 long rehashidx; /* rehashing not in progress if rehashidx == -1 */
 int iterators; /* number of iterators currently running */
} dict;

为了能更清楚地展示 dict 的数据结构定义，我们用一张结构图来表示它。如下。

结合上面的代码和结构图，可以很清楚地看出 dict 的结构。一个 dict 由如下若干项组成：

一个指向 dictType 结构的指针（type）。它通过自定义的方式使得 dict 的 key 和 value 能够存储任何类型的数据。

一个私有数据指针（privdata）。由调用者在创建 dict 的时候传进来。

两个哈希表（ht[2]）。只有在重哈希的过程中，ht[0]和 ht[1]才都有效。而在平常情况下，只有 ht[0]有效，ht[1]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。

当前重哈希索引（rehashidx）。如果 rehashidx = -1，表示当前没有在重哈希过程中；否则，表示当前正在进行重哈希，且它的值记录了当前重哈希进行到哪一步了。

当前正在进行遍历的 iterator 的个数。这不是我们现在讨论的重点，暂时忽略。

dictType 结构包含若干函数指针，用于 dict 的调用者对涉及 key 和 value 的各种操作进行自定义。这些操作包含：

hashFunction，对 key 进行哈希值计算的哈希算法。

keyDup 和 valDup，分别定义 key 和 value 的拷贝函数，用于在需要的时候对 key 和 value 进行深拷贝，而不仅仅是传递对象指针。

keyCompare，定义两个 key 的比较操作，在根据 key 进行查找时会用到。

keyDestructor 和 valDestructor，分别定义对 key 和 value 的析构函数。

私有数据指针（privdata）就是在 dictType 的某些操作被调用时会传回给调用者。

需要详细察看的是 dictht 结构。它定义一个哈希表的结构，由如下若干项组成：

一个 dictEntry 指针数组（table）。key 的哈希值最终映射到这个数组的某个位置上（对应一个 bucket）。如果多个 key 映射到同一个位置，就发生了冲突，那么就拉出一个 dictEntry 链表。

size：标识 dictEntry 指针数组的长度。它总是 2 的指数。

sizemask：用于将哈希值映射到 table 的位置索引。它的值等于 (size-1)，比如 7, 15, 31, 63，等等，也就是用二进制表示的各个 bit 全 1 的数字。每个 key 先经过 hashFunction 计算得到一个哈希值，然后计算(哈希值 sizemask) 得到在 table 上的位置。相当于计算取余(哈希值 % size)。

used：记录 dict 中现有的数据个数。它与 size 的比值就是装载因子（load factor）。这个比值越大，哈希值冲突概率越高。

dictEntry 结构中包含 k, v 和指向链表下一项的 next 指针。k 是 void 指针，这意味着它可以指向任何类型。v 是个 union，当它的值是 uint64_t、int64_t 或 double 类型时，就不再需要额外的存储，这有利于减少内存碎片。当然，v 也可以是 void 指针，以便能存储任何类型的数据。

dict 的创建（dictCreate）

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 的数据结构分配空间并为各个变量赋初值。其中两个哈希表 ht[0]和 ht[1]起始都没有分配空间，table 指针都赋为 NULL。这意味着要等第一个数据插入时才会真正分配空间。

dict 的查找（dictFind）

#define dictIsRehashing(d) ((d)- rehashidx != -1)
dictEntry *dictFind(dict *d, const void *key)
 dictEntry *he;
 unsigned int h, idx, table;
 if (d- ht[0].used + d- ht[1].used == 0) return NULL; /* dict is empty */
 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 || dictCompareKeys(d, key, he- key))
 return he;
 he = he- next;
 }
 if (!dictIsRehashing(d)) return NULL;
 }
 return NULL;
}

上述 dictFind 的源码，根据 dict 当前是否正在重哈希，依次做了这么几件事：

如果当前正在进行重哈希，那么将重哈希过程向前推进一步（即调用_dictRehashStep）。实际上，除了查找，插入和删除也都会触发这一动作。这就将重哈希过程分散到各个查找、插入和删除操作中去了，而不是集中在某一个操作中一次性做完。

计算 key 的哈希值（调用 dictHashKey，里面的实现会调用前面提到的 hashFunction）。

先在第一个哈希表 ht[0]上进行查找。在 table 数组上定位到哈希值对应的位置（如前所述，通过哈希值与 sizemask 进行按位与），然后在对应的 dictEntry 链表上进行查找。查找的时候需要对 key 进行比较，这时候调用 dictCompareKeys，它里面的实现会调用到前面提到的 keyCompare。如果找到就返回该项。否则，进行下一步。

判断当前是否在重哈希，如果没有，那么在 ht[0]上的查找结果就是最终结果（没找到，返回 NULL）。否则，在 ht[1]上进行查找（过程与上一步相同）。

下面我们有必要看一下增量式重哈希的_dictRehashStep 的实现。

static void _dictRehashStep(dict *d) { if (d- iterators == 0) dictRehash(d,1);
int dictRehash(dict *d, int n) {
 int empty_visits = n*10; /* Max number of empty buckets to visit. */
 if (!dictIsRehashing(d)) return 0;
 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++;
 if (--empty_visits == 0) return 1;
 }
 de = d- ht[0].table[d- rehashidx];
 /* Move all the keys in this bucket from the old to the new hash HT */
 while(de) {
 unsigned int 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;
 d- ht[0].used--;
 d- ht[1].used++;
 de = nextde;
 }
 d- ht[0].table[d- rehashidx] = NULL;
 d- rehashidx++;
 }
 /* Check if we already rehashed the whole table... */
 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;
 }
 /* More to rehash... */
 return 1;
}

dictRehash 每次将重哈希至少向前推进 n 步（除非不到 n 步整个重哈希就结束了），每一步都将 ht[0]上某一个 bucket（即一个 dictEntry 链表）上的每一个 dictEntry 移动到 ht[1]上，它在 ht[1]上的新位置根据 ht[1]的 sizemask 进行重新计算。rehashidx 记录了当前尚未迁移（有待迁移）的 ht[0]的 bucket 位置。

如果 dictRehash 被调用的时候，rehashidx 指向的 bucket 里一个 dictEntry 也没有，那么它就没有可迁移的数据。这时它尝试在 ht[0].table 数组中不断向后遍历，直到找到下一个存有数据的 bucket 位置。如果一直找不到，则最多走 n *10 步，本次重哈希暂告结束。

最后，如果 ht[0]上的数据都迁移到 ht[1]上了（即 d - ht[0].used == 0），那么整个重哈希结束，ht[0]变成 ht[1]的内容，而 ht[1]重置为空。

根据以上对于重哈希过程的分析，我们容易看出，本文前面的 dict 结构图中所展示的正是 rehashidx= 2 时的情况，前面两个 bucket（ht[0].table[0]和 ht[0].table[1]）都已经迁移到 ht[1]上去了。

dict 的插入（dictAdd 和 dictReplace）

dictAdd 插入新的一对 key 和 value，如果 key 已经存在，则插入失败。

dictReplace 也是插入一对 key 和 value，不过在 key 存在的时候，它会更新 value。

int dictAdd(dict *d, void *key, void *val)
 dictEntry *entry = dictAddRaw(d,key);
 if (!entry) return DICT_ERR;
 dictSetVal(d, entry, val);
 return DICT_OK;
dictEntry *dictAddRaw(dict *d, void *key)
 int index;
 dictEntry *entry;
 dictht *ht;
 if (dictIsRehashing(d)) _dictRehashStep(d);
 /* Get the index of the new element, or -1 if
 * the element already exists. */
 if ((index = _dictKeyIndex(d, key)) == -1)
 return NULL;
 /* Allocate the memory and store the new entry.
 * Insert the element in top, with the assumption that in a database
 * system it is more likely that recently added entries are accessed
 * more frequently. */
 ht = dictIsRehashing(d) ?  d- ht[1] :  d- ht[0];
 entry = zmalloc(sizeof(*entry));
 entry- next = ht- table[index];
 ht- table[index] = entry;
 ht- used++;
 /* Set the hash entry fields. */
 dictSetKey(d, entry, key);
 return entry;
static int _dictKeyIndex(dict *d, const void *key)
 unsigned int h, idx, table;
 dictEntry *he;
 /* Expand the hash table if needed */
 if (_dictExpandIfNeeded(d) == DICT_ERR)
 return -1;
 /* Compute the key hash value */
 h = dictHashKey(d, key);
 for (table = 0; table  = 1; table++) { idx = h   d- ht[table].sizemask;
 /* Search if this slot does not already contain the given key */
 he = d- ht[table].table[idx];
 while(he) { if (key==he- key || dictCompareKeys(d, key, he- key))
 return -1;
 he = he- next;
 }
 if (!dictIsRehashing(d)) break;
 }
 return idx;
}

以上是 dictAdd 的关键实现代码。我们主要需要注意以下几点：

它也会触发推进一步重哈希（_dictRehashStep）。

如果正在重哈希中，它会把数据插入到 ht[1]；否则插入到 ht[0]。

在对应的 bucket 中插入数据的时候，总是插入到 dictEntry 的头部。因为新数据接下来被访问的概率可能比较高，这样再次查找它时就比较次数较少。

_dictKeyIndex 在 dict 中寻找插入位置。如果不在重哈希过程中，它只查找 ht[0]；否则查找 ht[0]和 ht[1]。

_dictKeyIndex 可能触发 dict 内存扩展（_dictExpandIfNeeded，它将哈希表长度扩展为原来两倍，具体请参考 dict.c 中源码）。

dictReplace 在 dictAdd 基础上实现，如下：

int dictReplace(dict *d, void *key, void *val)
 dictEntry *entry, auxentry;
 /* Try to add the element. If the key
 * does not exists dictAdd will suceed. */
 if (dictAdd(d, key, val) == DICT_OK)
 return 1;
 /* It already exists, get the entry */
 entry = dictFind(d, key);
 /* 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 = *entry;
 dictSetVal(d, entry, val);
 dictFreeVal(d,  auxentry);
 return 0;
}

在 key 已经存在的情况下，dictReplace 会同时调用 dictAdd 和 dictFind，这其实相当于两次查找过程。这里 Redis 的代码不够优化。

dict 的删除（dictDelete）

dictDelete 的源码这里忽略，具体请参考 dict.c。需要稍加注意的是：

dictDelete 也会触发推进一步重哈希（_dictRehashStep）

如果当前不在重哈希过程中，它只在 ht[0]中查找要删除的 key；否则 ht[0]和 ht[1]它都要查找。

删除成功后会调用 key 和 value 的析构函数（keyDestructor 和 valDestructor）。

上述内容就是 Redis 中内部数据结构 dict 的作用是什么，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注丸趣 TV 行业资讯频道。