日期:2014-05-16  浏览次数:20448 次

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 结构的定义如下:

?

/* 字典结构 */
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 结构。


好的,最后,就是链