java基础巩固-宇宙第一AiYWM：为了维持生计，Redis基础Part2(Redis的数据结构)~整起

PART1:Redis的数据结构：5+3数据类型<----------------->数据结构【未来随着 Redis 新版本的发布，可能会有新的数据结构出现，通过查阅 Redis 官网【[Redis官网命令中心](http://www.redis.cn/commands.html)】 对应的介绍，你总能获取到最靠谱的信息。】
在这里插入图片描述

跟学Java基础时候其实一样，刚开始玩黑面板，玩完黑面板走向各种IDEA，Redis这里也有这个感觉：【当然，我自己的redis是安装在docker中的，首先找到镜像和容器之后，还得 从docke容器中，docker exec -it redis-test /bin/bash，然后redis-cli】
- 比如在Linux中，咱们进入到redis中，可以通过help @string、help @set、help @list、help @hash、help @zset来查询相关数据结构对象的常用操作/API
- 另外一种就是，咱们在项目中当然一般也不会这样搞原生的API，咱们一般会写一个自己的RedisUtils，内容呢，到这里ctrl+F搜一下RedisUtils，有你想要的

Redis用到的主要数据结构，比如简单动态字符串（SDS）、双端链表、字典、压缩列表、哈希表、跳表、整数集合、快速链表、listpack等等。Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，并规定Reedis的键值对中的key就是字符串对象，然后键值对中的值value就是字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象中的某一种，从而实现了Redis的键值对数据库】。通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。
在这里插入图片描述
（Redis所有的数据结构都是以唯一的key字符串作为名称来获取相应的value数据。五种不同类型的对象结构的差异就是由唯一的key获取到的value的结构不一样）。换句话说，Redis数据库里面的每个键值对都是由对象组成的，其中数据库键总是一个字符串对象，数据库键对应的值可以是字符串对象、列表对象（list object）、哈希对象（hash object）、集合对象（set object）、有序集合对象（sorted set object）这五种对象中的其中一种。【也可以说，这五种对象就是唯一的字符串对象的键对应的不同的值的类型】
在这里插入图片描述

使用对象系统的好处：
- 的一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
  - 同一数据类型会根据键的数量和值的大小也有不同的底层编码类型实现。在 Redis 2.2 版本之后，存储集合数据（Hash、List、Set、SortedSet）在满足某些情况下会采用内存压缩技术来实现使用更少的内存存储更多的数据。当这些集合中的数据元素数量小于某个值且元素的值占用的字节大小小于某个值的时候，存储的数据会用非常节省内存的方式进行编码，理论上至少节省 10 倍以上内存（平均节省 5 倍以上）【所以我们需要尽可能地控制集合元素数量和每个元素的内存大小，这样能充分利用紧凑型编码减少内存占用。】
    - 或者说，对一种数据类型实现多种不同编码方式主要原因是想通过不同编码实现效率和空间的平衡【比如当我们的存储只有100个元素的列表，当使用双向链表数据结构时，需要维护大量的内部字段。比如每个元素需要：前置指针，后置指针，数据指针等，造成空间浪费，如果采用连续内存结构的压缩列表(ziplist)，将会节省大量内存，而由于数据长度较小，存取操作时间复杂度即使为O(n) 性能也相差不大，因为 n 值小与 O(1) 并明显差别。】
  - 比如 Hash 类型里面的数据不是很多，虽然哈希表的时间复杂度是 O(1)，ziplist 的时间复杂度是 O(n)，但是使用 ziplist 保存数据的话会节省了内存，并且在少量数据情况下效率并不会降低很多。
- 除此之外，Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放
- Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。
- Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转时长较大的那些键可能会优先被服务器删除。
  - 除了下面介绍过的type、encoding、ptr和refcount四个属性之外， redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间：(OBJECT IDLETIME命令可以打印出给定键的空转时长，这一空转时长就是通过将当前时间减去键的值对象的lru时间计算得出的：)
    - 除了可以被OBJECT IDLETIME命令打印出来之外，键的空转时长还有另外一项作用：如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。
Redis中的五个对象中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性：(使用OBJECT ENCODING命令可以查看一个数据库键的值对象的编码)
- 对象的type属性：记录了对象的数据库的键所对应的值类型，键对应的值对应的的对象类型有五种
  - 当我们称呼一个数据库键为“字符串键”时，我们指的是“这个数据库键所对应的值为字符串对象”；（因为数据库键总是一个字符串对象，不同的是数据库键对应的值）
  - 当我们称呼一个键为“列表键”时，我们指的是“这个数据库键所对应的值为列表对象”。（因为数据库键总是一个字符串对象，不同的是数据库键对应的值）
  - 当我们对一个数据库键执行 TYPE命令时，命令返回的结果为数据库键对应的值对象的类型而不是键对象的类型：
- 对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定
- encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现
  - 通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。
    - 在列表对象包含的元素比较少时，Redis使用压缩列表作为列表对象的底层实现：(因为压缩列表比双端链表更节约内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中；)
    - 在列表对象包含的元素比较多时，，使用压缩列表来保存元素的优势逐渐消失时，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面；【对一种数据类型实现多种不同编码方式是想通过不同编码实现效率和空间的平衡。】
```
/* The actual Redis Object */
/** Redis 对象*/
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {// 类型unsigned type:4;// 编码unsigned encoding:4;// 对象最后一次被访问的时间unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */// 引用计数int refcount;// 指向实际值的指针，也就是指向底层实现数据结构的指针void *ptr;
} robj;
```

常用的5种对象系统具体如下：
PART1-1.五种对象系统之字符串对象（string）:

五种对象系统之字符串对象（string）的实现：
- String是最常用的一种数据类型，普通的key- value 存储都可以归为此类。其中String的Value既可以是数字也可以是字符串。
- 字符串对象的内部编码（底层实现）可以是int、raw或者embstr。【字符串对象的底层的数据结构实现主要是int和SDS（简单动态字符串）】
  - Redis是用C语言实现的，但是Redis没有直接使用C语言的char*字符数组来实现字符串【因为你C语言的char*数组有一些缺点人家Redis接受不了】，而是自己封装了一个名为简单动态字符串（SDS）的数据结构来表示字符串对象
    - 相比于 C 的原生字符串，Redis 的 SDS 不光可以保存文本数据还可以保存二进制数据，并且获取字符串长度复杂度为 O(1)（C 字符串为 O(N)）,除此之外，Redis 的 SDS API 是安全的，不会造成缓冲区溢出
      - String 是一种二进制安全的数据结构，可以用来存储任何类型的数据比如字符串、整数、浮点数、图片（图片的 base64 编码或者解码或者图片的路径）、序列化后的对象。
- 字符串对象中键是唯一标识【数据库键总是一个唯一的字符串对象，不同的是数据库键对应的值是不同的对象，五种中的一种对象而已】，值可以是字符串、数字（包括整数和浮点数）【value最多可以容纳的数据长度是512M】
  - 如果一个字符串对象保存的值【或者说键对应的值】是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int。(如下图举例：如果我们执行以下SET命令，那么服务器将创建一个如图所示的int编码的字符串对象作为number键的值： SET number 8888)
  - 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。【字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，并将对象的编码设置为raw】(如下图举例：如果我们执行以下命令，那么服务器将创建一个如图所示的raw编码的字符串对象作为story键的值：SET story “Long, long ago there lived a king …”)
  - 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度 小于等于32字节，那么字符串对象将使用embstr编码**的方式来保存这个字符串值。【字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，对象的编码是embstr】
    - Redis的字符串的两种存储方式（embstr编码是专门用于保存短字符串的一种优化编码方式，embstr编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示字符串对象，但raw编码会调用两次内存分配函数来分别创建redisObject结构和 sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构。）embstr编码的字符串对象在执行命令时，产生的效果和raw编码的字符串对象执行命令时产生的效果是相同的，但使用embstr编码的字符串对象来保存短字符串值有以下好处：
      - embstr 编码和 raw 编码的边界在 redis 不同版本中是不一样的
        redis 2.+ 是 32 字节
        redis 3.0-4.0 是 39 字节
        redis 5.0 是 44 字节
      - embstr和raw编码都会使用SDS来保存值，但不同之处在于：
        embstr编码将 创建字符串对象所需的内存分配次数 从raw编码的两次降低为一次。
        释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数。
        因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势。
        
        但是，embstr也是有缺点的：如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，所以embstr编码的字符串对象实际上是只读的，redis没有为embstr编码的字符串对象编写任何相应的修改程序。当我们对embstr编码的字符串对象执行任何修改命令（例如append）时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。
  - 用long double类型表示的浮点数在Redis中也是作为字符串值来保存的。如果我们要保存一个浮点数到字符串对象里面，那么程序会先将这个浮点数转换成字符串值，然后再保存转换所得的字符串值。
- 编码的转换：int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象。【redis可以支持编码转换，是为了二进制安全只取字节流，为了避免二进制截断溢出【不同客户端语言对同一类型的定义或者理解不一样】，也就是数据被破坏。一般序列化后面都跟一个编解码器，也为了避免二进制截断溢出，也就是数据被破坏】
  - 我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从int变为raw。
  - embstr编码的字符串对象实际上是只读的。所以当我们对embstr 编码的字符串对象执行任何修改命令时，程序会先将对象的编码从 embstr转换成raw，然后再执行修改命令。因为这个原因，embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。
在Redis的数据库里面，包含字符串值的键值对中的键和值在底层都是由SDS实现的。【（redis中的SDS，叫简单动态字符串，Simple Dynamic String），在内存中以字节数组的形式存在,类似于ArrayList,SDS是Redis的默认字符串表示。】
- 和C字符串（要知道长度得一个一个遍历到最后的空字符）不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O（1），因为我只需要访问SDS的len属性就可以立即知道SDS的长度为5Byte。
  - C语言中，char*指针指向字符数组的起始位置，而字符数组的结尾位置就用"\0"来标识，如果当前字符是"\0"说明字符串结束了，就要停止操作。也是这个缺陷使得 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据
    - C中的以"\0"标识结尾位置的方法有个缺陷就是，假如有个字符串中有个"\0"字符，这时在操作这个字符串时就有可能会提前结束，这不就出错了嘛
  - 设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，咱们使用SDS无须进行任何手动修改长度的工作。
  - 因为 C 语言的字符串并不记录自身长度，所以获取长度的复杂度为 O(n)；
- 与C字符串不同（C字符串，比如你要把某个字符串更新一下时，如果不提前检查一下新字符串的长度从而判断一下能不能装得下新字符串，就容易出现缓冲区溢出。比如strcat函数用来将两个字符串拼接在一起，C 语言的字符串是不会记录自身的缓冲区大小的，所以 strcat 函数假定程序员在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将可能会造成程序运行终止，这不就出错了嘛），SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。如果空间足够的话，API就会直接使用未使用空间，而无须执行内存重分配，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。
  - Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出。因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，所以不会导致缓冲区溢出的问题。
- 与C字符串不同，SDS 不仅可以保存文本数据，还可以保存二进制数据。因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，并且 SDS 的所有 API 都会以处理二进制的方式来处理 SDS 存放在 buf[] 数组里的数据。所以 SDS 不光能存放文本数据，而且能保存图片、音频、视频、压缩文件这样的二进制数据。
  - SDS 不需要用 “\0” 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 “\0” 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “\0” 字符。
  - SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的。通过使用二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，也可以保存任意格式的二进制数据。
- 与C字符串不同（C字符串每次增长或者缩短一个字符，程序都总要对保存这个C字符串的数组进行一次内存重分配操作（因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作），因为C字符串中需要额外的一个字符空间用于保存空字符，你得重新分配内存从而保证这种关联关系）。在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。 通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。
  - 空间预分配：用于优化SDS的字符串增长操作，从而减少当连续执行字符串增长操作时所需要的内存重分配次数。当SDS的API对一个 SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为 SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。
    - 如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。此时buf长度=len长度+free长度+1（额外的一字节用于保存空字符）
      - 虽然SDS的API都是一样遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的数据的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数。
    - 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
    - (Redis的字符串是动态的可以修改的（支持append操作）字符串，类似于ArrayList,采用预分配冗余空间的方式来减少或者说防止内存被频繁分配)
      - 一般而言，当前字符串实际分配的空间capacity > 实际字符串存的长度（字符串最大长度为512M。创建字符串时 len 和 capacity 一样长，不会多分配冗余空间，这是因为绝大多数场景下我们不会使用 append 操作来修改字符串。）
        当字符串长度小于1M时扩容是加倍现有的空间
        当字符串的长度超过1M时扩容时一次只会多扩1M的空间(为了避免加倍后的冗余空间过大而导致浪费)
  - 惰性空间释放：放用于优化SDS的字符串缩短操作(通过惰性空间释放策略，SDS避免了缩短字符串时所需要的内存重分配操作，并为将来可能有的增长操作提供了优化)：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来（内存要是回收了，这就不能算是你redis的空间了，但是你把这块算作free，此时就可以叫做你redis自己家的free），并等待将来使用。
    - 当然，SDS也提供了相应的API，让我们可以在有需要时可以真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。
SDS这个简单动态字符串，不仅可以用来保存数据库中的字符串值之外，还可以用作缓冲区buffer
- AOF模块中的AOF缓冲区，都是由SDS实现的
- 以及客户端状态中的输入缓冲区，都是由SDS实现的
字符串是由很多Byte组成，而Byte又等于8bit,所以就可以将一个字符串看成很多bit的组合（bitmap:位图，一种数据结构）
底层原理，redis中的字符串是一个带长度信息的字节数组
- SDS的结构
  - 将SDS的buf属性称为字节数组的原因：Redis不是用buf这个数组来保存字符，而是用它来保存一系列二进制数据。
    - SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。（你像C中，咱们不是以’\0’来作为字符串的结尾嘛，要是你字符串中间也出现一个’\0’这不就把后面那半串给害了嘛，相当于你此时的过滤或者叫限制操作就是不应该的。）。SDS来保存之前提到的特殊数据格式就没有任何问题，因为SDS使用len属性的值而不是空字符来判断字符串是否结束。
      - Redis使用字符串对象来表示位数组，因为字符串对象使用的SDS数据结构是二进制安全的，所以程序可以直接使用SDS结构来保存位数组，并使用SDS结构的操作函数来处理位数组。
        
        buf数组的每个字节都用一行来表示，每行的第一个格子buf[i]表示这是buf数组的哪个字节，而buf[i]之后的八个格子则分别代表这一字节中的八个位。需要注意的是，buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的，例如，在上图的buf[0]字节中，各个位的值分别是1、0、1、1、0、0、1、0，这表示buf[0]字节保存的位数组为01001101。使用逆序来保存位数组可以简化SETBIT命令的实现
      - SETBIT命令的实现：SETBIT用于将位数组bitarray在offset偏移量上的二进制位的值设置为value，并向客户端返回二进制位被设置之前的旧值：SETBIT

/** 每个sds.h/sdshdr结构表示一个SDS值：保存字符串对象的结构*/
struct sdshdr {// buf中已占用空间的长度(记录buf数组中已使用字节的数量),等于SDS所保存字符串的长度int len;// buf中剩余可用空间的长度,记录buf数组中未使用字节的数量,free属性的值为0，表示这个SDS没有分配任何未使用空间int free;// 数据空间,字节数组，用于保存字符串char buf[];
};...
struct SDS<T> { T capacity; // 表示所分配数组的长度T len; // 表示字符串的实际长度byte flags; // 特殊标识位，不理睬它byte[] content; // 存储真正的字符串内容
}

在这里插入图片描述

字符串对象的应用场景：
- 一般字符串对象常用在需要计数的场景，比如被用来统计用户的访问次数【页面单位时间的访问数】、热点文章的点赞转发数量、粉丝数等，简单的分布式锁也会用到该类型
  - 计数器举例：【计数比如用户单位时间的请求数（简单限流可以用到）】
    - 需要计数的场景，比如用户单位时间的请求数（简单限流可以用到）、页面单位时间的访问数。相关命令：SET、GET、 INCR、DECR
- 一个常见的用途就是缓存用户信息【常规数据（比如 session、token、、序列化后的对象）的缓存】。我们将用户信息结构体使用 JSON 序列化成字符串，然后将序列化后的字符串塞进 Redis 来缓存。同样，取用户信息会经过一次反序列化的过程【常规数据的场景比如 缓存 session、token、图片地址、序列化后的对象(相比较于 Hash 存储更节省内存)：SET、GET】
  - 使用 String 字符串对象来缓存对象有两种方式：
    - 直接缓存整个对象的 JSON。
    - 采用将key进行分离为user:ID属性，采用MSET存储，用MGET获取各个值，
  - String 还是 Hash 存储对象数据更好呢？在绝大部分情况，我们建议使用 String 来存储对象数据即可
    - String 存储的是序列化后的对象数据，存放的是整个对象。Hash 是对对象的每个字段单独存储，可以获取部分字段的信息，也可以修改或者添加部分字段，节省网络流量。如果对象中某些字段需要经常变动或者经常需要单独查询对象中的个别字段信息，Hash 就非常适合
    - String 存储相对来说更加节省内存，缓存相同数量的对象数据，String 消耗的内存约是 Hash 的一半。并且，存储具有多层嵌套的对象时也方便很多。如果系统对性能和资源消耗非常敏感的话，String 就非常适合
- 用作分布式锁：利用 SETNX key value 命令可以实现一个最简易的分布式锁；
  - set k1 value nx代表不为空则创建可以用于分布式锁。set k2 value xx代表不为空只能更新；
- 用作分布式系统下的session信息共享：通常我们在开发后台管理系统时，会使用 Session 来保存用户的会话(登录)状态，这些 Session 信息会被保存在服务器端，但这只适用于单系统应用，如果是分布式系统此模式将不再适用。
  - 例如用户一的 Session 信息被存储在服务器一，但第二次访问时用户一被分配到服务器二，这个时候服务器并没有用户一的 Session 信息，就会出现需要重复登录的问题，问题在于分布式系统每次会把请求随机分配到不同的服务器。

PART1-2.五种对象系统之列表对象（list）:类似于LinkedList

Hash 是一个键值(key => value)对集合。Redis 的hash 是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象，并且可以像数据库中update一个属性一样只修改某一项属性值
- list有序指的是存入弹出的顺序有序，它里面不维护排序
列表对象的编码（对象的底层实现）可以是ziplist或者linkedlist【双向链表或压缩列表】：【List 列表对象是简单的字符串列表，按照插入顺序排序，可以从头部或尾部向 List 列表添加元素。列表的最大长度为 2^32 - 1，也即每个列表支持超过 40 亿个元素】【 许多高级编程语言都内置了链表的实现比如 Java 中的 LinkedList，但是 C 语言并没有实现链表，所以 Redis 实现了自己的链表数据结构。人家Redis也很跟随时代潮流呀，你们都有我也跟。Redis 的 List 的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。】
- 如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List对象类型的底层数据结构；
  - ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。
  - ziplist:redis为了节约内存，zset 和 hash 容器对象在元素个数较少的时候都是采用压缩列表 (ziplist) 进行存储
    - （在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist ，也即是压缩列表。）压缩列表是一块连续的内存空间,元素之间紧挨着存储，没有任何冗余空隙。 ziplist 都是紧凑存储，意味着插入一个新的元素就需要调用 realloc 扩展内存。扩展多少取决于内存分配器算法和当前的 ziplist 内存大小
      - realloc 可能会重新分配新的内存空间（如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。），并将之前的内容一次性拷贝到新的地址
      - 也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝
      - 当debug object 输出的 encoding 字段都是 ziplist时就表示内部采用压缩列表结构进行存储
      - ziplist内部结构：
```
struct ziplist<T> { int32 zlbytes; // 整个压缩列表占用字节数int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点，然后就可以倒着遍历（压缩列表是为了支持双向遍历所以才有的ztail_offset这个字段）int16 zllength; // 元素个数T[] entries; // 元素内容列表，挨个挨个紧凑存储，entry 块随着容纳的元素类型不同，也会有不一样的结构。int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
```
```
struct entry { int<var> prevlen; // 表示前一个 entry 的字节长度，当压缩列表倒着遍历时需要通过这个字段来快速定位到下一个元素的位置。int<var> encoding; // 存储元素内容的编码类型信息，ziplist 通过这个字段来决定后面的 content 内容的形式optional byte[] content; // 元素内容, 定义为optional 类型，表示这个字段是可选的
}
```
  - 压缩列表（ziplist）:压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。【在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。】
    - 压缩列表各个组成部分:
      - zlbytes:uint32_t占4字节。记录整个压缩列表占用的内存字节数（压缩列表的总长）:在对压缩列表进行内存重分配，或者计算zlend的位置时使用
      - zltail：uint32_t4占字节。记录压缩列表表尾节点距离压缩列表的起始地址有多少字节:通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址
        假设列表zltail属性的值为0x3c（十进制60），这表示如果我们有一个指向压缩列表起始地址的指针p，那么只要用指针p加上偏移量60，就可以计算出表尾节点entry2的地址。
      - zllen：uint16_t占2字节。记录了压缩列表包含的节点数量,也就是有几个entryN:
        当这个属性的值小于UINT16_MAX(65535)时，这个属性的值就是压缩列表包含节点的数量;
        当这个值等于UINT16 MAX时，节点的真实数量需要遍历整个压缩列表才能计算得出
      - entryX：列表节点：压缩列表包含的各个节点，节点的长度由节点保存的内容决定
      - zlend：uint8_t 占1字节。特殊值 0xFF (十进制255)，用于标记压缩列表的末端
    - 压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。
      - 压缩列表节点的构成:一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。
        
        previous_entry_length:节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度（程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。）。【也可以说压缩列表里的每个节点中的 prevlen 属性都记录了前一个节点的长度，而且 prevlen 属性的空间大小跟前一个节点长度值有关】。previous_entry_length属性的长度可以是1字节或者5 字节：
        如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节：前一节点的长度就保存在这一个字节里面。
        如果前一节点的长度大于等于254字节，那么previous_entry_length 属性的长度为5字节：其中属性的第一字节会被设置为0xFE（十进制值 254），而之后的四个字节则用于保存前一节点的长度。
        压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性，程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点
        
        节点的encoding属性记录了节点的content属性所保存数据的类型以及长度：【encoding 属性的空间大小跟数据是字符串还是整数，以及字符串的长度有关：】
        当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。
        如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码。
        如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码
        
        节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定
      - 一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值
        字节数组可以是以下三种长度的其中一种:
        长度小于等于63（2^6–1）字节的字节数组；
        长度小于等于16383（2^14–1）字节的字节数组；
        长度小于等于4294967295（2^32–1）字节的字节数组；
        
        整数值则可以是以下六种长度的其中一种:
        4位长，介于0至12之间的无符号整数；
        1字节长的有符号整数；
        3字节长的有符号整数；
        int16_t类型整数；
        int32_t类型整数；
        int64_t类型整数;
      - 压缩列表的优缺点：【压缩列表的优点就是节省内存空间，并且是内存紧凑型的数据结构】
        
        压缩列表除了查找复杂度高的问题，还有压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
- 如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 对象类型的底层数据结构；【列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。】
  - linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。
  - list 的插入和删除操作非常快（列表键的底层实现之一就是链表），时间复杂度为 O(1)，但是索引定位或者说搜索访问很慢，时间复杂度为 O(n)
  - Redis的链表：实现是双端链表
    - 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针
    - Redis的链表实现的优缺点：
    - 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。【Redis在listNode结构体基础上又封装了list这个数据结构，这样使得操作比较方便而已】
```
/** 双端链表节点*/
typedef struct listNode {// 前置节点struct listNode *prev;// 后置节点struct listNode *next;// 节点的值void *value;
} listNode;/** 双端链表结构*/
typedef struct list {// 表头节点，也就是表头指针headlistNode *head;// 表尾节点,表尾指针taillistNode *tail;/***dup、free和match成员则是用于实现多态链表所需的类型特定函数：*/// 节点值复制函数,dup函数用于复制链表节点所保存的值void *(*dup)(void *ptr);// 节点值释放函数,free函数用于释放链表节点所保存的值void (*free)(void *ptr);// 节点值对比函数,match函数则用于对比链表节点所保存的值和另一个输入值是否相等int (*match)(void *ptr, void *key);// 链表所包含的节点数量,链表长度计数器lenunsigned long len;
} list;
```
- 在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。在 Redis 3.2 版本之后，List 数据类型底层数据结构就只由 quicklist 【快速链表quicklist:】实现了，替代了双向链表和压缩列表。
  - Redis 底层存储的不是一个简单的 linkedlist ，而是称之为快速链表 quicklist 的一个结构。（数据量比较多的时候才会改成 quicklist （quicklist是ziplist和linkedlist的混合体，Redis 有时候可以将链表和 ziplist 结合起来组成了 quicklist ，也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。）。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化）【或者这样说，其实 quicklist 就是双向链表 + 压缩列表组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。】
  - 虽然压缩列表是通过紧凑型的内存布局节省了内存开销，但是因为它的结构设计，如果保存的元素数量增加，或者元素变大了，压缩列表会有「连锁更新」的风险，一旦发生，会造成性能下降。【quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。】
  - quicklist的实现：quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是 quicklistNode。【quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。】
```
typedef struct quicklist {//quicklist的链表头quicklistNode *head;      //quicklist的链表头//quicklist的链表头quicklistNode *tail; //所有压缩列表中的总元素个数unsigned long count;//quicklistNodes的个数unsigned long len;       ...
} quicklist;//quicklistNode 的结构定义：
typedef struct quicklistNode {//前一个quicklistNodestruct quicklistNode *prev;     //前一个quicklistNode//下一个quicklistNodestruct quicklistNode *next;     //后一个quicklistNode//quicklistNode指向的压缩列表unsigned char *zl;              //压缩列表的的字节大小unsigned int sz;                //压缩列表的元素个数unsigned int count : 16;        //ziplist中的元素个数 ....
} quicklistNode;
```
- 编码转换：当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有列表元素都会被转移并保存到双端链表里面，对象的编码也会从ziplist变为linkedlist。
  - 当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：
    - 列表对象保存的所有字符串元素的长度都小于64字节
    - 列表对象保存的元素数量小于512个
  - 不满足上面这两个条件时的列表对象需要使用Linkedlist编码
当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
四种常用操作，在Redis中可以把list当作栈、队列等【像一个双向链表，有左边推右边推。后面可以用redis实现栈，队列等，就不用被进程限制了，直接用redis来搞】
- 右进左出：Queue
- 右进右出：Stack
- 满操作
列表对象的应用场景：列表对象的value是一个map，key肯定不用说就是一个字符串对象喽
- 所以列表对象经常用于发布与订阅、消息队列、慢查询等
  - 消息队列：
  - 常用来做异步队列使用，将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理。
  - 除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）。
- 通过 LRANGE 查看对应下标范围的列表元素：通过 LRANGE 命令可以基于 List 实现分页查询，性能非常高！
- 最新文章、最新动态：LPUSH、LRANGE。

PART1-3.五种对象系统之哈希对象（hash）（字典）:

哈希对象的编码（底层实现）可以是ziplist或者hashtable。
- Hash对象是一个键值对集合对象，其中 value 的形式入： value=[{field1，value1}，…{fieldN，valueN}]，就是因为哈希对象value是这么个怂样子，所以哈希对象特别合适来存储对象。【Redis 中的 Hash 是一个 String 类型的 field-value（键值对）的映射表，，特别适合用于存储对象，后续操作的时候，你可以直接修改这个对象中的某些字段的值。】
  - 哈希对象和字符串对象的差别：
- ziplist编码的哈希对象使用压缩列表作为底层实现【如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；】，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾
  - redis为了节约内存，zset 和 hash 容器对象在元素个数较少的时候都是采用压缩列表 (ziplist) 进行存储
  - 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
  - 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
- 在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了
  - quicklist 虽然通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题。因为 quicklistNode 还是用了压缩列表来保存元素，压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构。于是，Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。
  - listpack实现：listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。【listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题】
- hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存。【如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。或者说当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。】
  - Redis 是使用了一个哈希表保存所有键值对，哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对
    - 【为什么能这么快，就是因为哈希表是将一个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表大小)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第几个哈希桶。哈希表实际上是数组，这个数组的下标也叫做桶下标，然后就可以通过索引值快速查询到数据】。哈希表其实就是一个数组，数组中的元素叫做哈希桶，数组的下标就叫做桶下标。
  - Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维hash的数组位置碰撞时，就会将碰撞的元素使用链表串接起来【Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。】
    - 解决键冲突：当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。
      - Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。要想解决这一个问题就需要进行rehash，也就是对哈希表的大小进行扩展。
      - 链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。
    - 哈希算法：当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组dictEntry的指定索引上面。
      - Redis计算哈希值和索引值的方法：
        使用字典设置的哈希函数，计算键key 的哈希值 hash = dict->type->hashFunction(key);
        使用哈希表的sizemask 属性和哈希值，计算出索引值
        根据情况不同，ht[x] 可以是ht[0] 或者ht[1] index = hash & dict->ht[x].sizemask;
      - 当字典被用作数据库的底层实现，或者哈希键的底层实现时， Redis使用MurmurHash2算法来计算键的哈希值。这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。
    - Redis 的字典的值只能是字符串，另外它们rehash的方式不一样，因为 Java 的 HashMap在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash。Redis 为了高性能，不能堵塞服务，所以采用了 渐进式 rehash 策略
      - 为什么要进行rehash:
        随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩，而扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成。
        负载因子= 哈希表已保存节点数量/ 哈希表大小: load_factor = ht[0].used / ht[0].size
      - 触发 rehash 操作的条件，主要有两个：
        当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
        当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作
      - Redis对字典的哈希表执行rehash的步骤如下：
        
        1）为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：
        如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used*2的2^n（2的n次方幂）；
        如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于 ht[0].used的2^n（2的n次方幂）
        
        2）将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上
        
        这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。【为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。】
        在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）【之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表了】
        
        3）当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
      - 渐进式 rehash 会在rehash的同时，保留新旧两个 hash 结构，查询时会同时查询两个hash结构，然后在后续的定时任务中以及 hash操作指令中(将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。)，循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。当搬迁完成了，就会使用新的hash结构取而代之。
        
        大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个O(n)级别的操作，作为单线程的Redis表示很难承受这样耗时的过程,庞大的计算量可能会导致服务器在一段时间内停止服务。步子迈大了会扯着蛋，所以Redis使用渐进式rehash小步搬迁。虽然慢一点，但是肯定可以搬完。
        
        哈希表渐进式rehash的详细步骤：
        1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
        2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
        3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在 rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后**，程序将rehashidx属性的值增一**。
        因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。
        在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表
        
        4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
