【Redis】哈希表结构

1、背景

redis中的hashtable（哈希表）是一种高效的键值对存储结构，主要用于实现redis的字典类型，接下来就来讲解一下hashtable（redis版本6.2.18）的底层实现。

2、哈希表

【1】底层结构

hashtable主要包含以下结构体，dict-字典结构：

typedef struct dict {
    dictType *type; //类型特定函数
    void *privdata; //私有数据
    dictht ht[2]; //哈希表数组（两个，用于rehash）
    long rehashidx; //rehash索引，-1表示不在rehash
    int16_t pauserehash; //如果>0代表rehash暂停（<0表示编码错误）
} dict;

dictht-哈希表结构：

typedef struct dictht {
    dictEntry **table; //哈希表数组
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表大小掩码，用于计算索引值 
    unsigned long used; //哈希表已有节点数量
} dictht;

dictEntry-哈希表节点，头节点叫哈希桶：

typedef struct dictEntry {
    void *key; //键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; //值
    struct dictEntry *next; //指向下个哈希表节点，形成链表
} dictEntry;

【2】哈希冲突

在redis的hashtable实现中，哈希冲突发生在两个或多个不同的键（key）被哈希函数映射到同一个哈希桶（bucket）的情况。这种情况是不可避免的，因为：

1、哈希函数的输出空间（哈希值范围）通常小于输入空间（可能的键数量）
2、即使有完美的哈希函数，在实际应用中内存也是有限的

【3】链地址法

redis采用链地址法来处理哈希冲突，链地址法的实现如下：

1、每个哈希桶实际上是一个单向链表的头指针
2、当发生冲突时，新的键值对会被添加到对应桶的链表中
3、查找时需要遍历链表来找到匹配的键

冲突处理流程如下分为三类，插入操作流程如下：

<1>插入操作流程

1、计算键的哈希值
2、通过哈希值确定桶位置
3、将新节点插入到链表头部（时间复杂度O(1)）

<2>查找操作流程

1、计算键的哈希值
2、定位到对应的桶
3、遍历链表查找匹配的键

<3>删除操作流程

1、类似查找过程，找到节点后从链表中移除

【4】传统rehash

链地址法虽然能解决hash冲突，但是当链表越来越长的时候，查询速度也会越来越慢了，毕竟查询时间复杂度为O(n)。所以就需要rehash，rehash是哈希表在扩容或缩容时重新分配所有键值对到新哈希表的过程。传统的一次性rehash方式会一次性将所有键值对从旧表迁移到新表，这会导致：

1、内存占用翻倍（需要同时维护新旧两个表）
2、迁移过程可能阻塞服务（对于大哈希表）
3、响应时间不稳定

【5】渐进式rehash

redis采用渐进式rehash来解决传统rehash问题，核心思想是将rehash过程分摊到多个操作中完成，渐进式rehash的实现机制如下：

<1>使用双表结构：

typedef struct dict {
  	dictht ht[2]; //两个哈希表，ht[0]是主表，h[1]是rehash目标表
 	long rehashidx; //rehash进度索引，-1表示未进行rehash
} dict;

<2>触发条件满足时：

1、分配新的哈希表ht[1]
2、设置rehashidx = 0，开始rehash过程

<3>逐步迁移：

1、每次对字典的增删改查操作时，除了执行指定操作外，还会将ht[0]的rehashidx位置上的所有键值对迁移到ht[1]
2、迁移完成后rehashidx++

<4>完成条件：

1、当ht[0]的所有键值对都迁移到ht[1]后
2、释放ht[0]，将ht[1]设置为新的ht[0]
3、重置rehashidx = -1

渐进性rehash的访问逻辑如下：

<1>查找操作：

1、现在h[0]查找
2、如果没找到且正在rehash，再到ht[1]查找

<2>插入操作：

1、新键值对只插入到ht[1]
2、保证ht[0]只减不增

<3>删除/更新操作

1、同时在两个表中操作

【6】rehash触发条件

redis的哈希表在以下两种情况会触发rehash：

1、扩容条件：当负载因子（哈希表已使用的节点数量/哈希表大小）> 1时，且服务器没有执行RDB快照或AOF重写
2、缩容条件：负载因子 < 0.1时

【7】特性

hashtable的特性如下：