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住的现象，保证服务可用。
