参考资料（http://www.redisbook.com）
参考了上面的的资料，但是，这份资料的作者阅读的redis版本和我阅读的版本不一样，对于他在书中提到的字典的功能，还没有验证。所以，只讨论字典的具体设计，它的应用场景可能要等到阅读完大部分代码才能知道。

文件依赖

dict.h dict.c zmalloc.h

字典实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 哈希表结点 */
typedef struct dictEntry {
    void *key;					/* 键 */
    void *val;					/* 值 */
    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;
/* 字典 */
typedef struct dict {
    dictEntry **table;			/* 哈希表 */
    dictType *type;				/* 字典的配套函数 */
    unsigned long size;			/* 哈希表的长度 */
    unsigned long sizemask;		/* 哈希表长度掩码，用于计算索引值 */
    unsigned long used;			/* 已经使用的长度 */
    void *privdata;				/* 私有数据 */
} dict;
/* 字典迭代器 */
typedef struct dictIterator {
    dict *ht;					/* 字典指针 */
    int index;					/* 索引值 */
    dictEntry *entry, *nextEntry; /* 当前结点、下一个结点的指针 */
} dictIterator;

字典的底层是使用哈希表实现的。
dictEntry是哈希表单个结点的实现。
dictType是与字典的配套函数。
dict就是字典的具体实现，由于哈希表使用的“链地址法”来处理冲突，具有相同哈希值的函数组成链表，所以table是一个指针的指针。sizemask是哈希表的长度掩码，计算出的哈希值与sizemask进行“位运算”–“与”，可以快速的计算出该结点在哈希表中的“索引”，当然也可以将哈希值和size进行模运算，但模运算相较于位运算，需要花费更多的开销。
dictIterator是字典的迭代器，用于实现对字典中哈希表的遍历。

结构示意图：

函数实现

用宏实现的函数

对于一些简单的函数，仍然采用宏实现，省去函数调用的开销。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define dictFreeEntryVal(ht, entry) \ /* 释放哈希表结点的值 */
    if ((ht)->type->valDestructor) \
        (ht)->type->valDestructor((ht)->privdata, (entry)->val)

#define dictSetHashVal(ht, entry, _val_) do { \ /* 设置哈希表结点的值 */
    if ((ht)->type->valDup) \
        entry->val = (ht)->type->valDup((ht)->privdata, _val_); \
    else \
        entry->val = (_val_); \
} while(0)

#define dictFreeEntryKey(ht, entry) \ /* 释放哈希表结点的键 */
    if ((ht)->type->keyDestructor) \
        (ht)->type->keyDestructor((ht)->privdata, (entry)->key)

#define dictSetHashKey(ht, entry, _key_) do { \ /* 设置哈希表结点的键 */
    if ((ht)->type->keyDup) \
        entry->key = (ht)->type->keyDup((ht)->privdata, _key_); \
    else \
        entry->key = (_key_); \
} while(0)

#define dictCompareHashKeys(ht, key1, key2) \ /* 比较哈希表结点的键 */
    (((ht)->type->keyCompare) ? \
        (ht)->type->keyCompare((ht)->privdata, key1, key2) : \
        (key1) == (key2))

#define dictHashKey(ht, key) (ht)->type->hashFunction(key) /* 调用哈希函数得到哈希值 */

#define dictGetEntryKey(he) ((he)->key) /* 得到哈希结点的键 */
#define dictGetEntryVal(he) ((he)->val) /* 得到哈希结点的值 */
#define dictSlots(ht) ((ht)->size)		/* 得到哈希表的总长度 */
#define dictSize(ht) ((ht)->used)		/* 得到哈希表已经使用的长度 */

其他函数的具体实现

1. “私有”函数

dict.c中有很多命令以下划线开头的函数，它们作为dict公共接口的内部接口。 使用static关键字，可以限定函数的作用域，使得这些函数只能让本程序中的其他函数访问，相当于c++中的私有成员。

_dictPanic

