Redis 字典结构细谈

Redis 字典底层基于哈希表实现。

一、哈希表结构 1、dictht

typedef struct dictht {

  dictEntry **table; //哈希表数组,存储具体的键值对元素,对象类型 dictEntry

  unsigned long size; //哈希表容量

  unsigned long sizemask; //哈希表大小掩码,计算索引使用

  unsigned long used; //已使用容量

} dictht

2、示例数据:

 

Redis 字典结构细谈

二、哈希表节点 1、dictEntry

typedef struct dictEntry {

  void *key; //键值对 key

  union{  //键值对 value 三种类型

    void *val;

    uint64_tu64;

    int64_ts64;

  } v;

  struct dictEntry *next;  //下一个节点指针

} dictEntry;

说明:next 为指向下一个节点的指针,是我们熟悉的链表节点结构,单向链表,用于处理键哈希冲突问题。

相同哈希值的键的键值对会以链表的形式存在同一位置。

2、示例数据:

 

Redis 字典结构细谈

三、Redis 字典
1、dict

typedef struct dict{

  dictType *type; //类型特定函数

  void *privdata; //私有数据

  dictht ht[2]; //哈希表数组,类型为dicththt[0]为实际存储数据使用,ht[1] rehash时使用

  int rehashidx; //rehash进度标志,-1 代表当前不在 rehash

} dict

2、示例数据:

 

Redis 字典结构细谈

四、添加元素

向字典中添加元素主要涉及一下几步操作:

1、计算键值对键的哈希值

hashdict->type->hashFunction(key)

使用dictType内部的哈希函数得到键哈希值

2、计算需要放入的位置索引

indexhash&dict->ht[0].sizemask

使用上一步计算得到的哈希值与哈希表的sizemask属性进行与操作得到需要放入的位置索引值

3、键冲突解决

没有完美的哈希函数,哈希冲突往往无法避免,当多个键被所引导同一个位置时,这种现象,我们称之为键冲突。

解决间冲突,Redis 采用链地址法,也即将冲突的键值对组成一条链条放到同一个哈希位置上。上面第二节我们介绍过 dictEntry的结构,其中包含一个指向另一个节点的指针next

这里需要说明的一点是,冲突节点插入时,是插入到链表的头部,这样只需要执行操作一次操作即可,也即时间复杂度为O(1)

如下图:(k2v2)与(k1v1)发生冲突,直接将(k2v2插入到链表头部:

Redis 字典结构细谈

五、rehash

rehash过程是在重新规划哈希表占用空间时发生的。

负载因子 load_factor:已保存节点数量(dict.ht[0].used/ 哈希表容量dict.ht[0].size

负载因子用以表名当前哈希表的使用状态,它需要保持在一个合理的范围,以保障资源的最优利用。通常需要适时的对哈希表进行扩展或者收缩来对负载因子进行维护,而这个过程,我们称之为 rehash

这里涉及到一个问题,就是什么时候需要进行伸缩维护?

1、扩展时机:

当前无bgsavebgrewriteaop操作,load_factor >= 1

当前存在bgsavebgrewriteaop操作,load_factor >= 5

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjywg.html