一口气读完了redis的基本类型相关代码，是时候好好静下心思来整理整理了。
字典在高级语言十分常见，C++有map类型，Python有dict类型等，C没有字典这种类型，因此Redis实现了字典。字典主要由值和键的映射组成，称为键值对，字典中的每个键都是独一无二的。字典在Redis中的应用十分广泛，后续将会体现出来。

涉及的主要代码

1. dict.h
2. dict.c

dict的定义

//哈希表节点
typedef struct dictEntry {
    void *key;              //字典中的key
    union {                 //union结构体，字典中的值，可以为一个void指针、无符号整型，有符号整型、浮点数
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //键冲突的形成一个链表结构
} dictEntry;

//类型特定函数
typedef struct dictType {
    unsigned int (*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;

//hash table 哈希表
typedef struct dictht {
    dictEntry **table;      //哈希表节点指针数组
    unsigned long size;     //哈希表大小
    unsigned long sizemask; //哈希表掩码，sizemask = size - 1
    unsigned long used;     //已有节点数量
} dictht;

//字典
typedef struct dict {
    dictType *type;         // 类型特定函数结构指针
    void *privdata;         // 私有数据，调用dictType中函数的时候需要传入   
    dictht ht[2];           // 哈希表，dictht[0]用来存储数据，dictht[1]用来rehash是重新使用
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */      //记录rehash到哪一个哈希表节点（类似于数组index）
    int iterators; /* number of iterators currently running */              //正在运行的迭代器数量
} dict;

字典.png

如图所示，这个字典结构由多个层级组成，分别有哈希表节点、哈希表、字典组成。

哈希表节点

最底层的是哈希表节点dictEntry，dictEntry中保存着键值对，key属性保存着键，它是一个空类型指针，意味着可以使用任何类型作为键；v属性保存着值，它是一个结构体，可以是一个空类型指针，亦或者是一个无符号整型，亦或者是一个有符号整型，亦或者是一个浮点数。next属性是指向下一个dictEntry节点的值，可以将多个键冲突的键值对用next连接在一起，形成一个链表，以此来解决键冲突的问题。

哈希表

dictht表示哈希表，多个dictEntry链表由dictht中的table属性管理，dictht中size表示了table数组的大小，sizemask用来计算索引值，通常等于size-1；used属性记录该dictht包含的键值对数量，图中展示了table大小为4，键值对数量为3的dictht结构。

字典

图中总共有2个dictht结构，通常dict只是用其中一个dictht，另一个不使用；只有在进行rehash的时候，才会使用到另一个dictht结构，后面会讲到rehash的过程。dict表示字典，这个是我们所见到的字典对象，dict来管理dictht（属性ht），该结构还包含了关于字典的一些其他信息；type属性是一个dictType对象，它包含了一些关于键和值的操作，如复制、比较、销毁等，与private属性相结合就可以实现多态字典；rehashidx用来表示是否正在进行hash以及hash的进度；iterator表示当前正在运行的迭代器数量。

dict实现细节

哈希算法

要将一个键值对方到字典中，首先需要通过键算出一个hash值，然后再通过hash值算出一个索引值，接着根据索引，找到键值要插入对应的哈希表中。

对应的伪代码如下：

hash = dict->type-> hashFunction(key);
index = hash & dict->dictht[x].sizemask;  //ht[x]根据是否在rehash，可能是ht[0]，也可能是ht[1]

根据key所指向的类型，redis提供了以下几种hash算法：

1. unsigned int dictIntHashFunction(unsigned int key)，不过该函数没有在源码看到有被调用；
2. unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len)；
3. unsigned int dictGenHashFunction(const void *key, int len)。

其中，dictGenHashFunction函数使用了MurmurHash2算法，具体原来还没有详细研究，待整体代码看完后得空在来研究，若有兴趣可以看下MurmurHash，**该算法能够在有规律的输入情况下，仍然能够保持很好的随机分布性。

键冲突

键冲突是指不同的键算出了相同的索引。Redis使用链表来解决键冲突的问题，即算出同一个索引值的键值用next指针连接起来构成一个单向链表。当一个键值对进来时，先要计算出其索引，然后在dictht[0]（根据是否在rehash来决定是否需要在dictht[1]中寻找）中寻找该键是否存在，如果不存在，都将其插入到对应的链表头结点。

#define dictIsRehashing(d) ((d)->rehashidx != -1)               //判断当前是否在hash阶段

/* Add an element to the target hash table */
//添加一个键值对
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);              //设置值
    return DICT_OK;
}

//添加dictEntry节点，并返回其地址，上层来设置key
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);     //如果正在rehash中，那么rehash一个slot

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

    /* Allocate the memory and store the new entry */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];            //如果正在rehash，选择ht[1]插入
    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;
}

//返回所在的slot
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    /* Compute the key hash value */
    h = dictHashKey(d, key);        //获取key的hash
    for (table = 0; table <= 1; table++) {    //两个ht都要寻找
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))       //比较键值
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break; //如果不是在rehash过程中，ht[1]可以不用寻找
    }
    return idx;
}

哈希表的扩张和收缩

