- 一种保存键值对的抽象数据结构
- 每个键都是独一无二的,换言之,自带去重。
- 是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