redis源码学习:字典的实现

字典是一种数据结构。可以用来保存key-value形式的键值对。redis作为非关系型数据库就很依赖这种形式的映射字典,它有一套自己的实现方法。在这里我就学习并记录一下它的依赖于hash表的底层实现方法。

基本数据结构

hash表数据结构的定义都在dict.h头文件下:

hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {

// 哈希表数组
dictEntry **table;

// 哈希表大小
unsigned long size;

// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;

// 该哈希表已有节点的数量
unsigned long used;

} dictht;
> ####dictEntry 以key-value形式保存数据的结构,定义如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dictEntry {

// 键
void *key;

// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;

// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;

字典:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct dict {

// 类型特定函数
dictType *type;

// 私有数据
void *privdata;

// 哈希表
dictht ht[2];

// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */

// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */

} dict;

其中包含了两个hash表,一个用来存储数据,一个是用来做rehash的。
字典的核心源码在dict.h和dict.c中。下面简述下字典的增加,删除,查询等操作的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key);

if (!entry) return DICT_ERR;
dictSetVal(d, entry, val); //设置当前节点的value值
return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d); //若需要rehash,则先执行rehash操作。

/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key)) == -1) //通过_dictKeyIndex方法算出当前key所属table的index
return NULL;

/* Allocate the memory and store the new entry */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry)); //把当前的dictEntry指针放到hash表链表的头部
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;

/* Set the hash entry fields. */
dictSetKey(d, entry, key); //设置当前节点的key值
return entry;
}

在执行_dictKeyIndex()方法时,在函数开始会检查当前使用的hash表是否需要扩展。若满足

1
2
3
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))

那么redis就会分配新的空间给dict.ht[1],并将rehash标志位打开,开始rehash操作。dict_can_resize变量由系统控制,当服务器在执行BGSAVE或BGREWRITEAOF命令时,该变量为真。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;

if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
if (dictIsRehashing(d)) _dictRehashStep(d);//若在rehash状态,则执行rehash操作
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL; //如果不在rehash中,则没有必要去查找ht[1]了。key肯定不存在。
}
return NULL;
}

dictFind函数可以找到指定key的节点,先通过hash函数和sizemask值算出index,然后扫描一遍链表结构找到匹配的节点并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;

if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);

for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while(he) {
if (dictCompareKeys(d, key, he->key)) {
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR; /* not found */
}

dictGenericDelete函数用来删除节点上的值并释放空间。
几个简单操作的核心代码就在这里了。