Redis笔记之基本数据结构 字典

字典

符号表、关联数组或者映射，有点类似于java中的map，用于保存键值对key-value。字典中的键key是独一无二的。底层实现为哈希表。下面进行简述：

• 哈希表。哈希表主要包含table数组、size、sizemask以及used。table用于保存哈希表节点，保存数据；sizemask为哈希表掩码用于计算索引；size用于保存table大小；used用于保存已经保存的节点数目，如图dictht结构体。
• 哈希表节点。用于保存key-value数据，以及next指针用于指向下一个节点，为了解决哈希冲突而采用的拉链法。

typedef struct dictEntry{
	void *key;
	union{
		void *val;
		uint64_t u64;
		int64_t s64;
	} v;
	struct dictEntry *next;
} dictEntry;

• 字典。主要包含type、privdata、ht[2]、rehashidx几个属性。type表示字典数据类型；privdata保存了需要传递给type指定类型函数的可选参数；ht[2]指向两个哈希表，一个用于平时保存数据，另一个用于rehash（扩容等）时使用；rehashidx在rehash使用，用于表示当前正在转移table中第几个索引的数据。整体结构茹下图。
  

哈希算法以及rehash

• 哈希算法。首先，计算key的哈希值然后使用掩码sizemask求得在table中的索引（例如， hash & sizemask），然后使用头插法直接插入，使用链地址法解决哈希冲突。
• rehash。当哈希表的负载因子过大或者过小时，需要进行扩展以及压缩，这个时候需要rehash，也就是需要重新计算当前值在新的table中的位置；扩展时，扩展为第一个大于等于ht[0].used*2的2的n次幂、压缩时，压缩为第一个大于等于ht[0].used的2的n次幂；负载因子等于used/size，当当前正在进行持久化时（BGSAVE或者BGREWRITEAOF），负载因子大于等于5扩展，平常选择1，当负载因子小于0.1时，进行压缩。rehash时，查询操作，先到ht[0]中查询，如果没有再去ht[1]中查询，插入新数据时，直接在ht[1]中插入。rehashidx默认为-1，当rehash时，保存的为正在转移的ht[0]中table的索引。

本文为《Redis设计与实现》阅读笔记