dict是一个key-value存储的hash map，实际上redis对外提供的key-value服务的底层数据结构就是dict。hash map由一个hash算法来确定数据的在数组中的放置位置，dict使用开链法解决冲突。
dict的数据结构：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
unsigned int (*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;
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
dictEntry是key-value中value的存储节点，其中存储了key、v和next，next指向下一个节点用于解决hash冲突
dictType定义了一组函数指针用来指定hash算法、比较、复制和销毁等方法。
dictht定义了一个哈希表，其中size是哈希表数组的大小，sizemask用于和hash函数一同计算一个key-value对在数组中的索引位置。used记录保存的key-value对的数量。
dict中包含两个哈希表dictht，当进行rehash操作时会用到ht[1]，由rehashidx记录当前rehash的进度，这个进度即hash数组的索引号，如果没有rehash操作则rehashidx的值为-1。
rehash操作：随着对redis的操作，会有大量的数据加入到hash表中。遇到这情况都会进行rehash操作，重新确定hash数组的大小，放置键值对数据。触发rehash操作是由一个负载因子(load factor)决定的，计算方法也比较简单：load factor = used / size。
rehash的过程如下：
-
为ht[1]分配空间
-
将ht[0]的数据迁移到ht[1]
-
清空ht[0]，交换ht[0]和ht[1]的指针
可以看到最终结果数据还是在ht[0]中访问。
rehash分两种：
自然rehash：需满足used/size >= 1 && dict_can_resize条件时触发（dict_can_resize表示目前没有执行BGSAVE或BGREWRITEAOF命令）
强制rehash：需满足load factor>dict_force_resize_ratio(默认值为5)条件时触发
分配的空间大小根据公式ht[0].used*2 < min(2^n)，设置为min(2^n)
rehash过程采用了渐进式rehash，主要是为了性能考虑，不能一次将全部或大量的键值对rehash到ht[1]中，而是每次将一个hash数组索引号下的所有键值对rehash到ht[1]中，下一次rehash时再执行下一个索引号，直到所有的索引号全部执行完毕，完成rehash操作。在一次渐进式rehash中，如果连续发现10个索引号下都是空的，则只修改rehashidx，退出这次渐进式rehash过程，这也是从性能上考虑。
另外，dict还提供了一个dictRehashMilliseconds方法，由服务器常规任务程序执行，这时一次渐进式rehash过程处理100个索引号，直到耗时大于1ms时结束。
在rehash过程中，当有新节点插入到dict中时，会直接插入到ht[1]中，而非ht[0]中，每次渐进式rehash步骤，会把ht[0]中的键值对放到ht[1]中，因此可知，ht[0].used在rehash时只减不增，直至为0。
dict对外提供的接口包括增、删、改、查、创建和销毁等。