1
2
3
4
5
6
7
8
9
10
static void _dictPanic(const char *fmt, ...)
{
    va_list ap;

    va_start(ap, fmt);
    fprintf(stderr, "\nDICT LIBRARY PANIC: ");
    vfprintf(stderr, fmt, ap);
    fprintf(stderr, "\n\n");
    va_end(ap);
}

该函数用于向标准错误(stderr)中打印出错信息。

堆管理函数
1
2
3
4
5
6
7
8
9
10
11
tatic void *_dictAlloc(size_t size) /* 分配内存 */
{
    void *p = zmalloc(size);
    if (p == NULL)
        _dictPanic("Out of memory");
    return p;
}

static void _dictFree(void *ptr) { /* 释放内存 */
    zfree(ptr);
}

这两个函数是对zmalloc和zfree函数的封装。

有关字典操作的私有函数

(1) _dictReset 

1
2
3
4
5
6
7
8
9
10
/* 清空字典 */
/* Reset an hashtable already initialized with ht_init().
* NOTE: This function should only called by ht_destroy(). */
static void _dictReset(dict *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

该函数用于将字典“清零”。

(2) _dictInit 

1
2
3
4
5
6
7
8
9
10
/* 初始化字典中的哈希表 */
/* Initialize the hash table */
int _dictInit(dict *ht, dictType *type,
        void *privDataPtr)
{
    _dictReset(ht);				/* 先清空字典 */
    ht->type = type;
    ht->privdata = privDataPtr;
    return DICT_OK;
}

初始化字典中的哈希表，初始化之前先要将字典“清零”。

(3) _dictClear 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 销毁字典中的哈希表 */
/* Destroy an entire hash table */
int _dictClear(dict *ht)
{
    unsigned long i;
    /* 释放哈希表的每一个槽对应的链表中的每一个元素 */
    /* Free all the elements */
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;

        if ((he = ht->table[i]) == NULL) continue;
        while(he) {
            nextHe = he->next;
            dictFreeEntryKey(ht, he);
            dictFreeEntryVal(ht, he);
            _dictFree(he);
            ht->used--;
            he = nextHe;
        }
    } /* 释放整个哈希表 */
    /* Free the table and the allocated cache structure */
    _dictFree(ht->table);
    /* Re-initialize the table */
	_dictReset(ht);				/* 将字典清零 */
	return DICT_OK; /* never fails */
}

该函数用于销毁字典中的哈希表，先要释放哈希表中的每一个元素，然后调用_dictFree函数释放非配给table的内存，最后调用函数_dictReset将字典清零。

(4) _dictExpandIfNeeded 

1
2
3
4
5
6
7
8
9
10
11
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *ht)
{
    /* If the hash table is empty expand it to the intial size,
    * if the table is "full" dobule its size. */
    if (ht->size == 0)
        return dictExpand(ht, DICT_HT_INITIAL_SIZE);
    if (ht->used == ht->size)	/* 哈希表已满，将其容量扩大为原来的二倍 */
        return dictExpand(ht, ht->size*2);
    return DICT_OK;
}

在哈希表的容量不足的时候扩展哈希表，哈希表大小为0时，容量扩展为“初始长度”为4；若非零，则容量扩展为原来的2倍。
(5) _dictNextPower 

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 哈希表的容量是2的指数次方 */
/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;
    /* LONG_MAX定义在limit.h中，指定long类型的最大值 */
    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {                    /* 但是size是unsigned long */
        if (i >= size)            /* 所以是否应该与ULONG_MAX比较 */
            return i;
        i *= 2;
    }
}

哈希表的容量大小是2的指数次方，该函数用于计算出大于size的2的指数次方。

就像在注释中提到的，size的类型为unsigned long，所以size的上限是否应该是ULONG_MAX，而非LONG_MAX。

