Redis 的 Hash 基础类型一个非常经典的设计，完美体现了 Redis 在内存效率和性能之间所做的权衡。

我们将从以下几个核心方面进行剖析：

  1. 底层两种编码（实现）结构
  2. 两种编码的切换（转换）条件
  3. 核心操作命令的源码实现逻辑
  4. 设计思想与总结

底层两种编码结构

Redis Hash 类型并不是用一种单一数据结构实现的，而是根据存储数据的具体情况，在两种编码之间动态选择：

  • ziplist (压缩列表)： 在数据量较小时使用，以节省内存。
  • hashtable (哈希表)： 在数据量较大时使用，以保证操作效率。

你可以通过 OBJECT ENCODING your_hash_key 命令来查看一个 Hash 键使用的内部编码。

a) ziplist (压缩列表)

ziplist 是 Redis 为了节约内存而设计的一种紧凑的、双向的顺序数据结构。它本质上是一个字节数组，可以包含任意多个 entry，这些 entry 会根据存储的内容长度不同而占用不同的字节数。

源码定义 (ziplist.c)：
虽然没有一个显式的结构体定义 ziplist，但其内存布局可以抽象为：

1
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  • zlbytes (uint32_t)： 整个 ziplost 占用的内存字节数。
  • zltail (uint32_t)： 到达最后一个 entry 的偏移量，用于快速定位队尾。
  • zllen (uint16_t)： entry 的个数。如果超过 2^16-1，则需要遍历整个列表才能知道确切数量。
  • entry： 具体的节点，存储数据。
  • zlend (uint8_t)： 恒为 0xFF (255)，标记 ziplist 的结尾。

Entry 的构成：
每个 entry 由三部分组成：

1
<prevlen> <encoding> <content>
  • prevlen： 前一个 entry 的长度，用于反向遍历。长度可变（1字节或5字节）。
  • encoding： 编码类型，指明了 content 的数据类型（整数或字节数组）及其长度。长度可变（1, 2, 5字节）。
  • content： 实际存储的数据。

在 Hash 中的使用方式：
当 Hash 使用 ziplist 时，它的存储方式非常有趣。每对 field-value 会以两个连续的 entry 形式被追加到 ziplist 的末尾。

1
... [prev field entry] [prev value entry] | [new field entry] [new value entry] ...

例如，执行 HSET myhash name John，ziplist 中会添加两个 entry：一个是 "name"，另一个是 "John"。

优点：

  • 极省内存： 没有多余的指针开销，所有数据都存储在一块连续的内存里。prevlen 和 encoding 的可变长设计进一步压缩了空间。

缺点：

  • 操作效率低： 每次查找、插入、删除都需要遍历整个列表，时间复杂度为 O(N)。虽然因为数据量小，绝对时间可能很短，但复杂度是线性的。

b) hashtable (字典)

当数据量变大时，ziplist 的效率就无法接受了。此时，Redis 会将 Hash 的编码从 ziplist 转换为 hashtable。

Redis 的 hashtable 实现是一个标准的字典（Dict），使用链地址法解决哈希冲突。它和我们熟知的 Java HashMap 非常相似。

