Redis数据结构-字典

一、概述

redis字典的数据结构主要涉及三个结构体,分别为dict、dictht和dictEntry。

二、数据结构

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点
    struct dictEntry *next;
} dictEntry;
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引
    // 当rehash不再进行时,值为-1
    int rehashidx;
} dict;

三、哈希算法

Redis计算哈希值和索引值的方法如下:

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

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

其中dict的type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定数据类型的函数

四、解决键冲突

dictEntry结构的next指针可以看出,redis的字典采用链地址法解决哈希冲突。

注意当发生哈希冲突时,总是将新节点添加到表头

五、rehash

1.目的

随着操作的进行,哈希表保存的键值对会逐渐增多会减少,为了让哈希的负载因子维持在一个合理的范围内,程序需要对哈希表的大小进行相应的扩展或收缩。

负载因子计算公式:

load_factor = ht[0].used / ht[0].size

2.步骤

  1. 为字典的ht[1]分配空间,分配空间的大小取决与做什么操作及ht[0]当前包含的键值对数量。
    • 扩展操作,ht[1]的大小为第一个大于等于 (ht[0].used * 2)的2^n;
    • 收缩操作,ht[1]的大小为第一个大于等于(ht[0].used)的2^n;
  2. 将保存在ht[0]上的所有键值对rehash到ht[1]上。rehash是指重新计算键的哈希值和索引值,然后将键值对放到ht[1]哈希表指定的位置。
  3. 当ht[0]包含的所有键值对都迁移到ht[1]后,释放ht[0],将ht[1]设置成ht[0],并在ht[1]新创建一个空白的哈希表,为下一次rehash做准备。

渐进式rehash

1.目的

rehash动作不是一次性、集中式地完成的,当哈希表里保存的键值对是四百万、四千万甚至四亿个时,一次性将这些键值对rehash到ht[1],庞大的计算量可能会导致服务器一段时间内停止服务。

2.步骤

在rehash基础上,将步骤2细化

  • (1) 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作开始。
  • (2) 每次rehash工作完成之后,即将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]。rehashidx属性的值+1。
  • (3) 整个rehash操作完成后,即ht[0]上的所有键值对都被rehash至ht[1]。rehashidx的值设为-1

注意rehash过程中的删除、查找、更新将在ht[0]和ht[1]两个哈希表上进行,新增加的键值对一律保存到ht[1]里,保证了ht[0]里的键值对数量只减不增。

发表评论

电子邮件地址不会被公开。 必填项已用*标注