Redis基础数据结构——字典

redis的字典hash相当于Java里面的HashMap，实现结构上也与Java的HashMap一样，都是“数组+链表”的二维结构。
不同的是，redis的字典的值只能是字符串，并且它们rehash的方式也不一样，相较于Java中HashMap的一次性rehash，redis中是渐进式rehash。
hash结构用来存储用户信息时，与字符串需要一次性全部序列化整个对象不同，hash可以对用户结构中的每个字段单独存储，这样当我们需要获取用户信息时可以进行部分获取。
1.redis字典的基本操作

hset key field value #给字典key加入field-value键值对,若field已存在，则更新field对应的value
hget key field #获取字典key中field对应的value值
hgetall key #获取字典中所有键值对
hlen key #获取字典的元素数
hmset key field value [field value …] #批量创建

若是value为数值，也可以进行计数

hincrby key field increment #字典key中field对应的数值value增加increment

2.redis字典的内部实现
字典是redis服务器中出现最频繁的复合型数据结构，除了hash结构的数据会用到字典外，整个redis数据库的所有key和value也组成了一个全局字典，还有待过期时间的key集合也是一个字典。zset集合中存储value和score值的映射关系也是字典结构。

struct RedisDb {
	dict* dict;			//全局字典
	dict* expires;		//过期字典
	...
}
struct zset {
	dict *dict;			//存放value和score的映射关系
	zskiplist *zsl;
}

既然字典在redis中这么重要，那么搞懂它的内部实现就尤为重要。

字典结构内部包含两个hashtable，通常情况下只有一个hashtable是有值的，但是在字典扩容缩容时，需要分配新的hashtable，然后进行渐进式搬迁，这时候两个hashtable存储的分别是旧的hashtable和新的hashtable。ht[0]为旧的hashtable，ht[1]为新的hashtable。等到搬迁结束之后，旧的hashtable被删除，新的hashtable取而代之。

struct dict {
	...
	dictht ht[2];
}

hashtable的结构和Java的HashMap几乎是一样的，都是通过分桶的方式解决hash冲突。第一维是数组，第二维是链表，数组中存储的是第二维链表的第一个元素的指针，如图所示。

struct dictEntry {
	void* key;
	void* val;
	dictEntry* next;
}
struct dictht {
	dictEntry** table;
	long size;			//第一维数组的长度
	long used;			//hash表中的元素个数
	...
}

3.渐进式rehash
redis的hash相较于Java的HashMap来说还有一点不同就是rehash方式不同，为渐进式rehash，那么为什么要采用这种方式呢？
因为，大字典的扩容时比较耗时的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个O(n)级别的操作，作为单线程的redis很难承受这样耗时的过程，因而redis使用渐进式rehash，虽然会慢一些，但是最终肯定是可以搬迁完的。

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){
	long index;
	dictEntry *entry;
	dictht *ht;
	
	//这里进行小步搬迁
	if(dictIsRehashing(d))
		_dictRehashStep(d);
	
	/*获取新元素的索引，如果该元素已经存在了，则索引为-1
	 *如果新元素已经存在，则返回空指针 */
	if(
	(index = _dictKeyIndex(d, key, dictHashKey(d, key), existing)) 
	== -1)
		return NUll;
	
	/*分配内存并存储新的entry
	 *将元素插入尾部
	 *系统优先访问最近添加的entry */
	//如果字典处于搬迁过程中，要将新的元素挂接到新的数组下面
	ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
	entry = zmalloc(sizeof(*entry));
	entry->next = ht->table[index];
	ht->table[index] = entry;
	ht->used++;
	
	/*设置字典输入字段 */
	dictSetKey(d, entry, key);
	return entry;
}

字典搬迁在当前字典的后续指令中，比如来自客户端的hset、hdel等命令之后，这样稍显被动了些，除此之外，redis还会在定时任务中对字典进行主动搬迁。

//服务器定时任务
void databaseCron() {
	...
	if(server.activerehashing) {
		for(j = 0; j < dbs_per_call; j++) {
			int word_done = incrementallyRehash(rehash_db);
			if(work_done) {
				/*如果函数做了一些工作，请到此为止，
				 *将在下一个cron循环中做更多的工作*/
				 break;
			} else {
				/*如果这个db不需要rehash，
				 *将尝试rehash下一个
				 rehash_db++;
				 rehash_db %= server.dbnum;
			}
		}
	}
}

4.字典的查找过程
要想对字典进行插入，修改，删除操作都必须先要查找到元素，才可以进行数据结构的修改。因而，搞清楚hash的查找过程是很有必要的。
hashtable的元素是在第二维的链表上，所以首先要做的是确定目标key处在哪个链表上,然后再顺序遍历这个链表找到目标key。

func get(key) {
	//hash函数计算得出目标元素在数组中的位置，也就是处于哪个链表上
	let index = hash_func(key) % size;
	let entry = table[index];
	//遍历链表，找目标key
	while(entry != NULL){
		//查找成功，返回目标元素
		if(entry.key == target){
			return entry.value;
		}
		entry = entry.next;
	}
}

5.扩容和缩容
(1)扩容

//如果需要，对hash表进行扩容
static int _dictExpandIfNeeded(dict *d) {
	//若是字典正在进行rehash，则返回，此时选择不扩容
	if(dictIsRehashing(d))
		return DICT_OK;
		
	//若是hash表是空的，将其扩容至初始大小
	if(d->ht[0].size == 0)
		return dictExpand(d, DICT_HT_INITIAL_SIZE);
		
	/*如果元素数量大于等于桶的数量，
	 *且至少满足以下条件之一:
	 *1.该字典是可以进行扩容的
	 *2.元素数量/桶数量的比值大于安全阈值，默认为5
	 *此时要进行扩容，扩容为此时元素数量的两倍大小
	*/
	 if(d->ht[0].used >= d->ht[0].size &&
	 	(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)){
	 		return dictExpand(d, d->ht[0].used*2);
	 	}
	 return DICT_OK;
}

(2)缩容
当hash表因为元素逐渐被删除变得越来越稀疏时，redis会对hash表进行缩容来减少hash表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的10%，缩容不会考虑redis是否正在做bgsave。

int htNeedsResize(dict *dict) {
	long long size, used;
	size = dictSlots(dict);
	used = dictSize(dict);
	return (size > DICT_HT_INITIAL_SIZE &&
			(used*100/size < HASHTABLE_MIN_FILL));
}