三、Redis-字典

前言

字典，又称符号表、关联数组或映射，是一种保存键值对的抽象数据结构。

字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点

哈希表

Redis字典所使用的哈希表是这样的

struct dictht{
    //哈希表数组
    dictEntry **table;
    
    //哈希表大小
    unsigned long size;
    
    //哈希表大小掩码，用于计算索引值
    //总是size-1
    unsigned long sizemask;
    
    //该哈希表已有节点的数量
    unsigned long used;
}

table是一个数组，数组中的每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry结构保存着一个键值对。
size 记录了哈希表的大小，即是table数组的大小
used 记录哈希表目前已有节点（键值对）的数量
sizemask的值总是等于 size-1 ，这个属性和哈希值一起决定一个键有个被放到table数组的哪个索引上面

哈希表节点

我们来看看 dictEntry 是如何定义的

struct dictEntry{
    //键
    void *key;
    
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
}dictEntry;

key：保存着键值对中的键
v：保存着键值对中的值，其中键值对的值可以是一个指针(*val)，或者是一个uint64_t整数，又或者是一个int64_t整数
next：指向另一个哈希表节点的指针（链地址法）

字典

上面我们说了哈希表和哈希表节点，哈希表是一个个的哈希表节点，而我们的字典就是基于哈希表的，我们来看看。

struct dict{
    //类型特定函数
    dictType *type;
    
    //私有数据
    void *privdata;
    
    //哈希表
    dictht ht[2];
    
    //rehash 索引
    //当 rehash不在进行时，值为-1
    int trehashidx;
}dict;

我们发现上面的ht是ht[2]，就说明有两张哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 进行rehash时使用，而 trehashid 就是 rehash 的进度，如果目前没有在 rehash，那么它的值为-1；

哈希算法

当我们需要将一个键值对添加到字典中时，程序会先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希节点放到哈希表数组的指定索引上面。

在Redis中，它使用 MurmurHash2 算法计算键的哈希值

解决哈希冲突

在HashMap中使用的链地址法解决哈希冲突，而Redis中也是使用链地址法解决哈希冲突的，但是Redis中并没有红黑树机制。

而且dictEntry节点组成的链表没有指向链表表尾的指针，所以总是将新节点加入到链表的表头位置(复杂度为O(1))

rehash

当哈希表保存的键值对逐渐增多或者减少，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩容和收缩。而收缩和扩容可以通过执行 rehash 操作来完成。

由于ht[1] 刚开始是null，我们首先要为其分配空间，分配空间的大小取决于要执行的操作，以及ht[0]当前包含的键值对数量。如果是扩容操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used*2的2的n次方幂，如果是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used的2的n次方幂；
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1]；上面，rehash的时候会重新计算键的哈希值和索引值，所以原来在一条链的节点，rehash后不一定在同一条链上；
当 ht[0] 的所有键值对迁移到了 ht[1] 之后，ht[0] 变为空表，然后将 ht[1] 设置为 ht[0]

渐进式rehash

上面我们说的 rehash 动作并不是一次性、集中式的完成的，而是分多次、渐进式的完成的。你想一下，当数据很少时，我们一次性 rehash 还可以，但是如果数据很多有几亿个数据，我们一次性 rehash就会很慢，可能会导致服务器在一段时间内停止服务。

rehash的详细步骤：

为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；
在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0 ，表示 rehash 工作正式开始；
在 rehash 期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成后，程序将 rehashidx 属性的值增1；
随着字典的不断执行，最终 ht[0] 的所有键值对都会被 rehash 到 ht[1]，这是将 rehashidx的值设置为-1，表示 rehash 操作已经完成。

在渐进式rehash的过程中，插入元素的时候总是会插入到 ht[1] 中，这样就保证了 ht[0] 包含的键值对数量只会减少不会增加，最终 ht[0] 会变为空表。