• 一种保存键值对的抽象数据结构
• 每个键都是独一无二的，换言之，自带去重。
• 是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]最终转化为空表。