字典呢，可以理解为Java中的HashMap，通过Key取Value操作的时间复杂度为O(1)。

字典的结构：

typedef struct dict {
    // ...
    dictht ht[2]; // hash表
    int trehashidx; // rehash索引，没有进行rehash时，值为-1
} dict;

哈希表结构：

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

哈希表节点结构：

typedef struct dictEntry {
    void *key; // 键
    union {
        void *value;
        uint64_t u64;
        int64_t s64;
    } v; // 值
    struct dictEntry *next; // 下一个节点，单向链表
} dictEntry;

Hash算法

// 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
// 使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;

Hash冲突的解决

Redis使用链地址法来解决hash冲突问题，当两个key经过hash后，命中同一个索引时，会自动形成一个链表，总是在表头添加新元素。

rehash

翻译为“再散列”，当存储的键值对太多或者太少时会触发，根据负载因子决定的。负载因子的计算公式如下：

load_factor = ht[0].used / ht[0].size => 负载因子 = 哈希表中已有的键值对数量 / 哈希表的大小

哈希表的扩容策略

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

哈希表的收缩策略

哈希表的负载因子小于0.1时，自动开始对哈希表的收缩操作

无论是扩容还是收缩，都需要执行rehash操作。

扩展操作：根据原hash表已使用的空间，扩大一倍，创建一个新的hash表，用于rehash操作

收缩操作：根据原hash表已使用的空间，缩小一倍，创建一个新的hash表，用于rehash操作

所以为什么是ht[2]，另一个hash表就是给rehash操作准备的，默认指向null

所谓的rehash操作，就是对原有hash表中的所有键再次使用hash算法，计算出新的存储索引。

渐进式rehash

通过上文，我们也只知道，rehash操作需要完成对原有hash表的整体迁移操作。如果键值对的数量太多，一次性迁移的成本太高，会导致后续命令的长时间等待。所以，Redis采用了一种渐进式rehash的策略。

trehashidx的值就代表当前需要进行rehash的哈希表索引，当为-1时，表示不执行rehash的操作。

当值大于等于0时，执行rehash操作 => 遍历当前索引对应的dictEntry链表，将其全部rehash到新的hash表中。

rehash完毕后，trehashidx++。

要触发rehash，除了负载因子，还有就是客户端要访问对应的字典。（可以理解为这是一种被动的出发方式）

随着时间的推移，rehash的工作就会逐渐完成。

改变指针，将ht[0]指向h[1]，h[1]指向null

rehash操作执行期间的一些细节

查询、更新、删除操作会同时在两个hash表中进行，即ht[0]和ht[1]。

键值对的新增操作，只会在新创建的hash表中执行。

---

2024.10.21

writeBy kaiven