Redis源码分析(三)——Redis数据结构-字典

1. 数据结构

1.1 哈希表

typedef struct dictht{
  dictEntry **table;
  unsigned long size;
  unsigned long sizemask;
  unsigned long used;
} dictht;
  • table:存储节点的数组
  • size:table数组的长度
  • sizemask:size-1,用于在添加节点时计算节点在table中的位置
  • used:节点数量

1.2 哈希表节点

typedef struct dictEntry{
  void *key
  union {
    void *val;
    unit64_t u64;
    int64_t s64;
  }v;
  struct dictEntry *next
} dictEntry;
  • key:节点的key
  • union:节点的value(可以是指针、unit64_t整数、int64_t整数)
  • next:下一个节点的地址

1.3 字典

typedef struct dict {
  dictType *type
  void *privdata
  dictht ht[2]
} dict;
  • type:操作哈希表的各种函数
  • privdata:上述函数所需的入参
  • ht[2]:存储两个哈希表,一个正常使用,另一个在rehash时使用。

2. 哈希算法

  1. 计算哈希值 hash = dict->type->hashFunction(key);
  2. 计算在table数组的位置 index = hash & dict->ht[0].sizemask;
  3. 插入节点 创建新节点,并将其插入到table[index]的第一位。

3. rehash

3.1 何时进行rehash?

当加载因子(load factor)大于1或小于0.1时就要进行rehash。 加载因子计算公式:

load_factor = ht[0].used / ht[0].size

3.2 新哈希表大小的计算公式

当需要进行扩容/缩容的时候,究竟创建多大的哈希表呢?这取决于如下公式:

  • 若要进行扩容,则新的哈希表的大小=第一个大于等于h[0].used*2的2的n次方。
  • 若要进行缩容,则新的哈希表的大小=第一个大于等于h[0].used的2的n次方。

3.3 rehash过程

  1. 创建一个新的哈希表h[1],大小由上述公式计算得出;
  2. 将字典的rehashidx值从-1改为0;
  3. 依次遍历ht[0]上的所有节点,依次转移到ht[1]上去;
  4. 释放ht[0]的内存空间;

3.4 渐进式rehash

  • rehash过程中需要将所有节点迁移到新的哈希表中,如果节点个数很多的情况下,迁移的过程将非常漫长,那么程序将处于停止等待状态。所以事实上,Redis的rehash过程是分多次、分布完成的。
  • 在rehash过程中,每次对哈希表进行增删改查外,还要将ht[0][rehashidx]上的所有节点迁移到ht[1]中,并将rehashidx+1。从而几次操作后,ht[0]上的所有节点均被迁移至ht[1]中,rehash过程完成。
  • 在rehash过程中,对哈希表的添加操作均在ht[1]上完成,ht[0]只减不增。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

一文详解scala泛型及类型限定

今天知识星球球友,微信问浪尖了一个spark源码阅读中的类型限定问题。这个在spark源码很多处出现,所以今天浪尖就整理一下scala类型限定的内容。希望对大家...

772
来自专栏用户2442861的专栏

Java 8系列之重新认识HashMap

作者:美团点评技术团队 链接:https://zhuanlan.zhihu.com/p/21673805 来源:知乎 著作权归作者所有。商业转载请联系作者...

321
来自专栏高爽的专栏

HashMap深度解析(二)

上一篇比较深入的分析了HashMap在put元素时的整体过程,Java Collections Framework中实际操作的都是数组或者链表,而我们通常...

2070
来自专栏Golang语言社区

使用 Go 实现快速排序

快速排序(quick sort)号称是二十世纪最伟大的十大算法之一(The Best of the 20th Century: Editors Name Top...

982
来自专栏全华班

重新认识你认识的Hibernate(二)

Hibernate估计大家已经用过很多年了吧,好多同学说用过Hibernate,不需要你来讲,但再仔细想想,你能告诉我Hibernate是什么吗? 今天带大家重...

3674
来自专栏微信公众号:Java团长

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

471
来自专栏专注研发

poj-1131-(大数)八进制转化成十进制

Fractions in octal (base 8) notation can be expressed exactly in decimal notatio...

731
来自专栏Java进阶架构师

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

762
来自专栏架构师之旅

Java HashMap工作原理及实现(干货)

发生了什么呢?下面是一个大致的结构,希望我们对HashMap的结构有一个感性的认识:

843
来自专栏你不就像风一样

Java核心数据结构(List,Map,Set)使用技巧与优化

JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java...

1103

扫码关注云+社区