redis中的字典结构是怎样的？

Redis中的字典结构通过dict、dictht、dictEntry三种结构组合实现，采用哈希表存储键值对，并通过链表法解决哈希冲突，支持动态扩容和缩容。以下是详细说明：

一、字典结构的核心组成

Redis字典由以下三种结构组合实现，其关系如下：字典结构 = dict（字典整体） + dictht（哈希表） + dictEntry（哈希表节点）

dict（字典整体）
type：指向dictType结构，包含计算键哈希值的函数（如hashFunction）和比较键的函数。
privdata：私有数据，保存dictType中函数的参数（如哈希算法的种子）。
ht[2]：两张哈希表（dictht类型），ht[0]用于正常存储键值对，ht[1]在rehash时临时存储数据。
rehashidx：rehash进度标记。
-1：表示未进行rehash。
≥0：表示当前正在rehash，值为当前处理的ht[0]的数组下标。
dictht（哈希表）
table：指向dictEntry指针数组的地址，每个数组元素存储一个链表的头节点（解决哈希冲突）。
size：哈希表的数组长度（初始为4，且始终为2的幂次方）。
sizemask：掩码，值为size-1，用于计算键在数组中的下标（index = hash & sizemask）。
used：记录哈希表中已存储的节点数量（即键值对数量）。
dictEntry（哈希表节点）
key：键，类型为void*，可存储任意类型键。
v：值，通过联合体实现多种类型存储：
void* val：指针类型值。
uint64_t u64：无符号64位整数。
int64_t s64：带符号64位整数。
next：指向下一个dictEntry的指针，用于链表法解决哈希冲突（新节点采用头插法插入链表）。

二、键值对存储与哈希冲突解决

计算键在哈希表中的位置
步骤1：调用dict->type->hashFunction(key)计算键的哈希值（hash）。
步骤2：通过掩码计算下标：index = hash & dict->ht[x].sizemask（x为当前使用的哈希表索引，正常为0，rehash时可能为1）。
哈希冲突处理
当多个键的哈希值映射到同一数组下标时，采用链表法解决冲突。
新节点通过头插法插入链表，保持插入效率为O(1)。

三、负载因子与动态扩容/缩容

负载因子定义
公式：负载因子 = ht[0].used / ht[0].size（即已存储节点数 / 数组长度）。
负载因子反映哈希表的填充程度，触发rehash的阈值如下：
触发扩容的条件
无持久化操作时：负载因子 ≥ 1。
正在执行bgsave或bgrewriteaof时：负载因子 ≥ 5（避免持久化期间内存占用激增）。
原因：哈希冲突导致链表长度增加，查询效率从O(1)退化为O(n)，需通过扩容分散键值对。
触发缩容的条件
负载因子 ≤ 0.1（如数组长度为16，仅存储1个节点时触发）。
rehash过程
扩展：
分配新哈希表ht[1]，大小为第一个大于等于ht[0].used的2的幂次方（如ht[0].used=10，则ht[1].size=16）。
将ht[0]的所有键值对重新计算哈希值并插入ht[1]。
缩容：逻辑与扩展相同，仅目标大小不同。
完成标志：
ht[0]所有节点迁移完成后，释放ht[0]，将ht[1]设为ht[0]，并新建空白ht[1]。

四、渐进式rehash优化性能

分阶段迁移
避免一次性迁移所有节点导致Redis阻塞，采用渐进式rehash：
初始化时设置rehashidx=0。
每次对字典执行增、删、改、查操作时，迁移ht[0].table[rehashidx]链表的所有节点到ht[1]，并递增rehashidx。
当rehashidx超过ht[0].size-1时，完成迁移，重置rehashidx=-1。
操作兼容性
查询：先查ht[0]，未找到再查ht[1]。
插入：直接插入ht[1]（避免新数据插入旧表导致重复迁移）。
删除/更新：同时操作ht[0]和ht[1]。
内存开销
rehash期间需同时维护两张哈希表，内存占用翻倍，但通过分阶段迁移平衡了性能与资源消耗。

五、总结

Redis字典通过哈希表+链表实现高效键值对存储，动态调整数组大小以适应数据量变化，并通过渐进式rehash避免阻塞。其设计核心包括：

这一结构使得Redis的Hash类型在平均情况下能保持O(1)时间复杂度的查询效率，同时支持高并发操作。

热门标签