Redis里字典（dict）主要用在两个场景：

1、保存数据库的键值对2、Hash类型的底层实现之一（另一种是通过压缩列表实现）

数据结构定义

字典的定义如下：

/* * 字典 * * 每个字典使用两个哈希表，用于实现渐进式 rehash */typedef struct dict {    // 特定于类型的处理函数    dictType *type;    // 类型处理函数的私有数据    void *privdata;    // 哈希表（2 个）    dictht ht[2];    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行    int rehashidx;    // 当前正在运作的安全迭代器数量    int iterators;} dict;

（以上注释来自《Redis设计与实现》）

哈希表dictht的定义如下：

/* * 哈希表 */typedef struct dictht {    // 哈希表节点指针数组（俗称桶，bucket）    dictEntry **table;    // 指针数组的大小    unsigned long size;    // 指针数组的长度掩码，用于计算索引值    unsigned long sizemask;    // 哈希表现有的节点数量    unsigned long used;} dictht;

哈希表用链地址法来解决碰撞。这里table是个二级指针，每个指针指向了对应索引的节点连成的链表。

哈希表节点定义如下：

/* * 哈希表节点 */typedef struct dictEntry {    // 键    void *key;    // 值    union {        void *val;        uint64_t u64;        int64_t s64;    } v;    // 链往后继节点    struct dictEntry *next;} dictEntry;

哈希表性能问题

哈希表的性能取决于大小（dictht的size属性）与保存节点数量（dictht的used属性）之间的比率：

1、哈希表的大小与节点数量，比率在 1:1 时，哈希表的性能最好；2、如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势便不复存在。

rehash解决性能问题

之所以前面定义dict的时候，用了两个哈希表dictht，是因为，在哈希表的节点比较多的时候，在第一个哈希表ht[0]上查找比较慢，这时，就需要对哈希表重新调整，也就是rehash。

关于rehash，有以下几点需要注意：1、创建一个更大的哈希表，然后赋给ht[1]，将ht[0]上的节点移动到ht[1]上，移动结束后，将ht[1]设置为ht[0]。2、rehash分主动和被动，主动是指，Redis的常规服务定时去检查并且rehash，被动是指，用户在添加新键值对时触发rehash。3、当哈希表比较大的时候（表大，节点多），进行rehash可能会比较慢，这个时候，rehash不是一步阻塞完成的，是“渐进式”的，也就是分几次完成，也就是，我这次移动1个索引的全部节点，下次常规服务里移动另一个索引的节点，以这种方式来完成rehash。4、在rehash的过程中，会同时使用到两个哈希表，新添加进来的节点是放在ht[1]上。个人猜测是因为，ht[1]是rehash的最终结果，如果添加在ht[0]上，还需要多做一步，把ht[0]上的移动到ht[1]上。5、在查找删除的时候，会同时操作ht[0]和ht[1]，因为在rehash的过程中，哈希表分布在这两个表上。

收缩字典防止浪费资源

当比值 used*100/size 小于10的时候，也就是字典的填充率小于10%的时候，就收缩字典，收缩过程与rehash过程类似，不过ht[1]比ht[0]小。收缩是由常规服务检查触发的，用户不会触发收缩。

参考：

1、《Redis设计与实现》