[redis] hashmap数据结构

2022-08-26 16:45:53 浏览数 (1)

大家好,又见面了,我是你们的朋友全栈君。

一、描述

redis的其中一个数据类型为hashmap,即散列表

正常实现hashmap:

1.分配固定大小的桶,大小为n

2.计算key的hash值,并且与n取模,得到在桶的索引位置index

3.根据2中计算的index,然后存放在对应的桶中

4.当遇到碰撞情况,则会通过链表来解决碰撞问题

二、redis中数据结构定义

struct dictht:为hash table的实际实现结构

struct dict:为hash table的外层封装,主要一个作用是当当前使用dictht需要进行rehash的时候,其会创建新的dictht,并且会在词请求的时候,完成一部分的搬运工作

struct dictEntry:为每个桶,其中的next为解决冲突的链表

三、rehash:

redis的散列表和正常的散列表实现没有太大区别,唯一的区别是在rehash-即需要重新扩容的情况有所区别

正如我们所知,redis是单进程单线程模式,那么对于rehash如果一次性完成数据的搬运的,在数据量大的时候,会是

很耗时的操作,因此redis并不是一次性搬运完所有的数据,而是在每次请求的时候,都会触发搬运工作,

但是搬运的数据都是一小部分而已。

1.lazy rehash,每次操作dict的时候,会搬运一个slot到新的hashmap

2.active rehash,每过一段时间便会进行数据的搬运

四、小点:

在使用hashmap的时候,并不是说每次redis都会直接用散列表的方式来存储数据,因此在单独使用key-value,value作为hashmap使用的时候,

很可能只是用于存放简单而且少量的数据,因此处于对内存消耗和性能等综合考量,在一开始redis会通过ziplist(压缩双向链表来存储数据)相关链接。

而控制什么时候会采用hashmap来存储,可以通过参数来控制:

hash-max-ziplist-entries 512(ziplist最大存储entry的数量)

hash-max-ziplist-value 64(ziplist最大一个entry存储的字节数)

凡是超过这两个限制,都会讲ziplist转换为hashmap

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/144718.html原文链接:https://javaforall.cn

0 人点赞