Knowledge4J

切换主题

02.3 - Hash 底层实现 ​

定位: Redis 的哈希类型适用于对象存储（如用户信息、商品详情）和计数器场景

面试高频度: ⭐⭐⭐⭐⭐

考查方式: 编码转换（ziplist→hashtable）、渐进式 rehash 原理、rehash 过程

一、这是什么？为什么需要它？ ​

是什么 ​

Redis Hash 是一个键值对集合（field-value pairs），底层在小数量时用 ziplist 紧凑存储，大数量时自动切换到 dict（哈希表）。

为什么需要 Hash？ ​

存储模型 ​

二、原理拆解 ​

2.1 编码切换策略 ​

2.2 Dict（哈希表）结构 ​

c





// Redis 哈希表结构（简化）





struct dictht {





    dictEntry **table;      // 哈希表数组





    unsigned long size;     // 表大小





    unsigned long sizemask; // size - 1（用于索引计算）





    unsigned long used;     // 已用节点数





};











struct dict {





    dictht ht[2];          // 两个哈希表（用于渐进式 rehash）





    long rehashidx;         // rehash 进度，-1 表示未进行





    // ...





};











struct dictEntry {





    void *key;





    union {





        void *val;





        uint64_t u64;





        int64_t s64;





        double d;





    } v;





    dictEntry *next;        // 链表解决冲突





};

哈希表关键设计：






1. 链表法解决哈希冲突





   table[idx] → entry1 → entry2 → entry3（同 hash 的 key）











2. 负载因子触发 rehash





   负载因子 = used / size





   扩容：负载因子 > 1（有 BGSAVE）或 > 5（无 BGSAVE）





   缩容：负载因子 < 0.1











3. MurmurHash2 哈希算法





   高效、分布均匀

2.3 渐进式 Rehash 详解 ​

rehash 期间的访问策略：






增：只在 ht[1] 新增（保证 ht[0] 只减不增，最终变空）





删：先在 ht[0] 删，不存在则在 ht[1] 删





改：先找 ht[0]，再找 ht[1]





查：先找 ht[0]，再找 ht[1]

三、图解全景 ​

四、实战验证 ​

4.1 验证编码转换 ​

bash





redis-cli











# 1. 小 Hash → ziplist 编码





127.0.0.1:6379> HSET user:42 name "Alice" age 30 city "Beijing"





(integer) 3





127.0.0.1:6379> OBJECT ENCODING user:42





"listpack"          # Redis 7.x 用 listpack 替代 ziplist





# 或 "ziplist"（Redis 6.x）











# 2. 插入大量 field → 触发编码转换





127.0.0.1:6379> EVAL "for i=1,600 do redis.call('HSET',KEYS[1],i,i) end" 1 bighash





(nil)





127.0.0.1:6379> HLEN bighash





(integer) 600





127.0.0.1:6379> OBJECT ENCODING bighash





"hashtable"











# 3. 混合条件：某个 value 超过 64 字节也会触发转换





127.0.0.1:6379> HSET smallhash longfield "$(printf 'A%.0s' {1..100})"





(integer) 1





127.0.0.1:6379> OBJECT ENCODING smallhash





"hashtable"

4.2 渐进式 rehash 观察 ​

bash





# 渐进式 rehash 是渐进式的，在大量 key 时可以通过





# 多次访问观察内存变化来间接验证











# 创建一个较大 Hash





for i in $(seq 1 10000); do





  redis-cli HSET largehash "field:$i" "value:$i" > /dev/null 2>&1





done











# 查看编码





redis-cli OBJECT ENCODING largehash





# hashtable











# 删除大量 key（触发缩容 rehash）





for i in $(seq 1 9500); do





  redis-cli HDEL largehash "field:$i" > /dev/null 2>&1





done











# 查看 Hash 信息





redis-cli HLEN largehash





# (integer) 500











# 注意：rehash 过程对调用者透明，INFO 没有直接暴露 rehash 状态





# 可以通过 redis-rdb-tools 分析 RDB 重建哈希表看到分桶情况

4.3 Hash 的性能基准测试 ​

bash





# 对比 Hash 存取 vs String 存取











# Hash 方式：存入 1000 个用户（每个用户 5 个字段）





time for i in $(seq 1 1000); do





  redis-cli HSET "user:$i" name "user$i" age "$i" city "Beijing" > /dev/null





done  # ~2 秒











# String 方式：存入 1000 个用户（每个用户 5 个单独的 key）





time for i in $(seq 1 1000); do





  redis-cli MSET "user:$i:name" "user$i" "user:$i:age" "$i" > /dev/null





done  # ~3-4 秒（更多的 key 管理开销）











# 结论：对象场景 Hash 比 String 更省内存、更快

五、面试视角 ​

| 追问 | 答案要点 |

|------|---------|

| Hash 什么时候用 ziplist，什么时候用 hashtable？ | 小数据时（默认 entry≤512 且 value≤64B）用 ziplist，超阈值转 hashtable（不可逆）|

| 渐进式 rehash 怎么保证不阻塞？ | 每次操作搬一个 bucket，分摊成本；同时操作两个表（ht[0]查/ht[1]增）|

| rehash 期间怎么保证数据不错？ | 读查两个表；写只写新表（ht[1]）而旧表只减不增；最终 ht[0] 变空后释放 |

| rehash 的触发条件？ | 扩容：负载因子>1（有子进程）或 >5（无子进程）；缩容：负载因子<0.1 |

| 为什么 rehash 是不可逆的？ | ziplist→hashtable 后不会转为 ziplist，因为假设业务增长后不会再缩回小数据量。可用 OBJECT ENCODING 验证 |

| 相同的 field 多次 HSET 会怎样？ | 覆盖旧值，ziplist 中可能需要重新分配内存（连锁更新风险）|

📚 相关链接 ​

  • **Set 底层** — 也使用 dict 但有差异

  • **数据结构概览** — Hash 在整体中的位置

  • **内存优化** — ziplist/listpack 参数调优

  • ← 返回 **核心数据结构索引**

Knowledge4J — Java 知识库

MIT License