My-Notes

Search

SearchSearch

017.哈希表

Sep 02, 2024, 5 min read

哈希表是一种保存键值对（key-value）的数据结构，以 key 为索引，每个 key 都是独一无二的（不可重复），且是无序的

优点在于，能以 O(1) 的时间复杂度快速通过 key 索引数据。怎么做到的？

  1. 哈希表实际上是一个数组，数组中每一个元素就是一个哈希桶
  2. 当一个键值对的 key 经过 Hash 函数计算后得到哈希值，(哈希值 % 哈希表大小) 就是其哈希表（数组）索引，也就是第几个哈希桶
  3. 当不同的 key 得到相同的索引，称为哈希冲突。Redis 采用「链式哈希」来解决哈希冲突：具有相同索引的数据串成一个链表

哈希表结构设计

// 哈希表
typedef struct dictht {
    dictEntry **table; // 哈希表数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码，用于计算索引值
    unsigned long used; // 该哈希表已有的节点数量
} dictht;
// 哈希表节点
typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 指向下一个哈希表节点，形成链表
} dictEntry;

rehash

随着链表长度的增加，查询这一索引上数据的耗时就会增加，因为链表的查询时间复杂度是 O(n)

要想解决这一问题，就需要进行 rehash，就是对哈希表的大小进行扩展

Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表，使用双缓存技术进行 rehash：

typedef struct dict {
    ...
    dictht ht[2]; // 两个 Hash 表，交替使用，用于 rehash 操作
    ...
} dict;

正常阶段下，插入的数据都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间

随着数据逐步增多，触发了 rehash 操作，这个过程分为 3 步：

  1. 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大一倍
  2. 将「哈希表 1」的数据迁移到「哈希表 2」 中
  3. 迁移完成后，「哈希表 1」的空间被释放，并把「哈希表 2」设置为「哈希表 1」，为下次 rehash 做准备

这个过程看起来简单，但其实第二步很有问题：如果「哈希表 1」的数据量非常大，那么在迁移至「哈希表 2」时，会涉及大量的数据拷贝，可能会对 Redis 造成阻塞，无法服务其他请求

渐进式 rehash

为了避免这种情况，Redis 采用了渐进式 rehash，就是将数据的迁移分成多次，而不是一次性完成

渐进式 rehash 步骤如下：

  1. 给「哈希表 2」分配空间
  2. 在 rehash 进行期间，每次哈希表元素进行增删改查时，除了执行对应操作外，还会顺序将「哈希表 1」中索引位置上的所有 key-value 迁移到「哈希表 2」上
  3. 随着操作越多，最终在某个时间点会把「哈希表 1」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash

在渐进式 rehash 进行期间：

  • 哈希表元素的增删改查都会在这两个哈希表进行，如：查找时，先在「哈希表 1」找，没找到就继续到「哈希表 2」中找
  • 新增一个 key-value 时，会被保存到「哈希表 2」中，而「哈希表 1」不会进行任何添加操作，保证了「哈希表 1」的 key-value 数量只会减少，直到变成空表

rehash 触发条件

负载因子（load factor）= 哈希表已保存节点数量 / 哈希表大小

触发 rehash 的条件：

  • 当负载因子大于等于 1，且 Redis 没有在执行 bgsave 或 bgrewiteaof 命令，也就是没有执行 RDB 快照或 AOF 重写时，进行 rehash
  • 当负载因子大于等于 5，此时说明哈希冲突非常严重，不管有没有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash

Graph View

Backlinks