- 编码转换:对于使用ziplist编码的列表对象来说，当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面，对象的编码也会从ziplist变为hashtable。
  - 当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：
    - 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
    - 哈希对象保存的键值对数量小于512个；
  - 不能满足这两个条件的哈希对象需要使用hashtable编码。
- 字典是一种用于保存键值对（key-value pair）的抽象数据结构。
  - 除了用来表示数据库之外，字典还是哈希键的底层实现之一。
  - Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。
  - 字典的每个键都是一个字符串对象，对象中保存了键值对的键；
  - 在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。
  - 字典的每个值都是一个字符串对象，对象中保存了键值对的值。
底层结构：

/*- 哈希表：Redis 的哈希表结构-  - 每个字典都使用两个哈希表，从而实现渐进式 rehash 。*/
typedef struct dictht {// 哈希表数组。dictht中的table属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。dictEntry **table;//哈希表是一个数组（dictEntry **table），数组的每个元素是一个指向「哈希表节点（dictEntry）」的指针。// 哈希表大小，也即是table数组的大小，unsigned long size;// 哈希表大小掩码，用于计算索引值// 总是等于 size - 1。sizemask属性的值总是等于 size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。unsigned long sizemask;// 该哈希表已有节点的数量。used属性则记录了哈希表目前已有节点（键值对）的数量unsigned long used;
} dictht;
...struct RedisDb { dict* dict; // all keys key=>valuedict* expires; // all expired keys key=>long(timestamp)... 
} 
struct zset { dict *dict; // all values value=>scorezskiplist *zsl; 
}
.../** 哈希表节点。dictht中的table属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对。* dictEntry 结构里不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。*/
typedef struct dictEntry {// 键。key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。void *key;// 值。而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。union {void *val;uint64_t u64;int64_t s64;} v;// 指向下个哈希表节点，形成链表。next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，也就是拉链法，以此来解决键冲突（collision）的问题。struct dictEntry *next;
} dictEntry;/** 字典*/
typedef struct dict {/***type属性和privdata属性是针对不同类型的键值对，为创建多态字典 而设置的：*/// 类型特定函数。type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置 不同的类型特定函数。dictType *type;// 私有数据。而privdata属性则保存了需要传给那些类型特定函数的可选参数void *privdata;// 哈希表。ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用dictht ht[2];// rehash 索引// 当rehash不在进行时，值为-1。除了ht[1]之外，另一个和rehash有关的属性就是rehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在运行的安全迭代器的数量int iterators; /* number of iterators currently running */
} 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;

