集合具有唯一性和无序性的特点，这个和哈希表的键是不是很像？我们可以通过哈希表实现类似的功能特性，然后将哈希表的值置为空即可，实际上 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) 的效率也很高。
评论区