专栏首页用户7890857的专栏3、Redis数据结构——字典-hashtable
原创

3、Redis数据结构——字典-hashtable

字典简介:

字典,又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对的抽象数据结构。

字典是一种用于保存键值对的抽象数据结构。由于C没有内置这种数据结构,Redis构建自己的字典实现。

Redis的数据库就是使用字典来作为底层实现的。除了用来实现数据库之外,字典还是哈希键的底层实现之一,当一个哈希键包含的键值对比较多,又或者键值对中的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现。

1、字典实现

Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。

1.1、哈希表定义

typedef struct dictht {     
//哈希表数组     
dictEntry **table;    
//哈希表大小    
unsigned long size;    
 //哈希表大小掩码,总是等于size-1     
unsigned long sizemask;    
//该哈希表已有节点数量    
unsigned long used;
} 

table属性是一个数组,数组中的每个元素都是一个指向dict.h/ dictEntry结构的指针,每个dictEntry结果保存着一个键值对。size属性记录了哈希表的大小,也即是table数组的大小,而used属性则记录了哈希表目前已有节点(键值对)的数量。sizemask属性的值总是等于size-1,这个属性和哈希值一起决定了一个键应该被放到table数组的哪个索引上面。下图是一个空哈希表。

1.2、哈希表节点

typedef struct dictEntry {     
void *key;    
 union{     
     void *val;      
     uint64_t u64;         
     int64_t s64;     
 } v;     
 //指向下个哈希表节点,形成链表----解决哈希冲突   
struct dictEntry *next; 
} dictEntry; 

key属性保存着键值对中的键而v属性保存着键值对中的值,其中键值对的值可以是一个指针,或者是一个uint64整数或者是一个int64_t整数。

next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一起,以此来解决键冲突(collision)的问题。

下图展示了将两个索引值相同的键k1和k0连接在一起。

1.3、字典

typedef struct dict {     
//类型特定函数     
dictType *type;     
//私有数据     
void *privata;     
//哈希表     
dictht ht[2];     
//rehash索引,当rehash不进行时,为-1     
int rehashidx; 
} 

type属性和privdata属性是针对不同类型的键值对,为创建多态字典而设置的

type:一个指向ditcType结构的指针,每个ditcType结构保存了一簇用于操作特定类型键值对的函数,redis会为用途不同的字典设置不同的类型特定函数。

privata:保存了需要传给那些类型特定函数的的可选参数。

ht属性包含两个项的数组,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0]进行rehash时使用

除了ht[1]之外,另一个和rehash有关的属性就是rehashidx,它记录了rehash目前的进度,如果目前没有在进行rehash,那么它的值-1。

下图是一个普通状态下的字典

上图是一个没有处在 rehash 状态下的字典。可以看到,字典持有两张哈希表,其中一个的值为 null, 另外一个哈希表的 size=4, 其中两个位置上已经存放了具体的键值对,而且没有发生 hash 冲突。

2、哈希算法

哈希表添加一个元素首先需要计算当前键值的 hash 值,之后根据 hash 值来定位即将被放入的槽。由于 hash 值可能冲突,因此 hash 算法的选择尤其重要,要将 key 值打散的足够均匀。

在 Redis 5.0 以及 4.0 版本,都使用了 siphash 哈希算法。siphash 可以在输入的 key 值很小的情况下,产生随机性比较好的输出。

在 Redis 3.2, 3.0 以及 2.8 版本,使用 Murmurhash2 哈希算法,Murmurhash 可以在输入值是有规律时,也能给出比较好的随机分布。

3、解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时,我们称这些键发生了冲突。

Redis的哈希表使用链地址法来解决键冲突,每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

因为dictEntey节点组成的链表没有指向链表表尾的指针,所以为了速度考虑,程序总是将新节点添加到链表的表头位置(复杂度为0(1)),排在其他已有节点的前面。下图为k2加入到哈希表中出现冲突,加入到链表头之后的情况。

4、扩展与缩容

随着操作不断进行,哈希表保存的键值会逐渐增多或者减少,为了让哈希表负载因子维持在一个合理范围之内,当哈希表保存的键值数量太多或者太少时,就会对哈希表进行相应的扩展或者收缩。

既然想要进行扩展或收缩,那么就需要描述当前表的填充程度,这就有了负载因子概念。计算公式:负载因子=哈希表已保存节点数量/哈希表大小 【load_factor = ht[0].used / ht[0].size】

自动执行扩展操作条件:

  1. 服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令,并且负载因子大于等于1进行扩容。
  2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且负载因子大于等于5。
  3. 当哈希表负载因子小于0.1时,程序自动开始对哈希表执行收缩操作。

扩展和收缩通过执行rehash(重新散列)操作来执行。步骤如下:

1)为字典ht[1]哈希表分配空间,空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量:

  • 如果扩展,ht[1]大小等于第一个大于等于ht[0].used*2的n次幂(2的n次方幂)。
  • 如果收缩,ht[1]大小等于ht[0].used的2的n次幂(2的n次方幂)。

2)将ht[0]中的所有键值对rehash到ht[1]上面;rehash指的是重新计算键的哈希值和索引值,然后放到指定位置上。

3)当ht[0]所有的键值对都迁移过去后,将ht[1]设置为ht[0],并为ht[1]创建新的空白哈希表,为下一次rehash做准备。

举个例子,如下图

1、ht[0].used当前的值为4,4*2=8,而8(2^3)恰好是第一个大于等于4的2的n次方,所以程序会将ht[1]

哈希表的大小设置为8。下图展示了ht[1]分配空间之后,字典的样子。

2、 将ht[0]包含的四个键值对都rehash到ht[1],如下图

3、 释放ht[0],并将ht[1]设置为ht[0],然后为ht[1]分配一个空白哈希表,如下图,至此,哈希表的扩展操作执行完毕。

5、渐进式rehash

rehash操作并不是一次性、集中式完成的,而是分多次、渐进式完成的。如果在数据量很大的情况下,一次性操作可能会导致服务器一段时间内停止服务。

因此,为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1],而是分多次、渐进式的进行。

以下是哈希表渐进式rehash的详细步骤:

1 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。

2 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始。

3 在rehash进行期间,每次对字典执行添加、删除、查找或者更新时,程序除了执行指定的操作以外,还顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后,程序将将rehashidx属性的值增一。

4 随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被都会被rerhash至ht[1],这时程序程序将rehashidx属性的值设为-1,表示rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式rehash而带来的庞大计算量。

6、渐进式rehash执行期间的哈希表操作

进行渐进式rehash的过程中,字典同时使用ht[0]和ht[1]两个哈希表,所以在渐进式rehash进行期间,字典的删除、查找、更新等操作会在两个哈希表上进行。另外,新添加到字典的键值对一律保存到ht[1]里面,而ht[0]则不再进行任何添加操作。这一措施保证了ht[0]包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。。

7、总结

Redis 字典数据结构是面试中高频考题【另外一个是跳表数据结构】。可以多看多思考,彻底攻克它。

Redis 字典中,用 table[2] 的数组保存着两张 hash 表,正常情况下只使用其中一张,在 rehash 的时候使用另外一张表。

Redis 为了提高自己的性能,rehash 过程不是一次性完成的,而是使用了渐进式 hash 的策略,逐步的将原有元素 rehash 到新的哈希表中,直到完成。

最后,欢迎关注我的个人公众号 CodingCode,会不定期更新学习笔记。也欢迎直接公众号私信,一定知无不言,言无不尽。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis数据结构-字典

    字典(dictionary), 又名映射(map)或关联数组(associative array)是一种抽象数据结构, 由一集键值对(key-value pai...

    程序员酷森
  • Redis03-Redis的数据结构之Redis的字典数据结构

    周末被社会的皮鞭狠狠的抽打了几下。人微言轻,为生计奔波,劳碌一生。个人牢骚。今天接着来学习Redis的第三篇,字典的数据结构。字典的数据结构其实完全可以类比Ja...

    码农飞哥
  • Redis五种数据类型及应用场景

    String: 一般做一些复杂的计数功能的缓存 List: 做简单的消息队列的功能 Hash: 单点登录 Set: 做全局去重的功能 SortedSet: 做排...

    HUC思梦
  • 《闲扯Redis九》Redis五种数据类型之Set型

    Redis 中的 Set 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • 细品Redis高性能数据结构之hash对象

    上一节讲Redis的高性能字符串结构SDS,今天我们来看一下redis的hash对象。

    居士
  • Redis学习系列四Hash(字典)

    Redis中的Hash字典相当于C#中的Hashtable,是一种无序字典,内存存储了很对的键值对,实现上和Hashtable一样,都是"数组+链表"二维结构,...

    郑小超.
  • 《闲扯Redis六》Redis五种数据类型之Hash型

    Redis 中的 hash 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • 《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

    《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理 (原创内容,转载请注明来源,谢谢) 一、集合 集合的编码方式有intset和has...

    用户1327360
  • Redis 基本数据结构三:哈希

    几乎所有的编程语言都提供了哈希(hash)类型,例如 Java 中的 Map,python 中的字典,在Redis中,哈希类型是指键的值本身又是一个键值对结构,...

    CoderJed
  • Redis 的底层数据结构(字典)

    字典相对于数组,链表来说,是一种较高层次的数据结构,像我们的汉语字典一样,可以通过拼音或偏旁唯一确定一个汉字,在程序里我们管每一个映射关系叫做一个键值对,很多个...

    Single
  • 老板们都应该学一学 Redis,它能管理上亿对象,你们呢?

    我们知道一个大型的公司往往都具有复杂的组织结构,成百上千号员工,要做到大而不乱,就必须依靠合理的组织结构来优化内部的交流成本。Redis 内部也有组织结构,不同...

    老钱
  • [Redis] redis的设计与实现-对象系统

    1.redis并没有直接使用前面的数据结构实现键值对数据库,而是基于数据结构创建了一个对象系统,字符串对象/列表对象/哈希对象/集合对象/有序集合对象都用到了至...

    陶士涵
  • redis学习笔记--哈希

    type:表示对象类型,对象类型可以为以下任意一种:字符串对象、列表对象、哈希对象、集合对象、有序集合对象。这也是redis中5种数据类型。

    吃完橙子了哈
  • Redis源码分析(三)——Redis数据结构-字典

    1. 数据结构 ? 1.1 哈希表 typedef struct dictht{ dictEntry **table; unsigned long s...

    大闲人柴毛毛
  • Redis 数据结构-字典源码分析

    字典这种数据结构并不是 Redis 那几种基本数据结构,但是 hash , sets 和 sorted sets 这几种数据结构在底层都是使用字典来实现的(并不...

    Java技术编程
  • Redis系列(九)底层数据结构之五种基础数据类型的实现

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • 一文读懂 Redis 常见对象类型的底层数据结构

    Redis 是一个基于内存中的数据结构存储系统,可以用作数据库、缓存和消息中间件。Redis 支持五种常见对象类型:字符串(String)、哈希(Hash)、列...

    肉眼品世界
  • Redis 选择hash还是string 存储数据?

    在stackoverflow 看到一个问题,Redis strings vs Redis hashes to represent JSON: efficienc...

    goodspeed
  • Redis专题(2):Redis数据结构底层探秘

    上篇文章 Redis闲谈(1):构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制,相信大家对redis有了初步的认识。互联网的很多应用场景都有...

    宜信技术学院

扫码关注云+社区

领取腾讯云代金券