Redis源码研究

计划每天花1小时学习Redis 源码。在博客上做个记录。 --------6月18日----------- redis的字典dict主要涉及几个数据结构， dictEntry：具体的k-v链表结点 dictht：哈希表 dict：字典 具体关系为 1 typedef struct dict { 2 dictType * type; 3 void * privda

计划每天花1小时学习Redis 源码。在博客上做个记录。

--------6月18日-----------

redis的字典dict主要涉及几个数据结构，

dictEntry：具体的k-v链表结点

dictht：哈希表

dict：字典

具体关系为

1 typedef struct dict { 2 dictType *type; 3 void *privdata; 4 dictht ht[2]; iterators; } dict;

1 typedef struct dictht { 2 dictEntry **table; 3 unsigned long size; 4 unsigned long sizemask; 5 unsigned long used; 6 } dictht;

1 typedef struct dictEntry { 2 void *key; 3 union { 4 void *val; 5 uint64_t u64; 6 int64_t s64; 7 } v; 8 struct dictEntry *next; 9 } dictEntry;

一个字典有两个哈希表， 冲突后采用了链地址法，很好理解。

一些简单操作采用了宏

#define dictGetKey(he) ((he)->key) #define dictGetVal(he) ((he)->v.val) #define dictGetSignedIntegerVal(he) ((he)->v.s64) #define dictGetUnsignedIntegerVal(he) ((he)->v.u64)

------------6月19日----------------------

字典具体用到了两种哈希算法，我只看了简单的那一种，没想到代码竟然可以那么少，算法名字为djb2，

unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { 3 unsigned int hash = (unsigned int)dict_hash_function_seed; (len--) hash; 8 }

dict_hash_function_seed是个全局变量，为5381.
The magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.
JDK中采用的哈希算法取得数字是31，一个素数。
创建一个新字典并初始化：

1 dict *dictCreate(dictType *type, void *privDataPtr){ 2 dict *d = malloc(sizeof(*d)); 3 _dictInit(d,type,privDataPtr); 4 return d; 5 } _dictInit(dict *d, dictType *type, void *privDataPtr){ 8 _dictReset(&d->ht[0]); 9 _dictReset(&d->ht[1]); 10 11 d->type = type; 12 d->privdata = privDataPtr; 13 d->rehashidx = -1; 14 d->iterators = 0; DICT_OK; 17 } _dictReset(dictht *ht){ 20 ht->table = NULL; 21 ht->size = 0; 22 ht->sizemask = 0; 23 ht->used = 0; 24 }

学了这么多年c语言了，malloc(sizeof(*d))我还是第一次看到。
说到sizeof，我还要提一句，c99之后，sizeof是运行时确定的，c99还加入了动态数组这一概念。csdn上的回答是错的。
对字典进行紧缩处理，让 哈希表中的数/哈希表长度接近1：

1 int dictResize(dict *d){ 2 int minimal; (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; 5 6 minimal = d->ht[0].used; (minimal < DICT_HT_INITIAL_SIZE) 9 minimal = DICT_HT_INITIAL_SIZE; dictExpand(d, minimal); 12 } dictIsRehashing(ht) ((ht)->rehashidx != -1) 15 #define DICT_HT_INITIAL_SIZE 4

当字典正在Rehash的时候不能进行Resize操作，初始时哈希表大小为4，哈希表大小一般都是2的幂次方。
如果minimal是5，经过dictExpand后，哈希表大小变为8.

1 static unsigned long _dictNextPower(unsigned long size){ 2 unsigned long i = DICT_HT_INITIAL_SIZE; (size >= LONG_MAX) return LONG_MAX; 5 while(1) { 6 if (i >= size) 7 return i; 8 i *= 2; 9 } 10 } dictExpand(dict *d, unsigned long size){ unsigned long realsize = _dictNextPower(size); the size is invalid if it is smaller than the number of (dictIsRehashing(d) || d->ht[0].used > size) 20 return DICT_ERR; n.size = realsize; 24 n.sizemask = realsize-1; 25 n.table = zcalloc(realsize*sizeof(dictEntry*)); 26 n.used = 0; Is this the first initialization? If so it's not really a rehashing (d->ht[0].table == NULL) { 31 d->ht[0] = n; 32 return DICT_OK; 33 } d->ht[1] = n; 37 d->rehashidx = 0; DICT_OK; 40 }

新建了一个哈希表n，size是扩展后的size，，ht[0].table 为空说明这是第一次初始化，不是扩展，直接赋值。
ht[0].table 不为空，说明这是一次扩展，把n赋给ht[1]，ReHash标志rehashix也被设为0.
上边这段不大好理解，先看后面的，一会返过来再研究dictExpand函数。
--------------------6月20日--------------------------

向字典中添加元素需要调用dictAdd函数：