Redis 字典

发表于 | 分类于
本篇文章将介绍：dictht、dictEntry 的结构以及存储字段的解释，redis 字典使用的哈希算法，redis 如何解决哈希冲突

世界以痛吻我，我仍报之以歌。

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

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

table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对。size 属性记录了哈希表的大小，也即是 table 数组的大小，而 used 属性则记录了哈希表目前已有节点（键值对）的数量。sizemask 属性的值总是等于 size-1，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

哈希表节点

哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对：

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef struct dictEntry {
    // 健
    void *key;
    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

哈希算法

如果我们要将一个键值对 k0 和 v0 添加到字典里面，那么程序会先使用语句：

1
 
hash = dict -> type -> hashFunction(k0);

计算键 k0 的哈希值。假设计算得出的哈希值为8，那么程序会继续使用语句：

1
 
index = hash & dict -> ht[0].sizemask = 8 & 3 = 0;

计算出键 k0 的索引值0，这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引0位置上。

Redis 使用 MurmurHash2 算法来计算键的哈希值。这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

解决哈希冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。

Redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。

因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。