Redis系列(七):Redis 数据结构之 dict


redis 作为 key value 的数据库,字典是 redis 使用非常多的数据结构之一,本篇文章简单来了解一下 redis 的内部字典的实现

字典的数据结构

redis 的字典的数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dict {

// 类型特定函数
dictType *type;

// 私有函数
void *privatdata;

// 哈希表
dictht ht[2];

// rehash 索引
// 当 rehash 不在进行时,为 -1
int trehashidx;
}

ht属性,一个包含两个项的数组,数组的每一个元素都是 dicth 哈希表,一般情况下,字典只会使用 dict[0] 的哈希表,当进行 rehash 时候,才会需要用到 dicth[1] 的哈希表。

trehashidex 属性,跟 rehash 相关,记录当前 rehash 的索引值。

dictht 的数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictht {

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

// table 大小
int size;

// 计算索引的掩码
int sizemask;

// 已使用的大小
int used
}

每一个的 dictEntry 结构里都存着两个属性,key 和 val,也就是字典的 key 和 value

哈希算法

redis 的 hash 算法相对比较简单。分为两步:

  1. 根据哈希函数计算出 key 的哈希值,得到哈希值

    1
    hash = hashFunc(key);
  2. 根据哈希值和哈希表的掩码进行运算,得到哈希表的索引值

    1
    idx = hash & sizemask;

计算出的索引值即为该 key 和 value 在 table 中的存储位置。

哈希碰撞

使用 hashTable, 那么就必须要解决哈希碰撞。

1
哈希碰撞就是当 key 计算出来的哈希索引的位置上已经存在了一个 key,那么就是发生了哈希碰撞。就是两个 key 都哈希到了同一个哈希索引的位置上

redis 解决哈希碰撞的方法是:链地址法

当发生哈希碰撞时,哈希节点通过 next 指针连接起来构成单向链表。

为了速度考虑,程序总是将新节点添加到表头的位置(时间复杂度为 1),排在其他节点的前面。

ReHash 的原理

随着操作的不断进行,哈希表中保存的 key 会增多获或减少,为了让 hash 表的负载因子维持在一个合理的范围之内,redis 会进行 rehash 的操作。

1
负载因子 = 哈希表已保存节点数量 / 哈希表的大小

当负载因子大于等于 1 会触发哈希表的扩展操作
当负载因子小于等于 0.1 会触发哈希表的收缩操作

rehash 的过程:

  1. 为字典的 ht[1] 分配空间,空间的大小取决于要执行的操作以及哈希表 ht[0] 包含的键值对的大小
  2. 将保存在 ht[0] 上的所有的键 rehash 到 ht[1] 上,rehash 需要重新计算得到索引值。
  3. rehash 完成后,ht[0] 为空,释放 ht[0],将 ht[1] 设置为 ht[0], 并为 ht[1] 创建一个空白的哈希表,为下次 rehash 准备。

渐进式的 rehash

redis 如果只保存了少量的键值对,那么一次 rehash 可以很快完成,但是当健值对很多的时候,一次性全部 rehash 肯定会影响 redis 的性能。所以,trehashidx 的属性派上用场。

当不需要 rehash 的时候,rehashidx = -1,当需要 rehash 的时候,rehashidx = 0;

这时候,当该 hashTable 中需要操作时,除了操作指定的键以外,同时还会将 ht[0] rehashidx 的索引位置的所有的键值对 rehash 到 ht[1] 的 hastTable 中,完成后对 rehashidx + 1。随着操作的不断进行,最终会完成 ht[0] 到 ht[1] 全部 rehash 工作。

渐进式的 rehash 过程中,发生增删改查的操作时的处理:

  1. 增加新的键值对,只会对 ht[1] 的表新增
  2. 查找键值对,先查找 ht[0],没有的话查找 ht[1]
  3. 修改键值对,对 ht[0] 和 ht[1] 都进行修改
  4. 删除键值对,对 ht[0] 和 ht[1] 同时删除

字典的使用场景

字典在 redis 的使用场景比较多。

  1. redis 的 key value 的存储结构
  2. redis 的 hash 存储结构
  3. redis zaset 中根据 memeber 查找 score
    。。。

总结

hashtable 是最常使用的一种数据结构,因为有 1 的时间复杂度,在设计 hashtable 时,可以借鉴 redis 的哈希碰撞和 rehash 的设计。