核心源码结构 (dict.h)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 哈希表节点
typedef struct dictEntry {
    void *key;              // 键 (field)
    union {
        void *val;          // 值 (value)
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下个哈希表节点，形成链表（解决哈希冲突）
} dictEntry;

// 哈希表结构
typedef struct dictht {
    dictEntry **table;      // 指针数组，俗称桶（bucket）
    unsigned long size;     // table数组的大小，总是2的幂次
    unsigned long sizemask; // size-1，用于计算索引值
    unsigned long used;     // 已有节点的数量
} dictht;

// 字典（主结构）
typedef struct dict {
    dictType *type; // 类型特定函数，用于实现多态（如计算hash的函数）
    void *privdata; // 私有数据
    dictht ht[2];   // 两个哈希表，用于渐进式Rehash
    long rehashidx; // Rehash进度，如果不在rehash中，值为-1
    int iterators;  // 当前正在运行的迭代器数量
} dict;

在 Hash 中的使用方式：
Redis 的 Hash 对象使用一个 dict 结构来存储。field 作为字典的 key，value 作为字典的 value。

特点：

  • O(1) 时间复杂度： 平均情况下，查找、插入、删除操作都非常快。
  • 消耗更多内存： 因为需要维护一个指针数组（table）以及每个节点的指针（next），内存开销比 ziplist 大。
  • 渐进式 Rehash： 这是 Redis Dict 的一个核心特性。当需要扩容或缩容时，它不是一次性完成的，而是分多次、渐进式地将数据从 ht[0] 迁移到 ht[1]。在此期间，查找、删除、更新操作会在两个表上进行，而新增操作只会在 ht[1] 上进行。rehashidx 记录了当前迁移的进度。这避免了单次 Rehash 操作导致的服务器停顿。

两种编码的切换条件

Redis 不会无缘无故地在两种编码间切换，它遵循严格的配置规则。

源码检查逻辑 (t_hash.c)：
在每次执行 HSET、HMSET 等可能增加字段的命令时，都会调用 hashTypeSet 函数。在这个函数中，会检查是否需要转换编码。

相关的配置参数在 redis.conf 中：

  • hash-max-ziplist-entries： 默认 512
  • hash-max-ziplist-value： 默认 64

转换规则：

  1. 从 ziplist 转换为 hashtable的条件（满足任一即可）：

    • Hash 中的 字段数量 超过了 hash-max-ziplist-entries。
    • 任意一个 字段或值的字节大小 超过了 hash-max-ziplist-value。

  2. 从 hashtable 转换回 ziplist？

    • 不会！ 编码转换是单向的。一旦从 ziplist 转成了 hashtable，即使后来通过 HDEL 删除了大量数据，字段数和 value 大小都降回了阈值以下，它也不会再转回 ziplist。这是因为转换操作需要遍历所有元素重新构建 ziplist，成本较高，且可能很快又会再次触发转换，得不偿失。

核心操作命令的源码实现逻辑

我们以 HSET 和 HGET 为例，看看它们的实现路径。

HSET 命令流程：

  1. 查找键： 根据 key 找到对应的 Redis Hash 对象。
  2. 检查编码：
    • 如果当前是 ziplist：
      • 先检查插入的 field 和 value 的长度是否超过 hash-max-ziplist-value。如果超过，则触发转换：创建一个空的 dict，遍历 ziplist 中的所有 field-value 对，将其逐一插入到 dict 中，然后释放 ziplist，并将对象的编码改为 hashtable。
      • 如果没超过，则继续使用 ziplist。
    • 如果当前是 hashtable，则直接使用。
  3. 插入/更新操作：
    • ziplist：
      1. 从 ziplist 的尾部开始，反向遍历所有 field entry（即每隔一个 entry 跳一次）。
      2. 比较当前 field 是否与要插入的 field 相等。如果找到，则说明是更新操作，需要先删除旧的 value entry，然后再在尾部插入新的 field-value entry 对。
      3. 如果没找到，则是新增操作，直接在 ziplist 尾部连续插入两个新的 entry（field 和 value）。
    • hashtable：
      1. 调用 dictFind 在字典中查找 field。
      2. 如果找到，则更新其 value (dictReplace)。
      3. 如果没找到，则新增一个 dictEntry (dictAdd)。在这个过程中，可能会触发字典的扩容和渐进式 Rehash。

HGET 命令流程：

  1. 查找键： 根据 key 找到对应的 Redis Hash 对象。
  2. 检查编码：
    • ziplist：
      1. 从 ziplist 的头部开始，顺序遍历所有 field entry。
      2. 将当前 entry 的 content（即 field 字符串）与目标 field 进行比较。
      3. 如果匹配成功，下一个 entry 就是对应的 value，将其取出并返回。
      4. 如果遍历完都没找到，返回 nil。
    • hashtable：
      1. 调用 dictFind 在字典中查找 field。
      2. 这个函数会计算 field 的哈希值，定位到具体的桶，然后遍历桶对应的链表进行比较。
      3. 如果找到，返回对应的 value；否则返回 nil。

从 HGET 的流程可以清晰地看到，在 ziplist 中查找是 O(N) 的线性操作，而在 hashtable 中几乎是 O(1) 的常数时间操作。

设计思想与总结

  1. 时空权衡 (Time-Memory Tradeoff)：
    Redis Hash 的设计是计算机科学中时空权衡原则的完美体现。为了节省空间（内存），它使用了访问效率较低的 ziplist；为了节省时间（性能），它使用了访问效率高但更耗内存的 hashtable。通过一个可配置的阈值，让用户可以根据自己的实际需求（是内存敏感还是CPU敏感）来调整这个平衡点。

  2. 平滑转换：
    编码的自动转换对用户是完全透明的。开发者无需关心底层实现，Redis 会自动选择最合适的结构。这种自优化的特性非常友好。

  3. 小数据优化：
    在互联网应用中，存在大量包含少量字段的小 Hash 对象（例如存储用户会话信息、对象属性）。ziplist 的设计使得存储这些对象时的元数据开销极低，这对于拥有大量此类键的 Redis 实例来说，内存节约效果非常显著。

  4. 渐进式 Rehash：
    hashtable 的渐进式 Rehash 机制确保了 Redis 即使在处理大型 Hash 表的扩容时，也能保持高性能，避免服务出现明显的停顿，这对于高性能数据库至关重要。

总结：
Redis 的 Hash 类型不是一个简单的黑盒，其内部是一个智能的、自适应的系统。它通过两种截然不同的底层数据结构（ziplist 和 hashtable），在不同的数据规模下自动切换，巧妙地平衡了内存和性能的矛盾。理解其内部机制，有助于我们更好地设计和优化业务数据结构，例如合理设置 hash-max-ziplist-entries 和 hash-max-ziplist-value 参数，以使其尽可能多地使用 ziplist 编码，从而达到节约内存的目的。