dict是一个用于维护key和value映射关系的数据结构，与很多语言中的Map或dictionary类似。redis实现了自己的dict实现。redis数据库底层主要使用字典dict来实现的，对redis数据库db的增删改查都是基于字典进行操作的。这只是它在Redis中的一个用途而已，它在Redis中被使用的地方还有很多。比如，一个Redis hash结构，当它的field较多时，便会采用dict来存储。再比如，Redis配合使用dict和skiplist来共同维护一个sorted set。下面这篇文章先简单介绍redis的dict结构体实现。
字典实体节点
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下个表节点，形成链表，解决链表冲突
struct dictEntry *next;
} dictEntry;
dictEntry是redis存储数据的真正实体，其结构中包含k, v和指向链表下一项的next指针。
- k是void指针，这意味着它可以指向任何类型。
- v是个union，当它的值是uint64_t、int64_t或double类型时，就不再需要额外的存储，这有利于减少内存碎片。当然，v也可以是void指针，以便能存储任何类型的数据。
- next指向下个表节点，形成链表，解决hash冲突
字典表结构体
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
// hash表数组
dictEntry **table;
// hash表大小
unsigned long size;
// hash表大小掩码，用于计算索引值，大小等于size-1
unsigned long sizemask;
// hash表已有节点数量
unsigned long used;
} dictht;
dictType结构包含若干函数指针，用于dict的调用者对涉及key和value的各种操作进行自定义。这些操作包含：
- hashFunction，对key进行哈希值计算的哈希算法。
- keyDup和valDup，分别定义key和value的拷贝函数，用于在需要的时候对key和value进行深拷贝，而不仅仅是传递对象指针。
- keyCompare，定义两个key的比较操作，在根据key进行查找时会用到。
- keyDestructor和valDestructor，分别定义对key和value的析构函数。
dictht结构，它定义一个哈希表的结构，由如下若干项组成：
- table: 一个dictEntry指针数组。key的哈希值最终映射到这个数组的某个位置上（对应一个bucket）。如果多个key映射到同一个位置，就发生了冲突，那么就拉出一个dictEntry链表。
- size：标识dictEntry指针数组的长度。它总是2的指数。
- sizemask：用于将哈希值映射到table的位置索引。它的值等于(size-1)，比如7, 15, 31, 63，等等，也就是用二进制表示的各个bit全1的数字。每个key先经过hashFunction计算得到一个哈希值，然后计算(哈希值 & sizemask)得到在table上的位置。相当于计算取余(哈希值 % size)。
- used：记录dict中现有的数据个数。它与size的比值就是装载因子（load factor）。这个比值越大，哈希值冲突概率越高。
字典
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 包含两个dictht的数组，一般使用ht[0]，rehash才会使用的ht[1]
dictht ht[2];
// rehash索引
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
dict的结构由如下若干项组成：
- 一个指向dictType结构的指针（type）。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。
- 一个私有数据指针（privdata）。由调用者在创建dict的时候传进来。type与privdata针对不同类型的键值对，实现多态。
- 两个哈希表（ht[2]）。只有在重哈希的过程中，ht[0]和ht[1]才都有效。而在平常情况下，只有ht[0]有效，ht[1]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。
- 当前重哈希索引（rehashidx）。如果rehashidx = -1，表示当前没有在重哈希过程中；否则，表示当前正在进行重哈希，且它的值记录了当前重哈希进行到哪一步了。
- 当前正在进行遍历的iterator的个数。
下图可以清晰展示redis的dict的数据结构
没有进行rehash的字典.png
参考：
http://zhangtielei.com/posts/blog-redis-dict.html
《redis设计与实现》第二版
