Redis中内部数据结构dict的作用是什么

本篇文章为大家展示了Redis中内部数据结构dict的作用是什么，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。dict的数据结构定义
为了实现增量式重哈希（incremental rehashing），dict的数据结构里包含两个哈希表。在重哈希期间，数据从第一个哈希表向第二个哈希表迁移。dict的C代码定义如下（出自Redis源码dict.h）：为了能更清楚地展示dict的数据结构定义，我们用一张结构图来表示它。如下。结合上面的代码和结构图，可以很清楚地看出dict的结构。一个dict由如下若干项组成：一个指向dictType结构的指针（type）。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。一个私有数据指针（privdata）。由调用者在创建dict的时候传进来。两个哈希表（ht[2]）。只有在重哈希的过程中，ht[0]和ht[1]才都有效。而在平常情况下，只有ht[0]有效，ht[1]里面没有任何数据。上图表示的就是重哈希进行到中间某一步时的情况。当前重哈希索引（rehashidx）。如果rehashidx = -1，表示当前没有在重哈希过程中；否则，表示当前正在进行重哈希，且它的值记录了当前重哈希进行到哪一步了。当前正在进行遍历的iterator的个数。这不是我们现在讨论的重点，暂时忽略。dictType结构包含若干函数指针，用于dict的调用者对涉及key和value的各种操作进行自定义。这些操作包含：hashFunction，对key进行哈希值计算的哈希算法。keyDup和valDup，分别定义key和value的拷贝函数，用于在需要的时候对key和value进行深拷贝，而不仅仅是传递对象指针。keyCompare，定义两个key的比较操作，在根据key进行查找时会用到。keyDestructor和valDestructor，分别定义对key和value的析构函数。私有数据指针（privdata）就是在dictType的某些操作被调用时会传回给调用者。需要详细察看的是dictht结构。它定义一个哈希表的结构，由如下若干项组成：一个dictEntry指针数组（table）。key的哈希值最终映射到这个数组的某个位置上（对应一个bucket）。如果多个key映射到同一个位置，就发生了冲突，那么就拉出一个dictEntry链表。size：标识dictEntry指针数组的长度。它总是2的指数。sizemask：用于将哈希值映射到table的位置索引。它的值等于(size-1)，比如7, 15, 31, 63，等等，也就是用二进制表示的各个bit全1的数字。每个key先经过hashFunction计算得到一个哈希值，然后计算(哈希值 & sizemask)得到在table上的位置。相免费云主机域名当于计算取余(哈希值 % size)。used：记录dict中现有的数据个数。它与size的比值就是装载因子（load factor）。这个比值越大，哈希值冲突概率越高。dictEntry结构中包含k, v和指向链表下一项的next指针。k是void指针，这意味着它可以指向任何类型。v是个union，当它的值是uint64_t、int64_t或double类型时，就不再需要额外的存储，这有利于减少内存碎片。当然，v也可以是void指针，以便能存储任何类型的数据。dictCreate为dict的数据结构分配空间并为各个变量赋初值。其中两个哈希表ht[0]和ht[1]起始都没有分配空间，table指针都赋为NULL。这意味着要等第一个数据插入时才会真正分配空间。上述dictFind的源码，根据dict当前是否正在重哈希，依次做了这么几件事：如果当前正在进行重哈希，那么将重哈希过程向前推进一步（即调用_dictRehashStep）。实际上，除了查找，插入和删除也都会触发这一动作。这就将重哈希过程分散到各个查找、插入和删除操作中去了，而不是集中在某一个操作中一次性做完。计算key的哈希值（调用dictHashKey，里面的实现会调用前面提到的hashFunction）。先在第一个哈希表ht[0]上进行查找。在table数组上定位到哈希值对应的位置（如前所述，通过哈希值与sizemask进行按位与），然后在对应的dictEntry链表上进行查找。查找的时候需要对key进行比较，这时候调用dictCompareKeys，它里面的实现会调用到前面提到的keyCompare。如果找到就返回该项。否则，进行下一步。判断当前是否在重哈希，如果没有，那么在ht[0]上的查找结果就是最终结果（没找到，返回NULL）。否则，在ht[1]上进行查找（过程与上一步相同）。下面我们有必要看一下增量式重哈希的_dictRehashStep的实现。dictRehash每次将重哈希至少向前推进n步（除非不到n步整个重哈希就结束了），每一步都将ht[0]上某一个bucket（即一个dictEntry链表）上的每一个dictEntry移动到ht[1]上，它在ht[1]上的新位置根据ht[1]的sizemask进行重新计算。rehashidx记录了当前尚未迁移（有待迁移）的ht[0]的bucket位置。如果dictRehash被调用的时候，rehashidx指向的bucket里一个dictEntry也没有，那么它就没有可迁移的数据。这时它尝试在ht[0].table数组中不断向后遍历，直到找到下一个存有数据的bucket位置。如果一直找不到，则最多走n*10步，本次重哈希暂告结束。最后，如果ht[0]上的数据都迁移到ht[1]上了（即d->ht[0].used == 0），那么整个重哈希结束，ht[0]变成ht[1]的内容，而ht[1]重置为空。根据以上对于重哈希过程的分析，我们容易看出，本文前面的dict结构图中所展示的正是rehashidx=2时的情况，前面两个bucket（ht[0].table[0]和ht[0].table[1]）都已经迁移到ht[1]上去了。dictAdd插入新的一对key和value，如果key已经存在，则插入失败。dictReplace也是插入一对key和value，不过在key存在的时候，它会更新value。以上是dictAdd的关键实现代码。我们主要需要注意以下几点：它也会触发推进一步重哈希（_dictRehashStep）。如果正在重哈希中，它会把数据插入到ht[1]；否则插入到ht[0]。在对应的bucket中插入数据的时候，总是插入到dictEntry的头部。因为新数据接下来被访问的概率可能比较高，这样再次查找它时就比较次数较少。_dictKeyIndex在dict中寻找插入位置。如果不在重哈希过程中，它只查找ht[0]；否则查找ht[0]和ht[1]。_dictKeyIndex可能触发dict内存扩展（_dictExpandIfNeeded，它将哈希表长度扩展为原来两倍，具体请参考dict.c中源码）。dictReplace在dictAdd基础上实现，如下：在key已经存在的情况下，dictReplace会同时调用dictAdd和dictFind，这其实相当于两次查找过程。这里Redis的代码不够优化。dictDelete的源码这里忽略，具体请参考dict.c。需要稍加注意的是：dictDelete也会触发推进一步重哈希（_dictRehashStep）如果当前不在重哈希过程中，它只在ht[0]中查找要删除的key；否则ht[0]和ht[1]它都要查找。删除成功后会调用key和value的析构函数（keyDestructor和valDestructor）。上述内容就是Redis中内部数据结构dict的作用是什么，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注百云行业资讯频道。

相关推荐: oracle中怎么设置UTL_FILE_DIR参数

oracle中怎么设置UTL_FILE_DIR参数，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。 oracle中设置UTL_FILE_DIR参数第一步：以管理员用户登陆 如：conn sys/pa…