乐趣区

关于redis:Redis数据结构-字典

jiezi

字典

字典，即键值对的形象数据结构。

因为 Redis 应用的 C 语言没有内置这种数据结构，因而 Redis 构建了本人的字典实现，和其它高级编程语言个性一样，字典中的每个键都是举世无双的。

字典在 Redis 中的利用相当宽泛，比方 Redis 的 数据库 就是应用字典来作为底层实现的。

除此之外，字典还是 哈希键 的底层实现之一，当一个哈希键蕴含的键值对比拟多，又或者键值对中的元素都比拟长的字符串时，Redis 就会应用字典作为哈希键的底层实现。

字典的实现

Redis 的字典应用哈希表作为底层实现，一个哈希表外面能够有多个哈希表节点，而每个哈希表节点就保留了字典中的一个键值对。

哈希表

typedef struct dictht {
    dictEntity **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
}
  • table : 是一个数组，数组中的每个元素都是一个指向 dictEntity 构造的指针，每个 dictEntity 构造保留着一个键值对。
  • size : 记录了哈希表的大小，即 table 数组的大小
  • sizemask : 哈希表大小掩码，用于计算索引值，总是等于 size – 1，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引下面
  • used : 记录了哈希表目前已有节点（键值对）的数量

哈希表节点

typedef struct dictEntity {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntity *next;
} dictEntity;
  • key : 保留着键值对中的键
  • v : 保留着键值对中的值，其中键值对的值能够是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 属性
  • next : 指向另一个哈希表节点的指针，这个指针能够将多个哈希值雷同的键值对连贯在一起，以此来解决键抵触的问题

字典

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int trehashidx;
} dict;

  • type : 属性是一个指向 dictType 构造的指针，每个 dictType 构造保留了一簇用于操作特定类型键值对的函数，Redis 会为用处不同的字典设置不同的类型特定函数

    typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction) (const void *key);
    // 复制键的函数
    void *(*keyDup) (void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup) (void *privdata, const void *obj);
    // 比照键的函数
    int (*keyCompare) (void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor) (void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor) (void *privdata, void *obj);
} dictType;
  • privdata : 保留了须要传给那些类型特定函数的可选参数
  • h2 : 是一个蕴含两个项的数组，数组中的每个项都是一个哈希表，个别状况下，字典只应用 ht[0] 哈希表，h[1] 哈希表只会在对 h[0] 哈希表进行 rehash 时应用
  • trehashidx : 记录了 rehash 目前的进度，当 rehash 不在进行时，值为 -1

哈希算法

当要将一个新的键值对增加到字典外面时，程序须要先依据键值对的键计算出哈希值和索引值，而后再依据索引值，将蕴含新键值对的哈希表节点放到哈希数组的指定索引下面。

Redis 别离应用 hashFunction 来计算哈希值，应用哈希表的 sizemask 和哈希值，来计算索引值。

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 应用 MurmurHash 算法来计算键的哈希值。

MurmurHash 算法的长处在于，即便输出的键是有法则的，算法仍能给出一个很好的随机散布性，并且算法的计算速度也十分快。

解决键抵触

当 有两个或以上数量的键被调配到了哈希表数组的同一索引下面 时，称为键产生了抵触。

Redis 的哈希表应用 链地址法 来解决键抵触，每个哈希表节点都有一个 next 指针，多个哈希表节点能够用 next 指针形成一个单向链表，被调配到同一个索引上的多个节点能够用这个单向链表连接起来，这就解决了键抵触的问题。

因为哈希表节点（dictEntity）组成的链表没有指向链表表尾的指针，所以为了速度思考，程序总是将新节点增加到链表的表头地位（工夫复杂度为 O(1)）。

rehash

随着操作的一直执行，哈希表保留的键值对会逐步地增多或者缩小，为了让哈希表的负载因子（load factor）维持在一个正当的范畴之内，当哈希表保留的键值对数量太多或者太少时，程序须要对哈希表的大小进行相应的扩大或者膨胀。

扩大和膨胀哈希表的工作能够通过执行 rehash（从新散列）操作来实现，步骤如下：

  1. 为字典的 ht[1] 哈希表调配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 以后蕴含的键值对数量，即 ht[0].used 属性的值。

    1. 如果执行的是扩大操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2n
    2. 如果执行的是膨胀操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2n
  2. 将保留在 ht[0] 中的所有键值对 rehash 到 ht[1] 下面，具体操作是从新计算键的哈希值和索引值，而后将键值对搁置到 ht[1] 哈希表的指定地位上
  3. 当 ht[0] 蕴含的所有键值对都迁徙到了 ht[1] 之后（此时 ht[0] 变为空表），开释 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做筹备

rehash 的机会

当以下条件中的任意一个被满足时，程序会主动开始对哈希表进行扩大操作

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5

当哈希表的负载因子小于 0.1 时，程序主动开始对哈希表执行膨胀操作。

其中，哈希表的负载因子能够通过公式：

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

即：负载因子 = 哈希表已保留节点数量 / 哈希表大小

依据 BGSAVE 或 BGREWRITEAOF 命令是否在执行，而采纳不同的负载因子，这时因为在执行 BGSAVE 或 BGREWRITEAOF 命令的过程中，Redis 须要创立以后服务器进行的子过程，而大多数操作系统都采纳写时复制技术来优化子过程的应用效率，所以在子过程存在期间，服务器会进步执行拓展操作所需的负载因子，从而尽可能地防止在子过程存在期间进行哈希表拓展操作，者能够防止不必要的内存写入，最大限度地节约内存。

渐进式 rehash

在进行 rehash 操作时，须要将 ht[0] 所有键值对 rehash 到 ht[1] 外面，如果 ht[0] 外面保留了特地多的键值对时，这个操作可能会导致服务器在一段时间内进行服务。

所以，为了解决这个问题，Redis 采纳分屡次、渐进式地实现 rehash 操作

以下是哈希表渐进式 rehash 的具体步骤：

  1. 为 ht[1] 调配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；
  2. 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，示意 rehash 工作正式开始；
  3. 在 rehash 进行时，每次对字典进行增加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作实现之后，程序将 rehashidx 属性的值增一；
  4. 随着字典操作的一直执行，最终在某个工夫点上，ht[0] 的所有键值对都会被 rehash 到 ht[1]，这时程序将 rehashidx 属性的值设为 -1，示意 rehash 操作已实现。

渐进式 rehash 的益处在于它采取分而治之的形式，将 rehash 键值对所需的计算工作均摊到对字典的每个增加、删除、查找和更新操作上，从而防止了集中式 rehash 而带来的宏大计算量

同时，也会带来一个问题，如何确定要操作的值在 ht[0] 和 ht[1]？

Redis 在删除、查找、更新等操作时，会先在 ht[0] 外面进行查找，如果没有找到，会再到 ht[1] 中进行查找；在新增操作时，一律被保留到 ht[1] 外面。这样是，即保障了 ht[0] 蕴含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表

退出移动版