redis0.1源码解析之字典---theanarkh

字典也叫哈希表。看一下redis中的实现。下面是数据结构关系图。

redis中，哈希表的设计思想是，申请一个指针数组，然后每个元素指向一个链表用来存储数据（即链地址法）。

1 创建一个字典// 申请一个表示字典的数据结构 dict *dictCreate(dictType *type, void *privDataPtr) { dict *ht = _dictAlloc(sizeof(*ht)); _dictInit(ht,type,privDataPtr); return ht; } // 初始化字典数据结构 int _dictInit(dict *ht, dictType *type, void *privDataPtr) { _dictReset(ht); ht->type = type; ht->privdata = privDataPtr; return DICT_OK; } // 扩容 int dictResize(dict *ht) { int minimal = ht->used; if (minimal < DICT_HT_INITIAL_SIZE) minimal = DICT_HT_INITIAL_SIZE; return dictExpand(ht, minimal); }

首先调用申请一个dict结构体用来表示一个字典。然后初始化他的相关字段，最后调用dictExpand开辟保存数据的内存。

int dictExpand(dict *ht, unsigned long size) { dict n; // size是数组元素的个数，需要是2的倍数 unsigned long realsize = _dictNextPower(size), i; _dictInit(&n, ht->type, ht->privdata); // 哈希表数组的长度 n.size = realsize; // 索引掩码，用于计算索引 n.sizemask = realsize-1; // 用作哈希表的指针数组 n.table = _dictAlloc(realsize*sizeof(dictEntry*)); // 初始化内存为0 memset(n.table, 0, realsize*sizeof(dictEntry*)); // 之前字典已经使用的项数，复制过来，used是字典里节点个数 n.used = ht->used; for (i = 0; i < ht->size && ht->used > 0; i++) { dictEntry *he, *nextHe; // 空项，不需要复制 if (ht->table[i] == NULL) continue; he = ht->table[i]; while(he) { unsigned int h; // 保存下一个节点的地址，table的每一个项都是一个链表 nextHe = he->next; /* Get the new element index */ // 重新计算he的索引 h = dictHashKey(ht, he->key) & n.sizemask; // 插入索引为h的字典项中，头插法 he->next = n.table[h]; n.table[h] = he; // 使用数减一 ht->used--; he = nextHe; } } assert(ht->used == 0); // 释放旧的内存 _dictFree(ht->table); // 覆盖之前的信息 *ht = n; return DICT_OK; }

这样就形成了一个和文章开始那个图一样的结构。

2 往字典加入一个元素int dictAdd(dict *ht, void *key, void *val) { int index; dictEntry *entry; // 计算key是否已经存在，不存在则返回key对应的索引 if ((index = _dictKeyIndex(ht, key)) == -1) return DICT_ERR; // 申请一个字典项 entry = _dictAlloc(sizeof(*entry)); // 头插法插入第index项对应的链表中 entry->next = ht->table[index]; ht->table[index] = entry; // 设置键值 dictSetHashKey(ht, entry, key); dictSetHashVal(ht, entry, val); // 节点数加一 ht->used++; return DICT_OK; }

1 首先判断key是否已经存在，存在的话就无法添加。 2 根据key和哈希函数，计算对应的索引。 3 头插法插入对应索引的链表。

3 修改某个key对应的值int dictReplace(dict *ht, void *key, void *val) { dictEntry *entry; // 尝试新增，成功说明之前还没有这个key，否则说明存在，下面再替换 if (dictAdd(ht, key, val) == DICT_OK) return DICT_OK; // 找到key对应的索引 entry = dictFind(ht, key); // 释放当前的value dictFreeEntryVal(ht, entry); // 重新设置新值 dictSetHashVal(ht, entry, val); return DICT_OK; }4 删除一个元素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) { // 比较key，找到返回true if (dictCompareHashKeys(ht, key, he->key)) { /* Unlink the element from the list */ // 上一个不匹配节点的next指针指向待删除节点的下一个节点 if (prevHe) prevHe->next = he->next; else // prevHe为空，说明待删除的节点是链表的第一个节点，则更新头指针指向待删除节点的下一个 ht->table[h] = he->next; // if (!nofree) { dictFreeEntryKey(ht, he); dictFreeEntryVal(ht, he); } // 删除这个节点 _dictFree(he); // 已使用个数减一 ht->used--; return DICT_OK; } // 保存上一个不匹配的 prevHe = he; he = he->next; } return DICT_ERR; /* not found */ }

首先根据key找到索引的对应的链表，然后遍历链表找到key一样的节点，最后就是从链表中删除一个节点。 新增和删除等操作都涉及到查找元素，我们看看怎么查找。

5 查找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]; while(he) { // 自定义的比较函数钩子 if (dictCompareHashKeys(ht, key, he->key)) return he; he = he->next; } return NULL; }

我们可以看一下某个钩子的实现。

// 哈希函数 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; } // 比较函数 static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1, const void *key2) { return strcmp(key1, key2) == 0; }

总来的流程就是根据key产生一个索引，然后根据索引到哈希表中取得对应的一个链表，然后操作这个链表（新增，查找，删除）。

6 销毁字典// 销毁整个字典 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 */ }

该函数只是释放字典里存储数据的内存，但是没有释放字典本身。下面函数可以释放字典本身的内存。

// 释放字典里的数据和字典本身 void dictRelease(dict *ht) { _dictClear(ht); _dictFree(ht); }

7 迭代字典 redis中实现了各种迭代器对某种数据结构进行迭代，比如字典。

// 申请字典迭代器 dictIterator *dictGetIterator(dict *ht) { dictIterator *iter = _dictAlloc(sizeof(*iter)); iter->ht = ht; iter->index = -1; iter->entry = NULL; iter->nextEntry = NULL; return iter; } // 迭代字典的元素，每次调用返回一个节点 dictEntry *dictNext(dictIterator *iter) { while (1) { // 初始化时entry为NULL if (iter->entry == NULL) { iter->index++; // 到底了才break，而不是entry为空 if (iter->index >= (signed)iter->ht->size) break; // 返回索引为0对应的链表 iter->entry = iter->ht->table[iter->index]; } else { iter->entry = iter->nextEntry; } // 还有节点，则同时记录下一个节，返回entry节点 if (iter->entry) { iter->nextEntry = iter->entry->next; return iter->entry; } } return NULL; }

基本的逻辑就是，按照哈希表数组的索引，从小到大，每一个索引，先去遍历他对应的链表，遍历完后，继续下一个索引，直到最后一个索引结束。

总结，redis的字典里还有其他的一些方法，没有一一列举。有兴趣可以看https://github.com/theanarkh/read-redis-0.1。

---来自腾讯云社区的---theanarkh