Redis 底层字典

前言

<<redis设计与实现>>,看书学习知识,做笔记,加深对知识的理解。

字典

字典是redis中的一种数据结构,在字典中一个key对应一个value称为键值对(字典有多个键值对),redis底层是由C语言开发的,本身是没有字典的，所以redis自己封装了一个字典的数据结构。

实现

字典的底层是由哈希表来实现的,所以整体的顺序应该由大到小来介绍。

哈希表

字典的数据结构:

1. type 类型特定函数
2. private 私有数据
3. ht[2] 哈希表
4. rehashidx 当rehash没在进行时值为-1

哈希表的结构包括:

1. table 哈希表数组
2. size 哈希表的大小
3. sizemask 哈希表大小掩码,用来计算索引值 sizemask = size – 1
4. used 哈希表已用的节点

哈希表节点数据结构:

1. key 键
2. v 值
3. next 下一个节点的地址

如下图所示:

当我们往字典中添加一个键值对的时候，我们的会把key传入根据算法(MurmurHash2)求出哈希值,然后在跟 sizemask进行”&”运算,即可计算出放入的索引值。

随着操作不断地进行 哈希表中保存键值会增多或减少，为了让负载因子维持在一个合理范围，就会进行rehash,
满足任意一个条件自动进行rehash:

1. 服务器没有执行 BGSAVE 或 BGREWRITEAOF 命令时并且负载因子大于等于1的时候执行。
2. 服务器执行BGSAVE 或 BGREWRITEAOF 命令时并且负载因子大于等于5的时候执行。
3. 当负载因子小于0.1的时候执行rehash。

负载因子：哈希表保存的节点数量 / 哈希表的大小。

rehash它是渐进式的，原因是如果ht[0]的数据过多，直接一次性转入ht[1]会导致一段时间停止服务。

渐进式的过程：

1. 为ht[1] 分配空间 并且把rehashidx 变为0，则代表正在进行hash
2. 在rehash期间，对字典进行添加,删除，修改，会对h[1]也进行一次修改，修改完一次 rehashidx + 1
3. 随着字典的不断操作，最终h[0]的键值对迁移到h[1]，然后把rehashidx 变为 -1 代表rehash结束。

最后留一个书的总结

加油努力 有什么问题希望指出及时纠正。