参考资料(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部分结束)