字典，简单说就是存储key-value键值数据，当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map，STL中的map是用red-black tree实现的，因为map不仅能够保证key不重复，而且key还是按照字典序存储的，而Redis中的字典并不要求有序，因此为了降低编码的难度使用哈希表作为字典的底层实现。Redis的字典是使用一个桶bucket，通过对key进行hash得到的索引值index，然后将key-value的数据存在桶的index位置，Redis处理hash碰撞的方式是链表，两个不同的key hash得到相同的索引值，那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候，字典不免会退化成多个链表，效率大大降低，Redis采用rehash的方式对桶进行扩容来解决这种退化。

Redis使用的hash算法有以下两种：

1. MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好，具体信息请参考 MurmurHash 的主页：http://code.google.com/p/smhasher/ 。
2. 基于djb算法实现的一个大小写无关散列算法：具体信息请参考
http://www.cse.yorku.ca/~oz/hash.html 。

字典数据结构

typedef struct dictEntry {//字典的节点
    void *key;
    union {//使用的联合体
        void *val;
        uint64_t u64;//这两个参数很有用
        int64_t s64;
    } v;
    struct dictEntry *next;//下一个节点指针
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key); //hash函数指针
    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 table
    dictEntry **table;//可以看做字典数组，俗称桶bucket
    unsigned long size; //指针数组的大小，即桶的层数
    unsigned long sizemask;
    unsigned long used; //字典中当前的节点数目
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata; //私有数据
    dictht ht[2];   //两个hash table
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引
    int iterators; /* number of iterators currently running */ //当前该字典迭代器个数
} dict;

dict数据结构中声明了两个字典hashtable结构dictht，ht[1]在rehash时候使用，后面具体分析。

下图给出整个字典结构，图片来自Redis设计与实现一书：

上图ht[1]为空，说明当然字典没在Rehash状态。

字典的API函数

创建新字典

通过dictCreate函数创建一个新字典dict *dictCreate(dictType *type, void *privDataPtr)，一个空字典的示意图如下(图片来自Redis设计与实现一书): 上面已经提起过，ht[1]只在Rehash时使用。

字典添加元素

根据字典当前的状态，将一个key-value元素添加到字典中可能会引起一系列复制的操作：

如果字典未初始化（即字典的0号哈希表ht[0]的table为空），那么需要调用dictExpand函数对它初始化；

如果插入的元素key已经存在，那么添加元素失败；

如果插入元素时，引起碰撞，需要使用链表来处理碰撞；

如果插入元素时，引起程序满足Rehash的条件时，先调用dictExpand函数扩展哈希表的size，然后准备渐进式Rehash操作。

字典添加元素的流程图，来自Redis设计与实现一书