Redis哈希表(Hash Table)实现原理

▶Redis核心
- ▶数据结构
- ▶内存管理
  - 内存分配策略
  - 淘汰算法
▶持久化
- ▶RDB机制
  - 快照生成原理
  - 文件格式解析
- ▶AOF机制
  - 命令追加策略
  - 重写过程分析
▶高可用
- ▶主从复制
  - SYNC原理
  - 增量复制
- ▶哨兵机制
  - 故障检测
  - 领导选举
▶高级特性
- ▶事务系统
  - ACID实现
  - WATCH原理
- ▶Lua脚本
  - 沙盒环境
  - 执行管道
▶实战问题
- ▶缓存问题
- ▶数据一致性
  - 读写一致性
  - 双写一致性
- ▶性能优化
  - 大key处理
  - 热点key优化

发布时间: 2025-03-22 10:35

↑

# Redis哈希表(Hash Table)实现原理

## 引言

Redis哈希表是一种键值对的数据结构，它不仅是Redis键值对存储的底层实现，也是Redis提供给用户使用的数据类型之一。本文将深入探讨Redis哈希表的实现原理、内部编码方式以及实际应用场景。

## 底层实现

### 哈希表结构

Redis的哈希表使用链地址法解决冲突，其主要结构包含：

```c
// 哈希表节点
typedef struct dictEntry {
    void *key;            // 键
    union {
        void *val;       // 值
        uint64_t u64;    // 整数值
        int64_t s64;     // 有符号整数值
        double d;        // 双精度浮点值
    } v;                 // 值联合体
    struct dictEntry *next;  // 指向下一个节点
} dictEntry;

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

// 字典
typedef struct dict {
    dictType *type;  // 类型特定函数
    void *privdata;  // 私有数据
    dictht ht[2];    // 哈希表[2]用于rehash
    long rehashidx;  // rehash索引
    int iterators;   // 当前正在使用的迭代器数量
} dict;
```

### 哈希算法

Redis使用MurmurHash2算法计算键的哈希值：

```c
uint32_t dictGenHashFunction(const void *key, int len) {
    uint32_t seed = dict_hash_function_seed;
    return MurmurHash2(key, len, seed);
}
```

### 渐进式Rehash

Redis采用渐进式rehash策略，避免一次性rehash带来的性能问题：

1. **触发条件**
   - 负载因子 > 1，且服务器没有执行BGSAVE或BGREWRITEAOF
   - 负载因子 > 5

2. **rehash过程**
   ```c
   // 执行N步渐进式rehash
   int dictRehash(dict *d, int n) {
       int empty_visits = n * 10;
       if (!dictIsRehashing(d)) return 0;
       
       while (n-- && d->ht[0].used != 0) {
           dictEntry *de, *nextde;
           
           while (d->ht[0].table[d->rehashidx] == NULL) {
               d->rehashidx++;
               if (--empty_visits == 0) return 1;
           }
           
           de = d->ht[0].table[d->rehashidx];
           while (de) {
               uint64_t h;
               nextde = de->next;
               
               h = dictHashKey(d, de->key) & d->ht[1].sizemask;
               de->next = d->ht[1].table[h];
               d->ht[1].table[h] = de;
               d->ht[0].used--;
               d->ht[1].used++;
               de = nextde;
           }
           d->ht[0].table[d->rehashidx] = NULL;
           d->rehashidx++;
       }
       
       if (d->ht[0].used == 0) {
           zfree(d->ht[0].table);
           d->ht[0] = d->ht[1];
           _dictReset(&d->ht[1]);
           d->rehashidx = -1;
           return 0;
       }
       
       return 1;
   }
   ```

## 内部编码

Redis的哈希对象有两种内部编码方式：

### 1. ziplist（压缩列表）

当哈希对象同时满足以下条件时，使用ziplist编码：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个

```redis
HSET user:1 name "John" age "25"
```

### 2. hashtable（哈希表）

当不满足ziplist的条件时，使用hashtable编码：

```redis
HSET user:1 description "这是一个很长的描述..."
```

## 常用命令

### 基本操作

```redis
# 设置字段值
HSET key field value

# 获取字段值
HGET key field

# 删除字段
HDEL key field [field ...]

# 获取所有字段和值
HGETALL key
```

### 批量操作

```redis
# 批量设置字段值
HMSET key field value [field value ...]

# 批量获取字段值
HMGET key field [field ...]
```

### 字段操作

```redis
# 判断字段是否存在
HEXISTS key field

# 获取字段数量
HLEN key

# 获取所有字段名
HKEYS key

# 获取所有字段值
HVALS key
```

## 应用场景

### 1. 用户信息缓存

```redis
# 存储用户信息
HMSET user:1001 name "张三" age "25" email "zhangsan@example.com"

# 更新某个字段
HSET user:1001 age "26"

# 获取用户信息
HGETALL user:1001
```

### 2. 商品库存

```redis
# 设置商品库存
HMSET product:stock p1001 100 p1002 200 p1003 300

# 减少库存（使用Lua脚本保证原子性）
eval "
    local stock = redis.call('HGET', KEYS[1], ARGV[1])
    if not stock or tonumber(stock) < tonumber(ARGV[2]) then
        return 0
    end
    return redis.call('HINCRBY', KEYS[1], ARGV[1], -ARGV[2])
" 1 product:stock p1001 1
```

### 3. 购物车

```redis
# 添加商品到购物车
HSET cart:user:1001 product:1 2 product:2 1

# 更新商品数量
HINCRBY cart:user:1001 product:1 1

# 获取购物车信息
HGETALL cart:user:1001
```

### 4. 配置信息管理

```redis
# 存储配置信息
HMSET config:app:1 port "8080" max_conn "1000" timeout "30"

# 动态更新配置
HSET config:app:1 max_conn "2000"
```

## 性能优化

### 1. 键设计

- 使用合适的键名前缀
- 避免过长的字段名
- 控制字段数量在512以内（利用ziplist编码）

### 2. 内存优化

```redis
# 使用HSCAN代替HGETALL（大hash）
HSCAN key 0 COUNT 100

# 合理设置hash-max-ziplist-entries和hash-max-ziplist-value
CONFIG SET hash-max-ziplist-entries 512
CONFIG SET hash-max-ziplist-value 64
```

### 3. 批量操作

```redis
# 使用HMSET代替多次HSET
HMSET user:1001 name "张三" age "25" email "zhangsan@example.com"

# 使用HMGET代替多次HGET
HMGET user:1001 name age email
```

## 注意事项

1. **大Key问题**
   - 避免单个hash存储过多字段
   - 考虑拆分大hash为多个小hash

2. **内存管理**
   - 合理设置ziplist阈值
   - 注意字段值大小对内存的影响

3. **原子性**
   - 多个操作需要原子性时使用Lua脚本
   - 注意并发访问的数据一致性

4. **过期策略**
   - hash结构本身不支持过期
   - 可以通过key过期实现整个hash过期

## 总结

Redis哈希表通过巧妙的数据结构设计和渐进式rehash机制，在保证性能的同时提供了灵活的键值对存储能力。通过合理使用ziplist和hashtable两种编码方式，可以在不同场景下实现最优的空间效率。在实际应用中，需要注意键的设计、内存优化和并发访问等问题，以充分发挥Redis哈希表的优势。

元素码农