字典
Redis 中的字典由 dict.h/dict 结构表示：
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; ------------------分割线--------------------------- typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType;
ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
4.3.2.Redis rehash(重新散列)
随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的**负载因子**（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。
在对哈希表进行扩展或者收缩操作时，reash 过程并不是一次性地完成的，而是**渐进式**地完成的。
以下是哈希表渐进式 rehash 的详细步骤： 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
4.3.3.重点
- 字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和哈希键。
- Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行
rehash时使用。 - 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
- 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
- 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对
rehash到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。
4.4.跳跃表
4.4.1.跳跃表
Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义， 其中 zskiplistNode 结构用于表示跳跃表节点， 而 zskiplist 结构则用于保存跳跃表节点的相关信息， 比如节点的数量， 以及指向**表头节点和表尾节点**的指针， 等等。
跳跃表节点
typedef struct zskiplistNode { // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; } zskiplistNode;
- zskiplistNode 不同层高节点
跳跃表节点的 level 数组可以包含多个元素， 每个元素都包含一个指向其他节点的指针， 程序可以通过这些层来加快访问其他节点的速度， 一般来说， 层的数量越多， 访问其他节点的**速度就越快**。
看到这里，如果还有疑惑，不理解什么是跳跃表，传送一篇不错的跳跃表介绍文章：https://www.cnblogs.com/hunternet/p/11248192.html
4.4.2.重点
跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存**跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点**。
- 每个跳跃表节点的层高都是 1 至 32 之间的**随机数**。
- 在同一个跳跃表中， 多个节点可以包含**相同的分值， 但每个节点的成员对象必须是唯一**的。
- 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。
4.5.整数集合
- 整数集合是**集合键(set)**的底层实现之一。
- 整数集合的底层实现为**数组， 这个数组以有序、无重复的方式保存集合元素，在有需要时， 程序会根据新添加元素**的类型， 改变这个数组的类型。
- 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
- 整数集合**只支持升级**操作， 不支持降级操作。
整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现**重复元素**。
数据结构：
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;
4.4.2.重点
跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存**跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点**。
每个跳跃表节点的层高都是 1 至 32 之间的**随机数**。
在同一个跳跃表中， 多个节点可以包含**相同的分值， 但每个节点的成员对象必须是唯一**的。
跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。
4.5.整数集合
整数集合是**集合键(set)**的底层实现之一。
整数集合的底层实现为**数组， 这个数组以有序、无重复的方式保存集合元素，在有需要时， 程序会根据新添加元素**的类型， 改变这个数组的类型。
升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
整数集合**只支持升级**操作， 不支持降级操作。
整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值， 并且保证集合中不会出现**重复元素**。
我们知道，数组要求每个元素大大小相同，如果要存储长度不同的字符串，那就需要用**最大长度**的字符串大小作为元素的大小。以最大长度为标准，就会浪费一部分存储空间。
数组的优势占用一片**连续的空间**可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势，又想节省存储空间我们可以对数组进行压缩。
那就需要给每个节点增加一个 lenght 的属性。
4.6.2.Redis 压缩列表
压缩列表(zip1ist)是 Redis 列表和 Redis 哈希的底层实现之一。
当一个列表只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现。
当一个哈希只包含少量键值对,比且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希的底层实现。
- 表是Redis为节约内存自己设计的一种顺序型数据结构。
- 表被用作列表键和哈希键的底层实现之一。
- 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
- 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高。
4.7.Redis的对象
4.7.1.Redis的对象
Redis 中当我们创建一个键值对时，我们至少会创建俩个对象，一个用作键(键对象)，一个用作值(值对象)。
- Redis 对象结构
typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 指向底层实现数据结构的指针 void *ptr; // ... } robj;
- Redis 内存回收
值得一提的是 redis 内存回收，因为 C 语言并不具备自动的内存回收功能， 所以 Redis 在自己的对象系统中构建了一个**引用计数（reference counting）技术实现的内存回收机制， 通过这一机制， 程序可以通过跟踪对象的引用计数信息， 在适当的时候自动释放对象并进行内存回收**。每个对象的引用计数信息由
redisObject结构的refcount属性记录：typedef struct redisObject { // ... // 引用计数 int refcount; // ... } robj;
- Redis 对象共享
举个例子， 假设键 A 创建了一个包含整数值 100 的字符串对象作为值对象，如果这时键 B 也要创建一个同样保存了整数值 100 的字符串对象作为值对象。
在 Redis 中， 让多个键共享同一个值对象需要执行以下两个步骤：
- 将数据库键的值指针指向一个现有的值对象；
- 将被共享的值对象的引用计数增一。
目前来说， Redis 会在初始化服务器时， 创建一万个字符串对象， 这些对象包含了从 0 到 9999 的所有整数值， 当服务器需要用到值为 0到 9999 的字符串对象时， 服务器就会使用这些共享对象， 而不是新创建对象。
- Redis 对象的空转时长
除了前面介绍过的 type 、 encoding 、 ptr 和 refcount 四个属性之外， redisObject 结构包含的最后一个属性为 lru 属性， 该属性记录了对象最后一次被命令程序访问的时间：
typedef struct redisObject { // ... unsigned lru:22; // ... } robj;
4.7.2.重点
内存回收和对象的空转时长涉及到 Redis 配置文件(内存的算法 volatile-lru、allkeys-lru等其他知识点)，后面单独一篇详细讲解。
Redis 数据库中的每个键值对的键和值都是一个对象。
Redis 共有字**符串、列表、哈希、集合、有序集合**五种类型的对象， 每种类型的对象至少都有两种或以上的编码方式， 不同的编码可以在不同的使用场景上优化对象的使用效率。
服务器在执行某些命令之前， 会先检查给定键的类型能否执行指定的命令， 而检查一个键的类型就是检查键的值对象的类型。
Redis 的对象系统带有引用计数实现的**内存回收机制**， 当一个对象不再被使用时， 该对象所占用的内存就会被自动释放。
Redis 会共享值为 0 到 9999 的字符串对象。
对象会记录自己的最后一次被访问的时间， 这个时间可以用于计算对象的**空转时间**。
