Redis数据结构之——hash

article/2025/9/13 22:58:19

写在前面

以下内容是基于Redis 6.2.6 版本整理总结

一、Redis 数据结构hash的编码格式

Redis中hash数据类型使用了两种编码格式:ziplist(压缩列表)、hashtable(哈希表)

在redis.conf配置文件中，有以下两个参数，意思为：当节点数量小于512并且字符串的长度小于等于64时，会使用ziplist编码。

hash-max-ziplist-entries 512    
hash-max-ziplist-value 64

二、压缩链表（ziplist）

ziplist 我们整理在下一篇文章。

三、哈希表（hashtable）

Redis中的字典（dict）使用哈希表作为的底层实现，一个哈希表里可以有多个哈希表的节点，每个节点保存字典中的一个键值对。

哈希表结构定义如下：

typedef struct dictht {dictEntry **table;  // 哈希表数组 每个元素都是 dictEntry 的指针，指向 dictEntry;unsigned long size; // 哈希表大小unsigned long sizemask; // 用来计算索引值 always： sizemask = size - 1unsigned long used; // 哈希表已有节点的数量
} dictht;

哈希表节点定义如下：
哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对和冲突后的链表的下一个节点。

typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next; // 保存下一个 dictEntry 的地址，形成链表
} dictEntry;

其中，value 是一个联合体，可以保存多种数据类型。当value类型为 uint64_t 、int64_t 或 double时可以直接存储。其他类型需要在其他位置申请一段空间来存放，并用val指向这段空间来使用。

字典结构定义如下：

// location： dict.h
typedef struct dict {dictType *type;  // 指向 dictType 结构的指针void *privdata;  // 存储私有数据的指针，在 dictType 里面的函数会用到dictht ht[2];    // 两个哈希表，扩容时使用，后面会结合源码详细说明long rehashidx;  // 值为-1时，表示没有进行rehash，否则保存rehash执行到那个元素的数组下标 int16_t pauserehash; // >0 表示rehash暂停，<0 表示编码错误 
} dict;

dictType 结构定义如下

dictType 结构体定义了一系列操作key-value键值对的方法的函数指针，在实际运行时传入指定函数，就能实现预期的功能，有点运行时多态绑定的味道。

// 操作特性键值对的函数簇
typedef struct dictType {uint64_t (*hashFunction)(const void *key); // 计算哈希值的函数void *(*keyDup)(void *privdata, const void *key);  // 复制key的函数void *(*valDup)(void *privdata, const void *obj);  // 复制value的函数int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比key的函数void (*keyDestructor)(void *privdata, void *key);  // 销毁key的函数void (*valDestructor)(void *privdata, void *obj);  // 销毁value的函数int (*expandAllowed)(size_t moreMem, double usedRatio); // 扩容
} dictType;

字典整体结构可以用下图来描述：
在这里插入图片描述

3.1 hash冲突

当两个或两个以上的键被分配到哈希数组的同一个索引上面时，我们称这些键发生了冲突。Redis的哈希表使用拉链法解决hash冲突。

3.2 负载因子

负载因子 = used / size ; used 是哈希数组存储的元素个数，size 是哈希数组的长度。
负载因子越小，冲突越小；负载因子越大，冲突越大。

3.3 rehash

随着命令的不断执行，哈希表保存的减值对会逐渐增加或者减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表中的键值对过多或过少时，需要对哈希表的大小进行相应的扩展和收缩。而哈希表的扩展和收缩可以通过rehash来执行。rehash 就是将 ht[0] 中的节点，通过重新计算哈希值和索引值放到 ht[1] 哈希表指定的位置上。

扩容

  • 如果负载因子大于1，就会触发扩容，扩容的规则是每次翻倍；
  • 如果正在fork，执行持久化则不会扩容，但是，如果负载因子大于5，会立马扩容。

缩容
如果负载因子小于0.1，就会触发缩容。缩容的规则是：恰好包含used的2^n。

3.4 渐进式rehash

