Redis源代码分析之二：散列表——Dict（上）

winston

先介绍Redis散列表实现的几个重要数据结构：

字典项DictEntry：typedef struct dictEntry {

2.     void *key;
3.     void *val;
4.     struct dictEntry *next;
5. } dictEntry;

复制代码

字典类型DictType：typedef struct dictType {

2.     unsigned int (*hashFunction)(const void *key);
3.     void *(*keyDup)(void *privdata, const void *key);
4.     void *(*valDup)(void *privdata, const void *obj);
5.     int (*keyCompare)(void *privdata, const void *key1, const void *key2);
6.     void (*keyDestructor)(void *privdata, void *key);
7.     void (*valDestructor)(void *privdata, void *obj);
8. } dictType;

复制代码

哈希表结构dictht：/* This is our hash table structure. Every dictionary has two of this as we

2. * implement incremental rehashing, for the old to the new table. */
3. typedef struct dictht {
4.     dictEntry **table;
5.     unsigned long size;
6.     unsigned long sizemask;
7.     unsigned long used;
8. } dictht;

复制代码

字典结构dict：typedef struct dict {

3.     dictType *type;
4.     void *privdata;
5.     dictht ht[2];
6.     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
7.     int iterators; /* number of iterators currently running */
8. } dict;

复制代码

字典迭代器dictIterator：/* If safe is set to 1 this is a safe iteartor, that means, you can call

2. * dictAdd, dictFind, and other functions against the dictionary even while
3. * iterating. Otherwise it is a non safe iterator, and only dictNext()
4. * should be called while iterating. */
5. typedef struct dictIterator {
6.     dict *d;
7.     int table, index, safe;
8.     dictEntry *entry, *nextEntry;
9. } dictIterator;

复制代码

然后介绍一下字典接口定义：dict *dictCreate(dictType *type, void *privDataPtr);

2. int dictExpand(dict *d, unsigned long size);
3. int dictAdd(dict *d, void *key, void *val);
4. int dictReplace(dict *d, void *key, void *val);
5. int dictDelete(dict *d, const void *key);
6. int dictDeleteNoFree(dict *d, const void *key);
7. void dictRelease(dict *d);
8. dictEntry * dictFind(dict *d, const void *key);
9. void *dictFetchValue(dict *d, const void *key);
10. int dictResize(dict *d);
11. dictIterator *dictGetIterator(dict *d);
12. dictIterator *dictGetSafeIterator(dict *d);
13. dictEntry *dictNext(dictIterator *iter);
14. void dictReleaseIterator(dictIterator *iter);
15. dictEntry *dictGetRandomKey(dict *d);
16. void dictPrintStats(dict *d);
17. unsigned int dictGenHashFunction(const unsigned char *buf, int len);
18. unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);
19. void dictEmpty(dict *d);
20. void dictEnableResize(void);
21. void dictDisableResize(void);
22. int dictRehash(dict *d, int n);
23. int dictRehashMilliseconds(dict *d, int ms);

复制代码

下面分析扩张或者创建哈希表的重要函数dictExpand：

3. /* Expand or create the hashtable */
4. int dictExpand(dict *d, unsigned long size)
5. {
6.     dictht n; /* the new hashtable */
7.     unsigned long realsize = _dictNextPower(size);
9.     /* the size is invalid if it is smaller than the number of
10.      * elements already inside the hashtable */
11.     if (dictIsRehashing(d) || d->ht[0].used > size)
12.         return DICT_ERR;
14.     /* Allocate the new hashtable and initialize all pointers to NULL */
15.     n.size = realsize;
16.     n.sizemask = realsize-1;
17.     n.table = zcalloc(realsize*sizeof(dictEntry*));
18.     n.used = 0;
20.     /* Is this the first initialization? If so it's not really a rehashing
21.      * we just set the first hash table so that it can accept keys. */
22.     if (d->ht[0].table == NULL) {
23.         d->ht[0] = n;
24.         return DICT_OK;
25.     }
27.     /* Prepare a second hash table for incremental rehashing */
28.     d->ht[1] = n;
29.     d->rehashidx = 0;
30.     return DICT_OK;
31. }

复制代码

对于传入的参数：新哈希表的大小size，首先调用内部函数_dictNextPower(size)取得大于size的最小2次幂整数，作为哈希表大小。掩码sizemask为size二进制表示长度减一的全1表示。调用内存管理函数zcalloc分配新哈希表的内存。
接下来，函数判断这是否是哈希表的首次初始化，这通过判断字典的哈希表数组ht的首个元素的dictEntry是否为空实现，如果为空，说明是首次初始化，则将该哈希表的size设为n，直接返回DICT_OK；否则，说明这是一次rehash，那么函数将准备第二个哈希表d->ht[1]，并将d的rehashidx设为0，准备进行后续的增量哈希，然后返回DICT_OK。
下面分析再哈希的实现dictRehash函数：/* Performs N steps of incremental rehashing. Returns 1 if there are still

1. * keys to move from the old to the new hash table, otherwise 0 is returned.
2. * Note that a rehashing step consists in moving a bucket (that may have more
3. * thank one key as we use chaining) from the old to the new hash table. */
4. int dictRehash(dict *d, int n) {
5.     if (!dictIsRehashing(d)) return 0;
7.     while(n--) {
8.         dictEntry *de, *nextde;
10.         /* Check if we already rehashed the whole table... */
11.         if (d->ht[0].used == 0) {
12.             zfree(d->ht[0].table);
13.             d->ht[0] = d->ht[1];
14.             _dictReset(&d->ht[1]);
15.             d->rehashidx = -1;
16.             return 0;
17.         }
19.         /* Note that rehashidx can't overflow as we are sure there are more
20.          * elements because ht[0].used != 0 */
21.         while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
22.         de = d->ht[0].table[d->rehashidx];
23.         /* Move all the keys in this bucket from the old to the new hash HT */
24.         while(de) {
25.             unsigned int h;
27.             nextde = de->next;
28.             /* Get the index in the new hash table */
29.             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
30.             de->next = d->ht[1].table[h];
31.             d->ht[1].table[h] = de;
32.             d->ht[0].used--;
33.             d->ht[1].used++;
34.             de = nextde;
35.         }
36.         d->ht[0].table[d->rehashidx] = NULL;
37.         d->rehashidx++;
38.     }
39.     return 1;
40. }

复制代码

首先判断这是否是一次合法的rehash调用，通过判断(ht)->rehashidx!=-1实现。
然后，进行n步rehash。其中的每一步都重复如下步骤：
(1) 检查我们是否已经rehash了整个哈希表（此时d->ht[0].used为0），如果是，析构旧的哈希表，将d->rehashidx置为-1。
(2)  遍历哈希表d->ht[0]，直到找到非空的字典项de，然后此后通过de->next继续遍历。在此之前，通过位操作dictHashKey(d, de->key) & d->ht[1].sizemask获得在新哈希表d->ht[1]中的索引h，并将该字典项复制到新哈希表d->ht[1]，同时更新两个哈希表的d->ht.used计数。然后将最初de对应的rehashidx对应的字典项标记为NULL，将->rehashidx加1，然后重复(1)层的循环。




作者：Aegeaner 发表于2012-2-1 20:16:48 原文链接