dict

Dict 字典，哈希表，是一种保存键值对的数据结构。哈希表中的每个键都是独一无二的，程序可以在哈希表中根据 key 查找与之关联的 value，或者通过 key 来更新 value，又或者根据 key 来删除整个 kv 键值对。

哈希表的优势在于它查询的时间复杂度是 O(1)，靠的就是 hash 函数，能够快速定位数据在表中的位置，其次，哈希表实际上是数组，所以可以通过索引值快速查找数据。然而，由于哈希表的大小是有限的，而数据是在不断增多的，随之而来的风险就是哈希冲突，Redis 通过「链地址法」来解决哈希冲突。

哈希表结构

「哈希表结构」

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

「哈希表节点结构」

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    void *val;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

Redis 是如何解决哈希冲突的？

哈希冲突：当有两个以上数量的 key 被分配到了哈希表中同一个哈希桶上时，就称这些 key 发生了冲突。

Redis 采用了「链地址法」来解决哈希冲突的。实现的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个哈希桶上的多个节点可以使用单向链表连接起来，这样就解决了哈希冲突。

但是，链地址法的局限性也是很明显的，随着链表长度的增加，在查找这一位置上数据的耗时就会增加，链表查询的时间复杂度是 O(n)。Redis 是通过 rehash 的方式，对哈希表的大小进行扩展解决这一问题的。

rehash

Redis 为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

渐进式 rehash 步骤：

给「哈希表 2」分配空间；
在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会按顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」上；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作；
互换两个哈希表的引用关系。

「渐进式 rehash」触发条件

rehash 的触发条件跟负载因子（load factor）有关系，负载因子 = 哈希表已经保存的节点数量 / 哈希表大小。

触发 rehash 操作的条件，主要有两个：

服务器目前没有在执行 bgsave 或者 bgrewriteaof 命令，并且哈希表的负载因子大于等于 1；
哈希表的负载因子大于等于 5 时，说明哈希冲突已经非常严重了，此时不管有没在执行 RDB 快照或者 AOF 重写，都会强制进行 rehash 操作。

此外，当哈希表的负载因子小于 0.1 时，哈希表会进行缩容操作。

youyichannel

Redis Dict

dict

哈希表结构

Redis 是如何解决哈希冲突的？

rehash