字典是一种用于保存键值对的抽象数据结构。Redis 的数据库就是使用字典作为底层实现的。
字典的实现
在 Redis 中，字典使用哈希表作为底层实现。具体结构看以下代码，其结构和 Java 中的 HashMap 很像，解决哈希冲突的方法也是一致的。
哈希表
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//size-1 ，便于计算哈希值的取模运算
unsigned long hashmask;
//哈希表中已有结点
unsigned long used;
}dictht;
字典.png
（上图引自 Redis 设计与实现）
字典
typedef struct dict{
//方便根据不同类型应用不同函数
dictType *type;
void *privdata;
//哈希表，两张是为了渐进式rehash
dictht ht[2];
//rehash时>=0,不然为 -1。用于指示当前rehash的索引
int rehashidx;
}dict;
哈希键冲突
当发生哈希键冲突时，使用链地址法解决，即将同一哈希值的 Entry 构成链表，并把新的放在前面。
rehash
扩容时，会令 ht[1] 的大小变为第一个大于等于 ht[0].used*2 的 2n。然后根据扩容后的大小重新计算哈希值，并将 ht[0] 的值放入 ht[1] 中，再令 ht[0] 指向 ht[1]。
那么什么时候会 rehash 呢？
- 服务器当前没有执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于一。
- 服务器当前在执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于五。
其中，哈希表负载因子 load_factor = ht[0].used/ht[0].size。
渐进式 rehash
渐进式 rehash 是指分多次、渐进式地将 ht[0] 里的所有键值对全部 rehash 到 ht[1]。
具体过程如下：
- 在字典中维护一个索引计数器变量 rehashidx ，设为 0
- rehash 期间，每次对字典进行添加、删除、查找或者更新操作时，程序除了执行指定操作外，还会将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 上，rehash 完成后，rehashidx 加一
- 随着操作不断进行，最终 ht[0] 上的所有键值对都会被 rehash 到 ht[1] 上， rehashidx 设为 -1 。
需要注意的是在 rehash 期间，对字典的删除、查找和更新会先在 ht[0] 上操作，没有找到的话再去 ht[1] 执行操作。而对于插入操作，很明显是在 ht[1] 上完成的。因为只有这样才能保证 ht[0] 大小不断减小，最终变为空表。