(6) _dictKeyIndex 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 给定键，若键在哈希表中不存在，返回一个空槽的索引，若已存在，出错 */
/* Returns the index of a free slot that can be populated with
* an hash entry for the given 'key'.
* If the key already exists, -1 is returned. */
static int _dictKeyIndex(dict *ht, const void *key)
{
    unsigned int h;
    dictEntry *he;

    /* Expand the hashtable if needed */
    if (_dictExpandIfNeeded(ht) == DICT_ERR)
        return 1;
    /* Compute the key hash value */
    h = dictHashKey(ht, key) & ht->sizemask;
    /* Search if this slot does not already contain the given key */
    he = ht->table[h];
    while(he) {
        if (dictCompareHashKeys(ht, key, he->key))
            return -1;
        he = he->next;
    }
    return h;
}

给定一个键，查找这个键在哈希表是否已经存在，如果已经存在了，返回-1；如果这个键不存在，返回这个键在哈希表中对应的索引。

StringCopy对应的哈希表函数原型

(1) _dictStringCopyHTHashFunction 

1
2
3
4
5
/* 调用哈希函数生成key对应的哈希值 */
static unsigned int _dictStringCopyHTHashFunction(const void *key)
{
    return dictGenHashFunction(key, strlen(key));
}

StringCopy使用的哈希函数。

(2) _dictStringCopyHTKeyDup 

1
2
3
4
5
6
7
8
9
10
11
/* 键复制函数 */
static void *_dictStringCopyHTKeyDup(void *privdata, const void *key)
{
    int len = strlen(key);
    char *copy = _dictAlloc(len+1);
    DICT_NOTUSED(privdata);

    memcpy(copy, key, len);
    copy[len] = '\0';
    return copy;
}

(3) _dictStringKeyValCopyHTValDup 

1
2
3
4
5
6
7
8
9
10
11
/* 值赋值函数 */
static void *_dictStringKeyValCopyHTValDup(void *privdata, const void *val)
{
    int len = strlen(val);
    char *copy = _dictAlloc(len+1);
    DICT_NOTUSED(privdata);

    memcpy(copy, val, len);
    copy[len] = '\0';
    return copy;
}

(4) _dictStringCopyHTKeyCompare 

1
2
3
4
5
6
7
8
/* 键比较函数 */
static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
        const void *key2)
{
    DICT_NOTUSED(privdata);

    return strcmp(key1, key2) == 0;
}

(5) _dictStringCopyHTKeyDestructor 

1
2
3
4
5
6
7
/* 键析构函数 */
static void _dictStringCopyHTKeyDestructor(void *privdata, void *key)
{
    DICT_NOTUSED(privdata);

    _dictFree((void*)key); /* ATTENTION: const cast */
}

(6) _dictStringKeyValCopyHTValDestructor 

1
2
3
4
5
6
7
/* 值析构函数 */
static void _dictStringKeyValCopyHTValDestructor(void *privdata, void *val)
{
    DICT_NOTUSED(privdata);

    _dictFree((void*)val); /* ATTENTION: const cast */
}

2. 哈希函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Thomas Wang's 32 bit Mix Function */
unsigned int dictIntHashFunction(unsigned int key)
{
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}

/* Identity hash function for integer keys */
unsigned int dictIdentityHashFunction(unsigned int key)
{
    return key;
}

/* Generic hash function (a popular one from Bernstein).
* I tested a few and this was the best. */
unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = 5381;

    while (len--)
        hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
    return hash;
}

这三个是字典使用的哈希函数，讨论这些函数性能是否优良，超出了我的能力范围。

dict对外提供的接口
1. dictCreate
1
2
3
4
5
6
7
8
9
10
/* 创建字典，初始化除table之外的其他元素，此时哈希表是空的 */
/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *ht = _dictAlloc(sizeof(*ht));

    _dictInit(ht,type,privDataPtr);
    return ht;
}

创建字典，调用_dictAlloc分配内存， 调用_dictInit初始化字典。

2. dictResize
1
2
3
4
5
6
7
8
9
10
/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USER/BUCKETS ration near to <= 1 */
int dictResize(dict *ht)        /* 将字典中哈希表的长度调到最小 */
{
    int minimal = ht->used;

    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(ht, minimal);
}

