Redis篇-14--数据结构篇6--Set内存模型（整数集合intset，哈希表hashtable）

1、概述

Redis的Set数据类型用于存储无序且唯一的元素集合。为了提高性能和节省内存，Redis对 Set的底层实现进行了多种优化。特别是通过使用整数集合（intset）和哈希表（hashtable） 两种不同的数据结构来适应不同场景下的需求。

2、整数集合（intset）

当Set中的所有元素都是整数时，Redis会使用一种特殊的紧凑表示法——整数集合（intset）来存储这些元素。intset是一种专门用于存储整数的有序数组，能够显著减少内存占用并提高操作效率。

（1）、intset的特点

- 紧凑存储：intset使用一个连续的内存块来存储所有整数元素，避免了指针开销。它根据元素的实际大小动态调整每个整数的存储空间，支持16位、32位和64位整数。
- 有序性：intset内部是有序的，插入新元素时会自动维护元素的顺序。这种有序性使得查找、插入和删除操作可以通过二分查找来实现，时间复杂度为O(log n)。
- 无重复元素：intset保证集合中没有重复元素，符合Set的语义要求。
- 内存高效：由于intset是一个紧凑的数组，它减少了内存碎片，并且不需要额外的指针开销。这使得intset在处理小规模整数集合时具有很高的内存利用率。

（2）、intset工作原理

- 变长编码：intset根据元素的实际大小选择最合适的编码方式。例如，对于较小的整数（如 0到65535），可以使用16位整数来表示；对于更大的整数，则使用32位或64位整数。这种变长编码方式减少了不必要的内存浪费。
- 自动升级：当intset中插入了一个更大范围的整数时，intset会自动将所有元素升级到更大的整数类型（如从16位升级到32位）。这个过程是一次性的，不会影响后续的插入操作。
- 二分查找：由于intset是有序的，查找、插入和删除操作都可以通过二分查找来实现，时间复杂度为O(log n)。这比传统的哈希表在处理小规模数据时更加高效。

（3）、intset的应用场景

- 小规模整数集合：当Set中的元素数量较少且全部为整数时，intset可以提供高效的内存利用率和操作性能。
- 频繁的查找操作：由于intset是有序的，查找操作可以通过二分查找来实现，时间复杂度为O(log n)，特别适合需要频繁查找的场景。

3、哈希表（hashtable）

当Set中的元素不是整数，或者元素数量较多时，Redis会切换到使用哈希表（hashtable）来存储Set。哈希表是一种基于哈希函数的数据结构，能够提供O(1)的平均查找、插入和删除操作。

（1）、hashtable 的特点

- 快速查找：哈希表通过哈希函数将键映射到固定的桶中，查找、插入和删除操作的平均时间复杂度为O(1)。这使得哈希表在处理大规模数据时具有很高的性能。
- 无重复元素：哈希表保证集合中没有重复元素，符合Set的语义要求。
- 动态调整大小：当哈希表的装载因子（已用槽位数与总槽数的比例）过高时，哈希表会进行扩容，以减少冲突并保持性能。Redis使用渐进式rehas来分摊rehash的工作量，避免一次性迁移所有元素导致的性能下降。
- 冲突解决：哈希表使用链地址法（Separate Chaining）来处理冲突。每个桶包含一个链表，当多个键被哈希到同一个桶时，它们会被添加到该链表中。虽然链地址法可能会导致链表过长，但Redis通过渐进式rehash来减少冲突的发生。

（2）、hashtable工作原理

- 哈希函数：哈希表使用哈希函数将键映射到固定的桶中。Redis使用MurmurHash2或 MurmurHash3作为默认的哈希函数，这些哈希函数具有良好的分布特性和较高的计算效率。
- 渐进式rehash：当哈希表的装载因子过高时，Redis会创建一个新的、更大的哈希表，并将元素逐步迁移到新的表中。这个过程是逐渐进行的，每次执行命令时，Redis会迁移一部分元素，直到所有元素都迁移完毕。渐进式rehash确保了在高并发环境下，Set的操作性能仍然保持稳定。
- 冲突处理：当多个键被哈希到同一个桶时，哈希表使用链地址法来处理冲突。每个桶包含一个链表，链表中的每个节点存储一个键值对。虽然链地址法可能会导致链表过长，但Redis 通过渐进式rehash来减少冲突的发生。

（3）、hashtable应用场景

- 大规模数据集合：当Set中的元素数量较多时，哈希表能够提供高效的查找、插入和删除操作，特别适合处理大规模数据。
- 非整数元素：当 Set中的元素不是整数时，哈希表是唯一的选择，因为intset只能存储整数。
- 高并发环境：哈希表通过渐进式rehas来分摊rehash的工作量，避免了一次性迁移所有元素导致的性能下降，特别适合高并发环境。

4、混合结构，自动转换

Redis的Set实现了一个智能的混合结构，能够在intset和hashtable之间自动转换，以适应不同的应用场景。

（1）、自动转换原理

- 初始状态：当Set中的元素数量较少且全部为整数时，Redis会使用intset来存储这些元素。此时，Set具有最高的内存利用率和操作效率。
- 自动升级：当Set元素数量超过某个阈值时，或者插入了一个非整数元素，Redis会自动将intset转换为hashtable。这个转换过程是一次性的，不会影响后续的操作。
- 不会反向转换：Redis不会将hashtable转换回intset。即使set中的元素变得很少且都是整数也不会逆向转换。因为转换是一次性完成的，底层结构转换会造成一定性能开销，同时也避免频繁的切换带来的性能问题。

（2）、自动转换的条件

- 元素类型：如果Set中插入了一个非整数元素，Redis会立即将intset转换为hashtable。
- 元素数量：即使Set中的元素全部为整数，当元素数量超过某个阈值时，Redis 也会将intset 转换为hashtable。这个阈值可以通过配置参数set-max-intset-entries来调整，阈值默认值为512。

5、内存优化的其他技术

除了intset和hashtable的结合使用，Redis还采用了其他一些内存优化技术来进一步提升Set的性能和内存利用率：

- 渐进式rehash：当Set的哈希表需要扩容时，Redis会使用渐进式rehash来分摊rehash的工作量，避免一次性迁移所有元素导致的性能下降。这确保了在高并发环境下，Set的操作性能仍然保持稳定。
- 惰性释放：当Set中的元素被删除时，Redis不会立即回收多余的内存，而是保留下来用于后续可能的增长。这减少了频繁的内存分配和释放操作，提升了性能。

6、总结

Redis的Set通过结合整数集合（intset）和哈希表（hashtable）两种不同的数据结构，实现了高效的内存优化。当Set中的元素全部为整数且数量较少时，Redis使用 intset来存储这些元素。当Set中的元素不是整数，或者元素数量较多时，Redis使用hashtable来存储Set。
Redis会在intset和hashtable之间自动转换，以适应不同的应用场景。当Set中插入了非整数元素，或者元素数量超过某个阈值时，intset会自动转换为hashtable。

学海无涯苦作舟！！！