Redis内部数据结构——词典哈希表dictht

这一节主要讨论”如何解决Hash碰撞“的问题，去理解Redis的哈希表dictht。

解决Hash冲突方法

我们知道，使用哈希函数对输入计算出的哈希值是相同，称为哈希碰撞。发生哈希碰撞通常有以下两种做法处理冲突的存储：

链表法
开放寻址法

链表法

链表法是Redis选择解决hash冲突的方法，数据结构为：数组 + 链表。

数组的每个位置，称之为桶（bucket）或槽(slot)。当计算的hash值在同一个槽位时，即发生哈希碰撞，后面的元素就依次添加到链表中。

查找过程就是先查到数组的槽位，再从链表中查找需要的key。

Redis内部数据结构——词典哈希表dictht

开放寻址法

开发地址法中，若发生哈希冲突，数据项不能直接存放在计算出来的数组下标时，就要寻找其他的位置。常用有三种方法：线性探测、二次探测以及再哈希法。

线性探测：插入数据时，如果数据计算的数组下标已经被占用，就从当前位置开始，依次往后查找，直到找到为止
二次探测：线性探测步长固定为1，而二次探测依次步长，是二的2次方，即hash(key)+0，hash(key)+1^2,hash(key)+2^2…
再哈希法：当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突。

Redis Hash Table的实现dictht

哈希表在dict/dictht.h文件中定义：

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

table：哈希表数组，数组中的每个元素都是一个链表。
size：哈希表数组的大小。
sizemask：是哈希表数组大小的掩码，取值为size-1。
used：哈希表已有节点的数量，即dictEntry的总数。

计算下标公示hash(key) & sizemask，如图：

表节点定义dict/dictEntry：

ypedef struct dictEntry {
    // 键
    void *key;
    // 值，使用union以适应不同类型的值
    union {
        void *val; // 整数与浮点数直接存储，其它类型使用引用
        uint64_t u64; // 无符号整数
        int64_t s64;  // 有符号整数
        double d;  // 浮点数
    } v;
    // 指向下一个节点
    struct dictEntry *next;
} dictEntry;

dictEntry是哈希表的节点，键值对数据保存在dictEntry节点。

key：指针指向哈希表中的键。
v：用于保存字典的值，是一个union类型，u64和s64可直接保存64位的整数值。如果值不是整数，则通过指针val来指向数据所在内存。
next指向下一个dictEntry节点，从而形成一个链表。

完整结构如图：

秒客网

Redis内部数据结构——词典哈希表dictht

解决Hash冲突方法

链表法

开放寻址法

Redis Hash Table的实现dictht

相关文章