将哈希表的调节到最小–如果为空，调节为4；如果非空，调节到used大写。

3. dictExpand
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USER/BUCKETS ration near to <= 1 */
int dictResize(dict *ht)        /* 将字典中哈希表的长度调到最小 */
{
    int minimal = ht->used;

    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(ht, minimal);
}

/* Expand or create the hashtable */
int dictExpand(dict *ht, unsigned long size)
{                                /* 创建一个新的哈希表 */
    dict n; /* the new hashtable */
    unsigned long realsize = _dictNextPower(size), i;
    /* 如果给定的size小于原表中已经使用的大小，则出错 */
    /* the size is invalid if it is smaller than the number of
    * elements already inside the hashtable */
    if (ht->used > size)
        return DICT_ERR;

    _dictInit(&n, ht->type, ht->privdata);
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = _dictAlloc(realsize*sizeof(dictEntry*));
    /* 将哈希表中的所有指针初始化为NULL */
    /* Initialize all the pointers to NULL */
    memset(n.table, 0, realsize*sizeof(dictEntry*));

    /* Copy all the elements from the old to the new table:
	* note that if the old hash table is empty ht->size is zero,
	* so dictExpand just creates an hash table. */
	n.used = ht->used;
	for (i = 0; i < ht->size && ht->used > 0; i++) {
	    dictEntry *he, *nextHe;

        if (ht->table[i] == NULL) continue;

        /* For each hash entry on this slot... */
        he = ht->table[i];
        while(he) {
            unsigned int h;

            nextHe = he->next;
            /* Get the new element index */
            h = dictHashKey(ht, he->key) & n.sizemask;
            he->next = n.table[h];
            n.table[h] = he;
            ht->used--;
            /* Pass to the next element */
            he = nextHe;
        } /* 190行的代码相当于 "h = dictHashKey(ht, he->key) % n.size" */
    }      /* 使用位运算可以比取模运算节省很多时间 */
    assert(ht->used == 0);
    _dictFree(ht->table);        /* 释放字典ht中的哈希表 */

    /* Remap the new hashtable in the old */
    *ht = n;                    /* 将字典n中存储的内容赋给ht指向的字典 */
    return DICT_OK;
}

该函数用于扩展或创建一个哈希表，它先创建一个临时的字典，将ht指向的字典的type,size,sizemask,used,privdata赋给临时字典n,然后对对ht->table中存储的每个元素重新计算哈希值，存储在n.table中，最后将n的内容赋给ht指向的字典。

4. dictAdd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Add an element to the target hash table */
int dictAdd(dict *ht, void *key, void *val)
{
    int index;
    dictEntry *entry;

    /* Get the index of the new element, or -1 if
    * the element already exists. */
    if ((index = _dictKeyIndex(ht, key)) == -1) /* 获取key对应的索引 */
        return DICT_ERR;

    /* Allocates the memory and stores key */
    entry = _dictAlloc(sizeof(*entry)); /* 为键值分配内存 */
    entry->next = ht->table[index];        /* 将结点插入到对应的索引链表中 */
    ht->table[index] = entry;

    /* Set the hash entry fields. */
    dictSetHashKey(ht, entry, key); /* 设置结点的各个域 */
    dictSetHashVal(ht, entry, val);
    ht->used++;
    return DICT_OK;
}

向目标字典中添加元素。

5. dictReplace
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 将键值插入到哈希表中，不管键对应的结点在哈希表中是否已经存在 */
/* Add an element, discarding the old if the key already exists */
int dictReplace(dict *ht, void *key, void *val)
{
    dictEntry *entry;

    /* Try to add the element. If the key
    * does not exists dictAdd will suceed. */
    if (dictAdd(ht, key, val) == DICT_OK)
        return DICT_OK;
    /* It already exists, get the entry */
    entry = dictFind(ht, key);
    /* Free the old value and set the new one */
    dictFreeEntryVal(ht, entry);
    dictSetHashVal(ht, entry, val);
    return DICT_OK;
}

