源码版本：redis-4.0.1
源码位置：

• dict.h：dictEntry、dictht、dict等数据结构定义。
• dict.c：创建、插入、查找等功能实现。

一、dict 简介

dict (dictionary 字典)，通常的存储结构是Key-Value形式的，通过Hash函数对key求Hash值来确定Value的位置，因此也叫Hash表，是一种用来解决算法中查找问题的数据结构，默认的算法复杂度接近O(1)，Redis本身也叫REmote DIctionary Server (远程字典服务器)，其实也就是一个大字典，它的key通常来说是String类型的，但是Value可以是
String、Set、ZSet、Hash、List等不同的类型，下面我们看下dict的数据结构定义。

二、数据结构定义

与dict相关的关键数据结构有三个，分别是：

• dictEntry 表示一个Key-Value节点。
• dictht表示一个Hash表。
• dict是Redis中的字典结构，包含两个dictht。

dictEntry结构的代码如下：

typedef struct dictEntry {
    void *key;                //key void*表示任意类型指针

    union {                   //联合体中对于数字类型提供了专门的类型优化
       void      *val;
       uint64_t  u64;
       int64_t   s64;
    } v;

    struct dictEntry *next;   //next指针

} dictEntry;

dictht的代码如下：

typedef struct dictht {
    dictEntry **table;        //数组指针，每个元素都是一个指向dictEntry的指针

    unsigned long size;       //表示这个dictht已经分配空间的大小，大小总是2^n

    unsigned long sizemask;   //sizemask = size - 1; 是用来求hash值的掩码，为2^n-1

    unsigned long used;       //目前已有的元素数量
} dictht;

最后是真正的dict结构：

typedef struct dict {
    dictType *type;     //type中定义了对于Hash表的操作函数，比如Hash函数，key比较函数等

    void *privdata;      //privdata是可以传递给dict的私有数据         

    dictht ht[2];       //每一个dict都包含两个dictht，一个用于rehash

    int rehashidx;      //表示此时是否在进行rehash操作

    int iterators;      //迭代器
} dict;

其实通过上面的三个数据结构，已经可以大概看出dict的组成，数据（Key-Value）存储在每一个dictEntry节点；然后一条Hash表就是一个dictht结构，里面标明了Hash表的size,used等信息；最后每一个Redis的dict结构都会默认包含两个dictht，如果有一个Hash表满足特定条件需要扩容，则会申请另一个Hash表，然后把元素ReHash过来，ReHash的意思就是重新计算每个Key的Hash值，然后把它存放在第二个Hash表合适的位置，但是这个操作在Redis中并不是集中式一次完成的，而是在后续的增删改查过程中逐步完成的，这个叫渐进式ReHash，我们后文会专门讨论。

三、创建、插入、键冲突、扩张

下面我们跟随一个例子来看有关dict的创建，插入，键冲突的解决办法以及扩张的问题。在这里推荐一个有关调试Redis数据结构代码的方法：下载一份Redis源码，然后直接把server.c中main函数注释掉，加入自己的代码，直接make之后就可以跑了。我们的例子如下所示：

int main(int argc, char **argv) {

    int ret;
    sds key = sdsnew("key");
    sds val = sdsnew("val");
    dict *dd = dictCreate(&keyptrDictType, NULL);

    printf("Add elements to dict\n");
    for (int i = 0; i < 6 ; ++i) {
        ret = dictAdd(dd, sdscatprintf(key, "%d", i), sdscatprintf(val, "%d", i));
        printf("Add ret%d is :%d ,", i, ret);
        printf("ht[0].used :%lu, ht[0].size :%lu, "
                       "ht[1].used :%lu, ht[1].size :%lu\n", dd->ht[0].used, dd->ht[0].size, dd->ht[1].used, dd->ht[1].size);
    }

    printf("\nDel elements to dict\n");
    for (int i = 0; i < 6 ; ++i) {
        ret = dictDelete(dd, sdscatprintf(key, "%d", i));
        printf("Del ret%d is :%d ,", i, ret);
        printf("ht[0].used :%lu, ht[0].size :%lu, "
                       "ht[1].used :%lu, ht[1].size :%lu\n", dd->ht[0].used, dd->ht[0].size, dd->ht[1].used, dd->ht[1].size);
    }

    sdsfree(key);
    sdsfree(val);
    dictRelease(dd);

    return 0;
}


Out >
Add elements to dict
Add ret0 is :0 ,ht[0].used :1, ht[0].size :4, ht[1].used :0, ht[1].size :0
Add ret1 is :0 ,ht[0].used :2, ht[0].size :4, ht[1].used :0, ht[1].size :0
Add ret2 is :0 ,ht[0].used :3, ht[0].size :4, ht[1].used :0, ht[1].size :0
Add ret3 is :0 ,ht[0].used :4, ht[0].size :4, ht[1].used :0, ht[1].size :0
Add ret4 is :0 ,ht[0].used :4, ht[0].size :4, ht[1].used :1, ht[1].size :8
Add ret5 is :0 ,ht[0].used :3, ht[0].size :4, ht[1].used :3, ht[1].size :8

