Redis字典是Redis中非常重要的底层数据结构，除了用来实现数据库本身的键值存储外，还支撑了哈希类型、集合类型等多种数据结构的实现，理解字典的实现原理对深入掌握Redis底层逻辑有很大帮助。
Redis字典的基础结构
Redis的字典底层由哈希表实现，整体结构分为字典结构、哈希表结构、哈希表节点三个层级，我们可以通过源码中的结构定义来理解各部分的作用。
核心结构定义
以下是Redis源码中字典相关结构的核心定义（简化后）：
// 哈希表节点结构，存储单个键值对
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; // 哈希表数组，每个元素是dictEntry链表头指针
unsigned long size; // 哈希表数组大小，即桶的数量
unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，等于size-1
unsigned long used; // 哈希表已有节点数量
} dictht;
// 字典结构
typedef struct dict {
dictType *type; // 类型特定函数，包含键哈希、比较、销毁等函数
void *privdata; // 类型特定函数的私有数据
dictht ht[2]; // 两个哈希表，ht[0]是日常使用，ht[1]用于rehash
long rehashidx; // rehash索引，当不在rehash时为-1
unsigned long iterators; // 正在运行的迭代器数量
} dict;字典的核心特性
哈希算法与冲突解决
字典在对键进行操作时，首先需要通过哈希算法计算键的哈希值，再通过sizemask计算对应的索引值，确定键值对要存放的哈希表桶位置。Redis默认使用MurmurHash2算法计算哈希值，该算法具有更好的随机性和性能，能减少哈希冲突的发生。
当两个不同的键计算出相同的索引值时，就会产生哈希冲突，Redis采用链地址法解决冲突，也就是把相同索引位置的节点通过next指针连成链表，放在对应的table数组位置上。
负载因子与扩容缩容
字典的负载因子决定了哈希表是否需要扩容或缩容，负载因子的计算公式为：负载因子 = ht[0].used / ht[0].size。
扩容的触发条件有两种：一是服务器没有执行BGSAVE或BGREWRITEAOF命令，且负载因子大于等于1；二是服务器正在执行上述命令，且负载因子大于等于5。缩容的触发条件是负载因子小于0.1。
以下是负载因子相关逻辑的伪代码示例：
def calc_load_factor(dict):
# 计算当前字典的负载因子
return dict.ht[0].used / dict.ht[0].size
def need_expand(dict):
# 判断是否需要扩容
load_factor = calc_load_factor(dict)
if not is_running_save_command():
return load_factor >= 1
else:
return load_factor >= 5
def need_shrink(dict):
# 判断是否需要缩容
load_factor = calc_load_factor(dict)
return load_factor < 0.1渐进式rehash机制
当哈希表需要扩容或缩容时，如果一次性把所有ht[0]的节点迁移到ht[1]，会造成服务停顿，因此Redis采用渐进式rehash的方式，分多次、渐进式地完成迁移。
渐进式rehash的流程如下：
- 为ht[1]分配空间，大小要么是第一个大于等于ht[0].used*2的2的幂，要么是第一个大于等于ht[0].used的2的幂（缩容场景）
- 将字典的rehashidx设置为0，表示开始rehash
- 在每次对字典执行增删改查操作时，除了执行指定操作外，还会顺带将ht[0]在rehashidx索引上的所有节点迁移到ht[1]，迁移完成后rehashidx加1
- 当ht[0]的所有节点都迁移完成后，释放ht[0]的空间，将ht[1]设置为ht[0]，重置ht[1]，将rehashidx设置为-1，结束rehash
在rehash过程中，字典的删除、查找、更新操作会同时在ht[0]和ht[1]两个哈希表执行，而新增操作只会在ht[1]执行，保证ht[0]的节点只减不增。
字典的基本操作示例
以下是用Python模拟Redis字典添加键值对的核心逻辑代码：
class DictEntry:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class Dict:
def __init__(self):
self.ht = [{"table": [None]*4, "size":4, "sizemask":3, "used":0},
{"table": None, "size":0, "sizemask":0, "used":0}]
self.rehashidx = -1
def _hash(self, key):
# 简化的哈希计算，实际Redis用MurmurHash2
return hash(key)
def _get_index(self, key, ht):
hash_val = self._hash(key)
return hash_val & ht["sizemask"]
def add(self, key, value):
# 简化的添加逻辑，省略rehash和扩容判断
idx = self._get_index(key, self.ht[0])
entry = DictEntry(key, value)
# 头插法解决冲突
entry.next = self.ht[0]["table"][idx]
self.ht[0]["table"][idx] = entry
self.ht[0]["used"] += 1
def find(self, key):
# 简化的查找逻辑
idx = self._get_index(key, self.ht[0])
cur = self.ht[0]["table"][idx]
while cur:
if cur.key == key:
return cur.value
cur = cur.next
return None通过以上内容可以看出，Redis字典的设计充分考虑了性能和场景适配，无论是哈希算法的选择还是渐进式rehash的机制，都保障了字典在高并发场景下的稳定表现。
Redis字典哈希表渐进式_rehash负载因子哈希算法修改时间：2026-05-24 23:23:10