前言

我们知道redis的value的底层结构是由动态简单字符串、整数数组、双向链表、跳表、压缩列表、哈希组成，而key到value的访问是通过哈希表实现的

思考

1.为什么哈希表的操作变慢了
2.redis如何处理哈希冲突

Dict

redis的哈希表是使用dict实现key到value的快速访问的
源码中对于其定义如下(src/dict.h)：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators; 
} dict;

1.type是一个指向dict的指针，它通过自定义的方式使得dict的key和value能够存储任何类型的数据。

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;

其中hasFunction就是所谓的key到value的映射函数，
keyDup和valDup是key和value的拷贝函数，keyCompare是两个key的比较函数，根据key查找时用到，另外是两个的析构函数
2.privData为私有数据指针由调用这在创建时传入
3.ht[2]为两个哈希表,ht[1]只有在重哈希的时候才会有用

typedef struct dictht {
    dictEntry **table;//key的哈希值最终映射到这个数组的某个位置上（对应一个bucket）。如果多个key映射到同一个位置，就发生了冲突，那么就拉出一个dictEntry链表
    unsigned long size;//标识table长度
    unsigned long sizemask;//用于将哈希值映射到table的位置索引
    unsigned long used;//记录dict中现有的数据个数
} dictht;

其中dictEntry:

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; //数据地址
    struct dictEntry *next;//下一项的指针
} dictEntry;

4.rehashidx为重hash索引

小结

哈希表（Dict），实际是一个数组(ht[0])，数组中的每个元素称为一个哈希桶(dictht )，每个哈希桶保存了键值对数据(dictEntry)，哈希桶中的元素都是指向他们的指针。dictEntry元素中保存了key和v的指针，分别指向实际的键和值，这样即使值是一个集合也可以被找到

哈希冲突

ht[0]我们称为全局哈希表，我们可以用O(1)的时间复杂度快速找到对应的dictEntry，但是既然是哈希计算那么随着数据量的增加肯定存在一个哈希冲突的问题，即两个不同的key计算出相同的value
redis的处理方式就是链式哈希，即在dictht的table数组中，对冲突的元素用一个链表来保存，他们之间依次指针连接，即dictEntry中的next指针，因为指针的查找需要遍历因此链长度越长，查找就越费事

渐进式重哈希

redis解决上面问题的方法就是利用ht[1]进行渐进式重哈希(重新计算哈希值)，如何重哈希？如下:
1.给ht[1]分配更大的空间
2.将ht[0]的数据重新拷贝映射到ht[1]
3.释放ht[0]空间
但是一次性拷贝所有数据，当数据量非常大的时候就会造成线程的阻塞，为避免这个问题redis就采用了渐进式，即在重哈希的第二步中，当一个请求进来(假设处理数据在ht[0][i]的位子上)，每处理一个请求，就将ht[0][0]到ht[0][i]的这一段数据拷贝到ht[1]中并更新dict的rehashidx，处理下一个请求时就从rehashidx位子开始重复上一步。
将一次性的大量拷贝分摊到多次处理请求的过程中，避免了耗时操作

//由_dictRehashStep判断是否要重哈希
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}
//每次至少重置n个哈希数据哈希
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; 
    if (!dictIsRehashing(d)) return 0;
//每一步都将ht[0]上某一个bucket（即一个dictEntry链表）上的每一个dictEntry移动到ht[1]上，它在ht[1]上的新位置根据ht[1]的sizemask进行重新计算
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        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;
        
            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;
//rehashidx记录了当前尚未迁移（有待迁移）的ht[0]的bucket位置
        d->rehashidx++;
    }

    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

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

总结

在redis中数据结构中，dict字典，就是hash表。都是通过链表的方式解决hash冲突。
redis dict使用渐进式rehash的好处是，避免保存大量数据的的dict在rehash时使redis一段时间内无法响应用户指令。
redis dict结构体包含两个hash表，ht[0]、ht[1]，其中ht[0]指向优先被使用的hash表，ht[1]指向扩容用的hash表，rehash使用dict结构体中的rehashidx属性辅助完成，rehashidx属性指向哪个slot，每次就将ht[0]的那个slot的元素移动到ht[1]中，然后自增rehashidx，直到遍历完整个hash表。由于不是一次性完成rehash，rehash进行时可能穿插着查找等操作，查找的过程是先从ht[0]中查找，若查找不到，则在ht[1]中查找元素。