字典是一种用于存储键值对的抽象数据结构。由于C语言没有内置字典作为数据结构，所以Redis自己构建了字典实现。在Redis中，字典用于实现底层数据库。对数据库的CURD操作也是基于对字典的操作。字典除了用来表示数据库外，也是hashkey的底层实现之一。当一个哈希键包含很多键值比较，或者键值对中的元素是比较长的字符串时，Redis会适配字典作为哈希键的底层实现。1字典的实现Redis的字典是使用哈希表作为底层实现的。一个哈希表中可以有多个哈希表节点，每个哈希表节点在字典中存储一个键值对。1.1哈希表Redis字典使用的哈希表结构：typedefstructdictht{dictEntry**table;//哈希表数组unsignedlongsize;//哈希表大小unsignedlongsizemask;//hashtablesizemask代码，用于计算使用的索引unsignedlong；//哈希表的节点数}dicttht;表属性是一个数组。数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存一个键值对。size属性记录了哈希表的大小，即表数组的大小。used属性记录哈希表中现有节点（键值对）的数量。sizemask属性的取值总数等于size-1。此属性与散列值一起确定应将键放置在表数组中的哪个索引。图1显示了一个大小为4的空哈希表。1.2哈希表节点哈希表节点由dictEntry结构表示，每个dictEntry结构存储一个键值对：typedefstructdictEntry{void*key;//键联合{void*val;//指向值类型的指针uint64_tu64;//值类型的无符号整数类型int64_ts64;//值类型的有符号整数类型doubled;//值类型的浮点型}v;//值结构dictEntry*next;//向下指向Hash表节点，形成链表}dictEntry;key属性保存键，而v属性保存值。下一个属性是指向另一个哈希表节点的指针。这个指针可以连接多个具有相同哈希值的键值对，解决键冲突的问题。图2显示了具有相同索引的两个键k1和k0通过next指针连接在一起的情况。1.3字典字典的结构：typedefstructdict{dictType*type;//类型特定函数void*privdata;//私有数据字典ht[2];//哈希表（二）longrehashidx;//记录rehash进度符号的。值为-1表示尚未在迭代器中执行rehash；//当前正在迭代的迭代器数量}dict;dictType的结构如下：typedefstructdictType{//计算哈希值的函数unsignedint(*hashFunction)(constvoid*key);//复制密钥的函数void*(*keyDup)(void*privdata,constvoid*key);//复制值的函数void*(*valDup)(void*privdata,constvoid*obj);//比较键的函数int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key2);//销毁密钥的函数void(*keyDestructor)(void*privdata,void*key);//销毁值函数void(*valDestructor)(void*privdata,void*obj);}dictType;设置type属性和privdata属性，为不同类型的键值对创建多态字典。其中：type属性是指向一个dictType结构体的指针，每个dictType结构体持有一堆操作特定类型键值对的函数。Redis为用于不同目的的字典设置了不同类型特定的函数。privdata属性包含需要传递给那些特定于类型的函数的可选参数。ht属性是一个包含两个哈希表的数组。通常，字典只使用ht[0]，而ht[1]只在ht[0]被重新散列时使用。rehashidx属性，记录了当前rehash的进度，如果当前没有rehash在进行，其值为-1。至于什么是rehash，不用急，后面会详细讲解。图3是没有rehash的字典：2插入算法当向字典中添加新的键值对时，Redis会先根据键值对的key计算哈希值和索引值，然后根据索引value,insert将包含新键值对的哈希表节点放置在哈希表数组指定的索引处。具体算法如下：#使用字典设置的哈希函数计算key的哈希值hash=dict->type->hashFunction(key);#利用哈希表的sizemask属性和哈希值计算索引值#根据不同情况，使用ht[0]或ht[1]index=hash&dict[x].sizemask;如图4所示，如果向字典中添加键值对[k0,v0]，则插入顺序为：hash=dict-type->hashFunction(k0);index=hash&dict->ht[0].sizemask;#8&3=0计算得到，[k0,v0]键值对应该放在哈希表数组中索引为0，如图5所示：2.1键冲突当两个或多个键被分配到同一个索引时的哈希表数组，我们认为这些键有冲突。Redis的哈希表使用链地址法来解决冲突。每个哈希表节点都有一个next指针，多个哈希表节点可以使用next指针组成单向链表，多个分配到同一个索引的节点可以使用next指针链接形成单向链表列表。例如，假设我们要将[k2,v2]键值对添加到图6所示的哈希表中，计算出k2的索引值为2，与k1冲突，所以这里使用next指针连接k2和k1所在的节点，如图7所示。3rehash和progressiverehash随着字典的运行，哈希表上报的键值对数量会逐渐增加或减少，以保持哈希表的负载因子在一个合理的范围内，当哈希表上报的键值对数量过多或过少时，程序需要对哈希表进行相应的扩容或缩容。这种扩展或收缩过程称为重新散列。对于负载因子，可以通过以下公式计算：#负载因子=哈希表中保存的节点数/哈希表的大小load_factor=ht[0].used/ht[0].size;3.1哈希表的扩容哈希表的扩容，源码如下：if(d->ht[0].used>=d->ht[0].size&&(dict_can_resize||d->ht[0].used/d->ht[0].size>dict_force_resize_ratio)){returndictExpand(d,d->ht[0].used*2);}当满足以下条件时，程序会自动启动扩展哈希表操作：服务器当前没有执行rehash；哈希表中存储的节点数大于哈希表的大小；dict_can_resize参数为1，或者加载因子大于设置比例（默认为5）；shrink哈希表的收缩，源码如下：inthtNeedsResize(dict*dict){longlongsize,used;大小=dictSlots(dict);//ht[2]使用的两个哈希表的大小之和=dictSize(dict);//ht[2]两个哈希表保存的节点数之和#DICT_HT_INITIAL_SIZE默认为4，HASHTABLE_MIN_FILL默认为10。return(size>DICT_HT_INITIAL_SIZE&&(used*100/size
