Redis 源码分析：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 结构的定义如下：

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

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

每个字典使用两个哈希表，是因为要实现渐增式 rehash ，redis 会逐个逐个地将 0 号哈希表的元素移动到 1 号哈希表，直到 0 号哈希表被清空为止，文章的后面会给出相关细节，不要心急！

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

接着来看看哈希表结构 —— dictht 结构，这个哈希表是一个 separate chaining hash table 实现，它通过将哈希值相同的元素放到一个链表中来解决冲突问题：

1. typedef struct dictht {   
2.     dictEntry **table;      // 节点指针数组   
3.     unsigned long size;     // 桶的数量   
4.     unsigned long sizemask; // mask 码，用于地址索引计算   
5.     unsigned long used;     // 已有节点数量   
6. } dictht; 

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

size 、 sizemask 和 used 这三个属性初看上去让人有点头晕，实际上，它们分别代表的是：

size ：桶的数量，也即是， table 数组的大小。

sizemask ：这个值通过 size - 1 计算出来，给定 key 的哈希值计算出来之后，就会和这个数值进行 & 操作，决定元素被放到 table 数组的那一个位置上。

used ：这个值代表目前哈希表中元素的数量，也即是哈希表总共保存了多少 dictEntry 结构。

好的，最后，就是链表节点结构 —— dictEntry 了：

1. typedef struct dictEntry {   
2.     void *key;              // 键   
3.     union {   
4.         void *val;   
5.         uint64_t u64;   
6.         int64_t s64;   
7.     } v;                    // 值(可以有几种不同类型)   
8.     struct dictEntry *next; // 指向下一个哈希节点(形成链表)   
9. } dictEntry;  

这个结构。。。阿，好吧，这个结构没啥要说的，赶紧进入下一部分吧。