当哈希表中的元素过多时，如果一次性rehash到ht[1]，庞大的计算量，可能导致redis服务在一段时间不可用。为了避免rehash对服务器带来的影响，redis分多次、慢慢的将ht[0]哈希表中的键值对rehash到ht[1]哈希表，这就是渐进式rehash。

核心思想：将整个rehash过程均摊到每次命令的执行中。

rehash的详细步骤：

  1. 为 ht[1] 哈希表分配空间，此时字典同时拥有ht[0] 和 ht[1] 两个字典
  2. 将字典中的rehashidx设置为0，表示开始rehash
  3. 在rehash期间，每次对字典的增删改查，除了执行指定的命令外，还会顺带将ht[0] 中 rehashidx 索引上的所有键值对都rehash到ht[1]中，执行完rehash，rehashidx属性加一。注意：新增的键值对只能插入到ht[1]哈希表中，保证ht[0]的键值对只减不增。
  4. 随着操作的不断进行，最终ht[0]哈希表中的所有键值对都被rehash到ht[1]中。此时，将ht[0]释放掉，让ht[0] 指向ht[1]，并设置rehashidx 为 -1，表示rehash完成。

四、字典常用 API

// 创建字典
dict *dictCreate(dictType *type, void *privDataPtr);
// 将键值对 key-val 插入到字典
int dictAdd(dict *d, void *key, void *val);
// 删除字典中指定 key 的键值对
int dictDelete(dict *d, const void *key);
// 获取指定key的value值
void *dictFetchValue(dict *d, const void *key);
// 将键值对 key-val 插入到字典,如果该key已经存在，则只更新val
int dictReplace(dict *d, void *key, void *val);

五、Rehash源码分析

5.1 添加元素步骤

// 1. 通过hash函数得到hash值
hash = dict->type->hashFunction(key);
// 2. 将hash值与对应哈希表的sizemask 进行 & 操作得到index
index= hash & d->ht[x].sizemask; // x = 0 or 1
// 3. 创建 dictEntry 节点，头插法插入到对应哈希表的index的位置
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
添加元素源码分析

redis使用 dictAdd() 方法往哈希表中添加元素。dictAdd 调用的是 dictAddRaw 方法，它会先通过_dictKeyIndex() 函数计算出table的index；再通过头插法将该节点插入到目标位置。

dictAdd() 函数

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{dictEntry *entry = dictAddRaw(d,key,NULL);if (!entry) return DICT_ERR;// 将 val 保存到 entry 节点dictSetVal(d, entry, val);return DICT_OK;
}

dictAddRaw() 函数

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{long index;dictEntry *entry;dictht *ht;if (dictIsRehashing(d)) _dictRehashStep(d);/* Get the index of the new element, or -1 if* the element already exists. */// 计算indexif ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)return NULL;/* Allocate the memory and store the new entry.* Insert the element in top, with the assumption that in a database* system it is more likely that recently added entries are accessed* more frequently. */ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];entry = zmalloc(sizeof(*entry));// 头插法 最快entry->next = ht->table[index];ht->table[index] = entry;ht->used++;// 将 key 保存在 entry 节点中dictSetKey(d, entry, key);return entry;
}

其中，在_dictKeyIndex() 函数计算index的时候，会调用 _dictExpandIfNeeded() 函数判断是否满足扩容的条件。其中有个条件是依赖于 dictTypeExpandAllowed(d) 的返回值。

_dictKeyIndex() 函数

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{unsigned long idx, table;dictEntry *he;if (existing) *existing = NULL;/* Expand the hash table if needed */if (_dictExpandIfNeeded(d) == DICT_ERR)return -1;for (table = 0; table <= 1; table++) {idx = hash & d->ht[table].sizemask;/* Search if this slot does not already contain the given key */he = d->ht[table].table[idx];while(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {if (existing) *existing = he;return -1;}he = he->next;}if (!dictIsRehashing(d)) break;}return idx;
}

