集合具有唯一性和无序性的特点,这个和哈希表的键是不是很像?我们可以通过哈希表实现类似的功能特性,然后将哈希表的值置为空即可,实际上 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 留空。
对照全局哈希表的结构图,我么可以绘制集合元素内部哈希表结构图如下:
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) 的效率也很高。
评论区