dict

理解redis中字典数据结构之前，需要先对哈希表的一些基本知识有所了解，因此，在这里，也先对哈希表这一数据结构进行一些介绍，并加入一点自己的理解。

hash table

所谓哈希，其实也就是要将一个较大的地址空间映射到较小的地址空间。为什么这样说呢？举一个简单的例子：一个班级里面有30位同学，每个同学都有一个10位数的电话号码，现在我们需要建立一个数据结构用于保存查询每个有效的电话号码对应的是哪一位同学。显然，最直观的方法就是，我们建立一个包含个字符串元素的数组，然后用电话号码作为下标，去查询对应的同学名字。虽然直观，但对于空间的利用率实在是太低了！可以说是和0相差无几。因此我们需要找到一种方式，或者说是一种映射，可以让我们不用使用那么多空间的前提下，也能达到查询的目的。前面所说的较小的地址空间，也就是我们开辟一个数组，但这个数组不用像那么大，然后我们通过映射函数，找出对于某一个电话号码，它应该存储在较小的数组中的哪一个entry(也就是确定它的下标)。这就是哈希表的意义，哈希表的核心就是哈希函数以及对于冲突的处理办法。对于哈希函数，我们需要满足一些条件：

• 映射函数(hash)无歧义。给定一个key，那么hash(key)就唯一确定；
• 映射函数计算复杂度低。只有这样，哈希效率才会有保障；
• 均匀性。应该尽量均匀的映射到目的地址空间，这样才能将哈希冲突降至最低。

冲突避免方式

• 取余法：将被除数M（也就是散列表空间大小）设置为一个素数，然后设定address = hash(key) = key mod M；这样可以有效避免冲突。需要注意的是，素数才有均匀性的良好性能，非素数的性能会大大降低。
• MAD法：hash(key) = (a * key + b) mod M, a>0 && b>0 && (a mod M != 0); 解决了取余法的一个弊端，即一些源地址空间中相邻的地址，当映射之后，在新的地址空间中仍然相邻。加了一个a和b之后，就将源地址空间中的相邻空间在映射之前就进行了分散处理，增强了均匀性。
• 伪随机数法：hash(key) = rand(key) mod M, rand(key)为系统的第key个伪随机数。目的也是一样的，将源地址首先进行随机分散处理，然后映射到新的地址空间。可以看出，设计一个好的hash函数，和设计一个好的伪随机数发生器，两者的目的是基本一致的。

冲突处理方式

1. 封闭定址(重新构造桶单元)
   所谓封闭定址，就是给定一个key，那么该键值对在数组中的entry下标就唯一确定了。既然如此，那么如果出现冲突，我们就需要对不得不在一个entry中存储多个键值对，也就是重新构造entry，即一个桶单元。常用的方式包括：① 多槽位：可以理解为将开始的一维数组变为二维数组，每一行保存相同hash值的键值对；② 独立链：即每个e桶单元形成一个链表。

2. 开放定址(重新选择桶单元)
   所谓开放定址，就是说，当发生冲突时，我们另外寻找其他的桶单元去存储键值对。这也就是说，一个键值对的存储位置，不仅仅和hash函数有关，还与之前已经存储的键值对有关。

3. rehash
   所谓rehash，就是目前的数组中已经存放了太多的键值对，再怎么进行冲突避免，都还是存在大量冲突，那么直观的解决方式就是另外开辟一个空间相对较大一点的数组，再将之前存放的键值对搬移到新的数组中，这就是rehash的概念。

---

接下来则是对于redis中字典这一数据结构的解析。redis的字典也够是层层递进的，从最基本的键值对数据结构到最终的字典结构，他们就是利用了上述关于哈希表的基本知识进行逐层构建。

dictEntry

dictEntry就是对于键值对进行抽象的数据结构，代码如下，并加入了一定的注释：

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值，可以保存不同的类型
    struct dictEntry *next; // 使用独立链的桶结构，因此使用next指针构成链表
} dictEntry;

dictType

定义一个哈希表，就必须要定义它的增删查改的规则，而dictType数据结构就包含了用于这些操作的函数指针。另外，privdata是这些函数的可选入参值

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key); // hash函数，计算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;

dictht

dictht则是对于哈希表的抽象数据结构，包含了我们在上面提到过的数组，用于存储不同的dictEntry(键值对)，当然，为了操作更为灵活，所以将数组改为了存储dictEntry指针:

typedef struct dictht {
    dictEntry **table; // 存储空间
    unsigned long size; // 指示存储空间的桶个数
    unsigned long sizemask; // 等于size-1，用于计算hash时计算桶下标
    unsigned long used; // 存储空间中已经存储的键值对个数
} dictht;

dict

dict则是最终的字典数据结构，结构中保存了各类会用到的属性。这里特别需要提到的就是rehash。redis中对于rehash采取渐进式的方法，即不会一次性将原来表中的所有键值对全部迁移，而是按照下标的顺序，每进行一次增删查改，就迁移一个桶单元，而rehashidx就是用于记录目前需要迁移的是哪一个桶。所以rehashidx==1就代表目前并没有进行rehash(因为桶单元的下标始终大于等于0嘛!)

typedef struct dict {
    dictType *type; // 定义增删查改的操作
    void *privdata; // 传给type的入参
    dictht ht[2]; // 哈希表
    long rehashidx; // 用于记录rehash时的进程
    unsigned long iterators; // 记录迭代器数量
} dict;

---

源码阅读笔记

1. rehash的实现

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    // 因为在rehash的过程中可能遇到空桶，如果还是一样的标准，固定处理完n个桶旧返回，
    // 其实挺浪费的，因为空桶其实并不需要处理
    // 所以每次执行dictRehash对于空桶的数量的处理上限变为n的十倍
    // 就是此处的empty_visits了；
    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) { // de实际上就是一个由多个键值对entry构成的链表
            uint64_t 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]; // 将de插入到新链表(新桶)的表头
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde; // de重新指向旧链表(旧桶)的下一个entry
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++; // 当前第rehashidx个桶已经迁移完毕，因此下标指向下一个桶
    }

---

待补充