字典是哈希键的底层实现之一,Redis数据库的底层实现也是使用字典。
redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。
相关的数据结构
哈希表dict的数据结构:
一个空的哈希表如图所示:
哈希节点使用dictEntry来表示,每个dictEntry结构都保存着一个键值对:
包含2个哈希节点的哈希表如图所示:
字典dict的数据结构如图所示:
type和privdata属性是针对不同类型的键值对,为创建多态字典而设置的。
type属性是一个指向dictType结构的指针,每个dictType结构保存了一组用于操作特定类型键值对的函数;privdata属性则保存了需要传给那些类型特定函数的可选参数
ht是2个哈希表数组,用于rehash时使用,一般情况下只是用ht[0]。
trehashidx用于表示rehash的进度,如果没有rehash,则为-1。
一个普通状态下的字典结构如图所示:
当要在字典中插入键值对的时候,先计算key的hash值,再与上sizemask,定位相应的槽位置即可。
哈希冲突
同时,对于哈希表中的键冲突,会采用链地址法的解决方案,但是因为dictEntry节点没有指向链表表尾的指针,因此采用头插法O(1)(感觉HashMap1.7采用头插法也可能是为了插入效率吧)。
rehash
哈希表rehash的时候会使用在ht[1]上进行扩容,然后交换ht[0]和ht[1]。满足以下任意一个条件的时候,程序会自动对哈希表进行扩容操作:
- 服务器目前没有执行BGSAVE或者BGREWRITEAOF命令,且哈希表负载因子大于等于1
- 服务器目前正在执行BFSAVE或者BGREWRITEAOF命令,且哈希表负载因子大于等于5
其中load_factor = ht[0].used / ht[0].size
当哈希表的负载因子小于0.1的时候,程序胡自动开始对哈希表执行收缩操作。
渐进rehash
rehash的动作并不是一次性集中完成的,而是分多次渐进完成的,通过rehashidx的值可以观察到当前rehash的进度。
在渐进rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,因此渐进rehash进行期间,字典的删除、查找、更新等操作会在2个哈希表上进行。如果要在字典里面查找一个键的话,会现在ht[0]里面找,找不到再在ht[1]里面找。
另外,渐进rehash期间,新添加到字典的键值对一律会被保存到ht[1]里面,来保证ht[0]包含的键值对数量只减不增,并随着rehash操作的执行而最终变成空表。