Redis源码、面试指南(3)数据对象类型编码（下）

Redis源码、面试指南(3)数据对象类型编码（上）：https://developer.aliyun.com/article/1508229

哈希对象

源码文件t_hash.c。

编码是ziplist或者hashtable。

• ziplist编码，底层是压缩列表，有两个条件，哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；哈希对象保存的键值对数量小于 512 个；
  

每当有新的键值对要加入到哈希对象时，保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；且这些键值对遵循先来后到的原则。

注：在使用ziplist编码的时候，获取键对应值的时间复杂度不是O(1)，而是O(N^2)(先遍历键，在遍历值是否相等)！但由于使用ziplist的时候，长度和键的长度较小，对性能影响不是很大。

• hashtable编码，当不满足上述的两个条件时，就使用字典作为底层实现。哈希对象中的每个键值对都使用一个字典键值对来保存：字典的每个键和值都是一个字符串对象；

以下是一个以字典为底层的哈希对象实例：

注：当ziplist不满足两个条件其中之一时，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面。

注：常用命令

集合对象

源码问阿金t_set.c。

集合对象的编码可以是intset或者hashtable 。

• intset编码，使用整数集合作为集合对象的实现，有两个条件：集合对象保存的所有元素都是整数值；集合对象保存的元素数量不超过512个；

集合对象包含的所有元素都被保存在整数集合里面，见下：

• hashtable编码，当intset编码的两个条件不满足时，使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为 NULL（因为没有没有键就代表了值）。

注：常用命令

有序集合对象

源码文件t_zset.c。

有序集合的编码可以是ziplist和skiplist。

• ziplist 编码，使用压缩列表作为底层实现有两个条件：有序集合保存的元素数量小于 128 个；有序集合保存的所有元素成员的长度都小于 64 字节；

注：ziplist为了保证有序性，每次插入删除操作时，都可能需要对其中的数据进行移动。

每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，而第二个元素则保存元素的分值（score）（排序）。

• skiplist 编码，不满足上述条件时的有序集合对象使用zset 结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：

typedef struct zset {
    zskiplist *zsl;
    dict *dict;
} zset;

zset结构中的跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的 object 属性保存了元素的成员，而跳跃表节点的 score 属性则保存了元素的分值。 通过这个跳跃表，

程序可以对有序集合进行范围型操作，比如 ZRANK 、ZRANGE 等命令就是基于跳跃表 API 来实现的。

除此之外，zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O(1)复杂度查找给定成员的分值,ZSCORE命令就是根据这一特性实现的，而很多其他有序集合命令都在实现的内部用到了这一特性。

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个 double 类型的浮点数。 值得一提的是，虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

为什么需要这么做呢？

在理论上来说，有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。

举个例子，如果我们只使用字典来实现有序集合，那么虽然以O(1)复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作一一一比如ZRANK、ZRANG等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O(NlogN)时间复杂度，以及额外的O(N)内存空间（因为要创建一个数组来保存排序后的元素）

另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将上升到到O(logn)。

因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

注：常用命令

Hyperloglog对象

源码文件：hyperloglog.c。

建议直接参考：

https://blog.csdn.net/qq_39885372/article/details/104245363

类型检查和多态

Redis中用于操作键的命令基本分为两种，一种是键共有操作，比如说DEL命令、EXPIRE命令、RENAME命令、TYPE 命令、OBJECT命令等。另一种是键特定操作，如SET、GET、APPEND、STRLEN等命令只能对字符串键执行。

类型检查

在执行一个类型特定的命令之前， Redis 会先检查输入键的类型是否正确， 然后再决定是否执行给定的命令。通过 redisObject 结构的 type 属性来实现的：

多态命令

这里指的是同一个对象一般具有两种编码方式，比如hash对象是hashtable和ziplist，那么执行命令的时候是怎么确定的呢？也是根据其对象的编码格式来的：

件：hyperloglog.c。

建议直接参考：

https://blog.csdn.net/qq_39885372/article/details/104245363

类型检查和多态

Redis中用于操作键的命令基本分为两种，一种是键共有操作，比如说DEL命令、EXPIRE命令、RENAME命令、TYPE 命令、OBJECT命令等。另一种是键特定操作，如SET、GET、APPEND、STRLEN等命令只能对字符串键执行。

类型检查

在执行一个类型特定的命令之前， Redis 会先检查输入键的类型是否正确， 然后再决定是否执行给定的命令。通过 redisObject 结构的 type 属性来实现的：

[外链图片转存中…(img-VOWn19Ck-1618293094079)]

多态命令

这里指的是同一个对象一般具有两种编码方式，比如hash对象是hashtable和ziplist，那么执行命令的时候是怎么确定的呢？也是根据其对象的编码格式来的：