Redis源码剖析——dict(一)

/ 0评 / 0

dict结构根本上是为了提供高效的搜索映射,因此红黑树、AVL树、哈希表都可以用来实现字典结构,不过树形结构怎么都不可能达到常数级别的时间复杂度,因此用树形结构来实现dict已经比较少见了,不过C++STL库中map的实现仍然是红黑树,红黑树也自有优点,在实现字典结构的同时还可以顺便提供中序排序,但是就查找来说他已经没有必要被使用了,Redis里dict的实现就是使用的哈希表。

以下所有代码为与dict.h


对于dict结构,我们不妨自底向上来看,由最小的结构到最大的结构

当然首先是字典里的每个KV元素的结构

image.png

key field是任意类型的void*,value field是可适用于四种变量类型的union结构。next指针用于指向下一个节点,典型的哈希桶挂链表的结构

接下来是一个dict所有相关方法,这是一个比较OO(面向对象)的结构,虽然C最初不是一个为面向对象的设计的语言,而事实上若你对OO理解能深刻一点就能很清楚意识到,OO不应该是和语言相关的,也就是说不是非得哪个语言才能OO,这样的写法就是在OO写C。

image.png

其中有必不可少的hash函数、keyDup方法、valDup方法,以及keyCompare、keyDestructor、valDestructor,这种设计在Redis是非常常见的,在Redis的ae事件库你也会见到这种设计。

有了字典中元素的结构以及相关的方法,接下来自然就是hash表本身了的结构

image.png

table: 一个二级指针,因为它指向的一个指针数组,这个数组里每个元素当然就是每个entry的指针

size: 哈希桶的槽位数

sizemask: 用于把把key在hash函数中的结果二进制截断为一个小于size的数,因此sizemask == size - 1,每个数&上sizemask得到的结果必然是小于mask,这样的好处是避免的求模运算

used: 哈希表中的元素个数

接下来是我们最顶层的dict结构

image.png

第一个字段type已经说过,privdata可以不必关心。但是注意一个很特别的地方,这里竟然有两个hash表,奇怪,为什么要有两个?(可以自己先猜一猜),接下来的rehashidx也是和两个hash表的存在紧密相关的,在此也就先留个悬念了,最后一个是用来用于遍历的迭代器。

下面来一张图,览其大观

image.png

最后顺便看看迭代器是怎么设计的(我准备把迭代器的具体相关放在dict的最后一篇再讲解)

image.png

d: 迭代器当然要绑定到具体的一个dict上

index: 迭代器在哈希桶中的槽位下标,即dictEnrty*指针数组的下标

table、safe: 暂且不说,这两也是和存在个hash表紧密相关

entry、nextEntry: 当前所在的entry与下一个访问的entry

fingerprint: 这个暂且不说


我们知道哈希桶一般都会有一个默认的初始桶数,在dict中其默认初始值为4

image.png

下面是一些方便操作的宏函数,如释放val、key、设定key、设定各种类型的val的函数等,都非常简洁,就不加以赘述了

image.png

下面是也是一些相关的简单宏函数,涉及到两个哈希表的函数想必你还是看不懂,不着急,下一篇我们会详细解析的

image.png

下面所有方法的原型列表,例如创建dict、扩容、添加元素、删除元素等等

image.png

下一篇我们深入剖析其dict核心部分的具体实现,两个哈希表的设计可能会让没见过这种设计的你耳目一新~

发表评论

电子邮件地址不会被公开。 必填项已用*标注