在这里插入图片描述

哈希对象的应用场景：在 Redis 中可以把 list 用作栈、队列、阻塞队列。或者用于系统中对象数据的存储。相关命令：HSET （设置单个字段的值）、HMSET（设置多个字段的值）、HGET（获取单个字段的值）、HMGET（获取多个字段的值）
- hash 结构也可以用来存储用户信息，不同于字符串一次性需要全部序列化整个对象，hash 可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。而以整个字符串的形式去保存用户信息的话就只能一次性全部读取，这样就会比较浪费网络流量。
  - 比如，购物车信息建议使用 Hash 存储：由于购物车中的商品频繁修改和变动
- 用作缓存对象：Hash 类型的（key，field， value）的结构与对象的（对象id，属性，值）的结构相似，也可以用来存储对象。
  - 在介绍 String 类型的应用场景时有所介绍，String + Json也是存储对象的一种方式，那么存储对象时，到底用 String + json 还是用 Hash 呢？【一般对象用 String + Json 存储，对象中某些频繁变化的属性可以考虑抽出来用 Hash 类型存储。】
  - 举例：在数据库中有这两行记录：
    
    使用如下命令，将用户对象的信息存储到 Hash 类型：

PART1-4.五种对象系统之集合对象（set）:类似于HashSet
在这里插入图片描述

