前言

本文是Redis数据结构详解系列的第二篇，上篇我们介绍了SDS与链表的数据结构，本篇将着重介绍哈希字典与整数集合。

哈希字典

哈希字典定义

一个完整的哈希字典由哈希表，哈希表节点以及字典三个部分组成。

哈希表定义:

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表掩码大小，用于计算索引值。他总是等于size-1
    unsigned long sizemask;

    // 哈希表已有节点的数量
    unsigned long used;

} dictht;

哈希表保存了一个哈希表数组，size属性记录了当前哈希表的大小即table数组的大小，同时有一个sizemask属性总是等于size-1，目的是方便计算哈希值索引位置(使用hash&sizemask确定索引值)。used属性则是统计哈希表已经保存的节点数量。

哈希表节点


typedef struct dictEntry {

    // key值键
    void *key;

    // 键对应的值 
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
 
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

哈希节点结构相对简单，每个哈希节点都保存着一个键值对。key属性保存的键，value属性保存的是key对应的值。值可以是一个指针，也可以是一个uint64_t整数，int64_t整数，double双精度浮点型。
同时我们还可以注意到，哈希节点还保存着一个指向下一个哈希节点的指针，该指针是用来将哈希值相同的键值对以链表的方式连接在一起以解决哈希冲突的问题。

字典


typedef struct dict {
    
   // 为不同用途字典提供特定函数用于操作键值对
    dictType *type;

    // 私有数据，保存传给特定函数的可选参数
    void *privdata;

    // 哈希表数组
    dictht ht[2];

    // rehash时所需要的索引，不在rehash时值为-1
    long rehashidx; 

} dict;

我们可以看到整个哈希字典拥有着两张哈希表，正常情况下我们只会用到其中一张ht[0],只有当扩容rehash时才需要使用到ht[1]。而rehashidx也是如此，一般情况下值为-1。

image.png

哈希过程

Redis的哈希表计算与Java中HashMap的哈希计算基本一致，可以参考我的这篇文章:探究JDK1.8中HashMap的实现原理。
我将大致列举下将一个键值对(key,value)添加到字典中的过程:

  1. 计算出key的hash值(Redis使用MurmurHash2算法)
  2. index=hash&sizemask 计算出该键值对应该保存在dictEntry[index]上(hash&sizemask其实也就是对哈希表大小取模计算，因为哈希表的大小是2的n次方)

解决冲突

当有多个键值对被分配到哈希表数组的同一个索引上面时，会出现哈希冲突。Redis使用了链地址法解决冲突。每个节点都有一个next指针，被分配到同一个所以上的节点可以用这个单向链表连接起来。同时为了速率考虑，Redis总是将新节点添加到链表的表头位置。

image.png

rehash

当哈希表保存的数据越来越多时，为了减少哈希冲突，Redis会对哈希表进行扩容。而保存的数据数据越来越少时，为了节省内存消耗，Redis同样会对哈希表进行收缩。扩容与收缩的操作都可以通过rehash来完成，以下我们将以扩容的操作进行举例。

rehash扩容时机

Redis会根据哈希表的负载因子是否超过阈值来判断是否需要扩容。(负载因子=哈希表已保存节点数量/哈希表大小)

  • 在Redis没有执行BGSAVE命令或者BGREWRITEOF命令时，哈希表的负载因子大于等于1时会进行扩容
  • 在Redis正在执行BGSAVE命令或者BGREWRITEOF命令时，哈希表的负载因子大于等于5时会进行扩容

可以看到Redis会根据是否在执行BGSAVE命令活BGREWRITEOF调整扩容的阈值，这样的原因是在执行上述命令时大多数操作系统会采用写时复制来fork出一个新的子进程，如果扩容导致内存频繁写入，反而会更加消耗内存。因此此时提高阈值可以减少不必要的内存写入，节约内存空间。

rehash扩容过程

rehash扩容过程分为如下3个步骤

  1. 将ht[1]的大小设置为第一个大于等于ht[0].used*2的2的n次幂(2的n次幂为了方便计算hash值)
  2. 将ht[0]中的键值对rehash到ht[1]上,即重新计算键的哈希值与索引值，将键值对放置到ht[1]哈希表中的指定位置上。
  3. 当ht[0]的数据全部迁移到ht[1]后，释放ht[0]的数据，并将ht[1]设为ht[0],在ht[1]上创建一个新的哈希空表为下次rehash做准备。

渐进式rehash

扩容或收缩时都会将ht[0]的键值对rehash到ht[1]中，但是需要考虑到哈希表的数据可能会很多，这个操作会很耗时。因此Redis并不会一次性集中完成rehash而是使用渐进式的rehash方式。

渐进式rehash步骤

  1. 字典中rehashidx保存了索引计数器，默认情况下是-1，开始rehash时将其设置为0，表示rehash开始。
  2. 在rehash过程中，每当对字典的数据进行增删改查时，除了执行这些操作外，还会将ht[0]中哈希表数组的dictEntry[rehashidx]的所有键值对rehash到ht[1]上，当rehash完成后，将rehashidx的属性值+1
  3. 随着操作不断执行，最终ht[0]的所有键值对都会被rehash至ht[1]上，此时将rehashidx的属性设为-1表示rehash已经完成。

注：rehash时，查询操作将会先去查询ht[0]的数据，如果没有的话再去查询ht[1]的数据。
渐进式rehash图解如下:
image.png

整数集合(intset)

整数集合是Redis用于保存整数值集合的一种数据结构，是集合对象（Set）的底层实现之一(当集合对象全是整数时)

整数集合定义

整数集合数据结构定义如下：

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

图示如下：

image.png

整数结合由三个属性组成：

  • encoding： 代表编码方式，有三种编码方式INTSET_ENC_INIT16,INTSET_ENC_INIT32,INTSET_ENC_INIT64分别表示可以数据占用16个字节，32个字节，64个字节。当然字节数越大可支持的整数值越大
  • length： 代表整数集合内所包含的元素数量
  • content： 按照从小到大顺序保存了集合中的整数数组

整数集合的升级

当一个新元素添加到整数集合里，且新元素的编码类型比现有所有元素的类型都要大时，整数集合就需要升级

升级步骤:

  1. 根据新元素类型，拓展整数集合数组空间大小，并预留新元素所需的空间大小
  2. 将数组所有元素都转换成与新元素相同的类型
  3. 将新元素添加到数组中

升级的好处

  1. 降低风险，提升灵活性，不必像C语言一样用多个整数类型的保存不同数组，而是通过升级底层数组来适应新元素，不必担心出现类型错误。
  2. 节约内存：能同时保存三种类型的值，又可以确保升级只在需要的时候进行，尽可能节约了内存。

注：整数集合不支持降级操作，一旦对数组进行了升级，编码会一直保持升级后的状态

结语

本文主要介绍了哈希字典与整型数组两个数据结构。
哈希字典：

  • 哈希字典由两个哈希表组成，一个用于存储键值对，一个用于扩容辅助
  • 哈希表使用了链地址法解决哈希冲突
  • 哈希表采用了渐进式hash的方式，分布式的完成扩容

整型数组：

  • 整型数组是集合(Set)对象的底层实现方式之一
  • 整型数组支持升级的方式以支持更大长度的编码类型
  • 整型数组不支持降级

参考资料

《Redis设计与实现》

Q.E.D.

吃得苦中苦，卷成王中王🏆