字典：dict.c/dict.h

Redis 源码分析（1）：字典和哈希表（dict.c 和 dict.h）
http://huangz.iteye.com/blog/1455808
两个点：
字典结构的运作流程
哈希表的渐进式 rehash操作
哈希表是 redis 的核心结构之一，在 redis 的源码中， dict.c 和 dict.h 就定义了哈希结构。

dict 、 dictht 和 dictEntry 这三个核心数据结构

/* 字典结构 */
typedef struct dict {
dictType *type; // 为哈希表中不同类型的值所使用的一族函数
void *privdata; //传给类型特定函数的可选参数
dictht ht[2]; // 每个字典使用两个哈希表
int rehashidx; // 指示 rehash 是否正在进行，如果不是则为 -1
int iterators; // 当前正在使用的 iterator 的数量
} dict;

代码的注释基本都说明相关属性的作用了，需要补充的一些是：

每个字典使用两个哈希表，是因为要实现渐增式 rehash ，redis 会逐个逐个地将 0 号哈希表的元素移动到 1 号哈希表，直到 0 号哈希表被清空为止，

另外， rehashidx 记录的实际上是 rehash 进行到的索引，比如如果 rehash 进行到第 10 个元素，那么 rehashidx 的值就为 9，以此类推，如果没有在进行 rehash ，rehashidx 的值就为 -1 。

哈希表结构 —— dictht 结构，这个哈希表是一个 separate chaining hash table 实现，它通过将哈希值相同的元素放到一个链表中来解决冲突问题：
typedef struct dictht {
dictEntry **table; // 节点指针数组
unsigned long size; // 桶的数量
unsigned long sizemask; // mask 码，用于地址索引计算
unsigned long used; // 已有节点数量
} dictht;

table 属性组成了一个数组，数组里带有节点指针，用作链表。

size 、 sizemask 和 used 这三个属性初看上去让人有点头晕，实际上，它们分别代表的是：
size ：桶的数量，也即是， table 数组的大小。
sizemask ：这个值通过 size - 1 计算出来，给定 key 的哈希值计算出来之后，就会和这个数值进行 & 操作，决定元素被放到 table 数组的那一个位置上。
used ：这个值代表目前哈希表中元素的数量，也即是哈希表总共保存了多少 dictEntry 结构。

链表节点结构
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
} v; // 值(可以有几种不同类型)
struct dictEntry *next; // 指向下一个哈希节点(形成链表)
} dictEntry;

字典创建流程

在初步解了几个核心数据结构之后，是时候可以来看看相关的函数怎么来使用这些数据结构了，让我们从最开始的创建字典开始，一步步研究字典（以及哈希表）的运作流程。

因为调用流程可以给我们一个高层次的观点来了解数据结构的运作流程，而不必陷入到代码细节中，因此，文章这里只给出程序调用流程的部分核心代码，如果你对代码的其他细节有兴趣，可以到我的 github 上去找注释版的代码，上面有完整的代码，而且我给大部分函数都加上了注释。

OK，说回来字典这边，创建新字典执行的调用链是： dictCreate -> _dictInit -> _dictReset

其中 dictCreate 函数为 dict 结构分配了空间，然后将新的 dict 传给 _dictInit 函数，让它初始化 dict 结构的相关属性，而 _dictInit 又调用 _dictReset ，对字典的 ht 属性（也即是两个哈希表）进行常量属性的设置。

注意， _dictReset 只是为字典所属的两个哈希表进行常量属性的设置(size、 sizemask 和 used），但并不为哈希表的链表数组分配内存：

static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}

0 号哈希表的创建流程

我们知道，一个 dict 结构使用两个哈希表，也即是 d->ht[0] 和 d->ht[1] ，为了称呼方便，我们将他们分别叫做 0 号和 1 号哈希表。

从上一节可以知道， dictCreate 并不为哈希表的链表数组分配内存( d->ht[0]->table 和 d->ht[1]->table 都被设为 NULL），那么，什么时候哈希表的链表数组会被初始化呢？

答案是，当首次通过 dictAdd 向字典添加元素的时候， 0 号哈希表的链表数组会被初始化。

首次向字典增加元素将执行以下的调用序列： dictAdd -> dictAddRaw -> _dictKeyIndex -> dictExpandIfNeeded -> dictExpand

其中 dictAdd 是 dictAddRaw 的调用者， dictAddRaw 是添加元素这一工作的底层实现，而 dictAddRaw 为了计算新元素的 key 的地址索引，会调用 _dictKeyIndex ：

dictEntry *dictAddRaw(dict *d, void *key)
{
// 被省略的代码...

// 计算 key 的 index 值
// 如果 key 已经存在，_dictKeyIndex 返回 -1
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;

// 被省略的代码...
}

然后 _dictKeyIndex 会在计算地址索引前，会先调用 _dictExpandIfNeeded 检查两个哈希表是否有空间容纳新元素：
static int _dictKeyIndex(dict *d, const void *key)
{
// 被省略的代码...

/* Expand the hashtable if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;

// 被省略的代码...
}

到 _dictExpandIfNeeded 这步，一些有趣的事情就开始发生了， _dictExpandIfNeeded 会检测到 0 号哈希表还没有分配任何空间，于是它调用 dictExpand ，传入 DICT_HT_INITIAL_SIZE 常量作为 0 号哈希表的初始大小（目前的版本 DICT_HT_INITIAL_SIZE = 4 )，为 0 号哈希表分配空间：
static int _dictExpandIfNeeded(dict *d)
{
// 被忽略的代码...

/* If the hash table is empty expand it to the intial size. */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

// 被忽略的代码...
}

dictExpand 会创建一个分配了链表数组的新哈希表，然后进行判断，决定是该将新哈希表赋值给 0 号哈希表还是 1 号哈希表。
这里因为我们的 0 号哈希表的 size 还是 0 ，因此，这里会执行 if 语句的第一个 case ，将新哈希表赋值给 0 号哈希表：
int dictExpand(dict *d, unsigned long size)
{
// 被省略的代码...

// 计算哈希表的(真正)大小
unsigned long realsize = _dictNextPower(size);

// 创建新哈希表
dictht n;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*)); // 分配链表数组
n.used = 0;

// 字典的 0 号哈希表是否已经初始化？
// 如果没有的话，我们将新建哈希表作为字典的 0 号哈希表
if (d->ht[0].table == NULL) {
d->ht[0] = n;
} else {
// 否则，将新建哈希表作为字典的 1 号哈希表，并将它用于 rehash
d->ht[1] = n;
d->rehashidx = 0;
}

// 被省略的代码...
}

字典的扩展和 1 号哈希表的创建

在 0 号哈希表创建之后，我们就有了一个可以执各式各样操作（添加、删除、查找，诸如此类）的字典实例了。

但是这里还有一个问题：这个最初创建的 0 号哈希表非常小（当前版本的 DICT_HT_INITIAL_SIZE = 4)，它很快就会被元素填满，这时候， rehash 操作就会被激活。

巴特西

字典：dict.c/dict.h

最新文章

热门文章