hash实现

Redis Hash 数据结构实现详解（基于 6.0.10 版本）

Redis 中的 Hash 类型（哈希表）是一种键值对集合，底层采用混合编码策略（ziplist 或 hash table），兼顾内存效率和操作性能。本文结合源码结构，详解其实现机制、编码转换、哈希冲突处理及扩容策略。

Hash 类型的编码策略

Redis 的 Hash 类型根据数据规模自动选择两种编码方式，通过配置参数控制转换阈值：

编码方式	适用场景	转换条件（满足任一即触发）
`OBJ_ENCODING_ZIPLIST`（压缩列表）	元素少且小（键值均为短字符串）	1. 元素数量 > `hash-max-ziplist-entries`（默认 512） 2. 任一键 / 值长度 > `hash-max-ziplist-value`（默认 64 字节）
`OBJ_ENCODING_HT`（哈希表）	元素多或大（键值为长字符串 / 整数）	上述条件触发后，自动转为哈希表编码

两种编码的权衡：

ziplist：连续内存存储，无哈希表元数据开销，内存紧凑（适合小数据），但插入 / 删除需移动元素（O (N) 时间复杂度）。
hash table：哈希表结构，插入 / 删除 / 查询平均 O (1) 时间复杂度（适合大数据），但内存开销较高（需存储指针和哈希表结构）。

哈希表核心源码结构

当 Hash 类型采用 OBJ_ENCODING_HT 编码时，底层依赖 dict（字典）结构体实现，源码如下：

1. `dict`（字典）

typedef struct dict {
    dictType *type;         // 字典类型（包含哈希函数、键值复制/释放函数等）
    void *privdata;         // 私有数据（传给 type 中函数的参数）
    dictht ht[2];           // 两个哈希表（ht[0] 存实际数据，ht[1] 用于扩容/缩容）
    long rehashidx;         // rehash 索引（-1 表示未进行 rehash，否则为当前迁移的数组下标）
    int16_t pauserehash;    // 暂停 rehash 标志（>0 表示暂停）
} dict;

核心作用：管理哈希表的生命周期（创建、插入、查询、扩容等），通过 ht[0] 和 ht[1] 实现动态扩容。

2. `dictht`（哈希表）

typedef struct dictht {
    dictEntry **table;      // 哈希表数组（元素为 dictEntry*，即键值对节点）
    unsigned long size;     // 哈希表容量（数组长度，必须为 2^n）
    unsigned long sizemask; // 容量掩码（size-1，用于计算哈希索引：hash & sizemask）
    unsigned long used;     // 已存储的节点数量
} dictht;

table：核心数组，每个元素是指向 dictEntry 的指针（链表头节点），解决哈希冲突。
sizemask：优化哈希索引计算（替代取模运算），例如 size=4 时 sizemask=3，hash & 3 等价于 hash % 4。

3. `dictEntry`（哈希表节点）

typedef struct dictEntry {
    void *key;              // 键（Redis 中为 sds 类型字符串）
    union {                 // 值（支持多种类型）
        void *val;          // 指针类型（如字符串对象）
        uint64_t u64;       // 无符号整数
        int64_t s64;        // 有符号整数
        double d;           // 浮点数
    } v;
    struct dictEntry *next; // 下一个节点（链表结构，解决哈希冲突）
} dictEntry;

哈希冲突处理：当两个键的哈希值通过 sizemask 计算后得到相同索引时，通过 next 指针形成链表（头插法，新节点插入链表头部）。

Hash 操作的核心流程

1. 添加元素（`HSET` 命令）

以 HSET hashkey field value 为例，底层流程如下：

编码检查：若当前为 ziplist 编码，检查是否需转为哈希表（如元素数超过 512）。
哈希计算：
- 对 field（键）调用哈希函数（dictType->hashFunction）生成哈希值。
- 通过 哈希值 & sizemask 计算索引，定位到 ht[0].table 中的数组位置。
冲突处理：
- 若索引位置为空，直接创建 dictEntry 节点插入。
- 若存在节点（哈希冲突），遍历链表检查是否有相同field：
  - 有则更新值（v.val）。
  - 无则创建新节点，通过头插法插入链表头部（new_entry->next = table[index]; table[index] = new_entry）。
扩容检查：若 used / size > 1（负载因子 > 1），触发扩容（dictExpand）。

2. 扩容与渐进式 Rehash

当哈希表负载因子（used / size）超过 1 时，Redis 会触发扩容（容量翻倍，且保持为 2^n），但为避免阻塞主线程，采用渐进式 Rehash：

步骤 1：初始化扩容

为 ht[1] 分配新容量（ht[0].size * 2），初始化 ht[1].table 数组。
设置 rehashidx = 0（标记开始 rehash，当前迁移索引为 0）。

步骤 2：渐进式迁移

触发时机：每次执行 HSET、HGET、HDEL 等命令时，除执行命令本身外，额外迁移 ht[0].table[rehashidx] 对应的链表节点到 ht[1]。
迁移逻辑：
1. 遍历 ht[0].table[rehashidx] 链表，将所有节点重新计算哈希索引并插入 ht[1]。
2. 迁移完成后，rehashidx += 1，继续处理下一个索引。
命令兼容：rehash 期间，查询 / 删除操作需同时检查 ht[0] 和 ht[1]；插入操作仅写入 ht[1]，保证数据一致性。

步骤 3：完成扩容

当rehashidx达到ht[0].size时，所有节点迁移完毕：
1. 释放 ht[0].table 内存。
2. 交换 ht[0] 和 ht[1]（ht[0] = ht[1]，ht[1] 清空）。
3. 重置 rehashidx = -1（标记 rehash 结束）。

3. 缩容机制

当哈希表负载因子过低（used / size < 0.1），Redis 会触发缩容（容量减半，保持 2^n），流程与扩容类似，同样采用渐进式 Rehash。

与 Java HashMap 的对比

特性	Redis Hash（dict）	Java HashMap
哈希冲突处理	头插法（新节点插入链表头部）	JDK 7 头插法，JDK 8 尾插法（避免循环链表）
扩容策略	渐进式 Rehash（分多次迁移，不阻塞）	一次性迁移（大数据量时可能阻塞）
负载因子阈值	扩容阈值 1，缩容阈值 0.1	扩容阈值 0.75（无自动缩容）
编码自适应	小数据用 ziplist，大数据自动转哈希表	固定哈希表结构
线程安全	单线程操作，无需同步	非线程安全（需 Collections.synchronizedMap）