Del elements to dict
Del ret0 is :0 ,ht[0].used :5, ht[0].size :8, ht[1].used :0, ht[1].size :0
Del ret1 is :0 ,ht[0].used :4, ht[0].size :8, ht[1].used :0, ht[1].size :0
Del ret2 is :0 ,ht[0].used :3, ht[0].size :8, ht[1].used :0, ht[1].size :0
Del ret3 is :0 ,ht[0].used :2, ht[0].size :8, ht[1].used :0, ht[1].size :0
Del ret4 is :0 ,ht[0].used :1, ht[0].size :8, ht[1].used :0, ht[1].size :0
Del ret5 is :0 ,ht[0].used :0, ht[0].size :8, ht[1].used :0, ht[1].size :0

• dict *dd = dictCreate(&keyptrDictType, NULL); 创建了一个名为dd，type为keyptrDictType的dict，创建代码如下，需要注意的是这个操作只给dict本身申请了空间，但是像dict->ht->table这些数据存储节点并没有分配空间，这些空间是dictAdd的时候才分配的。

/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));    //申请空间，sizeof(*d)为88个字节

    _dictInit(d,type,privDataPtr);    //一些置NULL操作，type和privdata置为参数指定值 
    return d;
}

• ret = dictAdd(dd, sdscatprintf(key, "%d", i), sdscatprintf(val, "%d", i)); 接着我们定义了两个sds，并且for循环分别将他们dictAdd，来看下dictAdd的代码，它实际上调用了dictAddRaw函数：

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

可以看到首先检测是否在进行ReHash（我们先跳过ReHash这个概念），接下来算出了一个index值，然后根据是否在进行ReHash选择了其中一个dt（0或者1），之后进行了头插，而且英文注释中也写的很清楚将数据插在头部基于数据库系统总是会经常访问最近添加的节点，然后将key设置之后就返回了，但是我们貌似还是没有发现申请空间的函数，其实是在算index的时候_dictKeyIndex()会自动判断，如下：

static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
    unsigned int idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

_dictExpandIfNeeded(d)进行空间判断，如果还未申请，就创建默认大小，其中它里面也有dict扩容的策略（见注释）：

static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;  
    //如果正在ReHash，那直接返回OK，其实也表明申请了空间不久。

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);  
    //如果 0 号哈希表的大小为0，表示还未创建，按照默认大小`DICT_HT_INITIAL_SIZE=4`去创建

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */

    //如果满足 0 号哈希表used>size &&（dict_can_resize为1 或者 used/size > 5） 那就默认扩两倍大小
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

对于我们的代码，走的是if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);这个分支，也就是会去创建一个dictht的table大小为4的dict，如下：

int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

需要注意的是_dictNextPower可以计算出距离size最近，且大于或者等于size的2的次方的值，比如size是4，那距离其最近的值为4（2的平方），size是6，距离其最近的值为8（2的三次方），然后申请空间，之后判断如果d->ht[0].table == NULL也就是我们目前的还未初始化的情况，则初始化 0 号Hash表，之后添加相应的元素，我们程序的输出如下所示：

Add ret0 is :0 ,ht[0].used :1, ht[0].size :4, ht[1].used :0, ht[1].size :0

如果图示目前的Hash表，如下所示:

• 接下来for循环继续添加，当i = 4时，也就是当添加第5个元素时，默认初始化大小为4的Hash表已经不够用了。此时的used=4，我们看看扩张操作发生了什么，代码从_dictExpandIfNeeded(d)说起，此时满足条件，会执行扩张操作，如下:

if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }

dictExpand(d, d->ht[0].used*2); 表示重新申请了一个大小为之前2倍的Hash表，即 1 号Hash表。然后将d->rehashidx = 0;即表明此时开始ReHash操作。

Rehash就是将原始Hash表（0号Hash表）上的Key重新按照Hash函数计算Hash值，存到新的Hash表（1号Hash表）的过程。

这一步执行之后此时Hash表如下所示：

由图可以看到 0 号Hash表已经满了，此时我们的新数据被存到了 1 号哈希表中，接下来我们开始了第6次循环，我们继续看在ReHash的情况下数据是如何存入的，也就是第6次循环，即添加key5的过程，继续调用dictAddRaw函数：

if (dictIsRehashing(d)) _dictRehashStep(d);

此时因为d->rehashidx = 0，所以会执行渐进式Hash操作，即_dictRehashStep(d)：

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);  //如果迭代器是0，ReHash步长为1
}

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[