侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Redis 常见数据结构的底层实现系列(四):集合篇

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 107 阅读 / 2,183 字

集合具有唯一性和无序性的特点,这个和哈希表的键是不是很像?我们可以通过哈希表实现类似的功能特性,然后将哈希表的值置为空即可,实际上 Redis 底层也是这么做的。

哈希表

这里的哈希表针对的是单个集合内部元素的存取实现,和前面说的全局哈希表不同。不过,哈希表是 Redis 底层很多地方都会复用到的数据结构,比如全局哈希表、集合、字典、有序集合等,Redis 底层把这种基于哈希表构建的数据结构称之为字典(这个字典和 Redis 上层支持的字典数据结构,即 Hash 不是同一个结构哈),这个字典底层的数据结构如下所示,它是一个结构体:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    unsigned long iterators; 
} dict;

其核心属性是两个 dictht 类型的数组:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

一个 dictht 就是一个哈希表,之所以字典中包含的是有两个哈希表的数组属性,是因为字典扩容缩容引入的 rehash 需要,在渐进式 rehash 时,这两个哈希表才同时不为空,否则只有一个哈希表用于存取集合元素。

哈希表结构 dictht 中的 table 属性存放的就是具体元素值了,其对应的数据类型是 dictEntry,这是一个链表结构:

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

其中 key 表示键名,v 表示键值(联合类型,支持整数、浮点数、字符串),next 表示链表中的下一个元素。

对于 Redis 集合类型(Set)而言,和字典类型(Hash)不同,没有 v 值,只需要设置 key 即可,v 可以通过指定为 NULL 留空。

对照全局哈希表的结构图,我么可以绘制集合元素内部哈希表结构图如下:

1.jpeg

IntSet

和其他数据结构的底层实现一样,为了充分优化内存管理效率,当集合中的元素都是整数,并且数据规模不大时,Redis 会使用小整数集合 IntSet 这种数据结构来存取集合元素:

typedef struct intset {
    uint32_t encoding; // 编码类型
    uint32_t length;  //  元素个数
    int8_t contents[]; // 整数数组
} intset;

它其实就是一个拥有长度字段的整数数组,使用数组的好处是可以分配连续的一整块内存空间,但是也继承了数组的不足 —— 不利于扩展,也就限制了它不能用来存放大量数据。

我们可以通过添加纯整数成员到集合来简单验证下:

127.0.0.1:6379> sadd test 1 2 3
(integer) 3
127.0.0.1:6379> debug object test
Value at:0x7f86796c4cd0 refcount:1 encoding:intset serializedlength:15 lru:421375 lru_seconds_idle:7

你可以通过 Redis 配置文件中提供的如下这个配置项配置 IntSet 元素上限,超过这个上限值,则会转化为通过哈希表存储集合元素:

set-max-intset-entries 512

或者一旦添加非整数成员,也会退化为使用哈希表存储:

127.0.0.1:6379> debug object test
Value at:0x7f86796c4cd0 refcount:1 encoding:hashtable serializedlength:12 lru:423614 lru_seconds_idle:12

对于哈希表而言,可以在时间复杂度为 O(1) 的情况下实现新增元素、获取集合长度以及查找指定集合元素,对于 IntSet,它会在内部对数组数据进行排序(这也是为什么 IntSet 只能存放整型数据),因此可以通过二分查找快速查找集合元素,时间复杂度虽然不及 O(1),但是 O(logN) 的效率也很高。

0

评论区