Redis数据结构--字典
2017-09-03 本文已影响0人
毛小力
字典是Redis的重要数据结构，Redis的数据库就是使用字典作为底层实现的。代码位于dict.h和dict.c中。
1. 字典（Dict）
1.1 哈希表（Hash Table）
Redis使用哈希表实现字典。
哈希表存储键值对，将键的哈希值映射到存储位置（即索引值），加快访问速度。
Redis默认哈希算法为SipHash（待以后写文分析），使用数组+链表作为哈希表数据结构（即链地址法），哈希值模数组大小即为索引值。
1.2 Redis哈希表
哈希表结构
哈希表结构如上图所示，为行文方便定义几个名词指代上图中的组件结构：
- ht（哈希表）：最左边的组件即为哈希表
- table（桶数组）：ht中有字段指向数组，此数组称为table，数组长度即为哈希表大小
- bucket（桶）：table的每一项称为bucket，bucket指向具有相同索引值的键值对链表
- entry（节点）：链表里的节点称为entry，entry包装了键值对的key和value，同时包含next指针指向链表的下一节点
- 哈希表
typedef struct dictht {
// 哈希桶数组
dictEntry **table;
// 哈希表大小，即数组长度
unsigned long size;
// 哈希表大小掩码常量，为数组长度-1，与哈希值与计算得出索引值
unsigned long sizemask;
// 哈希表已有键值对数量
// 装载因子 = used / size
unsigned long used;
} dictht;
- 哈希表节点
typedef struct dictEntry {
// 键
void *key;
// 值，使用union以适应不同类型的值
union {
void *val; // 整数与浮点数直接存储，其它类型使用引用
uint64_t u64; // 无符号整数
int64_t s64; // 有符号整数
double d; // 浮点数
} v;
// 指向下一个节点
struct dictEntry *next;
} dictEntry;
1.3 字典
字典结构
字典结构为上图所示，左边组件即为字典（本文称为dict），每个字典包含两个哈希表（本文称之为ht[0]和ht[1]）。代码定义如下：
- 字典
typedef struct dict {
// 指向字典类型结构
dictType *type;
// 私有数据
void *privdata;
// 2个哈希表
dictht ht[2];
// rehash索引，rehash未进行时其值为-1
long rehashidx;
// 当前的迭代器数量
unsigned long iterators;
} dict;
- 字典类型
// 字典类型，保存一组操作特定类型键值对的函数
// Redis为不同的字典设置不同的类型特定函数
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;
1.4 rehash（重哈希）
在初期，字典只使用ht[0]哈希表，ht[1]为空。随着操作的不断进行，ht[0]中元素最终会偏多或偏少，为了使哈希表的装载因子维持在一个合理范围，Redis使用rehash对哈希表进行伸缩。
rehash的基本原理是新建ht[1]哈希表，将ht[0]中的元素重新计算哈希值和索引值，然后迁移到ht[1]。但是如果字典中的元素数量太多，一次性地迁移所有元素会耗费很长时间，因此Redis采用分步渐进式rehash。
分步rehash的基本原理是将一次rehash拆分成多步来完成，每步只将ht[0]中一个bucket的元素迁移到ht[1]，直到全部迁移。分步rehash详细步骤如下：
- 每次添加元素时，判断是否需要rehash
- 允许rehash，装载因子达到1时
- 不允许rehash，但装载因子达到5时
- 需要rehash，则
- 新建ht[1]哈希表，其大小是：
- 若是扩张，为大于等于现有节点数2倍的最小2次幂
- 若是收缩，为大于等于现有节点的最小2次幂
- 将字典的rehashidx字段置为0，表示开始rehash（未开始时为-1）
- rehash对table中的bucket按顺序逐个迁移，rehashidx实际是下一步要迁移bucket的数组下标
- 新建ht[1]哈希表，其大小是：
- 开始rehash后，每次对字典进行增删查改操作时，顺带进行一步rehash，将一个bucket的所有元素从ht[0]迁移到ht[1]
- 最终，ht[0]中的所有元素迁移到ht[1]，然后释放ht[0]，将ht[1]置为ht[0]，rehashidx复位为-1，一次完整的rehash结束。
2. 创建字典
// 传入字典类型和私有数据，创建字典
dict *dictCreate(dictType *type, void *privDataPtr)
{
// 申请内存
dict *d = zmalloc(sizeof(*d));
// 初始化
_dictInit(d,type,privDataPtr);
return d;
}
// 初始化字典
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
// 初始化哈希表
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
// 初始化字典属性
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}
// 重置哈希表：全部置空
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
3. 添加元素
3.1 哈希值、键、值
- 计算键的哈希值
// 调用字典类型的hashFunction函数计算键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
- 比较键
// 若字典类型的keyCompare函数存在，则使用函数比较，否则比较是否是相同引用
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
- 设置键
// 若字典类型的keyDup函数存在，则使用函数计算后赋值，否则直接赋值
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
(entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
(entry)->key = (_key_); \
} while(0)
- 释放键
// 若字典类型的keyDestructor函数存在，则使用函数销毁键
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key)
- 设置值
// 若字典类型的valDup函数存在，则使用函数计算后赋值，否则直接赋值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
(entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
(entry)->v.val = (_val_); \
} while(0)
- 释放值
// 若字典类型的valDestructor函数存在，则使用函数销毁值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
3.2 rehash
- 判断是否处于rehash中
#define dictIsRehashing(d) ((d)->rehashidx != -1)
- 完成一步rehash
static void _dictRehashStep(dict *d) {
// 只有在无迭代器才进行rehash
// 如果rehash时有迭代器，不能对哈希表中的元素迁移，否则可能导致迭代时元素错过或重复
if (d->iterators == 0) dictRehash(d,1);
}
- 通用：完成n步rehash
// 进行n步rehash，如果还有键需要迁移则返回1，否则返回0
// 如果遇到空桶则继续，遇到N*10个空桶则返回，避免阻塞过久
int dictRehash(dict *d, int n) {
// 允许遇到的最大空桶数
int empty_visits = n*10;
if (!dictIsRehashing(d)) return 0;
// 如果ht[0]仍有元素，则进行下一步rehash
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
// rehashidx是下一个要迁移的桶的数组下标，自然要小于数组长度
assert(d->ht[0].size > (unsigned long)d->rehashidx);
// 如果遇到空桶，则顺延到下一个bucket，直到遇到最大空桶数，就返回
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 获取bucket链表的头节点
de = d->ht[0].table[d->rehashidx];
// 遍历链表的节点，全部迁移到ht[1]
while(de) {
unsigned int h;
// 获取下一节点
nextde = de->next;
// 计算迁移元素在ht[1]的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 迁移到ht[1]相应bucket链表头部
// ht[0]中的链表，因为全部迁移，所以迁移单个节点时不进行处理
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 修改计数
d->ht[0].used--;
d->ht[1].used++;
// 迭代下一节点
de = nextde;
}
// ht[0]迁移的bucket置空
d->ht[0].table[d->rehashidx] = NULL;
// 设置下一步rehash要处理的bucket索引下标
d->rehashidx++;
}
// 如果ht[0]中元素全部迁移完毕
if (d->ht[0].used == 0) {
// 释放ht[0]
zfree(d->ht[0].table);
// 将ht[1]哈希表设置为ht[0]
d->ht[0] = d->ht[1];
// ht[1]清空复位，以待下次rehash
_dictReset(&d->ht[1]);
// rehash状态设置为未开始
d->rehashidx = -1;
// 此次rehash完毕，返回0
return 0;
}
// 未迁移完毕，还需下一步rehash，返回1
return 1;
}
3.3 字典的扩张
- 如果需要则对字典进行扩张
static int _dictExpandIfNeeded(dict *d)
{
// 如果正在rehash中，返回
if (dictIsRehashing(d)) return DICT_OK;
// 如果ht[0]为空哈希表，则对其进行初始化
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 如果允许resize，且装载因子达到1
// 如果不允许resize，且装载因子达到5
if (d->ht[0].used >= d->ht[0].size && (dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
// 按照当前节点数的2倍进行扩张（进行rehash）
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
- 相关参数
// 字典初始大小
#define DICT_HT_INITIAL_SIZE 4
// 默认允许resize
static int dict_can_resize = 1;
// 不允许resize时，强制进行resize要达到的负载因子
static unsigned int dict_force_resize_ratio = 5;
- 获取大于等于指定大小的最小2次幂，作为实际哈希表的大小
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size) return i;
i *= 2;
}
}
- 将字典扩张到指定大小
int dictExpand(dict *d, unsigned long size)
{
// 创建新哈希表ht[1]
dictht n;
// 将指定大小值进行规整：不小于size的最小2次幂值
unsigned long realsize = _dictNextPower(size);
// 判断扩张大小无效的情况
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
if (realsize == d->ht[0].size) return DICT_ERR;
// 设置新哈希表属性
n.size = realsize;
n.sizemask = realsize-1;
// 按新的哈希表大小创建table数组
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 若是初始化，则此次不是rehash，将新哈希表设置为ht[0]即可。
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
// 若ht[0]存在，则此次是rehash，将新哈希表设置为ht[1]
// 并且设置为开始rehash状态，以便操作元素时进行rehash
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
3.4 添加元素
- 向字典添加键值对
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;
}
- 添加或查找键，若查找到则existing指向节点返回null，若添加成功则返回节点
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
int index;
dictEntry *entry;
dictht *ht;
// 若处于rehash中，则完成一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算键的哈希值，判断键是否已存在
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));
// 根据键的索引值寻找bucket链表，插入到表头
entry->next = ht->table[index];
ht->table[index] = entry;
// 增加节点计数
ht->used++;
// 设置节点的键
dictSetKey(d, entry, key);
return entry;
}
- 查找键是否已在哈希表中，若存在返回-1，若不存在则返回键的索引值
// 若existing非空，且键在哈希表中，则设置其指向键的节点
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
unsigned int idx, table;
dictEntry *he;
if (existing) *existing = NULL;
// 检查字典装载因子，若需要则扩张字典
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 遍历哈希表
for (table = 0; table <= 1; table++) {
// 找到键的索引值对应的bucket
idx = hash & d->ht[table].sizemask;
// 遍历bucket中的节点
he = d->ht[table].table[idx];
while(he) {
// 判断节点与键是否相同
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
// 如果找到键，返回-1
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
4. 查找元素
// 查找键对应的节点
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
// 若字典为空返回NULL
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
// 若正在rehash，进行一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算键的哈希值
h = dictHashKey(d, key);
// 遍历两个哈希表
for (table = 0; table <= 1; table++) {
// 计算键在哈希表的索引值
idx = h & d->ht[table].sizemask;
// 获取键所在bucket链表的头节点
he = d->ht[table].table[idx];
// 遍历链表节点
while(he) {
// 若键相同，则返回节点
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 若没有在rehash，则ht[1]为空，不需要遍历，直接返回
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
5. 替代元素
// 若键存在则替代值，若不存在则添加键值对
// 添加成功返回1，替代成功返回0
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, *existing, auxentry;
// dictAddRaw：若键存在，则existing指向节点返回null，若键不存在，则添加并返回节点
entry = dictAddRaw(d,key,&existing);
if (entry) {
// 添加成功，设置值，返回1
dictSetVal(d, entry, val);
return 1;
}
// 更新节点：设置新值、释放旧值、返回0
auxentry = *existing;
dictSetVal(d, existing, val);
dictFreeVal(d, &auxentry);
return 0;
}
6. 删除元素
// 删除键对应的元素，成功返回DICT_OK，找不到元素返回DICT_ERR
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
// 删除键对应的元素，删除成功返回其节点，找不到元素返回NULL
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
// 字典为空返回NULL
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
// 正在rehash，进行一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算键的哈希值
h = dictHashKey(d, key);
// 遍历哈希表
for (table = 0; table <= 1; table++) {
// 计算键的索引值
idx = h & d->ht[table].sizemask;
// 键所在bucket链表的头节点
he = d->ht[table].table[idx];
prevHe = NULL;
// 从头节点依次遍历整个链表
while(he) {
// 若找到相同键节点
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 将节点从链表中移除
if (prevHe) // 若是中间节点
prevHe->next = he->next;
else // 若是头节点
d->ht[table].table[idx] = he->next;
if (!nofree) {
// 释放键
dictFreeKey(d, he);
// 释放值
dictFreeVal(d, he);
// 释放节点
zfree(he);
}
// 节点计数减1
d->ht[table].used--;
// 返回删除的节点
return he;
}
// 当前节点不是，移动到下一节点
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL;
}
7. 释放字典
// 清空并释放字典
void dictRelease(dict *d)
{
// 清空两个哈希表
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
// 释放字典内存
zfree(d);
}
// 清空哈希表
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
unsigned long i;
// 遍历哈希表所有节点
for (i = 0; i < ht->size && ht->used > 0; i++) {
dictEntry *he, *nextHe;
if (callback && (i & 65535) == 0) callback(d->privdata);
// 若遇到空桶，跳过
if ((he = ht->table[i]) == NULL) continue;
// 从桶的头节点开始遍历节点，释放节点的键、值和内存
while(he) {
nextHe = he->next;
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
ht->used--;
he = nextHe;
}
}
// 释放table数组
zfree(ht->table);
// 重置字典
_dictReset(ht);
return DICT_OK;
}
8. 迭代器
8.1 迭代器定义
// 如果safe为1，则是安全迭代器，可在迭代时可调用dictAdd、dictFind以及其它函数
// 如果safe为0，则是非安全迭代器，在迭代时只可调用dictNext()
typedef struct dictIterator {
// 字典引用
dict *d;
// 字典的哈希表下标
int table;
// 哈希表的bucket数组下标
long index;
// 指向bucket的链表中上一次返回的节点
dictEntry *entry;
// 指向bucket的链表中下一次返回的节点
dictEntry *nextEntry;
// 1，安全模式；0，非安全模式
int safe;
// 非安全模式下，在迭代器创建时，计算字典状态的指纹
long long fingerprint;
} dictIterator;
8.2 获取迭代器
// 非安全迭代器
dictIterator *dictGetIterator(dict *d)
{
dictIterator *iter = zmalloc(sizeof(*iter));
// 设置字典引用
iter->d = d;
// 指向ht[0]哈希表
iter->table = 0;
iter->index = -1;
// 非安全模式
iter->safe = 0;
iter->entry = NULL;
iter->nextEntry = NULL;
return iter;
}
// 安全迭代器
dictIterator *dictGetSafeIterator(dict *d) {
dictIterator *i = dictGetIterator(d);
i->safe = 1;
return i;
}
8.3 获取下一元素
// 使用迭代器获取下一元素
// 按照哈希表数组、bucket数组、节点链表依次遍历节点
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
// entry为null，表示已遍历完一个bucket的链表，或者是第一次使用迭代器
if (iter->entry == NULL) {
// 获取当前的哈希表
dictht *ht = &iter->d->ht[iter->table];
// 如果是初次使用迭代器，设置相关参数
if (iter->index == -1 && iter->table == 0) {
// 若为安全迭代器，则字典的迭代器计数加1
if (iter->safe)
iter->d->iterators++;
// 若为非安全迭代器，计算字典当前状态的指纹
else
iter->fingerprint = dictFingerprint(iter->d);
}
// 遍历完一个bucket，则顺延至下一bucket
iter->index++;
// 若当前哈希表已遍历完
if (iter->index >= (long) ht->size) {
// 若为遍历完ht[0]且正在rehash，则还需要遍历ht[1]；否则ht[1]为空，不需遍历
if (dictIsRehashing(iter->d) && iter->table == 0) {
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else {
break;
}
}
// 开始遍历新的bucket链表，此次返回链表的头节点
iter->entry = ht->table[iter->index];
} else { // 还在遍历一个bucket链表
// 将下一节点设置为当前节点
iter->entry = iter->nextEntry;
}
if (iter->entry) {
// 设置下一节点
iter->nextEntry = iter->entry->next;
// 返回当前节点
return iter->entry;
}
}
return NULL;
}
8.4 释放迭代器
void dictReleaseIterator(dictIterator *iter)
{
if (!(iter->index == -1 && iter->table == 0)) { // 如果迭代器使用过
if (iter->safe) // 若为安全模式，字典迭代器计数减1
iter->d->iterators--;
else // 若为非安全模式，检查迭代期间字典是否变更
assert(iter->fingerprint == dictFingerprint(iter->d));
}
// 释放迭代器内存
zfree(iter);
}
