• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

redis源码阅读之dict

redis 海叔叔 20小时前 5次浏览 已收录 0个评论

dict这两个文件是用来实现哈希表功能的,其原文是这样说的

然后是定义了两个宏来表示dict的状态

之后的话就是定义了一堆结构体来表征dict,源代码里面是通过自底向上的方式进行罗列,但我还是喜欢自顶向下来描述一下,orz~~

首先是dict,其中存放了字典类型dictType(哈希函数、键值复制函数、键值销毁函数、键的比较)信息,两个哈希表dictht,这里之所以用两个,是为了在字典扩展或者缩容时将旧表rehash到新表时中间寄存数据所用,导完数据之后,会释放旧表。

接着是dictType和dictht

最后就是dict当中的基本单元dictEntry和iterator了

由以上结构我们也可以猜测一下,该哈希表解决hash冲突的途径是使用链表放进桶里面: )

接下来是定义了几个私有函数:

其中其哈希算法用的是siphash,它的输入是一个变长字符串以及一个128位的key,输出就是哈希值了,在redis的dict当中的定义如下,其中两个sip函数的具体实现参见源码的siphash.c文件:

下面简单说一下字典的扩展和rehash。扩展的话就是相同size不扩展,如果ht[0]为空就直接链过去,否则存在ht[1]备用

rehash,为了防止在redis存储大量数据时进行rehash而block在rehash,其定义了最多访问的空桶数目n*10,其采取了渐进式的rehash来处理,rehashidx由0一直增到ht[0].size,期间如果达到了最多访问的空桶数目,就要停止,等待下一次rehash

添加元素,如果正在rehash,则插入在ht[1]里面,确保插入正确;删除元素,如果正在rehash,需要遍历两个表

删除操作代码

它还使用了一个指纹信息用于确定在一个iterator的生命周期内,有没有对哈希表进行非法操作


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址