### dict数据结构 dict是一个用于维护key和value映射关系的数据结构，与很多语言中的Map或dictionary类似。Redis的一个database中所有key到value的映射，就是使用一个dict来维护的。dict本质上是为了解决算法中的查找问题(Searching)。 1.一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表，平常使用的各种Map或dictionary，大都是基于哈希表实现的。 2.dict也是一个基于哈希表的算法，跟java中的hashMap类似，用key计算出哈希值，并得到key在哈希表中的位置，再采用拉链法解决冲突，并在装载因子（load factor）超过预定值时自动扩展内存，引发重哈希（rehashing）。 为了能更清楚地展示dict的数据结构定义，用一张结构图来表示dict(字典)的构成。如下图：  数据结构代码 ~~~c #dict字典的数据结构 typedef struct dict{ dictType *type; //直线dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据 void *privdata; //私有数据，保存着dictType结构中函数的 参数 dictht ht[2]; //两张哈希表 long rehashidx; //rehash的标记，rehashidx=-1表示没有进行rehash，rehash时每迁移一个桶就对rehashidx加一 int itreators; //正在迭代的迭代器数量 } #dict结构中ht[0]、ht[1]哈希表的数据结构 typedef struct dictht{ dictEntry[] table; //存放一个数组的地址，数组中存放哈希节点dictEntry的地址 unsingned long size; //哈希表table的大小，出始大小为4 unsingned long sizemask; //用于将hash值映射到table位置的索引，大小为（size-1） unsingned long used; //记录哈希表已有节点（键值对）的数量 } ~~~ 上图就是Redis的dict(字典)数据结构，一个dict需要注意几点： （1）dict采用哈希函数对key取哈希值得到在哈希表中的位置(桶的位置)，采用拉链法解决hash冲突。 （2）两张哈希表（ht[2]）：只有在重哈希的过程中，ht[0]和ht[1]才都有效。而在平常情况下，只有ht[0]有效，ht[1]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。 （3）重哈希：跟HashMap一样当装载因子（load factor）超过预定值时就会进行rehash。dict进行rehash扩容，将ht[0]上某一个bucket（即一个桶上dictEntry链表）上的每一个链表移动到扩容后的ht[1]上(每次只移动一个链表，即渐进式rehash。原因是为了防止redis长时间的堵塞导致不可用)，触发rehash的操作有查询、插入和删除元素。rehashidx会记录每次需要移动链表bucket桶的位置(后面会详细讲解)。 （4）当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表），释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备