品牌网站首页怎么设计,wordpress手机仪表盘,综合门户网站建设方案,seo成创目录
一、从传统查找的痛点到哈希表的优势
二、哈希表的核心结构#xff1a;文件柜的构成
2.1、 dictht 结构体#xff1a;文件柜本体
2.2、dictEntry 结构体#xff1a;带链条的文件夹
2.2.1、 哈希冲突的解决#xff1a;抽屉里的链条
2.3、字典的高层封装…目录
一、从传统查找的痛点到哈希表的优势
二、哈希表的核心结构文件柜的构成
2.1、 dictht 结构体文件柜本体
2.2、dictEntry 结构体带链条的文件夹
2.2.1、 哈希冲突的解决抽屉里的链条
2.3、字典的高层封装文件柜管理系统
2.4、dictType文件处理工具包
三、哈希计算如何确定文件位置
四、动态扩容与收缩文件柜的大小调整
4.1、何时需要调整大小
4.2、调整大小的规则
4.3、渐进式 rehash边营业边搬家
4.4、写时复制优化拍照时不整理房间
五、字典与 SDS 的完美配合
六、字典设计的核心智慧 如果说 SDS 是 Redis 的 智能笔记本链表是 活页文件夹那么字典就是把这些笔记和文件夹有序管理起来的 智能文件柜系统。当你在 Redis 中使用哈希类型存储用户信息如HSET user:1 name 张三 age 30时背后正是字典结构在高效运作。
一、从传统查找的痛点到哈希表的优势
想象你在图书馆找书的三种方式
按书架顺序查找像数组遍历一样逐个查看每个书架效率极低
按分类目录查找像链表遍历一样虽然有分类但仍需逐个翻阅
按编号定位查找像哈希表一样通过书号直接计算出所在书架和位置一步到位
Redis 的字典采用哈希表作为底层实现正是为了实现这种 一步到位 的高效查找能力。哈希表就像配备了智能索引系统的文件柜能在 O (1) 时间复杂度内完成数据的查找、添加和删除操作。 二、哈希表的核心结构文件柜的构成
Redis 的哈希表结构由三个关键部分组成就像文件柜的不同组件
2.1、 dictht 结构体文件柜本体
struct dictht {dictEntry **table; // 抽屉数组哈希表节点数组unsigned long size; // 抽屉总数哈希表大小unsigned long sizemask; // 定位掩码总是等于size-1unsigned long used; // 已使用抽屉数节点数量};
这个结构体就像一个文件柜
table是一排抽屉每个抽屉可以放多个文件夹通过链表连接
size记录总共有多少个抽屉
sizemask是定位工具用来计算文件应该放入哪个抽屉
used记录已经放了多少文件
2.2、dictEntry 结构体带链条的文件夹
struct dictEntry {void *key; // 文件标签键union { // 文件内容值void *val;uint64_t u64;int64_t s64;} v;struct dictEntry *next; // 下一个文件夹解决冲突的链表};
每个节点就像一个带链条的文件夹
key是文件的标签在 Redis 中通常用 SDS 存储比如 name、age
v是文件内容可以是字符串指针void *val、无符号整数u64或有符号整数s64
next是连接链条当多个文件需要放入同一个抽屉时用链条将它们串起来哈希冲突解决
2.2.1、 哈希冲突的解决抽屉里的链条
当两个不同的键计算出相同的抽屉编号时哈希冲突就像两个文件要放进同一个抽屉这时next指针就发挥作用了 —— 它把这些文件串成一个链表这种方法称为 链地址法。
比如 张三 和 张三丰 计算出相同的抽屉编号它们会通过next指针连接在一起查找时只需遍历这个小链表即可。
2.3、字典的高层封装文件柜管理系统
Redis 的字典结构在哈希表之上增加了管理层就像文件柜的智能管理系统
struct dict {dictType *type; // 操作工具集void *privdata; // 工具参数dictht ht[2]; // 两个哈希表主表和备用表int rehashidx; // 搬家进度-1表示未进行};
这个管理系统的核心功能
维护两个哈希表ht[0]日常使用和ht[1]搬家时使用
通过rehashidx记录数据迁移进度
提供type中定义的工具函数处理不同类型的数据
2.4、dictType文件处理工具包
struct dictType {unsigned int (*hashFunction)(const void *key); // 计算抽屉编号的工具void *(*keyDup)(void *privdata, const void *key); // 复制标签的工具void *(*valDup)(void *privdata, const void *obj); // 复制内容的工具int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 比较标签的工具void (*keyDestructor)(void *privdata, void *key); // 销毁标签的工具};
这些函数就像文件柜的配套工具
hashFunction根据文件名计算抽屉编号哈希函数
keyDup复制文件标签比如复制 SDS 字符串
keyCompare比较两个文件标签是否相同
其他工具负责数据的复制和销毁
三、哈希计算如何确定文件位置
把文件放入文件柜需要两步计算哈希值文件名编码和计算索引抽屉编号
计算哈希值用hashFunction对键key进行计算比如对 SDS 字符串 name 计算得到一个大整数
计算索引用哈希值与sizemasksize-1做与运算得到抽屉编号 索引 哈希值 sizemask 例如当size8sizemask7哈希值 10二进制 1010时 1010 0111 0010二进制→ 索引2 这种计算方式要求size必须是 2 的幂次方这样sizemask的二进制表示全是 1能保证索引均匀分布在0到size-1之间。
四、动态扩容与收缩文件柜的大小调整
随着文件增减文件柜需要动态调整大小以保持效率这个过程称为 rehash重新散列
4.1、何时需要调整大小
扩展条件当文件太多导致拥挤时
无备份任务时负载因子≥1used/size ≥1
有备份任务时负载因子≥5避免频繁复制内存
收缩条件当文件太少导致空间浪费时
负载因子≤0.1used/size ≤0.1
负载因子就像 拥挤度比如 8 个抽屉放了 10 个文件拥挤度 10/81.25。
4.2、调整大小的规则
扩展ht[1]的大小是第一个大于等于ht[0].used*2的 2 的幂次方 例used10 → 10*220 → 下一个 2 的幂次方是 32 收缩ht[1]的大小是第一个大于等于ht[0].used的 2 的幂次方 例used10 → 下一个 2 的幂次方是 16
4.3、渐进式 rehash边营业边搬家
如果文件柜需要从 8 个抽屉扩到 32 个抽屉不可能一次性搬完所有文件 —— 这会导致图书馆暂时停业。Redis 采用 渐进式 rehash 策略就像边营业边搬家
准备阶段为ht[1]分配新空间rehashidx0开始搬家
渐进迁移每次有读写操作时顺带迁移ht[0]中rehashidx索引处的所有文件到ht[1]然后rehashidx加 1
双表并行迁移期间查找操作会同时检查ht[0]和ht[1]新增操作直接放入ht[1]保证ht[0]只减不增
完成迁移当ht[0]所有文件都迁移到ht[1]后ht[1]成为新的ht[0]rehashidx-1搬家完成
这种策略把巨大的迁移工作分散到每次操作中避免了服务中断。
4.4、写时复制优化拍照时不整理房间
当 Redis 执行 BGSAVE备份或 BGREWRITEAOF日志重写时会创建子进程。为了减少内存复制开销Redis 采用 写时复制 技术
子进程创建时共享父进程内存只有当数据修改时才复制相关内存页
因此在备份期间Redis 提高扩展阈值负载因子≥5 才扩展减少内存写入操作
这就像拍照时不整理房间等照片拍完再整理避免重复劳动
五、字典与 SDS 的完美配合
SDS 在字典中扮演重要角色
键key的存储字典的键几乎都是用 SDS 存储的比如HSET user:1 name 张三中的 name key → SDS结构len4, free4, buf[n,a,m,e,\0] 字符串值的存储当值是字符串时也用 SDS 存储比如 张三 v.val → SDS结构len6, free6, buf[张,三,\0] 数值的优化存储当值是整数时直接用u64或s64存储避免 SDS 的内存开销
这种组合让字典既能高效存储字符串又能优化数值类型的存储。
六、字典设计的核心智慧 特性 生活比喻 技术价值 哈希表结构 智能文件柜 O (1) 时间复杂度的基本操作 链地址法 抽屉里的链条 优雅解决哈希冲突 双哈希表 新旧文件柜 支持动态扩容 / 收缩 渐进式 rehash 边营业边搬家 避免操作阻塞 类型特定函数 专用工具包 支持多类型数据处理 写时复制适配 拍照时不整理 优化备份时的性能
Redis 字典通过这些设计完美平衡了性能、灵活性和内存效率。它不仅是哈希类型的底层实现还被用于 Redis 数据库的核心键空间、集群节点通信等关键场景是 Redis 高效运作的基石之一。
理解了字典结构你就掌握了 Redis 数据管理的核心机制 —— 从简单的键值对到复杂的哈希对象都依赖这个精妙的 智能文件柜系统 来实现高效管理。