负载因子的计算：factor = used/size，哈希表大小变化的最终是使得负载因子小于1。

哈希表大小的变化总是在dictht[1]上面进行操作的，其要变化后的大小与当前字典包含的键值对数量有关：

1. 扩张操作：dictht[1]的大小为第一个大于等于dict[0].used*2的2^n；
2. 收缩操作：dictht[1]的大小为第一个大于等于dict[0].used的2^n；

//计算实际要创建的实际大小，添加键值对时会调用
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_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);

    /* 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. */
    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;
}

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;      //4，也是table数组长度最小的值

    if (size >= LONG_MAX) return LONG_MAX;
    //以2的n次方倍扩张
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

 //重新设置table的大小，使得其负载因子小于1，通常在rehash之前调用，调整dictht[1]
 //dictResize->dictExpand
int dictResize(dict *d)
{
    int minimal;

    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}

/* Expand or create the hash table */
//实际扩大dict的slot到指定大小
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);      //获得resize后实际的新大小，通常是2^n的大小

    /* 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) //通常要求新的长度要比1已拥有的键值数量大并且该dict不能正在rehahs中
        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*));     //分配slot
    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. */
    //如果ht[0]没有数据，则直接赋值给ht[0]
    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;           //准备rehash
    return DICT_OK;
}

rehash

当哈希表需要进行长度变化，首先设置dictht[1]到所需要的大小，然后将dictht[0]上的所有键值迁移到dictht[1]上，迁移完成之后，释放dictht[0]，将dictht[1]的值赋值给dictht[0]，然后为dictht[1]创建一个空白的哈希表。整个过程就是rehash。

//rehash 字典，n表示此处rehash的bucket，n表示最多可连续空转 n*10个bucket
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */    //最多轮过n*10个空bucket
    if (!dictIsRehashing(d)) return 0;

    //最多rehash n个bucket
    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++;        //通过rehashidx来指定当前rehash的进度
            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 */
        //bucket上面的每个节点进行迁移
        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[0].table[d->rehashidx] = NULL;      //链表清空
        d->rehashidx++;
    }

![微信免密1 (1).jpg](https://upload-images.jianshu.io/upload_images/6201701-ac661ef06320162b.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
    /* Check if we already rehashed the whole table... */
    //已经迁移完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);      //重置ht[1]
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

rehash过程图解：

rehash之前

扩张长度

节点迁移完成

rehash完成

当dict中节点比较少时，进行rehash的速度是很快的，但如果dict中节点达到百万、千万、甚至亿的时候，如果只进行一次性rehash，会导致服务不可用一段时间（因为redis是单进程处理请求的）。因此，redis进行rehash并不是一次性集中完成，而是渐进式、逐步的地完成迁移。

渐进式rehash的过程：

1. 在操作哈希表的过程中，发现需要扩大哈希表大小，因此计算要扩展的大小，分配空间给dictht[1];
2. dictht[1]分配完毕后，设置dict->rehashidx为0，表示dict要开始rehash，rehash的过程中，dict->rehashidx表示当前rehash的进度（已经rehash到dictht[0]->table[rehashidx]）；
3. 在添加、删除、查询等操作的过程中，每次rehahs一个dictEntry链表，新增的节点总是添加到dictht[1]哈希表中。
4. 最终，dictht[0]上的所有键值对都迁移到dictht[1]上，然后释放dictht[0]，将dict->ht[1]的值赋值给dict->ht[0]，重新申请空的hash表给dict->ht[1]，置dict->rehashidx=-1表示rehash完成。

可以看出，渐进式rehash将rehash过程分散到各种操作上，避免了一次性rehash带来的性能问题。

添加、删除、查找等都包含下面一段代码：

if (dictIsRehashing(d)) _dictRehashStep(d);     //如果正在rehash中，那么rehash一个slot

删除键值对

如果在rehash过程中，需要寻找dictht[0]和dictht[1]，因为之前新添加的键值对是直接在dictht[1]中的。

/* Search and remove an element */
//删除键值对，nofree表示是否释放锁找到的key和value
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
    if (dictIsRehashing(d)) _dictRehashStep(d);     //惰性hash
    h = dictHashKey(d, key);                        //获取键的hash

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while(he) {
            if (dictCompareKeys(d, key, he->key)) {     //比较键
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;                 //如果不在hash中，就没有必要
    }
    return DICT_ERR; /* not found */
}
//从dict中提出并删除寻找到的键值
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}
//从dict中剔除，但返回dictEntry
int dictDeleteNoFree(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

查找键值对

如果在rehash过程中，需要在dictht[0]和dictht[1]中分别寻找，因为之前新添加的键值对是直接在dictht[1]中的。

//寻找key对应的dictEntry
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
    if (dictIsRehashing(d)) _dictRehashStep(d);         //惰性rehash
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

//获取键所对应的值
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;

    he = dictFind(d,key);
    return he ? dictGetVal(he) : NULL;
}

总结

1. Redis的字典带有两个哈希表，另一个哈希表使用来做reahsh用；
2. rehash不是一次性、集中式的，而是渐进的；
3. Redis使用单链表来解决键冲突的问题。

字典主要API