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 {2dictType *type;3void *privdata;4dictht ht[2];iterators; } dict;

1 typedef struct dictht {2dictEntry **table;3unsigned long size;本文来源gao($daima.com搞@代@#码(网4unsigned long sizemask;5unsigned long used;6 } dictht;

1 typedef struct dictEntry {2void *key;3 union {4void *val;5 uint64_t u64;6 int64_t s64;7 } v;8struct 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) {3unsigned 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){ 2dict *d = malloc(sizeof(*d)); 3 _dictInit(d,type,privDataPtr); 4return d; 5 }_dictInit(dict *d, dictType *type, void *privDataPtr){ 8_dictReset(&d->ht[0]); 9_dictReset(&d->ht[1]);10 11d->type = type;12d->privdata = privDataPtr;13d->rehashidx = –1;14d->iterators = 0; DICT_OK;17 }_dictReset(dictht *ht){20ht->table = NULL;21ht->size = 0;22ht->sizemask = 0;23ht->used = 0;24 }

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

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

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

1 static unsigned long _dictNextPower(unsigned long size){ 2unsigned long i = DICT_HT_INITIAL_SIZE;(size >= LONG_MAX) return LONG_MAX; 5while(1) { 6if (i >= size) 7return i; 8i *= 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)20return DICT_ERR;n.size = realsize;24n.sizemask = realsize-1;25n.table = zcalloc(realsize*sizeof(dictEntry*));26n.used = 0; Is this the first initialization? If so it’s not really a rehashing(d->ht[0].table == NULL) {31d->ht[0] = n;32return DICT_OK;33 }d->ht[1] = n;37d->rehashidx = 0; DICT_OK;40 }

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

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

喜欢 (0)赏

[搞代码]

分享 (0)