Redis全名叫做Remote Dictionary Server,从全称就可以看出dict是Redis里重要的数据结构,看了下dict.c里的源码,简单分析下。
dict.c主要是实现了哈希功能,实际上实现哈希(字典)常见的方法有几种:
<1>比如我们数据结构课上学的数组和链表法,但是这种方法适用于元素个数不多的情况下
<2>使用复杂的平衡树(B-等等),性能比较不错,比如MySQL里的索引就使用了这种方法
<3>哈希表,兼顾了高效和简单性,Redis选择了这种方法。
我们就解读下dict.c里源码里的数据结构吧,我们知道hash表的性能由hash表的大小和解决冲突的方法决定。Redis里使用了两个哈希表(ht[0])和哈希表(ht[1]),hash[0]是字典主要使用的hash表,而hash[1]主要对0号哈希表进行rehash时才使用。读者可能不明白这个地方啥意思?其实就是,程序每次申请几个字节(默认为4字节),当key/value数量达到规定时,程序申请的4字节就翻一倍(这里使用了慢迁移),那什么时候rehash呢?我们知道size == used(根据下面的dictht结构体)时,达到最理想状态,所以当used/size > 1时,就进行rehash。我们先看看dict.h里定义的几个结构体吧: