首页 > 数据库 >redis字典

redis字典

时间:2023-03-18 19:33:07浏览次数:38  
标签:rehash hash void redis ht 键值 字典

  • 一种保存键值对的抽象数据结构
  • 每个键都是独一无二的,换言之,自带去重。
  • 是redis数据库的底层实现。
  • 是Hash键的底层实现之一,当Hash键包含的键值对过多,或键值对中的元素都是长字符串时,redis就会使用字典作为Hash键的底层实现。

字典的底层实现

内容:字典使用Hash表作为底层实现,每个Hash表里有多个hash节点,每个节点保存键值对。
源码:
hash表结构定义:

typedef struct dictht {
	dictEntry **table; // 哈希节点数组
	unsigned long size; // 哈希表大小
	unsigned long sizemask; // 哈希表大小掩码,用于计算索引值 value = size - 1
	unsigned long used; // 含有节点数量
...	
} dictht;

如图展示了一个size=4的空hash表结构。
![[dictht.png]]


hash表节点的结构定义:

typedef struct dictEntry {
	void *key; // 键
	union {
		void *val;
		uint64_t u64;
		int64_t s64;
	} v; // 值,可以是指针,uint64_t, int64_t整数
	struct dictEntry *next; // 指向下一个hash节点,形成链表
} dictEntry;

如图展示了节点指针的结构:
![[dictEntry.png]]


字典

字典dict操作hash表:

	typedef struct dict {
		dictType *type; // 类型执行函数
		void *private; // 私有数据,作为参数传递给dictType类型特定函数
		dictht ht[2]; // 两个hash表
		int trehashidx; // rehash索引,默认-1.
	} dict;

上述类型执行函数的定义:

typedef struct dictType {
	//计算哈希值的函数
	unsigned int (*hashFunction)(const void *key);
	//复制键的函数
	void *(*keyDup)(void *privdata, const void *key);
	//复制值的函数
	void *(*valDup)(void *privdata, const void *obj);
	//对⽐键的函数
	int (*keyCompare)(void *privdata, const void *key1, const void *key2);
	//销毁键的函数
	void (*keyDestructor)(void *privdata, void *key);
	//销毁值的函数
	void (*valDestructor)(void *privdata, void *obj);
} dictType;

字典中含有两个hash表:dictht ht[2], 一般情况下,只是用ht[0],作为存储键值对的容器,ht[1]是在 rehash 时使用的。
最后一个参数:int trehashidx 表示rehash的进度,没有rehash进行时,默认为0;

Hash算法

键值对存储在ht[0],或ht[1]上时,会计算键的 哈希值 和 索引值 , 随后根据索引值将键值对存放到hash表的对应位置。
计算方法如下:
hash = dict -> type -> hashFunction(key) 求得hash值
index = hash & dict -> ht[x].sizemask 求得索引值

键冲突:当多个键值对求得索引值相同时,这些键值对就会被存储到相同位置,这是先来的节点就会用next指针指向下一个节点,构成单向链表,解决键冲突。
![[Pasted image 20230318183704.png]]

rehash

触发条件:哈希表的键值对在增多或减少的过程中,哈希表的负载因子不在正常范围,就会触发哈希表的扩容和收缩,该过程使用rehash操作完成。

扩展条件:

  • 服务器没有执行BGSAVE或BGREWRITEOF命令时,load_factor ≥ 1
  • 服务器正在执行BGSAVE或BGREWRITEOF命令时,load_factor ≥ 5
    收缩条件:
  • load_factor ≤ 0.1

负载因子计算:load_factor = ht[0].used / ht[0].size

步骤:

  • 如果执行扩展操作,ht[1]的大小为第一个使 2 ^ n ≥ ht[0].used * 2 的整数n的 2^n。
  • 如果执行收缩操作,ht[1]的大小为第一个使2 ^ n ≥ ht[0].used 的整数n的2 ^ n。
  • 将ht[0]上的键值对rehash(重新计算索引值)后转移到ht[1]上。
  • 所有节点迁移完毕后,释放ht[0].

优化:当hash表存储的巨量键值对,一次性rehash带来的巨大计算量必然会导致性能降低,所以服务器采用分多次、渐进式地将键值对转移。

渐进rehash

  • 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  • 在字典中维持⼀个索引计数器变量rehashidx,并将它的值设置为0,表⽰rehash⼯作正式开始。
  • 在rehash进⾏期间,每次对字典执⾏添加、删除、查找或者更新操作时,程序除了执⾏指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash⼯作完成之后,程序将rehashidx属性的值增⼀。
  • 随着字典操作的不断执⾏,最终在某个时间点上,ht[0]的所有键值对都会被rehash⾄ht[1],这时程序将rehashidx属性的值设为-1,表⽰rehash操作已完成。
    总而言之:渐进式rehash就是在对redis数据库操作时,维持一个rehashidx表示ht[0]上该转移的键值对的索引,每次操作完数据库,就顺便转移掉rehashidx索引下的键值对,转移完后+1,直到所有键值对转移完毕,rehashidx变为-1.

rehash期间,对字典的添加操作会在ht[1]上进行,确保ht[0]最终转化为空表。

标签:rehash,hash,void,redis,ht,键值,字典
From: https://www.cnblogs.com/wz-NO1/p/17231541.html

相关文章