陈川的个人专栏
上一篇

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

广告
选中文字可对指定文章内容进行评论啦,→和←可快速切换按钮,绿色背景文字可以点击查看评论额。
大纲

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

解决Hash冲突方法

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

  1. 链表法
  2. 开放寻址法

链表法

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

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

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

开放寻址法

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

  • 线性探测:插入数据时,如果数据计算的数组下标已经被占用,就从当前位置开始,依次往后查找,直到找到为止
  • 二次探测:线性探测步长固定为1,而二次探测依次步长,是二的2次方,即hash(key)+0hash(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节点,从而形成一个链表。

完整结构如图:

 

版权声明:著作权归作者所有。

X

欢迎加群学习交流

联系我们