dict是什么

  dict是redis里的字典结构，类似于STL中的map，是按key查值的。

dict结构

/* 字典词条（键值对） */
typedef struct dictEntry { void *key;	      //该词条的key值union {void *val;    //其他数据类型uint64_t u64; //uint64_t整型int64_t s64;  //int64_t整型double d;     //double浮点型} v;struct dictEntry *next; //指向同一行的下个哈希表节点(即与该位置有冲突的节点)
} dictEntry;/* 字典类型 */
typedef struct dictType {uint64_t (*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;/* 哈希表(字典中储存数据的结构体) */
typedef struct dictht {dictEntry **table;      //哈希表数组unsigned long size;     //哈希表大小，即哈希表数组大小unsigned long sizemask; //哈希表大小掩码，总是等于size-1，主要用于计算索引unsigned long used;     //已使用节点数，即已使用键值对数
} dictht;/* 字典 */
typedef struct dict {dictType *type;     		//类型特定函数void *privdata;     		//私有数据，给自定义函数提供参数dictht ht[2];       		//2个哈希表，哈希表负载过高进行rehash的时候才会用到第2个哈希表long rehashidx;     		//rehash目前进度，当哈希表进行rehash的时候用到，其他情况下为-1unsigned long iterators; 	//正在运行安全迭代器的数量
} dict;/* 字典迭代器 */
typedef struct dictIterator {dict *d;long index;      				//正在遍历词条的下标int table, safe; 				//safe等于1是安全指针，可修改；0不安全，只可遍历dictEntry *entry, *nextEntry;	//当前词条、下一个冲突词条long long fingerprint;  		//不安全迭代器的指纹，判断不安全迭代器运行是否正常
} dictIterator;

重点函数

  dict的内部采用哈希表实现，通过dictType中的各种函数指针赋值实现各种类型的存储，dict文件里大部分函数都是实现哈希表，在此不一一介绍，其中比较重要的函数有rehash和scan。
在了解重点函数之前，我们首先需要知道redis是单线程的程序，因此当它某件事需要做很长时间时，为了防止阻塞，他都不会一次性全部做完，通常会分成一点一点来做。

redis在内存中运行，不需要等待缓慢的磁盘和等待输入，所以设计成单线程更快

resize函数

  一般情况下只使用ht[0]存储数据，当数据量太大或太小时需要对哈希表的大小进行调整，改变大小后原来的hash值可能不再是正确的，所以需要重新调用hash函数并将ht[0]中的数据逐一移动到ht[1]中，该操作称为rehash。

/*
参数d:需要rehash的字典n:rehash桶的个数
返回值int: 0 全部桶rehash完成1 全部桶rehash未完成
*/
int dictRehash(dict *d, int n) {int empty_visits = n*10; //最大空白访问量，防止消耗时间过长if (!dictIsRehashing(d)) return 0; //不需要rehash就退出while(n-- && d->ht[0].used != 0) { // 只移动n个桶dictEntry *de, *nextde;assert(d->ht[0].size > (unsigned long)d->rehashidx); // 判断rehashdix是否超出/* 排除空词条 */while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++;if (--empty_visits == 0) return 1;}de = d->ht[0].table[d->rehashidx]; //de：rehashidx桶的第一个词条/* 将旧表中的整个rehashidx桶的词条移动到新表 */while(de) {uint64_t h;nextde = de->next;h = dictHashKey(d, de->key) & d->ht[1].sizemask; //获取哈希值de->next = d->ht[1].table[h];d->ht[1].table[h] = de; //移动到新表d->ht[0].used--;d->ht[1].used++;de = nextde; // 下一个冲突词条}d->ht[0].table[d->rehashidx] = NULL;d->rehashidx++;}/* 检测旧表是否移动完 */if (d->ht[0].used == 0) {zfree(d->ht[0].table);d->ht[0] = d->ht[1];_dictReset(&d->ht[1]);d->rehashidx = -1;return 0; // 旧表没数据了}return 1; //旧表还有数据
}

scan函数

  scan函数的作用是对字典的遍历，由于存在rehash的机制，使得redis不能使用普通的递增遍历，而是光标倒序遍历。通过光标倒序遍历可以避免在rehash期间重复访问词条和遗漏词条的现象。

什么是光标倒序遍历

  假设ht的size为8，普通递增遍历顺序如下
001→010→011→100→101→110→111
光标倒序遍历顺序如下
100→010→110→001→101→011→111

采用光标倒序遍历的原因

  假设有一个ht表，size为8，used为16，如下图所示，现在我们开始遍历

ht[0]	value
0	v0→v8
1	v1→v9
2	v2→v10
3	v3→v11
4	v4→v12
5	v5→v13
6	v6→v14
7	v7→v15

  每次scan函数只遍历一个桶，原因上面解释过了，一件事分一点点做。
假设我们上次scan还是未rehash的且遍历完ht[0]的1桶，这次进来scan函数本来是要去访问ht[0]的2桶，但是进来发现正在rehash，已经把一部分数据移动到ht[1]里面了，我们需要访问的v2和v10也被移过去了。

ht[0]	value	ht[1]	value
0		0	v0
1		1	v1
2		2	v2
3	v3→v11	3
4	v4→v12	4
5	v5→v13	5
6	v6→v14	6
7	v7→v15	7
		8	v8
		9	v9
		10	v10
		11
		12
		13
		14
		15

  我们可以看出他们移动是有规律的，2的二进制是010，会在2桶的都是hash值余数等于2，所以当size扩张到16时发散会移动到0010和1010（也就是2和10），此时进来我们只需要高位补0通过光标倒序就可以访问到v2和v10

光标倒序实现

  假设ht的size为16，rev()是将一个数的bit位全部翻转，m0是长度的掩码（m0=size-1），具体实现如下

		m0 = size - 1; 		//m0 = 0000 1111v = 0b 0000 1000;	//v = 0000 1000────┐v |= ~m0; 			//v = 1111 1000    │v = rev(v);			//v = 0001 1111  右进1位v++;				//v = 0010 0000    │v = rev(v);			//v = 0000 0100<───┘

源码解析

/*
参数d:需要遍历的字典fn:访问词条的函数bucketfn:访问桶的函数privdata:传给fn和bucketfn的参数
返回值unsigned long:遍历到哪个桶了
*/
unsigned long dictScan(dict *d,unsigned long v,dictScanFunction *fn,dictScanBucketFunction* bucketfn,void *privdata)
{dictht *t0, *t1;const dictEntry *de, *next;unsigned long m0, m1;if (dictSize(d) == 0) return 0;d->iterators++; //安全迭代器加一（iterators不等于0，无法rehash）if (!dictIsRehashing(d)) { // 没有rehasht0 = &(d->ht[0]);m0 = t0->sizemask;if (bucketfn) bucketfn(privdata, &t0->table[v & m0]); //通过bucketfn()对每个桶进行操作de = t0->table[v & m0]; //获取v桶的头词条，这里对 v&m0 适应了长度不同的v/* 遍历整个桶 */while (de) {next = de->next;fn(privdata, de); //通过fn函数对每个词条进行操作de = next;}/* 光标倒序遍历 */v |= ~m0;v = rev(v);v++;v = rev(v);} else { // 有rehasht0 = &d->ht[0];t1 = &d->ht[1];/* 有rehash时，同一个桶的词条，可能有些在旧表，有些在新表，遍历小表再遍历大表，这样不会冲突，小表放t0，大表放t1 */if (t0->size > t1->size) {t0 = &d->ht[1];t1 = &d->ht[0];}m0 = t0->sizemask;m1 = t1->sizemask;/* 先访问小表，同上步骤 */if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);de = t0->table[v & m0];while (de) {next = de->next;fn(privdata, de);de = next;}/* 访问大表 */do {if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);de = t1->table[v & m1];while (de) {next = de->next;fn(privdata, de);de = next;}/* 光标倒序遍历 */v |= ~m1;v = rev(v);v++;v = rev(v);/* 遍历完高位即遍历完小表的那个桶m0^m1 = 1000小表访问010大表访问0010和1010，当v变成0110时退出*/} while (v & (m0 ^ m1));}/* 解除上面的++ */d->iterators--;return v;
}