Redis中，字典是基础结构。Redis数据库数据、过期时间、哈希类型都是把字典作为底层结构。
字典的结构
哈希表
哈希表的实现代码在：dict.h/dictht，Redis的字典用哈希表的方式实现。
typedefstructdictht{ //哈希表数组，俗称的哈希桶(bucket)dictEntry**table;//哈希表的长度unsignedlongsize;//哈希表的长度掩码，用来计算索引值，保证不越界。总是size-1//h=dictHashKey(ht,he-key)n.sizemask;unsignedlongsizemask;//哈希表已经使用的节点数unsignedlongused;}dictht;table是一个哈希表数组，每个节点的实现在dict.h/dictEntry，每个dictEntry保存一个键值对。size属性记录了向系统申请的哈希表的长度，不一定都用完，有预留空间的。sizemask属性主要是用来计算索引值=哈希值sizemask，这个索引值决定了键值对放在table的哪个位置。它的值总是size-1，其实我有点不明白为啥计算的时候不直接用size-1，知道的大佬请明示。used属性用来记录已经使用的节点数，size-use就是未使用的节点啦。下图展示了一个大小为4的空哈希表结构，没有任何键值对
哈希节点
哈希表dictht的table的元素由哈希节点dictEntry组成，每一个dictEntry就是一个键值对
typedefstructdictEntry{ //键void*key;//值union{void*val;uint64_tu64;int64_ts64;doubled;}v;//下一个哈希节点，用于哈希冲突时拉链表用的structdictEntry*next;}dictEntry;next指针是用于当哈希冲突的时候，可以形成链表用的。后续会将
字典
Redis的字典实现在：dict.h/dict。
typedefstructdict{ //哈希算法dictType*type;//私有数据，用于不同类型的哈希算法的参数void*privdata;//两个哈希表，用两个的原因是rehash扩容缩容用的dicththt[2];//rehash进行到的索引值，当没有在rehash的时候，为-1longrehashidx;/*rehashingnotinprogressifrehashidx==-1*///正在跑的迭代器unsignedlongiterators;/*numberofiteratorscurrentlyrunning*/}dict;//dictType实际上就是哈希算法，不知道为啥名字叫dictTypetypedefstructdictType{ //hash方法，根据key计算哈希值uint64_t(*hashFunction)(constvoid*key);//复制keyvoid*(*keyDup)(void*privdata,constvoid*key);//复制valuevoid*(*valDup)(void*privdata,constvoid*obj);//key比较int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);//销毁keyvoid(*keyDestructor)(void*privdata,void*key);//销毁valuevoid(*valDestructor)(void*privdata,void*obj);}dictType;dictType属性表示字典类型，实际上这个字典类型就是一组操作键值对算法，里面规定了很多函数。privdata则是为不同类型的dictType提供的可选参数。如果有需要，在创建字典的时候，可以传入dictType和privdata。
dict.c
//创建字典，这里有type和privdata可以传dict*dictCreate(dictType*type,void*privDataPtr){dict*d=zmalloc(sizeof(*d));_dictInit(d,type,privDataPtr);returnd;}//初始化字典int_dictInit(dict*d,dictType*type,void*privDataPtr){_dictReset(d-ht[0]);_dictReset(d-ht[1]);d-type=type;d-privdata=privDataPtr;d-rehashidx=-1;d-iterators=0;returnDICT_OK;}下图是比较完整的普通状态下的dict的结构(没有进行rehash，也没有迭代器的状态)：
#哈希算法当字典中需要添加新的键值对时，需要先对键进行哈希，算出哈希值，然后在根据字典的长度，算出索引值。
//使用哈希字典里面的哈希算法，算出哈希值hash=dict-type-hashFunction(key)//使用sizemask和哈希值算出索引值idx=hashd-ht[table].sizemask;//通过索引值，定位哈希节点he=d-ht[table].table[idx];哈希冲突
哈希冲突指的是多个不同的key，算出的索引值一样。
Redis解决哈希冲突的方法是：拉链法。就是每个哈希节点后面有个next指针，当发现计算出的索引值对应的位置有其他节点，那么直接加在前面节点后即可，这样就形成了一个链表。
下图展示了{k1,v1}和{k2,v2}哈希冲突的结构。假设k1和k2算出的索引值都是3，当k2发现table[3]已经有dictEntry{k1,v1}，那就dictEntry{k1,v1}.next=dictEntry{k2,v2}。
rehash
随着操作的不断进行，哈希表的长度会不断增减。哈希表的长度太长会造成空间浪费，太短哈希冲突明显导致性能下降，哈希表需要通过扩容或缩容，让哈希表的长度保持在一个合理的范围内。Redis通过ht[0]和ht[1]来完成rehash的操作，步骤如下：
为ht[1]分配空间，分配的空间长度有两种情况：扩容：第一个大于等于ht[0].used*2的\(2^n\)的数，例如ht[0].used=3，那么分配的是距离6最近的\(2^3=8\)缩容：第一个大于等于ht[0].used/2的\(2^n\)的数，例如ht[0].used=6，那么分配的是距离3最近的\(2^2=4\)将h[0]上的键值对都迁移到h[1]，迁移的时候都是重新计算索引值的。由于h[1]的长度较长，之前在h[0]拉链的元素大概率会被分到不同的位置。ht[0]所有的键值对迁移完之后，h[0]释放，然后h[0]=h[1]，并把h[1]清空，为下次rehash准备渐进式rehash
上面说的rehash中的第二步，迁移的过程不是一次完成的。如果哈希表的长度比较小，一次完成很快。但是如果哈希表很长，例如百万千万，那这个迁移的过程就没有那么快了，会造成命令阻塞！下面来说说，redis是如何渐进式地将h[0]中的键值对迁移到h[1]中的：
为h[1]开辟空间，字典同时持有h[0]和h[1]字典中的rehashidx维护了rehash的进度，设置为0的时候，开始rehash字典每次增删改查的时候，除了完成指定操作之外，还会顺带把rehashidx上的整条链表迁移到h[1]中。迁移完之后rehashidx+1随着字典的不断读取、操作，最终h[0]上的所有键值对都会迁移到h[1]中。全部迁移完成之后rehashidx=-1这种渐进式rehash的方式的好处在于，将庞大的迁移工作，分摊到每次的增删改查中，避免了一次性操作带来的性能的巨大损耗。缺点就是迁移过程中h[0]和h[1]同时存在的时间比较长，空间利用率较低。
下面一系列的图，演示了字典是如何渐进式地rehash(图片来自《Redis设计与实现》图片集)