如果“键值对”在哈希表中已经存在， 则更新“键”对应的“值”；如果不存在，将该“键值对”插入到哈希表中。

6. dictGenericDelete
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 查找并删除一个元素 */
/* Search and remove an element */
static int dictGenericDelete(dict *ht, const void *key, int nofree)
{
    unsigned int h;
    dictEntry *he, *prevHe;

    if (ht->size == 0)
        return DICT_ERR;
    h = dictHashKey(ht, key) & ht->sizemask;
    he = ht->table[h];

    prevHe = NULL;
    while(he) {
        if (dictCompareHashKeys(ht, key, he->key)) {
            /* Unlink the element from the list */
            if (prevHe)            /* 要删除的结点不是头结点 */
                prevHe->next = he->next;
            else                /* 要删除的是头结点 */
                ht->table[h] = he->next;
            if (!nofree) {        /* 调用者指定参数释放key和value */
                dictFreeEntryKey(ht, he);
                dictFreeEntryVal(ht, he);
            }
            _dictFree(he);        /* 释放结点 */
            ht->used--;
            return DICT_OK;
        }
        prevHe = he;
        he = he->next;
    }
    return DICT_ERR; /* not found */
}

从字典的哈希表中删除一个结点，nofree指定了是否释放该结点对应的“键值对”。

7. dictDelete
1
2
3
4
/* 释放键对应的结点的key和value */
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}

调用dictGenericDelete函数，删除对应的结点，并释放结点对应的“键值对”。

8. dictDeleteNoFree
1
2
3
4
/* 不释放键对应的结点的key和value */
int dictDeleteNoFree(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

只删除结点，不删除对应的“键值对”。

9. dictRelease
1
2
3
4
5
6
7
/* 先将字典清零，再释放掉整个字典 */
/* Clear & Release the hash table */
void dictRelease(dict *ht)
{
    _dictClear(ht);
    _dictFree(ht);
}

先将字典清零，再释放掉整个字典。

10. dictFind
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 查找给定键对应的结点 */
dictEntry *dictFind(dict *ht, const void *key)
{
    dictEntry *he;
    unsigned int h;

    if (ht->size == 0) return NULL;
    h = dictHashKey(ht, key) & ht->sizemask;
    he = ht->table[h];w
    while(he) {
        if (dictCompareHashKeys(ht, key, he->key))
            return he;
        he = he->next;
    }
    return NULL;
}

查找某个结点，未找到，返回NULL。

11. dictGetIterator
1
2
3
4
5
6
7
8
9
10
11
/* 获取一个给定字典的迭代器，并初始化 */
dictIterator *dictGetIterator(dict *ht)
{
    dictIterator *iter = _dictAlloc(sizeof(*iter));
    /* 该迭代器返回当前索引的下一个非空索引对应的链表的首结点 */
    iter->ht = ht;
    iter->index = -1;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

获取迭代器，并初始化。

12. dictNext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
        if (iter->entry == NULL) {
            iter->index++;
            if (iter->index >=
                (signed)iter->ht->size) break;
            iter->entry = iter->ht->table[iter->index];
        } else {
            iter->entry = iter->nextEntry;
        }
        if (iter->entry) {
            /* We need to save the 'next' here, the iterator user
            * may delete the entry we are returning. */
            iter->nextEntry = iter->entry->next;
            return iter->entry;    /* 我们要把下一个结点保存起来 */
        }                        /* 调用者有可能会删除我们返回的结点*/
    }
    return NULL;
}

获取当前迭代器指向的下一个结点。

13. dictReleaseIterator
1
2
3
4
5
/* 销毁迭代器 */
void dictReleaseIterator(dictIterator *iter)
{
    _dictFree(iter);
}

销毁迭代器

