Hash表与Dict及渐进式Rehash

1435597771 · Jul 23, 2026

Redis Hash是什么 RedisHash是Redis中的数据类型，他存储的是键值对数组。键值对数组中，每一个元素都是一个key-value成对出现。 RedisHash底层实现 RedisHash的底层实现数据结构是listpack和dict。在键值对数组个数小于512个,所有值小于64字节，那么就用listpack来存储键值对。如果不满足上述条件，那么Redishash就会选择用Dict（也叫做哈希表，不过因为哈希表和Hash数据结构在字面上看上去是一个东西，所以就用Dict来表述哈希表，用作区分Hash数据结构）结构体来存储键值对数组。本文主要来介绍Dict结构体 Dict是什么 Dict是一个保存键值对的数据结构，他本质上是一个数组。为什么说他是数组，我们需要看Dict的结构体来说明。dict的字段有： ht[2]：是两个dictht结构体，平时存放数据只存放进一个dictht中。那么dictht的结构是什么样子的呢，他有几个字段需要说明 dictEntry **table: 是一个数组，数组中的元素存储的是指向 dictEntry的指针。我们常说的hash桶就是指这个数组中的一个位置。实际的值就是存储在这个数组中元素指向的地址 size：dictht大小，表明dictEntry **table有几个元素 sizemask：dictht大小掩码，用来计算索引值 used：used 是一个简单的累加计数器，代表当前哈希表里所有 dictEntry` 节点（包含所有拉出来的链表节点）的绝对物理总数 dictEntry **table是什么：他是一个数组，数组中每个元素都是一个指向dictEntry的指针。我们一直都在说dictEntry，那么他又是什么呢？ dictEntry的字段如下： key: 就是我们往hash中存入的key value：往hash中存入的value next：这个字段比较重要，他是指向下一个dictentry的指针所以，我们通过next这个字段可以看见，dictEntry是一个单向链表。我们结合dictEntry和dictEntry **table 可以看出来，ditch就是一个数组+单向链表的结构数据是如何存入Dict中的我们在上面了解了Dict的基础信息，知道了Dict是Hash数据结构的底层实现之一，那么一个键值对是如何存入Dict中的呢？他的步骤是：对键值对中的key进行哈希函数运算，计算出哈希值将哈希值与dict大小取模计算，计算出来的位置，就是这个键值对在table中的位置将键值对放入对应的哈希桶中我们举例子再说明一下：dictEntry **table的大小为8，有key1-value1的键值对要存入其中。 hash(key1)%8 = 1 ，那么这个键值对就会被放在第一个位置。hash(key10)%8 = 2,那么就会被放入第二个位置。那么如果是hash(key9)%8=1，他是应该要存入第一个位置的对不对，那么他是怎么存放的呢？我们说过每一个dictEntry中有next节点，key9和key1要存入一个哈希桶中，这叫做哈希冲突，那么原来桶1已经存放了key1，现在来了key9，就新建一个节点，让桶1指向key9，然后key9的next指向key1。这种用链表的方式解决哈希冲突，也叫做链式哈希。现在有一个问题，如果哈希冲突严重，那么会造成单向链表过长，造成检索效率下降，那么Redis是如何解决这个问题的呢？渐进式Rehash是什么为了解决哈希冲突严重的问题，redis中使用渐进式Rehash的方法，我们先来了解什么是Rehash。还记得我们说过Dict结构体中是使用了两个dictht，只在其中一个dictht中存入数据吗？存数据的我们给他起名ht[0]，那么ht[1]就是在Rehash中使用的，也就是扩容，整个过程分三步：给ht[1]分配空间，是ht[0]的两倍大小将ht[0]中的数据转移给ht[1]中迁移完成，ht[0]的空间被释放，把ht[1]设置为ht[0]，然后创建一个新的ht，为下一次rehash做准备整个过程看起来很简单，但是这里面有问题，问题就在第二步中，在迁移数据的时候，会涉及大量的数据拷贝，redis又是单线程的，如果数据多，可能会对redis造成阻塞，无法服务别的请求。为了解决这个问题，redis提出了渐进式Rehash，其实简单来说，就是不一次性迁移完所有的数据，在对数据每一次更新，新增等操作的时候，除了再执行操作之外，还会执行迁移操作。巧妙的把数据迁移拆分成多次处理请求过程中。同时，在数据的迁移的过程中，因为会使用到两个ht，所以更新，删除都会在这两个ht中进行操作。总的来说，现在ht[0]中找对应的key，如果没找到就去ht[1]中找。需要特别说明的是，新增操作直接在ht[1]中操作。负载因子我们说了渐进式Rehash是什么，那么什么时候他会被触发呢？在redis中提出了负载因子这个概念。还记得我们dichht中有size和used这两个字段吗？负载因子就是used/size 。当负载因子大于等于1，并且Redis没有在执行RDB快照或者没有进行AOF重写的时候就会进行rehash操作当负载因此大于等于5的时候，不论redis在进行什么操作，都会强制执行rehash操作常用命令 HSET key field value: 在存储一个哈希表（key）的键值对 HGET key field：获取哈希表（key）中对应的field的值 HMSET key [field value...] 在一个哈希表（key）存储多个键值对 HMGET key [field...] 批量获取哈希表中的多个field对应的值 HDEL key field [field....] 删除哈希表(key)中的field键值对 HLEN key 获取哈希表中field的数量 HGETALL key 获取哈希表中所有的键值对 HINCRBY key field n 给哈希表key中的field对应的值+n 使用场景缓存对象：与string不同的是，用hash缓存结构型的数据。而string只能缓存字符串，因此可以说明string+json 才能达成hash数据类型的操作。但是hash的优势在于，可以直接操作哈希表中的键值对