文章目录

• • • • 字典介绍
      • 字典的实现
      • • 哈希表(dictionary hashtable)
        • • 结构体
          • 图解哈希表数据结构
        • 哈希节点(dictionary entry)
        • • 结构体
          • 图解哈希节点数据结构
        • 字典(dictionary)
        • • 结构体
          • 图解字典数据结构
        • 哈希掩码在哈希算法中的巧妙应用
        • 哈希冲突
        • rehash(重新散列)
        • • Redis对字典哈希表进行rehash的步骤
        • 渐进式rehash
        • • 渐进式rehash期间读/写操作的执行过程
          • 那么问题来了
          • 有个要注意的点
        • 哈希表的扩容和缩容
        • • 扩容
          • 缩容
        • 参考

字典介绍

字典，一种用于保存键值对（key-value）的抽象数据结构，也就是我们常见的映射map。

​ 因为Redis是用C语言实现的，但C自己又没有实现字典这种数据结构，所以Redis构建了自己的字典实现。

​ 我们从Redis全称Remote Dictionary Server（远程字典服务）可以看出Redis本身底层实现就是一个字典，所以Redis也被称为Key-Value数据库。

当我们执行指令：

localhost:1>set msg "hello world"
"OK"

对于上面的指令，msg就是字典的键(key)，hello world是字典键对应的值(value)

字典的实现

哈希表(dictionary hashtable)

结构体

typedef struct dictht {
    //哈希表数据
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算哈希桶索引
    //总是等于size-1
    unsigned long sizeMask;
    //哈希表已使用节点的数量
    unsigned long used;
}

图解哈希表数据结构

空哈希表(没有使用一个哈希节点)

哈希节点(dictionary entry)

结构体

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        unit64_tu64;
        int64_ts64;
    } v;
    //指向下一个节点，哈希冲突时形成链表
    struct dictEntry *next;
} dictEntry;

图解哈希节点数据结构

使用了2个节点且哈希冲突了的哈希表，used=2

字典(dictionary)

结构体

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引,值为-1时表示没有在进行rehash操作
    int rehashidx;
} dict;

属性介绍：

• type:指向dictType结构的指针，每个dictType的结构保存了一簇用于操作指定类型键值对的函数，结构如下：

  typedef struct dictType {
      //复制hash值的函数
      unsigned int (*hashFunction)(const void *key);
      //复制键的函数
      void *(*keyDup) (void *privdata, const void *key);
      //复制值的函数
      void *(*valDup) (void *privdata, const void *val);
      //键对比函数
      int (*keyCompare) (void *privdata, void *key);
      //键销毁函数
      void (*keyDestructor) (void *privdata, const void *key1, const void* key2);
      //值销毁函数
      void (*valDestructor) (void *privdata, void *val);
  }
  

• privdata: 保存了需要传给以上类型特定函数的可选参数。

• ht: 2个长度的一维数组，一般只是用ht[0]，ht[1]在对ht[0]进行rehash时才使用。

• rehashidx: 当值不是-1时代表正在进行rehash操作，用于记录当前rehash的进度。

图解字典数据结构

哈希掩码在哈希算法中的巧妙应用

​ 通过dictht结构体，我们知道sizemask的大小总比size小于1（size大于0时），为什么要这么设计呢？首先我们需要先了解一个key在哈希表中索引怎么求。

​ 假设有一个大小为4的哈希表，现在准备插入一个键值对，求出了它key的哈希值为7，由于哈希表此时只有0_{3范围的索引，所以我们不能直接存到索引7，否则会导致数组越界，需要对大小4求余才能取到0}3范围的数，即7%4=3，最终这个哈希值为7的key会被存到索引为3的下标中。

​ 以上方法是可行的，但是从性能方面来说，使用%进行求余运算还是太慢了，所以大佬们发现了一种更快的求余运算方式——与位运算&。继续以上例为例：7%4的操作等价于7&(4-1)=3，运算中的4-1也就是sizemask掩码。

​ 不过这种算法有个限制，只对2^{n次幂的数生效，上面举例的4恰好是2}2，所以公式成立，如果大小是5则不适用，读者可自行验证，这也是为何哈希表扩容都是增长到2^n，大小初始化和缩容同理。

​ ps：但是为什么偏要另起一个sizemask属性的空间存储呢？我对着个问题还是存疑，毕竟直接size-1不就好了吗？如果有读者有个人见解或答案，请评论区留言告知，谢谢~

​ 总结：对于2^n的数N，可得m % N = m & (N-1)

求一个key在哈希数组中的索引过程：

1. 使用字典设置的哈希函数，计算出key的哈希值

   hash = doct->type->hashFunction(key);

2. 使用hash的sizemask属性和哈希值，计算索引值，其中ht[x]的x可以是0或1

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

​

哈希冲突

​ 因为不同的哈希值对同一个数求余后的结果是可能一样的，也就是不同key最终会插入到同一个哈希槽里，这就是我们常说的哈希冲突，或者哈希碰撞。例如有key1哈希值为7、key2哈希值为11，它们对4求余的结果都是3，此时我们称key1和key2出现了哈希冲突。

​ 在Redis中，采用了链地址法解决哈希冲突，当多个key被分配到同一索引上时，会将这多个dictEntry连接成一条链表，用next属性将它们之间的关系关联起来，所以也是一条单向链表。

​ 因为dictEntry没有指向链尾的指针，所以为了速度考虑，总是会将新加入的节点插入到链表的头部，时间复杂度为O(1)。

rehash(重新散列)

​ 当哈希表的节点数量达到一定的阈值时，会进行扩容/缩容操作，由于大小改变了，而当时分配哈希索引时的求余计算又是依赖这个大小的，也就意味着需要对所有的key重新计算所对应的哈希索引，这一过程称为rehash(重新散列)。

Redis对字典哈希表进行rehash的步骤

  	1. 为字典的ht[1]分配空间：
      - 如果是扩容操作，ht[1]大小为第一个大于等于ht[0].used*2的2^n
      - 如果是收缩操作，ht[1]大小为第一个大于等于ht[0].used的2^n
  	2. 将所有ht[0]中的键值对rehash到ht[1]，ht[0]中所有的键都要进行重新计算哈希值和索引值，放入ht[1]对应的新索引中；
  	3. 当ht[0]所有键值对都迁移到ht[1]之后，释放ht[0]，将ht[0]指向ht[1]，为ht[1]分配一个空的哈希表，为下次rehash做准备。

举个例子，对下图进行rehash扩容操作：

1. 为ht[1]分配空间，大小为第一个大于等于ht[0].used*2的2^n，即4*2=8

2. 对k0-v0进行rehash，rehasidx值为0，表示对ht[0]->dictEntry[0]进行rehash，假设k0计算后的索引值为4，迁移后ht[0].used-1=3，ht[0].used+1=1
   

3. 对k1-v1进行rehash，rehasidx值为1，表示对ht[0]->dictEntry[1]进行rehash，假设k1计算后的索引值为5，迁移后ht[0].used-1=2，ht[1].used+1=2
   

4. 对k2-v2进行rehash，rehasidx值为2，表示对ht[0]->dictEntry[2]进行rehash，假设k2计算后的索引值为2，迁移后ht[0].used-1=1，ht[1].used+1=3
   

5. 对k3-v3进行rehash，rehasidx值为3，表示对ht[0]->dictEntry[3]进行rehash，假设k3计算后的索引值为1，迁移后ht[0].used-1=0，ht[1].used+1=4
   

6. 迁移完毕，ht[0]指向迁移后的ht[1]，ht[1]指向空哈希表
   

渐进式rehash

​ 如果ht[0]中需要进行rehash的节点数量只有少数的几个时，整个rehash过程是很快的，基本不会影响到Redis的性能，但实际场景往往不是这样的，可能会有百万、千万甚至亿级以上的数据，如果rehash过程是集中式地独占整个线程的话，期间所有的读写操作都会被阻塞，极大地影响了Redis的使用体验，还可能导致服务停止。

​ 针对大数据量rehash的问题，Redis使用了渐进式的方式进行rehash操作，即不会一次性对所有键值对节点进行rehash，而是渐进式地边进行读写操作边rehash，在rehash期间(rehashidx不等于-1)，每次读写操作都会额外负责对当前rehashidx索引上的所有键值进行rehash。

渐进式rehash期间读/写操作的执行过程

• 增：如果是添加操作，会计算新节点的键在ht[1]上的索引，直接添加到ht[1]上，不会对ht[0]进行任何添加新节点的操作，添加成功后将当前rehashidx上的所有哈希节点迁移到ht[1]相应索引上，rehashidx+1，这样能保证ht[0]上的数据只减不增，直至为空，最终完成rehash；
• 删、改：先从ht[0]查找要操作的键，ht[0]没有则从ht[1]找，找到后执行删/改操作，将当前rehashidx上的所有哈希节点迁移到ht[1]相应索引上，rehashidx+1；
• 查：先从ht[0]读取本次数据，没有则从ht[1]读取，将当前rehashidx上的所有哈希节点迁移到ht[1]相应索引上，rehashidx+1，返回结果。

那么问题来了

Q：渐进式rehash期间如果没有读写操作，是不是rehash就卡住了？

A：不一定。如果字典在进行rehash操作且对activerehashing配置进行了非0值的设置，则会定时花费1毫秒时间主动进行rehash，activerehashing默认为1，表示开启主动rehash。

redis.c部分相关源码阅读：https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/redis.c

dict.c源码：

有个要注意的点

​ 因为rehash期间同时为ht[0]和ht[1]分配了空间，如果在内存将满或已满时进行rehash的话，内存会继续飙升，此时进行淘汰策略，大量key会被淘汰掉。

哈希表的扩容和缩容

​ 在讲扩容和缩容前，先了解一下负载因子的计算公式：负载因子=哈希表已保存节点数 / 哈希表大小，即load_factor = ht[0].used / ht[0].size

扩容

当以下任意一个条件被满足时，Redis会自动对哈希表进行扩容操作：

1. 当Redis没有在进行BGSAVE或BGREWIRITEAOF，且哈希表负载因子大于等于1；
2. 当Redis在进行BGSAVE或BGREWRITEAOF，且哈希表的负载因子大于等于5。

为什么在执行BGSAVE或BGREWRITEAOF命令时，所需的负载因子会更大，也就是为什么扩容操作会更晚进行呢？因为这两个命令都是需要Redis创建子进程来进行的，而大多数操作系统会采用写时复制(Copy-On-Write)来优化子进程的使用效率，提高扩展操作条件的负载因子是为了尽可能地避免子进程存在期间对哈希表进行扩展操作，可以避免不必要的内存写入，最大限度节省内存。

缩容

​ 当负载因子小于0.1时，程序自动开始对哈希表进行缩容操作。

参考

• 《Redis设计与实现》 —— 黄健宏

• Redis定时主动rehash源码:redis.c

• Redis字典源码:dict.c