作者:汪pallotta | 来源:互联网 | 2018-07-10 17:42
计划每天花1小时学习Redis源码。在博客上做个记录。--------6月18日-----------redis的字典dict主要涉及几个数据结构,dictEntry:具体的k-v链表结点dictht:哈希表dict:字典具体关系为1typedefstructdict{2dictType*type;3void*privda
计划每天花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函数: