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 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

排序----堆排序

1300
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch聚合初探——metric篇

Elasticsearch是一款提供检索以及相关度排序的开源框架,同时,也支持对存储的文档进行复杂的统计——聚合。 前言 ES中的聚合被分为两大类:Met...

17310
来自专栏DOTNET

【翻译】MongoDB指南/CRUD操作(四)

【原文地址】https://docs.mongodb.com/manual/ CRUD操作(四) 1 查询方案(Query Plans) MongoDB 查询优...

26910
来自专栏Clive的技术分享

MySQL索引原理及使用一、磁盘IO二、索引数据结构三、优化sql语句执行效率的方法四、建索引的几大原则

一、磁盘IO 磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读...

4496
来自专栏Jaycekon

深入浅出Redis-redis底层数据结构(下)

概述: 学习使用Redis,其实并不需要去研究其底层数据的实现。我们只需要了解他有哪些常用的数据类型,然后熟练使用,就可以很好的掌握Redis 这个工具了。但...

2816
来自专栏desperate633

深入理解SortSet类型的使用及应用Redis 有序集合(sorted set)SortSet的应用场景SortSet的常用命令

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

842
来自专栏Web 开发

JavaScript Cookbook 2nd 之 Function

昨晚翻了一下,虽然都是一些旧知识,不过深入下去对照着其他资料一起看,还是能发现一些有意思的地方。

660
来自专栏有困难要上,没有困难创造困难也要上!

Python Socket编程Python Socket编程

2837
来自专栏Java技术栈

一个诡异的“可见性”问题

之前介绍过可见性的特性,最近做测试的时候发现了一个很诡异的问题,下面看看这三个例子。 test1: test1这个例子加了volatile,所以程序正确退出输出...

2726
来自专栏我的博客

Tp3.1.2模型学习

1.模型定义 命名规则是除去表前缀的数据表名称,采用驼峰命名,并且首字母大写,然后加上后缀Model 其中tableName是不包含表前缀的数据表名称,一般用...

3074

扫描关注云+社区