02 Redis 的数据结构
2.3.0 哈希冲突
当往哈希表写入大量数据时，不可避免的就出现多个 key 计算出来的哈希值相同。也就是多个不同的 key 需要放到同一个哈希桶，这就是所谓的哈希冲突。
而 Redis 解决哈希冲突的手段很 Java 一样，都是链式哈希：同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。
如图，假设 entry1、entry2、entry3 的哈希值都是 3 ；那么他们将存放在下标为 3 的哈希桶里面，并转换成链表。
PS：没懂哈希冲突的看旧文。旧文：《HashMap 源码解读》有详细例子解析。
当不断发生哈希冲突，链表越来越长，影响查询性能时，Redis 就需要 rehash。
2.3.1 rehash（扩容）
Redis 开始执行 rehash，这个过程分为三步：
- 1、给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
- 2、把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
- 3、释放哈希表 1 的空间。
如此，就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。
你肯定以为这样就完美了？但还有坑，当哈希表 1 数据量很大，如果一次性复制就会造成线程阻塞，无法服务其他请求。Redis 不允许这种事发生，因此使用了渐进式 rehash。
PS：没懂 rehash 的看旧文。旧文：《HashMap 源码解读》有详细例子解析。
2.3.2 渐进式 rehash
啥是渐进式 rehash ？
在第二步拷贝数据时，Redis 仍然正常处理客户端请求，** 每处理一个请求，顺带从哈希表 1 中的第一个索引位置开始，把这个位置上所有的 entry 复制到哈希表 2 中，下个请求就复制位置 2 **；直至全部复制完成。
过程如下图所示：
具体到代码，它的过程是这样的：
- 1、在字典中维持一个索引计数器变量 rehashidx，并将设置为 0，表示 rehash 开始。
- 2、在 rehash 期间，客户端每次对字典进行 CRUD 操作时，会将 ht [0] 中 rehashidx 索引上的值 rehash 到 ht [1]，操作完成后 rehashidx+1。
- 3、字典操作不断执行，最终在某个时间点，所有的键值对完成 rehash，这时将 rehashidx 设置为 - 1，表示 rehash 完成
说到这，你可能还有以下几点疑问？
只有在操作字典的时候才进行复制数据吗？如果客户端只操作一次字段是不是就完不成 rehash 了？
渐进式 rehash 执行时，除了根据针对字典的 CRUD 操作来进行数据迁移，Redis 本身还会有一个定时任务在执行 rehash，如果没有针对字典的请求时，这个定时任务会周期性地（例如每 100ms 一次）搬移一些数据到新的哈希表。
渐进式 rehash，CRUD 究竟在哪个哈希表操作呢？
在渐进式 rehash 过程中，字典会同时使用两个哈希表 ht [0] 和 ht [1]，所有的 CRUD 操作也会在两个哈希表进行。
比如要查找一个键时，服务器会优先查找 ht [0]，如果不存在，再查找 ht [1]。当执行新增操作时，新的键值对一律保存到 ht [1]，不再对 ht [0] 进行任何操作，以保证 ht [0] 的键值对数量只减不增，最后变为空表。
2.4 跳跃表
跳跃表在 Java 中很少接触到，大家对这个知识点也是挺陌生的。之前在学习数据结构是看到过小灰的一篇文章，写得通俗易懂，大家可以看下，建议看完再往下看。
https://mp.weixin.qq.com/s/COBdoHWDhlw4rmG_fGFhSA
跳跃表 (shiplist) 是实现 sortset (有序集合) 的底层数据结构之一；除此以外，在集群节点中也有用到它。
Redis 的跳跃表由 zskiplistNode 和 zskiplist 两个结构定义，源码位于 redis.h 文件中。
其中前者是跳跃表的结构；后者的作用是保存跳跃表的节点数量与头、尾节点的指针等信息。
typeof struct zskiplistNode { // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; } zskiplistNode;
如下图所示，展示了不同层高的跳跃表节点
typeof struct zskiplist { // 表头节点，表尾节点 struct skiplistNode *header,*tail; // 表中节点数量 unsigned long length; // 表中最大层数 int level; } zskiplist;
下图展示了一个跳跃表示例：
图片最左边的是 zskiplist 结构，包含：
- header：指向跳跃表的表头节点。
- tail：指向跳跃表的表尾节点。
- level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
- length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。
zskiplist 结构右方的是四个 zskiplistNode 结构， 包含：
- 层：比如节点中的 L1、L2、L3 等，包括前进指针和跨度
- 前进指针：用于访问位于表尾方向的其他节点
- 跨度：记录了前进指针所指向节点和当前节点的距离
- 后退指针：指向当前节点的前一个节点，从表尾向表头遍历
- 分值：节点按各自分值从小到大排列
- 成员对象：节点所保存的成员对象
PS：跳跃表这块的内容比较多，比较难说清楚实现细节。具体的看上面的链接，以及《Redis 设计与实现》这本书（说得很好，微信读书网页版就有）
2.5 整数集合
整数集合是 Set（集合）的底层数据结构之一。当 Set 只包含整数值元素，并且这个 Set 的元素数量不多时，Redis 就会使用整数集合作为 Set 的底层实现。
Redis 使用了 intset 用于保存整数值集合，它保证了有序以及不重复。源码如下：
typeof struct intset { // 编码方式 unit32_t encoding; // 集合包含的元素数量 unit32_t lenght; // 保存元素的数组 int8_t contents[]; } intset;
一个保存了 5 个整数的集合如下所示：
length 就不说了，主要说下 contents 和 encoding 的关系；contents 的真正类型取决于 encoding 的值：
- INTSET_ENC_INT16
- INTSET_ENC_INT32
- INTSET_ENC_INT64
这三个值分别对应 16、32、64 编码对应能存放的数字范围是不一样的。16 最小（-32768~32767），32 在中间（-2147483648~2147483647）64 最大（-9223372036854775808~9223372036854775807）。
如下图所示为 INTSET_ENC_INT16 类型集合存放 5 位整数占用的空间：16 * 5
2.5.0 升级操作
如果 contents 本来保存 1、3、5 三个整数值，后面加一个 2147483647456。
那么只有 2147483647456 是真正需要 int64_t 类型来保存的，而其他的 1、3、5 都可以用 int16_t 类型来保存；这时是整体升级，所有元素都会被升级为 int64_t 类型。
也就是说本来是 int16_t 类型的集合，要放入大于本身的整数。就需要升级，步骤如下：
- 1、根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
- 2、将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
- 3、将新元素添加到底层数组。
举个栗子：
1、原来是数组是 INTSET_ENC_INT16 类型 3 位，占用 48 位空间；
2、插入整数 65535，超出 INTSET_ENC_INT16 范围；升级为 INTSET_ENC_INT32 。需要的空间也从 48 加到 128 位。如下所示：新分配空间 = 128 - 48 = 80
3、元素 3 排名第三，移动到 contents 索引 2 位置；其他类似，元素 2 移动到索引 1 位置；元素 1 移动到索引 0 位置
4、最后添加新元素 65535 即可完成升级。
注意点：整数集合只支持升级、不支持降级。
