简策小栈

Appearance

Hash（哈希） ​

1. 概述 ​

Hash是键值对集合，特别适合存储对象。

常用命令：HSET、HGET、HGETALL、HMGET、HINCRBY、HDEL、HEXISTS

2. 底层数据结构 ​

2.1 编码类型 ​

编码说明适用场景
ziplist压缩列表字段数少且值较小
hashtable哈希表大量字段或大值

2.2 编码转换条件 ​

c
// 满足任一条件使用ziplist
hash-max-ziplist-entries 512  // 字段数超过512
hash-max-ziplist-value 64     // 任意值超过64字节

2.3 hashtable结构 ​

c
// 字典结构
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];              // 两个哈希表，渐进式rehash
    long rehashidx;            // rehash进度，-1表示未进行
    unsigned long iterators;   // 正在遍历的迭代器数量
} dict;

// 哈希表
typedef struct dictht {
    dictEntry **table;         // 哈希表数组
    unsigned long size;        // 哈希表大小
    unsigned long sizemask;    // 掩码，用于计算索引
    unsigned long used;        // 已使用节点数
} dictht;

// 哈希表节点
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;    // 链表，解决哈希冲突
} dictEntry;

3. 渐进式rehash ​

3.1 什么是rehash？ ​

当哈希表负载因子过高时，需要扩容：

c
// 负载因子 = used / size
load_factor = ht[0].used / ht[0].size

// 扩容条件
load_factor > 1 && !bgsave  // 未进行BGSAVE
load_factor > 5 && bgsave   // 正在BGSAVE，激进扩容

3.2 渐进式rehash过程 ​

c
// 步骤1：创建新哈希表 ht[1]
// 步骤2：在ht[0]上标记 rehashidx = 0
// 步骤3：每次增删改查时迁移一个桶
// 步骤4：迁移完成，ht[0] = ht[1]，重置ht[1]

特点：

  • 迁移期间两个哈希表同时工作
  • 查找时先查ht[0]，再查ht[1]
  • 写入只写入ht[1]

3.3 rehash触发条件 ​

c
// 扩容
if (load_factor > 1 && !server.bgsave_in_progress)
    dictExpand(d, d->ht[0].used * 2);

// 缩容（used/size < 0.1）
if (load_factor < 0.1 && !(server.bgsave_in_progress))
    dictShrink(d, d->ht[0].used);

4. 面试考点 ​

Q1: Hash的底层实现？ ​

答案： Hash底层使用ziplist（压缩列表）或hashtable（哈希表）。当字段数较少（≤512）且值都不超过64字节时使用ziplist，否则使用hashtable。ziplist内存紧凑，hashtable支持O(1)查找。

Q2: 渐进式rehash是什么？ ​

答案： Redis的hashtable采用渐进式rehash避免阻塞。当需要扩容时，创建新哈希表ht[1]，将ht[0]的数据分多次迁移到ht[1]。期间增删改查操作会同时访问两个表，写操作只写入ht[1]。迁移完成后ht[0]释放。

Q3: rehash为什么需要两个哈希表？ ​

答案： 一次性迁移大量数据会导致Redis阻塞。渐进式rehash将迁移分散到每次操作中，每次访问时迁移一个桶（bucket），保证服务持续可用。

5. 应用场景 ​

5.1 对象存储 ​

bash
HSET user:1001 name "张三"
HSET user:1001 age "25"
HSET user:1001 city "北京"
HGETALL user:1001

5.2 购物车 ​

bash
HSET cart:1001 item:1001 1    # 用户1001添加商品1001，数量1
HINCRBY cart:1001 item:1001 1 # 增加数量
HLEN cart:1001                # 购物车商品数
HDEL cart:1001 item:1001      # 删除商品

5.3 计数器 ​

bash
HSET stats:2026-04-05 pv:home 0
HINCRBY stats:2026-04-05 pv:home 1
HGETALL stats:2026-04-05

6. 实践问题 ​

Q: Hash如何遍历？ ​

答案： 使用HSCAN命令：

bash
HSCAN cursor MATCH pattern COUNT count
# cursor: 游标，第一次为0
# MATCH: 匹配模式
# COUNT: 每次返回数量

# 示例
HSCAN 0 MATCH user:* COUNT 100

Q: 大Key问题如何解决？ ​

答案：

  • 拆分Hash：将大Hash拆分为多个小Hash
  • 避免存储过大的值
  • 定期清理过期数据

Q: Hash的内存占用？ ​

答案： Hash在ziplist模式下内存紧凑，但查找复杂度O(n)。hashtable模式下查找O(1)，但有额外内存开销（每Entry约40字节）。

最后更新: