Redis数据类型-Set-原理

特性

Set是无序且不可重复

一个集合最多可以存储 2 ^ 32 - 1 个元素

使用场景：

• 标签

  • 共同好友

  • 兴趣&爱好

  • 网页uv(独立访客数)统计

• 统计每天的新增用户数

  • key以user:id 以及当天日期，例如 user:uid:20220905； value为Set集合,记录当天登录的用户ID

• 排行

  • 热点话题

  • 点赞排行

  • ...

• 黑白名单

存储结构

inset

使用场景

当集合对象同时满足以下两个条件时，对象使用inset编码：

• 集合对象保存的所有元素都是整数值

• 集合对象保存的元素数量不超过512个(默认值，配置参数set-max-intset-entries可以修改)

原理分析1

intset的核心是一个字节数组，按照从小到大存放着set元素

• encoding：每个元素的编码方式，编码方式指定了一个整数元素占用多少个contents数组位

  • int16_t 2个字节，16位的整数，范围相当于java 的 short 类型

  • int32_t 4个字节，32位的整数，范围相当于java 的 int 类型

  • int64_t 8个字节，64位的整数，范围相当于java 的 Long 类型

• length：元素数量

• contents：存储具体的元素，元素按照从小到大排序

 

原理分析2

intset 升级(不支持降级)

1. 第一次插入的是 1 2 3，此时 encoding是int16_t

2. 第二次插入的是 99999，此时计算后得到新元素为 int32_t;

3. 将现有的元素全部转为新的元素类型，并存储在正确的空间上面；

4. 最后将新元素添加进数组内；

由于元素有序排列，所以set的获取操作采用二分查找方式实现，复杂度O(log(N))。

hashtable

使用场景

集合对象保存的所有元素不全是整数值，或者集合对象保存的元素数量超过512个（设定值）

原理分析

hashtable编码的的对象使用字典的方式作为底层实现，其中值就是key，value为null

 

• dictht（散列表）

  • table：哈希表数组

  • size：哈希表大小

  • sizemask：哈希表大小掩码，用于计算索引值

  • used：该哈希已有节点的数量

• dictEntity（散列表节点）

  • key：实际存储键的地方

  • union：联合体中就是实际存储值的地方

  • next：next域指向下一个节点, 可以用来解决哈希冲突问题