集合对象的编码（底层实现）可以是intset整数集合或者hashtable哈希表。【一个集合最多可以存储 2^32-1 个元素。Set 类型除了支持集合内的增删改查，同时还支持多个集合取交集、并集、差集。当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会使用整数集这个数据结构作为底层实现】
- intset编码的集合对象使用整数集合作为底层实现【如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构】，集合对象包含的所有元素都被保存在整数集合里面。
  - intset整数集合：是集合键的底层实现之一，当一个集合只包含整数值元素（集合中的所有元素都是整数值），并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
  - intset整数集合可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。
```
typedef struct intset {// 编码方式.虽然intset结构将contents属性声明为int8_t类型的数组，但实际上 contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决 于encoding属性的值：如果encoding属性的值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组，数组里的每个项都是一个int16_t类型的整数值（最小值为-32768，最大值为32767）。如果encoding属性的值为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组，数组里的每个项都是一个int32_t类型的整数值（最小值为-2147483648，最大值为2147483647）。如果encoding属性的值为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组，数组里的每个项都是一个int64_t类型的整数值（最小值为-9223372036854775808，最大值为9223372036854775807）。uint32_t encoding;// 集合包含的元素数量.length属性记录了整数集合包含的元素数量，也即是contents数组的长度。uint32_t length;// 保存元素的数组.contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。int8_t contents[];
} intset;
```
    - 可以看到，集合对象的底层编码或者叫做底层数据结构是整数集合，而这个整数集合保存元素的容器是一个 contents 数组，虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值【不同类型的 contents 数组，意味着数组的大小也会不同】。比如：
      - 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
      - 如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
      - 如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；
  - 每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时【比如当我们将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时】，整数集合需要先进行升级 （upgrade）(每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O（N）)，然后才能将新元素添加到整数集合里面。【也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里，当然升级的过程中，也要维持整数集合的有序性。】
    - 整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后在将每个元素按间隔类型大小分割，如果 encoding 属性值为 INTSET_ENC_INT16，则每个元素的间隔就是 16 位。
    - 升级整数集合并添加新元素共分为三步进行：
      - 1）根据新类型的长度，以及集合元素的数量（包括要添加的新元素在内），对底层数组进行空间重分配。也就是扩展整数集合底层数组的空间大小，并为新元素分配空间。
      - 2）将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
      - 3）将新元素添加到底层数组里面。
    - 举个例子：假设有一个整数集合里有 3 个类型为 int16_t 的元素。现在，往这个整数集合中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，所以整数集合要进行升级操作，首先需要为 contents 数组扩容，在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变
    - 整数集合的升级策略有两个好处:
      - 一个是提升整数集合的灵活性
        因为C语言是静态类型语言，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。就是因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将int16_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。
      - 另一个是尽可能地节约内存
        整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。
        或者说，如果要让一个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简单做法就是直接使用 int64_t 类型的数组。不过这样的话，当如果元素都是 int16_t 类型的，就会造成内存浪费的情况。【整数集合升级就能避免这种情况，如果一直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就一直是用 int16_t 类型的数组，只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进行升级操作。】
    - 整数集合不支持降级操作，一旦对数组进行了升级，就会一直保持升级后的状态。比如前面的升级操作的例子，如果删除了 65535 元素，整数集合的数组还是 int32_t 类型的，并不会因此降级为 int16_t 类型
- hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。
编码的转换:对于使用intset编码的集合对象来说，当使用intset编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典里面，并且对象的编码也会从intset变为hashtable。
- 当集合对象可以同时满足以下两个条件时，对象使用intset编码：
  - 集合对象保存的所有元素都是整数值；
  - 集合对象保存的元素数量不超过512个。
- 不能满足这两个条件的集合对象需要使用hashtable编码。
集合对象的应用场景：因为集合对象不能有重复元素，所以来于数据不能重复的场景、无序、多个数据源交集和并集的场景
- Set 类型比较适合用来数据去重和保障数据的唯一性，还可以用来统计多个集合的交集、错集和并集等，当我们存储的数据是无序并且需要去重的情况下，比较适合使用集合类型进行存储。
  - Set 的差集、并集和交集的计算复杂度较高，在数据量较大的情况下，如果直接执行这些计算，会导致 Redis 实例阻塞。【在主从集群中，为了避免主库因为 Set 做聚合计算（交集、差集、并集）时导致主库被阻塞，我们可以选择一个从库完成聚合统计，或者把数据返回给客户端，由客户端来完成聚合统计】
    - 去重,比如可以取出去重的结果集；可用于抽奖spop，可以保证一个人只抽中一个奖品
- 点赞：Set 类型可以保证一个用户只能点一个赞
- 共同关注：Set 类型支持交集运算【可以基于 Set 轻易实现交集、并集、差集的操作：共同好友(交集)、共同粉丝(交集)、共同关注(交集)、好友推荐（差集）、音乐推荐（差集）、订阅号推荐（差集+交集）等场景。相关命令：SINTER（交集）、SINTERSTORE （交集）、SUNION （并集）、SUNIONSTORE（并集）、SDIFF（差集）、SDIFFSTORE （差集）】，所以可以用来计算共同关注的好友、公众号等。【key 可以是用户id，value 则是已关注的公众号的id。】
- 抽奖活动：存储某活动中中奖的用户名【SPOP（随机获取集合中的元素并移除，适合不允许重复中奖的场景）、SRANDMEMBER（随机获取集合中的元素，适合允许重复中奖的场景）】，Set 类型因为有去重功能，可以保证同一个用户不会中奖两次。key为抽奖活动名，value为员工名称，将所有员工名称放入抽奖箱中
  - 使用 Set 实现抽奖系统需要用到什么命令？
    - SPOP key count ： 随机移除并获取指定集合中一个或多个元素，适合不允许重复中奖的场景
    - SRANDMEMBER key count : 随机获取指定集合中指定数量的元素，适合允许重复中奖的场景

