ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
`hash表`有两种存储的数据编码:ziplist 压缩列表,ht(hashtable) 哈希表 一, ziplist 压缩列表 ![](https://img.kancloud.cn/7d/9e/7d9e808a2b9e1c351499e196e23bf02a_886x430.png) ![](https://img.kancloud.cn/67/d2/67d25c899fd037750218048d4b4f6156_857x143.png) ①、previous\_entry\_ength:记录压缩列表前一个字节的长度。previous\_entry\_ength的长度可能是1个字节或者是5个字节,如果上一个节点的长度小于254,则该节点只需要一个字节就可以表示前一个节点的长度了,如果前一个节点的长度大于等于254,则previous length的第一个字节为254,后面用四个字节表示当前节点前一个节点的长度。利用此原理即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置,压缩列表可以从尾部向头部遍历。这么做很有效地减少了内存的浪费。 ②、encoding:节点的encoding保存的是节点的content的内容类型以及长度,encoding类型一共有两种,一种字节数组一种是整数,encoding区域长度为1字节、2字节或者5字节长。 ③、content:content区域用于保存节点的内容,节点内容类型和长度由encoding决定。 二ht(hashtable) 哈希表又或者叫字典dict (1)hashtable 被称为字典(dictionary),它是一个数组+链表的结构 (2)为什么有 ht\[0\] 和 ht\[1\] 两个hash表,是为了扩容 字典、哈希表和哈希表节点关系图: ![](https://img.kancloud.cn/bd/3c/bd3c2ad06e45d69c64c27dadb6683cef_1133x592.png) 1.字典 ![](https://img.kancloud.cn/4e/e6/4ee6187ad2b0a9556f64489bf85733b3_1202x531.png) * type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数; ![](https://img.kancloud.cn/1d/59/1d5971c24e8b1d33e4d4652b55b1397d_268x301.png) * privdata属性保存了需要传给那些类型特定函数的可选参数; * ht属性是一个包含两个项的数组,数组中的每个项都是一个dictht哈希表,ht\[1\]只有在对ht\[0\]哈希表进行rehash操作时使用; * trehashidx属性是rehash索引,没有进行rehash操作时值都为-1. 2.哈希表 ![](https://img.kancloud.cn/39/d3/39d3dc6a801fcda2533cba6ac67167fc_966x511.png) * table属性是一个数组,数组中的每个元素都是一个指向哈希表节点的指针,每个节点都保存着一个键值对; * size属性记录了哈希表的大小,也就是table数组的大小; * sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的那个索引上面; * used属性记录了哈希表目前已有节点的数量。 3.哈希表节点 ![](https://img.kancloud.cn/0c/9a/0c9a03f34a1d5742371d6f82ef87705b_1021x519.png) * key属性保存着键值对中的键; * v属性保存着键值对中的值,其中值用union定义,支持三种数据类型。 * next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一起,以此来解决键冲突的问题。 (2)哈希计算 ①、哈希算法:**Redis计算哈希值和索引值方法如下: 1、使用字典设置的哈希函数,计算键 key 的哈希值hash = dict->type->hashFunction(key); 2、使用哈希表的sizemask属性和第一步得到的哈希值,计算索引值index = hash & dict->ht[x].sizemask; ②、解决哈希冲突:**这个问题上面我们介绍了,方法是链地址法。通过字典里面的 \*next 指针指向下一个具有相同索引值的哈希表节点。 ③、扩容和收缩:**当哈希表保存的键值对太多或者太少时,就要通过 rerehash(重新散列)来对哈希表进行相应的扩展或者收缩。具体步骤: 1、如果执行扩展操作,会基于原哈希表创建一个大小等于 ht\[0\].used\*2n 的哈希表(也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表)。相反如果执行的是收缩操作,每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。 2、重新利用上面的哈希算法,计算索引值,然后将键值对放到新的哈希表位置上。 3、所有键值对都迁徙完毕后,释放原哈希表的内存空间。 ④、触发扩容的条件:** 1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且负载因子大于等于1。 2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且负载因子大于等于5。 ps:负载因子 = 哈希表已保存节点数量 / 哈希表大小。 ⑤、渐近式 rehash** 什么叫渐进式 rehash?也就是说扩容和收缩操作不是一次性、集中式完成的,而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个,那么 rehash 操作可以瞬间完成,但是如果键值对有几百万,几千万甚至几亿,那么要一次性的进行 rehash,势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间,字典的删除查找更新等操作可能会在两个哈希表上进行,第一个哈希表没有找到,就会去第二个哈希表上进行查找。但是进行 增加操作,一定是在新的哈希表上进行的。