- Redis版本:5.0.5
- 文件：dict.h dict.c
字典概念
- 字典，又称为符号表，关联数组或映射，是一种用于保存键值对的抽象数据结构。
- 在字典中，一个键可以和一个值进行关联（或者说为映射），这些关联的键和值就称为键值对。
- 字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对等。
字典的结构
- 哈希表
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表的大小
unsigned long size;
//哈希表的掩码，用于计算索引值，并且其大小总是等于size-1
unsigned long sizemask;
//哈希表已有节点的数量
unsigned long used;
} dictht;
- 哈希表节点
typedef struct dictEntry {
//键
void *key;
//值(值可以是指针，可以是unit64_t, int64_t, double)
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//指向下一个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
- dictype
typedef struct dictType {
//计算哈希值的函数
uint64_t (*hashFunction)(const void *key);
//复制键的函数
void *(*keyDup)(void *privdata, const void *key);
//复制值的函数
void *(*valDup)(void *privdata, const void *obj);
//对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
//销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
//销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
- 字典dict
typedef struct dict {
//函数结构体
dictType *type;
//私有数据
void *privdata;
dictht ht[2]; //两个数组，ht[0]用来hash，ht[1]用来rehash
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running 迭代器*/
} dict;
字典的创建、插入、Rehash、删除查找等函数(很详细的在代码中进行注释讲解)
1.创建函数
//dictCreate暴露给用户
//该函数只是给dict分配了空间，而其内部的ht->table还没有分配空间，等到第一次添加键值对时分配
dict *dictCreate(dictType *type,
void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
void *privDataPtr)
{
//_dicRest函数初始化dictht
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}
2.插入函数
- dictAdd函数是暴露给用户的函数，其内部调用了dictAddRaw函数来进行添加
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
- dicAddRaw函数
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
//判断是否该dict是否正在rehash，如果是则调用_dictRehashStep函数
if (dictIsRehashing(d)) _dictRehashStep(d);
//调用_dictKeyIndex获取要插入的位置，下面会讲到这个函数
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
//如果正在rehash则插入到ht[1]中，否则插入的ht[0]中。
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
- _dictKeyIndex函数
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
//判断是否还需要额外的空间，下面会将这个函数
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
for (table = 0; table <= 1; table++) {
//算出插入的位置idx
idx = hash & d->ht[table].sizemask;
//找到idx位置的头结点
he = d->ht[table].table[idx];
//判断idx位置的链表中是否有相同的key
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
/*
*没有正在rehash的话就只需要判断ht[0]就可以
*如果正在rehash，则还需要判断ht[1]中是否也有相同的键
*/
if (!dictIsRehashing(d)) break;
}
//返回要插入的位置
return idx;
}
- _dictExpandIfNeeded函数
static int _dictExpandIfNeeded(dict *d)
{
//如果正在rehash，则直接返回DICT_OK(因为正在rehash表明有足够的空间)
if (dictIsRehashing(d)) return DICT_OK;
//如果是第一次插入，则需要给ht[0]分配空间，调用dicExpand函数(这就是上面将创建dict时没有给ht->table分配空间在这里进行创建)
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); //这个函数下面也会讲
//当已有的元素大于size或者大于初始装载因子时则需要扩容
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
//used*2 扩容两倍,调用dictExpand函数
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
- dictExpand函数
int dictExpand(dict *d, unsigned long size)
{
//扩容, d正在rehash或者已有元素大于扩容的容量
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
//new hash table
dictht n;
//返回新hashtable的容量 _dictNextPower函数比较简单，可以自行去阅读(该函数总是返回距离size最近的大于它的2的n次方的数)
//举个例子：扩容的size = 6，该函数就会返回8。 size = 17，该函数就会返回32。
unsigned long realsize = _dictNextPower(size);
if (realsize == d->ht[0].size) return DICT_ERR;
//给新的hash table分配空间
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
//如果ht[0]还没有分配空间，则n赋值给ht[0]。
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
d->ht[1] = n;
//将d->rehashidx = 0 表明要开始rehash操作
d->rehashidx = 0;
return DICT_OK;
}
- 总结一下插入的流程。
1.第一次插入： 调用插入函数，发现是第一次插入，就需要给ht[0]分配内存，然后找到要插入的下标进行插入。
2.之后的插入：调用插入函数，判断空间是否还能插入，可以插入则直接插入。空间不足，就需要新的table，就为ht[1]分配空间，然后将rehashidx置为0，进行rehash，这个时候的插入都将会插入到ht[1]中。
3.Rehash函数
- _dictRehashStep函数(这个函数在上文中的dictAddRaw函数中出现)
static void _dictRehashStep(dict *d)
{
if (d->iterators == 0) dictRehash(d,1);
}
- dictRehash函数
int dictRehash(dict *d, int n) {
//一次rehash n*10个桶的元素
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
//开始rehash
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsigned long)d->rehashidx);
//当前桶已经为空，将rehashidx++
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
//本次rehash已经结束，但是hash[0]中还有元素，return 1，表明还需要继续rehash操作。
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
//将ht[0].table[d->rehashidx]桶的元素移动到ht[1]中
while(de) {
uint64_t h;
nextde = de->next;
//需要重新计算在ht[1]中的位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
//检查是否rehash完毕
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
- 总结rehash
从上面的代码中可以看出，Redis中的字典是采用渐进式rehash方法，如果ht[0]中元素非常多，采用渐进式rehash不会导致rehash操作浪费太多时间而导致服务器阻塞一段时间。
掌握了上文中讲的所有函数后，大家自行去看删除查找的源码就没有什么难度了。