PART.1-5.五种对象系统之有序集合对象（zset(有序列表)）:
在这里插入图片描述

有序集合的编码（底层实现）可以是ziplist或者skiplist。有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。【Zset 类型（有序集合对象类型）相比于 Set 对象类型多了一个排序属性 score（分值）或者说权重参数 score，对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序集合的元素值，一个是排序值或者叫分值。这个有序集合的元素值虽说不能重复但是排序值或者叫分值可以重复（使得集合中的元素能够按 score 进行有序排列，还可以通过 score 的范围来获取元素的列表。有点像是 Java 中 HashMap 和 TreeSet 的结合体）】
- ziplist编码的压缩列表对象使用压缩列表ziplist作为底层实现【如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构】，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。
  - 压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。
- skiplist编码的有序集合对象使用zset结构作为底层实现【如果有序集合的元素不满足元素个数小于 128 个，并且每个元素的值小于 64 字节的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构】，一个zset结构同时包含一个字典和一个跳跃表：
  - Redis 只有在 Zset 有序集合对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。
    - Zset 对象是唯一一个同时使用了两个数据结构来实现的 Redis 对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是 既能进行高效的范围查询，也能进行高效单点查询。
      - Zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如 ZSCORE 操作）【这是因为它同时采用了哈希表进行索引】。