_dictExpandIfNeeded() 函数

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{/* Incremental rehashing already in progress. Return. */if (dictIsRehashing(d)) return DICT_OK;/* If the hash table is empty expand it to the initial size. */if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);/* If we reached the 1:1 ratio, and we are allowed to resize the hash* table (global setting) or we should avoid it but the ratio between* elements/buckets is over the "safe" threshold, we resize doubling* the number of buckets. */if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&dictTypeExpandAllowed(d)){return dictExpand(d, d->ht[0].used + 1);}return DICT_OK;
}

dictTypeExpandAllowed() 函数

static int dictTypeExpandAllowed(dict *d) {if (d->type->expandAllowed == NULL) return 1;return d->type->expandAllowed(_dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),(double)d->ht[0].used / d->ht[0].size);
}

可以看到，如果 dictType 中没有设置 expandAllowed 函数，则直接返回真；如果设置了expandAllowed 函数，就需要执行完相应的函数才能确定是否可以扩缩容。这就是 dictType 的一个典型的应用场景。

5.2 rehash 源码分析

该函数每次从rehashidx开始的位置，固定扫描 10 个bucket，如果对应的bucket中有数据就 rehash 到 ht[1]中。

static void _dictRehashStep(dict *d) {if (d->pauserehash == 0) dictRehash(d,1);
}int dictRehash(dict *d, int n) {int empty_visits = n*10; /* Max number of empty buckets to visit. */if (!dictIsRehashing(d)) return 0;while(n-- && d->ht[0].used != 0) {dictEntry *de, *nextde;/* Note that rehashidx can't overflow as we are sure there are more* elements because ht[0].used != 0 */assert(d->ht[0].size > (unsigned long)d->rehashidx);// 跳过空的槽位while(d->ht[0].table[d->rehashidx] == NULL) {d->rehashidx++;// 如果 经过 n*10 次，还是为空，本次rehash结束if (--empty_visits == 0) return 1;}// 找到要rehash的bucketde = d->ht[0].table[d->rehashidx];// 遍历该bucket对应的dictEntry链表while(de) {uint64_t h;nextde = de->next;// 为该dictEntry 获取在ht[1]中的index h = dictHashKey(d, de->key) & d->ht[1].sizemask;// 头插法 de->next 指向 ht[1].table[h]的第一个元素 （可能为NULL，可能有元素）de->next = d->ht[1].table[h];// 更新ht[1].table[h]的值指向该 dictEntryd->ht[1].table[h] = de;d->ht[0].used--;d->ht[1].used++;de = nextde; // 更新de，继续遍历，直至为空}// 将ht[0]中 d->rehashidx 对应的bucket清空d->ht[0].table[d->rehashidx] = NULL;// 更新rehashidxd->rehashidx++;}// 检查整个ht[0]表，rehash是否完成if (d->ht[0].used == 0) {zfree(d->ht[0].table); // 释放ht[0]d->ht[0] = d->ht[1];   // 让ht[0] 指向 rehash后的 ht[1]_dictReset(&d->ht[1]); // 重置 ht[0], 以备下次rehashd->rehashidx = -1;return 0;}/* More to rehash... */return 1;
}

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习


http://chatgpt.dhexx.cn/article/3Oq8nP39.shtml

相关文章

Redis底层数据结构详解

Redis底层数据结构详解

Redis底层数据结构详解 我们知道Redis常用的数据结构有五种&#xff0c;String、List、Hash、Set、ZSet&#xff0c;其他的集中数据结构基本上也是用这五种实现的&#xff0c;那么&#xff0c;这五种是Redis提供给你的数据结构&#xff0c;这五种数据结构式怎么实现的&#xf…
阅读更多...
Redis的五种基础数据结构

Redis的五种基础数据结构

Redis的五种基础数据结构 Redis有5种基础数据结构&#xff0c;分别为:String(字符串)&#xff0c;list(列表)&#xff0c;hash(字典)&#xff0c;set(集合)和zset(有序集合)。 1.String(字符串) 字符串的结构 字符串String是Redis最简单的数据结构&#xff0c;它的内部表示…
阅读更多...
Redis的数据结构

Redis的数据结构

一、redis的数据结构 1、String字符串类型 Redis的String能够表示字符串、整数、浮点数三种值的类型 应用场景&#xff1a; 普通的赋值使用incr、decr命令进行递增和递减统计数据。用于实现乐观锁watch(事物)setNx实现分布式锁 底层数据类型&#xff1a; // 数据结构 stru…
阅读更多...
为了拿捏 Redis 数据结构，我画了 40 张图（完整版）

为了拿捏 Redis 数据结构，我画了 40 张图（完整版）

大家好&#xff0c;我是小林。 Redis 为什么那么快&#xff1f; 除了它是内存数据库&#xff0c;使得所有的操作都在内存上进行之外&#xff0c;还有一个重要因素&#xff0c;它实现的数据结构&#xff0c;使得我们对数据进行增删查改操作时&#xff0c;Redis 能高效的处理。…
阅读更多...
IDEA 配置Services面板

IDEA 配置Services面板

IDEA中的services窗口是一个管理所有服务的地方&#xff0c;特别是在使用spring cloud项目开发中&#xff0c;对多个微服务的管理非常实用。 配置方式一&#xff1a; 在IDEA中可通过配置将services窗口面板显示出来。 配置方式二&#xff1a; 找到项目.idea目录下worksp…
阅读更多...
如何在IDEA配置Tomcat

如何在IDEA配置Tomcat

1、点击RUN下拉的Edit Configurations 2、点击左上角号&#xff0c;下拉找到Tomcat Server&#xff0c;选择Local 3、 配置Tmcat信息 4、点击Deployment,选择右边的号&#xff0c;选择Artifict 5、Application context这里只写个“/”就可以了 6、点击Apply&#xff0c;然后返回…
阅读更多...
idea配置代理服务器

idea配置代理服务器

1、查看代理服务器ip和端口 使用http代理 2、idea中配置代理服务器 选择File --> Settings --> 搜索HTTP Proxy --> 选择Manual proxy configuration --> 选择HTTP输入ip和端口 --> 点击Apply 3、配置jvm启动参数 -Djava.net.useSystemProxiestrue 完成!
阅读更多...
IDEA配置安卓环境

IDEA配置安卓环境

IDEA是JetBrains公司推出的Java集成开发环境 &#xff0c;这学期又开了安卓课&#xff0c;少不了安卓环境&#xff0c;不过android stdio是完全支持安卓的&#xff0c;不适合开发java项目&#xff0c;作为小白&#xff0c;我觉得IDEA一个软件就够了&#xff0c;当然&#xff0c…
阅读更多...
idea配置maven仓库

idea配置maven仓库

1、去达内开发文档服务器下载对应插件 达内开发文档服务器 找到配置文件下载 &#xff0c;下载阿里云Maven创库配置 以上下载压缩包先不动 2、创建maven项目 打开idea file-----new project 点击左侧选择maven然后next 3、然后查看对应的maven路径 点击file---setting 每个…
阅读更多...
IDEA配置本地Maven

IDEA配置本地Maven

IDEA配置Maven: 参考视频教程:https://www.bilibili.com/video/BV1Qf4y1T7Hx?p45 总体流程预览: 创建一个空的项目IDEA配置Maven环境Maven 坐标详解IDEA创建Maven项目IDEA导入Maven项目maven Helper插件依赖管理 1.创建一个空的项目 File—>New—>Project—>Empt…
阅读更多...
idea配置tomcat

idea配置tomcat

1.添加tomcat。 2.点击Edit Configurations后打开如下界面。| 3.点击加号 4.在这里配置tomcat信息&#xff0c; 5.填写好基本tomcat信息后&#xff0c;点击ok。我们就配置好了Tomcat&#xff0c;此时我们会看到。项目中显示了我们刚才配置的的Tomcat。 但是直接运行的话…
阅读更多...
idea配置docker

idea配置docker

IDEA作为开发电脑&#xff0c;要远程连接到另一台Linux电脑上部署的Docker服务&#xff0c;我们登陆到机器上&#xff0c;进行docker远程访问配置&#xff1a; IDEAdocker实践 - 邹姣姣 - 博客园 idea里 选择Plugins&#xff0c;插件 已经安装了docker插件 连接远程Docker服…
阅读更多...
idea配置maven

idea配置maven

idea配置maven 下载配置maven(如果有请跳过)打开idea开始配置maven附录&#xff1a; 下载配置maven(如果有请跳过) 首先你先得安装配置你本机maven的环境&#xff0c;官方下载maven&#xff0c;附带下载maven&#xff1a; 下载maven链接 我选择的时3.6.3-bin.zip&#xff0c…
阅读更多...
Idea配置Tomcat服务器

Idea配置Tomcat服务器

一、新建项目 首先新建一个Java项目 此时只是新建了一个Java项目&#xff0c;还不能用于写JavaWeb程序&#xff0c;所以接下来需要添加Web框架&#xff0c;并 配置Tomact服务器 右键点击项目Demo1&#xff0c;选择【添加框架支持】&#xff0c;然后再左侧中选择【Web应用程序…
阅读更多...
idea配置ant版本_idea配置ant项目

idea配置ant版本_idea配置ant项目

之前一直用的maven管理&#xff0c;所以编译 打包都交给了maven&#xff0c;但是最近接触了新的项目&#xff0c;不是用maven管理的&#xff0c;是ant去【管理】的(这么说不严谨)&#xff0c;在用idea去本地启动tomcat的时候周折了一番&#xff0c;特记录。 1、找build.xml 里面…
阅读更多...
IDEA配置jetty

IDEA配置jetty

&#x1f68c;一个人可以走的很快&#xff0c;一群人可以走的很远&#x1f4dd; &#x1f389;点赞➕评论➕收藏 ➕关注 养成习惯&#xff08;一键四连&#xff09;&#x1f4dd; &#x1f389;欢迎关注&#x1f497;一起学习&#x1f44d;一起讨论⭐️一起进步&#x1f4dd; &…
阅读更多...
IDEA 配置热部署

IDEA 配置热部署

IDEA 配置热部署 引言步骤1步骤2步骤3IDEA 旧版本IDEA 新版本 热部署的缺点总结 引言 平时如果我们修改了自己项目的代码后&#xff0c;都要重新运行启动类&#xff0c;才能使新的项目生效&#xff0c;配置了热部署后&#xff0c;我们就可以让 IDEA 自动帮我们重启项目了。 I…
阅读更多...
IDEA配置TestNG

IDEA配置TestNG

1.IDEA安装TestNG 若IDEA已经安装TestNG的插件&#xff0c;显示如下 若没有&#xff0c;则搜索TestNG&#xff0c;进行下载 2.创建单元测试方法 1.打开需要进行单元测试的方法&#xff0c;选择类名&#xff0c;点击AltEnter键&#xff0c;选择Create Test 第一次创建单元测…
阅读更多...
Idea配置SVN

Idea配置SVN

idea配置SVN 1. 配置svn.exe路径 2. 启用版本控制 VCS–enable version control integration 3. 设置Version Control Settings–Version Control 4. 在工程上右键可以看到 此时项目已经变更颜色了. 5. 提交maven工程到svn仓库 首先工程右键—subversion–share Directory…
阅读更多...
IDEA配置GitHub

IDEA配置GitHub

目录 1、IDEA配置 安装Git 配置GitHub账号 一、IDEA配置 安装Git File -> Setting -> Git ->Test 如果未安装Git&#xff0c;会提示安装 配置GitHub账号 配置账号&#xff0c;自动跳转到github上进行授权 二、代码管理 1、vcs配置&#xff0c;如下图 2、配置好…
阅读更多...
推荐文章

Copyright @ 2022~2023