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)