Redis 源码分析（1）：字典和哈希表（dict.c 和 dict.h）

简介

?

哈希表是 redis 的核心结构之一，在 redis 的源码中， dict.c 和 dict.h 就定义了 redis 所使用的哈希结构，在这篇文章中，我们将对 dict.c 和 dict.h 进行注解和分析，籍此加深对 redis 的理解。

?

因为 dict.c 中使用的 separate?chaining 哈希表实现可以在任何一本算法书上找到，因此，在本文中没有对查找和增删等操作做过多的着墨，而是将重点放到整个字典结构的运作流程，以及哈希表的渐进式 rehash 操作上。

?

?

数据结构概览

dict.h 中定义了被 dict.c 的程序所使用的几个数据结构，如 dict 、dictht 和 dictEntry 等，它们之间的关系可以用下图来描述(点击放大）：

?

?

数据结构实现细节

?

上一节的大图给出了数据结构之间相互关系，现在，让我们将注意力集中到 dict 、 dictht 和 dictEntry 这三个核心数据结构上面。

dict 结构的定义如下：

?

static unsigned long _dictNextPower(unsigned long size){    unsigned long i = DICT_HT_INITIAL_SIZE;    if (size >= LONG_MAX) return LONG_MAX;    while(1) {        if (i >= size)            return i;        i *= 2;    }}

??

虽然桶的元素个数 d->ht[0].size 刚开始是固定的(DICT_HT_INITIAL_SIZE)，但是，因为我们没有办法预知 d->ht[0].used 的值，所以我们没有办法预知哈希表的大小，不过，我们可以确定以下两个关于哈希表大小的性质：

1） 哈希表的大小总是 2 的乘幂（也即是 2^N，此处 N 未知）

2）1 号哈希表的大小总比 0 号哈希表大

?

?

就这样了！

?

对 redis 的 dict.c 和 dict.h 的源码分析就到这了，本人一直认为，好的源码分析应该能在不贴太多代码的情况下把原理和流程讲明白，在这篇文章我已经尽力地将实践这个原则，不过因为是第一次写源码分析类的文章，而且才刚开始读 redis 的源码，难免有不如人意之处，希望朋友们不吝指出。

dict 的结构本身还是很简单的，唯一的遗憾是，dictht 作为字典的内部实现，本该被隐藏起来的，现在却完全暴露了出来（什么， _dictReset(&d->ht[1])，你是说真的？），如果能在模块化方面多做一点努力的话，代码会更容易看一些，当然这里也有历史遗留的因素在里面。

最后， 我为 redis 的源码分析项目专门建立了一个 github project ，上面有完整的源码文件，大部分加上了注释（目前只有 dict.c 和 dict.h），如果对代码的完整细节有兴趣，可以到上面去取： ?https://github.com/huangz1990/reading_redis_source

?

?

?

1 楼 ppooooll 2012-03-19 支持一下，同在看redis源码，希望楼主再接再厉！