14. dictGetRandomKey
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 返回哈希表中的一个随机结点，这对实现随机化算法很有用 */
/* Return a random entry from the hash table. Useful to
* implement randomized algorithms */
dictEntry *dictGetRandomKey(dict *ht)
{
    dictEntry *he;
    unsigned int h;
    int listlen, listele;
    /* 字典的哈希表未存储结点 */
    if (ht->used == 0) return NULL;
    do {
        h = random() & ht->sizemask;
        he = ht->table[h];
    } while(he == NULL);

    /* Now we found a non empty bucket, but it is a linked
    * list and we need to get a random element from the list.
    * The only sane way to do so is to count the element and
    * select a random index. */
    listlen = 0;
    while(he) {
        he = he->next;
        listlen++;
    }
    listele = random() % listlen;
    he = ht->table[h];
    while(listele--) he = he->next;
    return he;
}

返回哈希表中的一个随机结点。

15. dictPrintStats
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define DICT_STATS_VECTLEN 50
void dictPrintStats(dict *ht) {
    unsigned long i, slots = 0, chainlen, maxchainlen = 0;
    unsigned long totchainlen = 0; /* 整个哈希表中一共又多少个结点 */
    unsigned long clvector[DICT_STATS_VECTLEN];
    /* 字典为空 */
    if (ht->used == 0) {
        printf("No stats available for empty dictionaries\n");
        return;
    }

    for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;
    for (i = 0; i < ht->size; i++) {
        dictEntry *he;

        if (ht->table[i] == NULL) {
            clvector[0]++;        
            continue;
        }
        slots++;
        /* For each hash entry on this slot... */
        chainlen = 0;
        he = ht->table[i];
        while(he) {                /* 哈希表的该位置对应的链表又多少个结点 */
            chainlen++;
            he = he->next;
        }
        clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
        if (chainlen > maxchainlen) maxchainlen = chainlen; /* 更新最大的链长度 */
        totchainlen += chainlen;
    }
    printf("Hash table stats:\n");
    printf(" table size: %ld\n", ht->size);
    printf(" number of elements: %ld\n", ht->used);
    printf(" different slots: %ld\n", slots);
    printf(" max chain length: %ld\n", maxchainlen);
    printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
    printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
    printf(" Chain length distribution:\n");
    for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {
        if (clvector[i] == 0) continue; /* 链长度分布，即长度为len的槽(slot)的个数占整个哈希表长度size的百分比 */
        printf("   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
    }
}

打印字典的相关信息。

dict配套函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 当key为字符串并且要复制key时封装的函数 */
dictType dictTypeHeapStringCopyKey = {
    _dictStringCopyHTHashFunction,        /* hash function */
    _dictStringCopyHTKeyDup,              /* key dup */
    NULL,                               /* val dup */
    _dictStringCopyHTKeyCompare,          /* key compare */
    _dictStringCopyHTKeyDestructor,       /* key destructor */
    NULL                                /* val destructor */
};
/* 当key为字符串但不许要复制key时封装的函数，用于解释器的共享字符串 */
/* This is like StringCopy but does not auto-duplicate the key.
* It's used for intepreter's shared strings. */
dictType dictTypeHeapStrings = {
    _dictStringCopyHTHashFunction,        /* hash function */
    NULL,                               /* key dup */
    NULL,                               /* val dup */
    _dictStringCopyHTKeyCompare,          /* key compare */
    _dictStringCopyHTKeyDestructor,       /* key destructor */
    NULL                                /* val destructor */
};
/* 需要同时复制key和value时封装的函数 */
/* This is like StringCopy but also automatically handle dynamic
* allocated C strings as values. */
dictType dictTypeHeapStringCopyKeyValue = {
    _dictStringCopyHTHashFunction,        /* hash function */
    _dictStringCopyHTKeyDup,              /* key dup */
    _dictStringKeyValCopyHTValDup,        /* val dup */
    _dictStringCopyHTKeyCompare,          /* key compare */
    _dictStringCopyHTKeyDestructor,       /* key destructor */
    _dictStringKeyValCopyHTValDestructor, /* val destructor */
};

dict中的type成员可以指向三个结构体中的一个。

(dict部分结束)