深入理解Redis数据结构字典

　　字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。在字典中，一个键可以和一个值进行关联，这些关联的键和值称为键值对。键值对中键是唯一的，我们可以根据键key通过映射查找或者更新对应的值value。
　　很多高级开发语言有对应集合支持字典这种数据结构，比如Java中的Map集合。C语言并未内置字典这种数据结构，Redis构建了自己的字典实现。应用
　　字典在Redis中应用非常广泛，Redis数据库就是使用字典作为数据底层的实现。对数据的增、删、改、查操作也是建立在字典之上操作。
　　当执行命令：setmsghello
　　在数据库中创建一个键为msg，值为hello的键值对，这个键值对就用字典来实现的。创建其他数据类型的键值对，比如list、hash、set、sortset也是用字典来实现的。
　　处理用来表示数据中的键值对，字典还是hash数据类型底层实现之一，比如一个hash数据类型website，包含100个键值对，这些键值对中的键是网址名称，值是网页地址：redisHGETALLwebsite1）Redis2）Redis。io3）nacos4）nacos。io。。。。。
　　website键的底层就是一个字典，包好了100个键值对，例如：键值对中的键为Redis，值为Redis。io。键值对中的键为nacos，值为nacos。io。字典的实现
　　Redis字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点，每个哈希表节点保存字典中的键值对。哈希表
　　Redis字典使用的哈希表由dict。hdictht结构来表示：Thisisourhashtablestructure。Everydictionaryhastwoofthisasweimplementincrementalrehashing，fortheoldtothenewtable。typedefstructdictht｛table数组dictE哈希表的大小等于size1，用于计算索引值已有的键值对数量｝
　　注释：这是哈希表结构，每个字典有两个实现增量重散列，从旧的哈希表到新的哈希表。table属性的是一个数组，数组中的每个元素都指向哈希节点dictEntry，每个dictEntry结构都保存一个键值对。size记录了哈希表的大小，也就是table数组的大小。used属性记录了哈希表目前已有的键值对数量。sizemask的值等于size1，这个属性和哈希表一起决定键应该放在table数组的那个位置上。
　　下图展示一个大小为4空哈希表（没有包含任务的键值对）：
　　哈希表节点
　　哈希表节点使用dictEntry结构来表示，每个dictEntry结构都保存着一个键值对：typedefstructdictEntry｛键值union｛uint64tu64；int64ts64；｝v；指向下一个哈希表节点，形成链表structdictE｝dictE
　　其中：key保存键值v保持值，v可以是一个指针，可以是uint64t整数，也可以是一个int64t整数。next指向另一个哈希表节点的指针，这个指针将多个哈希值相同的键值对连接在一起，以此解决hash冲突的问题。
　　下图展示两个键的hash值相同的哈希表节点k0和k1，两者通过next指针连接在一起。
　　字典
　　Redis中的字典由dict。hdict结构表示：typedefstructdict｛类型特定的函数dictT私有函数哈希表dicththt〔2〕；rehash索引rehashingnotinprogressifrehashidx1numberofiteratorscurrentlyrunning｝type属性和privadata属性是针对不同类型的键值对，为创建多态的字典而设置。type是指向dictType结构的指针，每个dictType包含几组针对特定类型的键值对操作的函数，Redis会为用途不同的字典设置不同的函数。下图展示dictType字典类型：typedefstructdictType｛计算哈希值unsignedint（hashFunction）（constvoidkey）；复制键void（keyDup）（voidprivdata，constvoidkey）；复制值void（valDup）（voidprivdata，constvoidobj）；对比键int（keyCompare）（voidprivdata，constvoidkey1，constvoidkey2）；销毁键void（keyDestructor）（voidprivdata，voidkey）；销毁值void（valDestructor）（voidprivdata，voidobj）；｝dictTprivdata属性保存针对不同的类型操作的函数传的可选参数。ht〔2〕是包含两个数大小的数组，类型为dictht哈希表。字典只使用ht〔0〕哈希表，ht〔1〕只会对ht〔0〕哈希表进行rehash时使用。rehashidx记录了rehash的进度，如果目前没有进行的rehash，那么它的值为1。
　　下图为一个普通状态下（没有进行rehash）的字典：
　　哈希算法
　　当要将一个新的键值对添加到字典中，程序需要先根据键值对中的键计算出哈希值和索引值，然后根据索引值，将包含新键值的哈希表放在哈希表数组的指定索引上。
　　Redis计算哈希值和索引值的步骤如下：使用字典设置的哈希函数，计算键的哈希值。
　　hashdicttypehashFunction（key）使用哈希表的sizemask属性和哈希值，取余计算出哈希值。
　　indexdictht〔x〕。sizemaskhash
　　了解过HashMap底层原理的同学应该知道，上面计算索引值和HashMap找到索引下标的原理是类似的。
　　什么是取余运算？
　　取余就是计算两数相除的余数，比如一个数组长度为4，索引范围是03，需要放置0，1，7，放置如下图所示：
　　举个例子，要将一个键值对k0和v0添加到下方的空字典表中：
　　首先计算键的哈希值：hashdicttypehashFunction（key）
　　计算键k0的哈希值。假设计算出来的哈希值为8，然后计算索引值：indexdictht〔0〕。sizemaskhash380；
　　计算出键k0的索引值0，这表示键值对k0和v0的节点放置到哈希表数组下标0的位置上，如下图所示：
　　键冲突
　　当两个或者两个以上的计算出数组索引值一致时，就发生了键冲突。
　　Redis的哈希表采用链表法来解决键冲突，每个哈希表的节点都有一个next指针，多个哈希表节点用next指针组成一个单链表，被分配到同一个数组索引上的多个节点使用单向链表连接起来，这就很好的解决了键冲突的问题。
　　举个例子，程序要将一个键值对k2和v2添加到下图的哈希表中，并且计算k2的索引值为2，那么键k1和k2将发生冲突：
　　解决冲突的办法就是使用next指针将k2和k1所在的节点连接起来，如下图所示：
　　总结字典是一种映射的键值对数据结构，其中键是唯一的，通过唯一的键可以快速找到对应的值。字典包含广泛用在Redis数据库中。其中所有数据类型的键值对都使用字典作为底层实现。Hash类型的键值对也是基于字典实现。字典的结构包含一个字典，包含根据特定类型处理的函数dictType、两个哈希表ht〔2〕，字典只用到了ht〔0〕，遇到了扩容才会使用ht〔1〕。一个字典包含两个哈希表，每个哈希表dictht包含一个table数组，size记录数组的大小，sizemask等于size1，sizemask和哈希值决定数据存在在table的位置。used记录已有的键值对。哈希表节点dictEntry结构保存一个键值对，其中key保存键，V保存值，V可以是一个指针、可以是uint64t整数、也可以是int64t的整数。next是为了解决键hash冲突，两个键的计算出的索引在数组的同一个地方，就使用next指针连接在一起。新增一个键值对，首先通过调用dicttypehashFunction（key）计算键的哈希值，再和dictht的sizemask做取余操作，计算得到要存放table数组的索引位置。如果发生键冲突时，使用链表法将多个哈希节点通过next指针组成一个单链表。Redis字典的实现和Java中的HashMap数据结构有以下类似的点：确定索引位置：键首先使用哈希算法算出哈希值，再和数组的长度1做取余操作，确定存放数组的下标。解决hash冲突：两个键值计算的索引一致，采用链表法，将多个节点通过next指针连在一起。参考
　　Redis设计与实现