上两篇我们分享了演示数据, 动态字符串和链表的底层实现, 现在, 我们分享一下字典, 跳跃表和压缩列表的具体实现:
4, 字典
字典又称为符号表或者关联数组, 或映射(map), 是一种用于保存键值对的抽象数据结构. 字典中的每一个键 key 都是唯一的, 通过 key 可以对值来进行查找或修改. C 语言中没有内置这种数据结构的实现, 所以字典依然是 Redis 自己构建的.
- typedef struct dictht{
- // 哈希表数组
- dictEntry **table;
- // 哈希表大小
- unsigned long size;
- // 哈希表大小掩码, 用于计算索引值
- // 总是等于 size-1
- unsigned long sizemask;
- // 该哈希表已有节点的数量
- unsigned long used;
- }dictht
哈希表是由数组 table 组成, table 中每个元素都是指向 dict.h/dictEntry 结构, dictEntry 结构定义如下:
- typedef struct dictEntry{
- // 键
- void *key;
- // 值
- union{
- void *val;
- uint64_tu64;
- int64_ts64;
- }v;
- // 指向下一个哈希表节点, 形成链表
- struct dictEntry *next;
- }dictEntry
key 用来保存键, val 属性用来保存值, 值可以是一个指针, 也可以是 uint64_t 整数, 也可以是 int64_t 整数.
字典. png
注意这里还有一个指向下一个哈希表节点的指针, 我们知道哈希表最大的问题是存在哈希冲突, 如何解决哈希冲突, 有开放地址法和链地址法. 这里采用的便是链地址法, 通过 next 这个指针可以将多个哈希值相同的键值对连接在一起, 用来解决哈希冲突.
5, 跳跃表
跳跃表 (skiplist) 是一种有序数据结构, 它通过在每个节点中维持多个指向其它节点的指针, 从而达到快速访问节点的目的. 具有如下性质:
1, 由很多层结构组成;
2, 每一层都是一个有序的链表, 排列顺序为由高层到底层, 都至少包含两个链表节点, 分别是前面的 head 节点和后面的 nil 节点;
3, 最底层的链表包含了所有的元素;
4, 如果一个元素出现在某一层的链表中, 那么在该层之下的链表也全都会出现(上一层的元素是当前层的元素的子集);
5, 链表中的每个节点都包含两个指针, 一个指向同一层的下一个链表节点, 另一个指向下一层的同一个链表节点;
跳跃表. png
Redis 中跳跃表节点定义如下:
- typedef struct zskiplistNode {
- // 层
- struct zskiplistLevel{
- // 前进指针
- struct zskiplistNode *forward;
- // 跨度
- unsigned int span;
- }level[];
- // 后退指针
- struct zskiplistNode *backward;
- // 分值
- double score;
- // 成员对象
- robj *obj;
- } zskiplistNode
多个跳跃表节点构成一个跳跃表:
- typedef struct zskiplist{
- // 表头节点和表尾节点
- structz skiplistNode *header, *tail;
- // 表中节点的数量
- unsigned long length;
- // 表中层数最大的节点的层数
- int level;
- }zskiplist;
6, 压缩列表
压缩列表 (ziplist) 是 Redis 为了节省内存而开发的, 是由一系列特殊编码的连续内存块组成的顺序型数据结构, 一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值.
压缩列表的原理: 压缩列表并不是对数据利用某种算法进行压缩, 而是将数据按照一定规则编码在一块连续的内存区域, 目的是节省内存.
压缩列表. png
大多数情况下, Redis 使用简单字符串 SDS 作为字符串的表示, 相对于 C 语言字符串, SDS 具有常数复杂度获取字符串长度, 杜绝了缓存区的溢出, 减少了修改字符串长度时所需的内存重分配次数, 以及二进制安全能存储各种类型的文件, 并且还兼容部分 C 函数.
通过为链表设置不同类型的特定函数, Redis 链表可以保存各种不同类型的值, 除了用作列表键, 还在发布与订阅, 慢查询, 监视器等方面发挥作用.
Redis 的字典底层使用哈希表实现, 每个字典通常有两个哈希表, 一个平时使用, 另一个用于 rehash 时使用, 使用链地址法解决哈希冲突.
跳跃表通常是有序集合的底层实现之一, 表中的节点按照分值大小进行排序.
压缩列表是 Redis 为节省内存而开发的顺序型数据结构, 通常作为列表键和哈希键的底层实现之一.
到这里 redis 中的数据结构我们差不多就实现了, 更多干货和资料请直接联系我, 也可以加群 710520381, 邀请码: 柳猫, 欢迎大家共同讨论
来源: http://www.jianshu.com/p/b20f33552193