Redis字典

一种用于保存键值对的抽象数据结构，Redis的数据库就是使用字典来作为底层实现的，字典还是哈希键的底层实现之一.

字典的实现

Redis中字典使用哈dictht表作为底层，一个哈希表里面可以有多个哈希表结点，而每个哈希表结点就保存了字典中的一个键值对.

哈希表

typedef struct dictht{
	//哈希表数据
	dictEntry **table;
	//哈希表大小
	unsigned long size;
	//哈希表大小掩码，用于计算索引值
	//总是等于size - 1
	unsigned long sizemask;
	//该哈希表已有结点数量
	unsigned long used;
}dictht;

table是一个数组，数组中每一个元素指向dictEntry结构的指针

size是哈希表的大小也就是数组的大小

used是哈希表中键值对的数量

sizemask用来确定一个键应该被放到table数组的哪一个索引里面

哈希表结点

typedef struct dictEntry{
	//键
	void *key;
	//值
	union{
		void *val;
		uint64_t u64;
		int64_t s64;
	}v;
	//指向下一个哈希表结点，形成链表
	struct dictEntry *next;
}dictEntry;

key保存键 v 保存值 next是使用链地址法来解决哈希冲突

字典

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

ht属性

是一个包含两个项的数组，数组中每个项都是一个哈希表，ht[1]会在rehash时候使用,正常情况下只使用ht[0].

rehashidx

它记录了rehash目前的进度，如果目前没有在进行rehash，那么他的值为-1。

哈希算法

使用字典设置的哈希函数计算键key的哈希值

hash = dict->type->hashFunction(key);

使用哈希表的sizemsk属性和哈希值计算出索引值

index = hash & dict->ht[x].sizemask;

计算到索引之后表示此k-v键值对应该被放到哈希表对应索引中

解决键冲突

Redis使用链地址法来解决键冲突

特点：因为dictEntry结点组成的链表没有指向链表表尾的指针，也就是没有像Redis链表一样的指向头和尾的指针，所以为了速度考虑，当出现哈希冲突时Redis总是使用头插法，将新结点插到最前面。

rehash（重新散列）

为了让哈希表的负载因子维持在一个合理的范围之内，程序会对哈希表进行扩展或者收缩。可以通过rehash完成。

rehash步骤

1.为ht[1]分配空间

​ 扩展操作：ht[1]的大小为2^n (2^n >= ht[0].used*2 )n取最小值 键值对数量的二倍

​ 收缩操作： ht[1]的大小为2^n (2^n >= ht[0].used)n取最小值 键值对数量

2.将ht[0]中的所有键值对执行rehash到ht[1] 重新计算哈希值与索引

3.迁移完毕后，释放ht[0] 将ht[1]设置为ht[0] 并在ht[1]创建一个空的哈希表

渐进式rehash

这个动作分多次的渐进式的完成

1.为ht[1]分配空间，让字典同时存在两个哈希表ht[0]和ht[1]

2.字典dict中的rehashidx（索引计数器）将其设置为0，表示rehash开始

3.在rehash期间对字典执行添加、删除、查找、或者更新操作程序除了执行操作还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作结束后rehashidx+1

4.当ht[0]上的所有键值都被rehash到ht[1]上时，将rehashidx设置为-1，表示rehash操作完成。

渐进式rehash的好处在于它采取分而治之的方式，将rehash的操作分解到对字典的增删改查上，避免了集中式rehash带来的大计算量

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

再次过程中字典会同时使用ht[0]和ht[1]两个哈希表，字典的个助攻操作都会在两个哈希表上进行，eg查找一个键会先查找ht[0]然后查找ht[1]，另外在rehash执行期间，新添加的键值对会被保存到ht[1]里面，而ht[0]不会在进行添加操作。