Redis 集合：整数集合与哈希表的风花雪月
各位观众，各位听众，各位程序员朋友们，大家好！我是今天的讲师，人称代码界的段子手，Bug 终结者（自封的）。今天，咱们来聊聊 Redis 集合的那些事儿，特别是它内部两种神秘的编码方式：整数集合（intset）和哈希表（hashtable）。
想象一下，Redis 集合就像一个百宝箱，里面装着各种各样的宝贝。但这个百宝箱可不是普通的箱子，它会根据宝贝的种类和数量，自动选择最合适的收纳方式。而intset和hashtable，就是这个百宝箱里两种常用的收纳隔间。
准备好了吗？让我们一起踏上这段探索 Redis 集合内部机制的奇妙旅程吧！🚀
一、集合的初印象：这货是干啥的？
首先，我们来简单认识一下 Redis 集合。简单来说，Redis 集合就是一个无序、唯一的元素集合。想想你的朋友圈，里面的朋友顺序不重要，重要的是不能有重复的。这，就是集合的精髓。
集合可以用来做什么呢？用途可大了！
- 好友推荐： 你和哪些朋友有共同的好友？用集合的交集运算，瞬间帮你找到潜在的基友。
- 标签系统： 给文章打标签，根据标签查找文章。集合的并集、交集、差集，轻松实现各种复杂的标签查询。
- 访问控制： 哪些用户拥有某个权限？用集合来管理用户的权限，简单高效。
总之，集合是个非常有用的数据结构，在很多场景下都能发挥重要作用。
二、intset：小而美的整数收纳盒
现在，我们聚焦到第一个收纳隔间：intset，也就是整数集合。顾名思义，intset专门用来存放整数。但它可不是简单的数组，它内部做了很多优化，让我们来一探究竟。
2.1 为什么需要intset？
你可能会想，直接用数组存放整数不就行了吗？为什么还要搞一个intset出来？
原因很简单：节省内存！
Redis 追求极致的性能和效率，内存管理当然不能马虎。如果集合里只存放小整数，却用 long long 类型来存储，岂不是浪费？intset 的巧妙之处就在于，它可以根据集合中整数的实际范围，动态调整存储类型。
2.2 intset 的结构：麻雀虽小，五脏俱全
intset 的结构体定义如下（简化版）：
typedef struct intset {
uint32_t encoding; // 编码方式，决定了整数的存储类型
uint32_t length; // 集合中元素的数量
int8_t contents[]; // 实际存储整数的数组
} intset;-
encoding： 这是intset的灵魂所在。它决定了contents数组中整数的存储类型。有三种取值：INTSET_ENC_INT16：每个整数用 16 位（int16_t）存储。INTSET_ENC_INT32：每个整数用 32 位（int32_t）存储。INTSET_ENC_INT64：每个整数用 64 位（int64_t）存储。
-
length： 记录了集合中元素的数量。 -
contents： 这是一个柔性数组，用于存储实际的整数。柔性数组意味着它的大小可以根据实际需要动态调整。
2.3 intset 的升级：从小到大的成长之路
intset 最令人称道的地方在于它的升级机制。当我们要插入一个比当前 encoding 类型更大的整数时，intset 会自动升级。
举个例子：
- 假设
intset当前的encoding是INTSET_ENC_INT16，也就是说，它只能存储 -32768 到 32767 之间的整数。 - 现在，我们要插入一个整数 65536，这个数超出了
int16_t的范围。 intset会先分配一块更大的内存，用于存储int32_t类型的整数。- 然后，它会将
contents数组中所有的整数都转换为int32_t类型，并移动到新的内存空间。 - 最后，将 65536 插入到新的数组中，并将
encoding更新为INTSET_ENC_INT32。
整个过程就像房子装修，发现原来的房子不够住了，就推倒重建，换成更大的房子。
升级的好处是显而易见的：
- 灵活性： 可以根据实际需要调整存储类型，避免浪费内存。
- 性能： 只有在需要的时候才会升级，不会一开始就分配最大的内存空间。
当然，升级也是有代价的：
- 时间复杂度： 升级需要重新分配内存和移动数据，时间复杂度为 O(N)。
2.4 intset 的查找：二分查找的魅力
由于 intset 中的整数是有序排列的，因此可以使用二分查找来快速查找元素。二分查找的时间复杂度为 O(log N)，效率非常高。
想象一下，你在一本字典里查找一个单词，二分查找就像每次都翻到中间页，然后判断目标单词是在前半部分还是后半部分，再继续在相应的半部分查找，直到找到目标单词为止。
2.5 intset 的局限性：只能存放整数
intset 虽好，但它也有自己的局限性：它只能存放整数。如果集合中包含字符串或其他类型的数据，intset 就无能为力了。这时候，就需要请出我们的另一位主角：hashtable。
三、hashtable：万能的哈希表
hashtable，也就是哈希表，是一种非常通用的数据结构，可以用来存储各种类型的数据。在 Redis 中，hashtable 被广泛应用于各种数据类型的实现，包括集合。
3.1 为什么需要hashtable？
当集合中包含字符串或其他非整数类型的数据时，intset 就无法满足需求了。这时候，就需要使用 hashtable 来存储集合中的元素。
hashtable 的优点是通用性强，可以存储任何类型的数据。但它的缺点是内存占用相对较大，并且查找效率不如 intset。
3.2 hashtable 的结构：复杂但强大
hashtable 的结构比较复杂，它由多个哈希桶组成，每个哈希桶可以存储一个或多个键值对。当发生哈希冲突时，可以使用链表或其他方式来解决。
Redis 的 hashtable 实现比较复杂，这里我们只简单介绍一下它的基本结构：
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表的大小
unsigned long sizemask; // 哈希表大小的掩码，用于计算哈希索引
unsigned long used; // 哈希表中已使用的节点数量
} dictht;
typedef struct dictEntry {
void *key; // 键
union {
void *val; // 值
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 指向下一个节点的指针，用于解决哈希冲突
} dictEntry;table： 这是一个指向dictEntry数组的指针，也就是哈希表的主体。size： 哈希表的大小，也就是table数组的长度。sizemask： 哈希表大小的掩码，用于计算哈希索引。used： 哈希表中已使用的节点数量。key： 键，也就是集合中的元素。v： 值，在集合中通常为空。next： 指向下一个节点的指针，用于解决哈希冲突。
3.3 hashtable 的哈希冲突：链地址法的应用
哈希冲突是指不同的键计算出相同的哈希索引，导致它们被分配到同一个哈希桶中。解决哈希冲突的常用方法是链地址法。
链地址法的思路是：当发生哈希冲突时，将新的键值对添加到哈希桶对应的链表的末尾。这样，同一个哈希桶中就可以存储多个键值对了。
3.4 hashtable 的扩容与收缩：动态调整大小
为了保证哈希表的性能，Redis 会根据哈希表的使用情况动态调整哈希表的大小。当哈希表的负载因子（used / size）超过一定阈值时，Redis 会对哈希表进行扩容。当哈希表的负载因子低于一定阈值时，Redis 会对哈希表进行收缩。
扩容和收缩的过程比较复杂，涉及到重新计算哈希索引和移动数据。为了避免阻塞主线程，Redis 使用了渐进式 rehash 的方式来进行扩容和收缩。
3.5 hashtable 的查找：哈希算法的效率
hashtable 的查找效率取决于哈希算法的质量。一个好的哈希算法应该能够尽可能地将键均匀地分布到不同的哈希桶中，从而减少哈希冲突的发生。
Redis 使用了 MurmurHash2 算法作为默认的哈希算法。MurmurHash2 算法具有良好的性能和分布性，能够满足 Redis 的需求。
四、intset 与 hashtable 的选择：因地制宜，量体裁衣
现在，我们已经了解了 intset 和 hashtable 的基本原理。那么，Redis 集合在什么情况下会使用 intset，什么情况下会使用 hashtable 呢？
Redis 的选择策略是：
- 当集合中的所有元素都是整数，并且元素的数量不超过
set-max-intset-entries配置项的值时，使用intset。 - 否则，使用
hashtable。
set-max-intset-entries 的默认值为 512。也就是说，当集合中的元素都是整数，并且数量不超过 512 个时，Redis 会使用 intset 来存储集合。
这个策略的目的是：
- 在保证性能的前提下，尽可能地节省内存。
intset比hashtable更节省内存，并且查找效率更高。 - 在需要的时候，可以灵活地切换到
hashtable。 当集合中包含非整数类型的数据，或者元素数量超过set-max-intset-entries时，Redis 会自动将intset转换为hashtable。
五、总结：Redis 集合的智慧
通过今天的学习，我们深入了解了 Redis 集合的两种编码方式：intset 和 hashtable。
intset是一种专门用于存储整数的有序集合，它具有节省内存和查找效率高的优点。hashtable是一种通用的哈希表，可以存储各种类型的数据，但内存占用相对较大。
Redis 集合会根据实际情况选择最合适的编码方式，以达到性能和内存的最佳平衡。
希望今天的讲解能够帮助大家更好地理解 Redis 集合的内部机制。记住，理解数据结构的底层原理，才能更好地使用和优化它们。
最后，送给大家一句话：代码的世界，没有终点，只有不断探索的乐趣！ 😋
谢谢大家！👏