```
/* ZSETs use a specialized version of Skiplists */
/** 跳跃表节点。zskiplistNode结构用于表示跳跃表节点，*/
typedef struct zskiplistNode {// 成员对象.跳跃表节点的object属性保存了元素的成员robj *obj;// 分值.跳跃表节点的score属性则保存了元素的分值double score;// 后退指针。每个跳表节点都有一个后向指针，指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 跨度unsigned int span;} level[];} zskiplistNode;/** 跳跃表。而zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。*/
typedef struct zskiplist {// 跳表的表头节点和表尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；struct zskiplistNode *header, *tail;// 表中节点的数量，或者说跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；unsigned long length;// 表中层数最大的节点的层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量int level;
} zskiplist;/** 有序集合*/
typedef struct zset {// 字典，键为成员，值为分值。zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值// 用于支持 O(1) 复杂度的按成员取分值操作dict *dict;// 跳跃表，按分值排序成员.zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个 跳跃表节点都保存了一个集合元素,通过这个跳跃表，程序可以对有序集合进行范围型操作// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作// 以及范围操作zskiplist *zsl;
} zset;
```
  - 跳表：又叫跳跃表（skiplist）。跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针【跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。】，从而达到快速访问节点的目的。下图是一个跳跃表。
    - 跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
      - 跳表的查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。
      - skip list快不快看跟哪个数据结构比，比如跟链表比优势就是大大的。
    - Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。
    - Redis只在两个地方用到了跳跃表，除此之外，跳跃表在Redis里面没有其他用途。我个人感觉 skip list相当于是一个三项链表，多了一个level数值，相当于就解决了链表查询的缺点，基本上可以算是从任意一个开始查询到任意一个，也就是牺牲存储空间来提高查询速度，跟树一样一样的。【skip list，类平衡树，保持平衡】
      - 一个是实现有序集合键
      - 另一个是在集群节点中用作内部数据结构
  - 跳跃表的实现：Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中：
    - zskiplistNode结构：zskiplistNode结构用于表示跳跃表节点，多个跳跃表节点zskiplistNode就可以组成一个跳跃表。那为什么还需要zskiplist结构呢(是因为通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息)。
      - zskiplistNode结构包含以下属性：
        层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1 代表第一层，L2代表第二层，以此类推。【level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了 指向下一个跳表节点的指针和跨度，跨度时用来记录两个节点之间的距离。】
        
        跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度， 一般来说，层的数量越多，访问其他节点的速度就越快。 每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为 level数组的大小，这个大小就是层的“高度”。
        
        跳表节点层数设置：跳表的相邻两层的节点数量的比例会影响跳表的查询性能。比如第二层的节点数量只有 1 个，而第一层的节点数量有 6 个。这时，如果想要查询节点 6，那基本就跟链表的查询复杂度一样，就需要在第一层的节点中依次顺序查找，复杂度就是 O(N) 了。所以，为了降低查询复杂度，我们就需要维持相邻层结点数间的关系。跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。。
        那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？【如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数【跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。】，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。】。相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64
        
        每个层都带有两个属性：前进指针和跨度。
        前进指针专门用于遍历操作访问位于表尾方向的其他节点（每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。）
        
        而跨度则记录了前进指针所指向节点和当前节点的距离（层的跨度（level[i].span属性）用于记录两个节点之间的距离）。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
        跨度实际上是用来计算这个节点在跳表中的排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。【因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。】
        
        后退（backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用【每个跳表节点都有一个后向指针，指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。】。
        节点的后退指针（backward属性）用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。
        
        分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
        节点的分值（score属性）是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。
        
        成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象。
        节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。
        在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。
    - zskiplist结构：zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。多个跳跃表节点zskiplistNode就可以组成一个跳跃表。那为什么还需要zskiplist结构呢(是因为通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息。zskiplist结构包含以下属性：
      - header：指向跳跃表的表头节点。通过这两个指针，程序定位表头节点和表尾节点的复杂度为O（1）。【跳表的头节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点】
      - tail：指向跳跃表的表尾节点。通过这两个指针，程序定位表头节点和表尾节点的复杂度为O（1）【跳表的尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点】
      - level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。 level属性则用于在O（1）复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。【跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数】
      - length：记录跳跃表的长度，也即是跳跃表目前包含节点的数量 （表头节点不计算在内）。通过使用length属性来记录节点的数量，程序可以在O（1）复杂度内返回跳跃表的长度。【跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量】
  - 跳跃表节点的查询过程：查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：
    - 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
    - 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
    - 如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。
- 在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了
- 编码的转换:对于使用ziplist编码的有序集合对象来说，当使用ziplist编码所需的两个条件中的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在压缩列表里的所有集合元素都会被转移并保存到zset结构里面，对象的编码也会从ziplist变为skiplist。
  - 当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：
    - 有序集合保存的元素数量小于128个；
    - 有序集合保存的所有元素成员的长度都小于64字节；
  - 不能满足以上两个条件的有序集合对象将使用skiplist编码。
- 压缩列表和跳表这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。
- 为什么有序集合需要同时使用跳跃表和字典来实现？
  - 在理论上，有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。
  - 举个例子：
    - 如果我们只使用字典来实现有序集合，那么虽然以O（1）复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作——比如ZRANK、ZRANGE等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O（NlogN）时间复杂度，以及额外的O（N）内存空间（因为要创建一个数组来保存排序后的元素）。
    - 另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

有序集合的应用场景：
- 有序集合经常用于需要对数据根据某个权重进行排序的场景，我们可以自己来决定每个元素的权重值【比如说，我们可以根据元素插入 Sorted Set 的时间确定权重值，先插入的元素权重小，后插入的元素权重大。】。。比如在直播系统中，实时排行信息（包括直播间在线用户列表、各种礼物排行榜、弹幕消息排行榜【也就是不同角度下的消息排行榜】，这些都是数据更新频繁或者需要分页显示，可以优先考虑使用 Sorted Set）等
  - Redis 中的 sorted set 的数据结构经常被用在各种排行榜的场景，比如直播间送礼物的排行榜、朋友圈的微信步数排行榜、王者荣耀中的段位排行榜、话题热度排行榜等等。相关的一些 Redis 命令: ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。
- 有序集合不能有重复元素，并且有序集合中的每个元素都需要指定一个分数，根据分数对元素进行升序排序。所以有序集合可以做排行榜
  - Redis 的 ZSET 做排行榜时，如果要实现分数相同时按时间顺序排序怎么实现？
    - 将 score 拆成高 32 位和低 32 位，高 32 位存分数，低 32 位存时间的方法。
- Redis中的有序集合Zset可以实现延时队列(把当前时间戳和延时时间相加，也就是到期时间，存入Redis中，然后不断轮询，找到到期的，拿到再删除即可。)，Zset可以看作是缩小版的redis，可以看作是用来存储键值对的集合，是集合名-K-V的结构，在Zset中，会按照Score进行排序。
  - Redis中的ZSet是一个有序的Set，内部使用HashMap和跳表(SkipList)来保证数据的存储和有序。zset有一个score值，可以在添加数据的时候，使用zadd把score写成未来某个时刻的unix时间戳，然后按照时间大小进行排序，定时去查询redis的zset队列首部，即可查询到最早过期的数据，进行处理。以此完成延时逻辑。
    - 底层：HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score,
      - 为什么使用跳跃表：使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。
  - 有序集合中键值对的键被称为成员，值被称为分值，分值必须为浮点数。
- 需要存储的数据有优先级或者重要程度的场景比如优先级任务队列。
  - ZRANGE (从小到大排序) 、 ZREVRANGE （从大到小排序）、ZREVRANK (指定元素排名)。

PART1-6:三种特殊数据类型:

1.geospatial indexes(地理空间): Redis 在 3.2 推出Geo类型，该功能可以推算出地理位置信息【Geospatial index（地理空间索引，简称 GEO） 主要用于存储地理位置信息。通过 GEO 我们可以轻松实现两个位置距离的计算、获取指定位置附近的元素等功能。，基于 Sorted Set 实现【GEO 中存储的地理位置信息的经纬度数据通过 GeoHash 算法转换成了一个整数，这个整数作为 Sorted Set 的 score(权重参数)使用。】。】，两地之间的距离。【Redis GEO 是 Redis 3.2 版本新增的数据类型，主要用于存储地理位置信息，并对存储的信息进行操作。】
- GEO 本身并没有设计新的底层数据结构，而是直接使用了 Sorted Set 集合类型。
  - GEO 类型使用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换，这其中的两个关键机制就是「对二维地图做区间划分」和「对区间进行编码」。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为 Sorted Set 元素的权重分数。这样一来，我们就可以把经纬度保存到 Sorted Set 中，利用 Sorted Set 提供的“按权重进行有序范围查找”的特性，实现 LBS 服务中频繁使用的“搜索附近”的需求。
- 在日常生活中，我们越来越依赖搜索“附近的餐馆”、在打车软件上叫车，这些都离不开基于位置信息服务（Location-Based Service，LBS）的应用
- 比如，应用场景的滴滴叫车：
  - 附近的人：相关命令: GEOADD、GEORADIUS、GEORADIUSBYMEMBER
2.hyperloglog（计数器）:HyperLogLog 提供不精确的去重计数。基数：数学上集合的元素个数，是不能重复的。这个数据结构常用于统计网站的 UV(独立访客,00:00-24:00内相同的客户端只被计算一次。)。
- Redis HyperLogLog 是 Redis 2.8.9 版本新增的数据类型，是一种用于「统计基数」的数据集合类型，基数统计就是指统计一个集合中不重复的元素个数。但要注意，HyperLogLog 是统计规则是基于概率完成的，不是非常准确，标准误算率是 0.81%。
  - HyperLogLog 是一种有名的基数计数概率算法，基于 LogLog Counting(LLC)优化改进得来，并不是 Redis 特有的，Redis 只是实现了这个算法并提供了一些开箱即用的 API
  - Redis 提供的 HyperLogLog 占用空间非常非常小，只需要 12k 的空间就能存储接近2^64个不同元素。这是真的厉害，这就是数学的魅力么！并且，Redis 对 HyperLogLog 的存储结构做了优化，采用两种方式计数：
    - 稀疏矩阵：计数较少的时候，占用空间很小。
    - 稠密矩阵：计数达到某个阈值的时候，占用 12k 的空间
- HyperLogLog 的优点：在输入元素的数量或者体积非常非常大时，计算基数所需的内存空间总是固定的、并且是很小的。在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数，和元素越多就越耗费内存的 Set 和 Hash 类型相比，HyperLogLog 就非常节省空间。
  - 用 Java 语言来说，一般 long 类型占用 8 字节，而 1 字节有 8 位，即：1 byte = 8 bit，即 long 数据类型最大可以表示的数是：2^{63-1。对应上面的2}64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024 字节的规则来计算内存总数，就是：((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K，而 HyperLogLog 却可以用 12K 就能统计完。
- 应用场景：热门网站每日/每周/每月访问 ip 数统计、热门帖子 uv 统计。相关命令：PFADD、PFCOUNT
  - 使用 HyperLogLog 统计页面 UV 怎么做？
    - 将访问指定页面的每个用户 ID 添加到 HyperLogLog 中:PFADD PAGE_1:UV USER1 USER2 ...... USERn
    - 统计指定页面的 UV:PFCOUNT PAGE_1:UV
3.bitmaps(位图): bitmap 就是 通过最小的单位 bit 来进行0或者1的设置，bitmaps是一串连续的只有0和1的二进制数组，可以通过偏移量（offset）定位元素，表示某个元素对应的值或者状态。一个 bit 的值，或者是0，或者是1；也就是说一个 bit 能存储的最多信息是2。
- 内部实现：Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型。【String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态，你可以把 Bitmap 看作是一个 bit 数组。】
- 常用操作：
- 应用场景：由于 bit 是计算机中最小的单位，使用它进行储存将非常节省空间【在记录海量数据时，Bitmap 能够有效地节省内存空间】，特别适合一些数据量大且使用二值统计的场景，比如用户签到情况、活跃用户情况、用户行为统计（比如是否点赞过某个视频）。相关命令：SETBIT、GETBIT、BITCOUNT、BITOP。
  - bitmap 常用于统计用户信息比如活跃粉丝和不活跃粉丝、登录和未登录、是否打卡【签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是 31 天）的签到情况用 31 个 bit 位就可以，而一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型。】
    - 使用 Bitmap 统计活跃用户怎么做？
      - 使用日期（精确到天）作为 key，然后用户 ID 为 offset，如果当日活跃过就设置为 1。
        初始化数据：
        
        统计 20220906~20220907 总活跃用户数:
        
        统计 20220906~20220907在线活跃用户数:
    - 如何统计这个月首次打卡时间呢？【Redis 提供了 BITPOS key bitValue [start] [end]指令，返回数据表示 Bitmap 中第一个值为 bitValue 的 offset 位置。】可以通过可选的 start 参数和 end 参数指定要检测的范围。命令将检测整个位图。
    - 判断用户登陆状态
      - 位图可以用setbit这个命令来统计用户登陆天数，且窗口随机，随机窗口就指得是这个长条bitmap数组。之前用数据库【如果用数据库的话，还要读磁盘，多慢呀对吧】，要建一个数据库表，记录用户名、登录时间等等。而redis用50个字节可以记录某个用户全年的登陆状态01.....01总共400个代表第一天第二天...第400天，为1就代表你登陆为0代表你没登陆。
    - 连续签到用户总数
Redis Stream 是 Redis 5.0 版本新增加的数据类型，Redis 专门为消息队列设计的数据类型。
- 在 Redis 5.0 Stream 没出来之前，消息队列的实现方式都有着各自的缺陷【基于以下问题，Redis 5.0 便推出了 Stream 类型也是此版本最重要的功能，用于完美地实现消息队列，它支持消息的持久化、支持自动生成全局唯一 ID、支持 ack 确认消息的模式、支持消费组模式等，让消息队列更加的稳定和可靠】，例如：
  - 发布订阅模式，不能持久化也就无法可靠的保存消息，
  - 并且对于离线重连的客户端不能读取历史消息的缺陷；
  - List 实现消息队列的方式不能重复消费，一个消息消费完就会被删除，
  - 而且生产者需要自行实现全局唯一 ID。

PART2:

容器型数据结构的通用规则
- list/set/hash/zset 这四种数据结构是容器型数据结构，
  - 如果容器不存在，那就创建一个，再进行操作。比如 rpush 操作刚开始是没有列表的，Redis 就会自动创建一个，然后再 rpush 进去新元素。
  - 如果容器里元素没有了，那么立即删除元素，释放内存。这意味着 lpop 操作到最后一个元素，列表就消失了
过期时间：Redis 所有的数据结构都可以设置过期时间，时间到了，Redis 会自动删除相应的对象。需要注意的是过期是以对象为单位，比如一个 hash 结构的过期是整个 hash 对象的过期，而不是其中的某个子 key。还有一个需要特别注意的地方是如果一个字符串已经设置了过期时间，然后你调用了 set 方法修改了它，它的过期时间会消失。
- 比如说单点登录，就可以利用Redis的过期时间来实现
类型检查与命令多态:
- Redis中用于操作键的命令基本上可以分为两种类型。
  - 其中一种命令可以对任何类型的键执行，比如说DEL命令、 EXPIRE命令、RENAME命令、TYPE命令、OBJECT命令等:
    - 命令操作：**http://redis.cn/commands.html**这个Redis的官方网站可以查看各种Redis的命令用法以及意义
  - 另一种命令只能对特定类型的键执行,比如:
    - SET、GET、APPEND、STRLEN等命令只能对字符串键执行；
    - HDEL、HSET、HGET、HLEN等命令只能对哈希键执行；
    - RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行；
    - SADD、SPOP、SINTER、SCARD等命令只能对集合键执行；
    - ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执
- 类型检查的实现:为了确保只有指定类型的键可以执行某些特定的命令，在执行一个类型特定的命令之前， Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令。
  - 类型特定命令所进行的类型检查是**通过redisObject结构的type属性**来实现的：
    - 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型:
      - 如果是的话，服务器就对键执行指定的命令；
      - 否则，服务器将拒绝执行命令，并向客户端返回一个类型错误。
- 多态命令的实现:Redis除了会根据值对象的类型来判断键是否能够执行指定命令之外(就是前面那个类型检查呗)，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。
  - 以列表对象为例:列表对象有 ziplist和linkedlist两种编码可用，其中ziplist使用压缩列表API来实现列表命令，而linkedlist则使用双端链表API来实现列表命令。比如咱们执行列表对象的LLEN命令:可以认为LLEN命令是多态（polymorphism）的，只要执行LLEN命令的是列表键，那么无论值对象使用的是ziplist编码还是linkedlist编码，命令都可以正常执行。
    - :基于类型的多态——一个命令可以同时用于处理多种不同类型的键，
    - :基于编码的多态——一个命令可以同时用于处理多种不同编码。
内存回收:因为C语言并不具备自动内存回收功能，所以Redis在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。
- 对象的引用计数信息会随着对象的使用状态而不断变化：
  - 在创建一个新对象时，引用计数的值会被初始化为1；
  - 当对象被一个新程序使用时，它的引用计数值会被增一；
  - 当对象不再被一个程序使用时，它的引用计数值会被减一；
  - 当对象的引用计数值变为0时，对象所占用的内存会被释放。

/* The actual Redis Object */
/*- Redis 对象*/
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {// 类型unsigned type:4;// 编码unsigned encoding:4;// 对象最后一次被访问的时间unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */// 引用计数int refcount;// 指向实际值的指针void *ptr;
} robj;

对象共享:除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。
- 举个例子:如果这时键B也要创建一个同样保存了整数值100的字符串对象作为值对象，那么服务器有以下两种做法：
  - 1）为键B新创建一个包含整数值100的字符串对象；
  - 2）让键A和键B共享同一个字符串对象； 以上两种方法很明显是第二种方法更节约内存。
    - 在Redis中，让多个键共享同一个值对象需要执行以下两个步骤：
      - 1）将数据库键的值指针指向一个现有的值对象；
      - 2）将被共享的值对象的引用计数增一。
- 目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到 9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
  - 尽管共享更复杂的对象可以节约更多的内存，但受到 CPU时间的限制，Redis只对包含整数值的字符串对象进行共享。

巨人的肩膀：
https://www.javalearn.cn
B站各位大佬
高性能MySQL
mysql技术内幕
小林coding
Redis设计与实现

java基础巩固-宇宙第一AiYWM：为了维持生计，Redis基础Part2(Redis的数据结构)~整起

相关文章

空间管理员（一）AFS文件目录系统索引节点vfs_inode结构

综合架构web服务之nginx详解

Hive 3.x详细笔记

淘宝、天猫API调用如何按关键词上搜索，item_search_tmall - 按关键字搜索天猫商品

计算机组成原理＜五＞——存储系统

redis配置文件密码加密

Python判断字符串是否包含特定子串的7种方法（转）

Kafka基础原理