当前位置：科技动态 > redis中的字典结构是怎样的？

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

发布：2023-10-06 04:53

-->

点赞再看，养成习惯，微信搜索“小大白日记”关注这位砖匠。

不定期同步文章公众号，还有各种一线厂商原创面试题和我的系列学习笔记。

基本概念

redis支持的5种数据类型中，就有hash类型。 hash类型底层是通过字典结构（多个键值对）实现的，字典结构=hashTable=的代码实现使用了哈希表

字典结构的实现

字典结构由三个结构组成：字典结构=dict+dicttht+dictEntry，关系如下：

代码实现：

typedef 结构字典 {

    字典类型*类型； //dictType也是一种数据结构。 dictType 结构包含一些函数。这些函数用来计算key的哈希值，然后用这个哈希值计算dictEntry类型表数组中key的下标

    无效*隐私数据； //私有数据，dictType结构体中保存函数的参数

    字典 ht[2]; //两张哈希表，一张用于正常存储节点，一张用于rehash时临时存储节点

    长期康复； //重新散列标签：默认-1。当表数组中现有元素的数量增加/减少到一定数量时，整个字典结构将被重新哈希以重新分配每个表元素的位置。 rehasidx代表rehash过程。进度，rehasidx==-1表示字典没有被rehash，rehasidx>-1表示字典结构正在rehash

字典；

typedef struct dicttht { //哈希表
dictEntry **表； //存储数组的地址。每个数组元素存储哈希表节点dictEntry
的地址
    无符号长尺寸； //哈希表的表数组长度较小，初始大小为4

    无符号长尺寸掩码； //哈希表掩码sizemask的值始终等于(size-1)，用于计算表中每个key的下标位置 =hash(key)&sizemask

    无符号长期使用； //记录哈希表的表中已有的节点数（node=dictEntry=键值对）。 

} 听话；

typedef struct dictEntry {

    void *key;//键

    union{ //值

        void *val;//值可以是指针

        uint64_tu64;//该值可以是无符号整数

        int64_ts64;//该值可以是有符号整数

    } v;

    struct dicEntry *next;//指向下一个dictEntry节点：redis的字典结构使用链表方法来解决哈希冲突。当表数组中某个位置有元素时，该位置使用头插值的方式形成链表来解决哈希冲突

} dictEntry;

使用key计算（key-value）在表中的位置下标：

//1。先计算key的哈希值：使用字典中的函数计算key的哈希值

hash = dict结构体->dictType结构体的函数hashFunction(key)

//2.根据哈希值与哈希表掩码sizemask进行AND运算得到下标，x=(0或1)=两个哈希表中正常用来存储节点的哈希表的下标Mark

索引 = hash & dict->ht[x].sizemask;

字典中的负载因子和重新哈希

我们来看看几个重要的概念：

redis字典中哈希表的rehash=扩大或缩小哈希表中的表数组长度；

负载因子=ht[0].dict结构的使用/ht[0].dict结构的大小=哈希表表中已有的节点数/哈希表的表数组长度;

bgsave操作：将redis内存中的数据以rdb的形式持久化到磁盘；

bgrewriteaof操作：将redis内存中的数据以aof的形式持久化到磁盘。持久化成功后，旧的aof文件会被替换（redis2.4以后aof由redis自动触发，bgrewriteaof需要手动触发）

redis中的哈希表什么时候扩容？

两种情况：

当没有bgsave操作&&没有bgrewriteaof操作&&负载因子>=1;

当(bgsave操作正在进行|| bgrewriteaof操作正在进行)&&负载因子>= 5;

为什么负载因子 >=1？因为当发生哈希冲突时，新的节点会以头插值的形式插入到哈希表的表数组的某个位置，形成链表，这样就会使得表中的节点总数>表数组的长度，然后负载因子 >= 1

redis中的哈希表什么时候扩容？

当负载因子 <= 0.1 时（例如表数组的长度经过多次扩展已达到 16，并且表在某一时刻只有 1 个元素，1/16=0.0625<0.1，则哈希表是重新哈希以缩小表长度）

redis中哈希表扩容或者缩容的过程？

扩展：dict数据结构中有两个哈希表ht[2]和ht[0]，平时用来存储redis数据（key-value），ht[1]用来存储ht[0]重新散列扩展。元素，直到ht[0]中的所有元素被重新计算并存储到ht[1]中的表数组中，ht[1]的大小=第一个大于或等于ht[0]的2^n。使用过

收缩：与“扩展”操作相同，ht[1]用于在收缩过程中保存ht[0]的元素，ht[1]的大小=前2个大于或等于到 ht[0].used ^n （公式与展开式相同）

特点：

扩张或收缩完成后，释放哈希表ht[0]，将哈希表ht[1]设置为ht[0]，然后重新分配一个新的空白ht[1]作为下次rehash使用
rehash（扩容或收缩）过程中存在两个哈希表，字典会同时使用两个哈希表：查找、删除、更新会同时操作两个哈希表（首先在ht [0]如果找不到，可以去ht[1]搜索）。 “插入”仅操作 ht[1]
重新哈希过程是渐进的。它采用分而治之的方法。以expansion为例，一开始将rehashidx值设置为-1到0，代表rehash工作开始：

此时rehashidx为0。如果第一次对redis字典进行【增、删、查、更新】操作，会重新计算ht[0]中table[rehashidx]=table[0]的数据。将下标放入ht[1]的table数组中，然后rehashidx增加到1；

此时rehashidx为1。如果第二次对redis字典进行【增、删、查、更新】操作，则ht[0]中table[rehasidx]=table[1]的数据会重新计算。将下标放入ht[1]的table数组中，然后rehashidx增加到1

...以此类推，直到ht[0]中的所有表元素都被重新计算并rehash到ht[1]中，最后rehashedx被设置为-1，此时rehash完成；

渐进式rehash可以将这个过程中的计算压力分配到每次对字典进行[添加、删除、搜索或更新]操作时，避免需要一次rehash整个hash类型数据（redis的5个数据）某个时刻。类型一）执行大量的rehash计算，从而避免redis阻塞。唯一的缺点是rehash时同时使用两个哈希表，导致redis内部使用量激增