redis 字典

字典

字典又称符号表、关联数组、映射，是保存k-v结构的抽象数据结构。

redis中字典是常用数据结构，数据库命令就是字典结构，还有哈希对象，底层也是字典，但是有条件。

字典的实现

redis字典所使用的哈希表在dict.h中第69行定义：

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

table属性是一个数组，数组每一个元素都是指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
size记录哈希表的大小，也是table数组的大小。
used属性记录哈希表目前已有节点(键值对)的数量。

哈希表节点

哈希表节点由dictEntry结构定义，每个dictEntry保存着一个键值对：

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

key属性保存键，v保存值。v的值可以是一个指针、int、double类型的值。
next 属性保存指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此解决键冲突。

字典

redis的字典由dict.h第76行dict定义：

typedef struct dict {
    dictType *type;    // 类型特定函数
    void *privdata;    // 私有数据
    dictht ht[2];    // 哈希表
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    // rehash索引，当rehash不在进行时为-1
    unsigned long iterators; /* number of iterators currently running */
} dict;

ht属性包含两个项的数组，每个项是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]进行rehash时使用。
rehashidx属性记录rehash目前的进度，没有进行rehash时为-1.

哈希算法

字典插入新的键值对，首先根据键计算出哈希值和索引值，根据索引值将包含键值对的哈希表节点放到哈希表数组的指定索引上面。

键冲突

当两个或两个以上的键被分配到哈希表数组的同一个索引上面，就发生了键冲突。

redis哈希表使用链地址法来解决键冲突，每个哈希表节点有一个next指针，将多个节点构成一个单向链表(头插法)。这样就解决了键冲突问题。

rehash(重新散列)

随着操作的变多，哈希表保存的键值对会增多或减少，为了让哈希表的负载因子(load factor)保持在一个合理的范围之内，会对哈希表进行扩展和收缩。

扩展和收缩哈希表的工作都由rehash操作完成，redis对字典的哈希表执行rehash操作的步骤：

为字典的ht[1]哈希表分配空间，大小取决于要执行的操作，以及ht[0]哈希表的数量(即ht[0].used属性).
如果是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方。

如果是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方。

将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，将键值对放到ht[1]哈希表指定的位置上。
当ht[0]全部迁移完后，ht[0]变为空表，释放ht[0]，将ht[1]设为ht[0]，并在ht[1]创建一个空表哈希表，为下一次rehash准备。

哈希表的扩展与收缩

当满足以下任意一个条件时，会自动对哈希表扩展：

服务器目前没有在执行bgsave命令或bgrewriteaof命令，且哈希表负载因子大于等于1。
服务器目前在执行bgsave命令或bgrewriteaof命令，且哈希表负载因子大于等于5。

哈希表负载因子可通过公式计算得出：

#负载因子 = 哈希表已保存节点数 / 哈希表大小
load_factor = ht[0].used / ht[0].size

为什么要根据bgsave命令或bgrewriteaof命令来调整负载因子大小？
因为当执行这两个命令时，服务器会创建子进程，而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程使用效率，所以在子进程存在期间，服务器会提高执行扩展操作的负载因子，从而尽可能避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度的节约内存。

收缩：当负载因子小于0.1，会自动收缩。

渐进式rehash

redis对哈希表扩展和收缩需要将ht[0]中的键值对rehash到ht[1]中，但是这个rehash动作不是一次性、集中完成的，而是分多次、渐进式完成。

为什么要渐进式？
原因是如果ht[0]保存4个键值对，服务器可以在瞬间rehash到ht[1]；但是，如果ht[0]保存了400万或4000万甚至4亿键值对，那么要一次性全部rehash到ht[1]的话，庞大的计算可能会导致服务器在一段时间内停止服务。

因此，为了避免rehash对服务器性能造成影响，采用渐进式、多次rehash：

为ht[1]哈希表分配空间，让字典同时保持两个哈希表；
在字典中维持一个计数器变量rehashidx，值设为0，表示rehash工作开始。
在rehash操作期间，每次对字典执行增删改查操作时，除了执行指定操作外，还会顺带将ht[0]哈希表rehashidx对应的索引上的键值对rehash到ht[1]，当rehash操作完成后，将rehashidx属性加1。
随着字典操作的执行，最终在某个时间点上，ht[0]所有键值对rehash到ht[1]，此时将rehashidx值设为-1，表示rehash结束。

渐进式rehash期间的哈希表操作

因为在执行渐进式rehash操作期间，字典会同时使用ht[0]和ht[1]两个哈希表，所以在这期间，插入键值对一律被保存到ht[1]哈希表中，ht[0]不在进行插入操作，保证ht[0]只减不增，最终变为空表。而查找、删除、更新操作会对两个表进行，先在ht[0]中查找，没找到则在ht[1]中查找，诸如此类。

重点回顾

字典被广泛应用，包括数据库和哈希键。
redis字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，一个rehash使用。
字典使用MurmurHash2算法来计算键的哈希值。
哈希表使用链地址法来解决键冲突，哈希表节点的指针，构建一个单向链表。
哈希表扩展与收缩时，将键值对rehash到新的哈希表，并且rehash过程不是一次性的，而是渐进式分步完成。

字典