redis-字典

redis所使用的C语言并没有内置丰富的数据结构，因而redis实现了很多数据结构，本文主要介绍字典。

字典又叫映射，是一种表示键值对的数据结构，在redis里应用广泛，redis里面的数据库就是用字典实现的。而字典的底层实现是hash表。

typedef struct dict {

    dictType *type;

    void *privdata;

    dictht ht[2];

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    int iterators; /* number of iterators currently running */

} dict;

字典数据结构，包含两个hash表，用于rehash，rehashidx用于标识rehash的进度。

typedef struct dictht {

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

 } dictht;

hash表数据结构，table是保存dictEntry *的数组，数组中每个成员指向一个bucket。hash表使用链地址法解决键冲突。size记录hash表的大小，used记录hash表中节点的数量。根据used/size的值来进行rehash。使用murmurhash2算法计算hash值。

rehash的步骤如下：

1）为字典的ht[1]分配空间，空间的大小分为扩展和收缩两种，扩展：第一个大于等于ht[0].used*2的2的n次幂，收缩：第一个大于等于ht[0].used的2的n次幂。

2）将ht[0]中的键值对rehash到ht[1]中，采用渐进式rehash，每次对执行新操作都会将rehashidx上的键值rehash到ht[1]中，并对rehashidx加1，写操作会在ht[1]上执行，保证ht[0]上只减不增。

3）rehash执行完成，将rehashidx的值设置为-1。

渐进式rehash将一个长时间的rehash过程切成许多小任务，并且在处理一个redis命令时完成一个小任务，虽然在rehash期间会影响redis的读写性能，但不会有长时间hang住的现象，保证服务可用。