redis源码分析3|*|#8212;结构体|*|#8212;字典_redis占用分析

hash表节点

key保存键值对中的键,v为值,union表示三个钟选择一个,next是指向另一个hash表节点的指针,这个指针可以将多个hash值相同的键值对连接在一起,以此来解决冲突的问题；

比如

字典结构

看完小编介绍的,没有rehash的字节结构图如下

扩展或收缩hash表的方式

值得注意的是,在hash的扩展或者收缩的时候,并不是在某一时间内快速完成的,而是分多次,渐进的完成的.

补充说明一下：在渐进式rehash中的时候,字典的删除,查找,更新等操作会在两个hash表上进行.

// 释放给定字典节点的值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
    (d)->type->valDestructor((d)->privdata, (entry)->v.val)

// 设置给定字典节点的值
#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)

// 将一个有符号整数设为节点的值
#define dictSetSignedIntegerVal(entry, _val_) \
do { entry->v.s64 = _val_; } while(0)

// 将一个无符号整数设为节点的值
#define dictSetUnsignedIntegerVal(entry, _val_) \
do { entry->v.u64 = _val_; } while(0)

// 释放给定字典节点的键
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
    (d)->type->keyDestructor((d)->privdata, (entry)->key)

// 设置给定字典节点的键
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
    entry->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
    entry->key = (_key_); \
} while(0)

// 比对两个键
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
    (d)->type->keyCompare((d)->privdata, key1, key2) : \
    (key1) == (key2))

// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
// 返回获取给定节点的键
#define dictGetKey(he) ((he)->key)
// 返回获取给定节点的值
#define dictGetVal(he) ((he)->v.val)
// 返回获取给定节点的有符号整数值
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
// 返回给定节点的无符号整数值
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
// 返回给定字典的大小
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
// 返回字典的已有节点数量
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
// 查看字典是否正在 rehash
#define dictIsRehashing(ht) ((ht)->rehashidx != -1)

/* Create a new hash table */
/*
 * 创建一个新的字典
 *
 * T = O(1)
 */
dict *dictCreate(dictType *type,
    void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));

return d;
}

/* Initialize the hash table */
/*
 * 初始化哈希表
 *
 * T = O(1)
 */
int _dictInit(dict *d, dictType *type,
    void *privDataPtr)
{
// 初始化两个哈希表的各项属性值
// 但暂时还不分配内存给哈希表数组
_dictReset(d->ht[0]);
_dictReset(d->ht[1]);

// 设置类型特定函数
d->type = type;

// 设置私有数据
d->privdata = privDataPtr;

// 设置哈希表 rehash 状态
d->rehashidx = -1;

// 设置字典的安全迭代器数量
d->iterators = 0;

return DICT_OK;
}

/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
/*
 * 缩小给定字典
 * 让它的已用节点数和字典大小之间的比率接近 1:1
 *
 * 返回 DICT_ERR 表示字典已经在 rehash ,或者 dict_can_resize 为假.
 *
 * 成功创建体积更小的 ht[1] ,可以开始 resize 时,返回 DICT_OK.
 *
 * T = O(N)
 */
int dictResize(dict *d)
{
int minimal;

// 不能在关闭 rehash 或者正在 rehash 的时候调用
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;

// 计算让比率接近 1：1 所需要的最少节点数量
minimal = d->ht[0].used;
if (minimal < DICT_HT_INITIAL_SIZE)
    minimal = DICT_HT_INITIAL_SIZE;

// 调整字典的大小
// T = O(N)
return dictExpand(d, minimal);
}

/* Expand or create the hash table */
/*
 * 创建一个新的哈希表,并根据字典的情况,选择以下其中一个动作来进行：
 *
 * 1) 如果字典的 0 号哈希表为空,那么将新哈希表设置为 0 号哈希表
 * 2) 如果字典的 0 号哈希表非空,那么将新哈希表设置为 1 号哈希表,
 *    并打开字典的 rehash 标识,使得程序可以开始对字典进行 rehash
 *
 * size 参数不够大,或者 rehash 已经在进行时,返回 DICT_ERR .
 *
 * 成功创建 0 号哈希表,或者 1 号哈希表时,返回 DICT_OK .
 *
 * T = O(N)
 */
int dictExpand(dict *d, unsigned long size)
{
// 新哈希表
dictht n; /* the new hash table */

// 根据 size 参数,计算哈希表的大小
// T = O(1)
unsigned long realsize = _dictNextPower(size);

/* the size is invalid if it is smaller than the number of
 * elements already inside the hash table */
// 不能在字典正在 rehash 时进行
// size 的值也不能小于 0 号哈希表的当前已使用节点
if (dictIsRehashing(d) || d->ht[0].used > size)
    return DICT_ERR;

/* Allocate the new hash table and initialize all pointers to NULL */
// 为哈希表分配空间,并将所有指针指向 NULL
n.size = realsize;
n.sizemask = realsize-1;
// T = O(N)
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;

/* Is this the first initialization? If so it's not really a rehashing
 * we just set the first hash table so that it can accept keys. */
// 如果 0 号哈希表为空,那么这是一次初始化：
// 程序将新哈希表赋给 0 号哈希表的指针,然后字典就可以开始处理键值对了.
if (d->ht[0].table == NULL) {
    d->ht[0] = n;
    return DICT_OK;
/* Prepare a second hash table for incremental rehashing */
// 如果 0 号哈希表非空,那么这是一次 rehash ：
// 程序将新哈希表设置为 1 号哈希表,
// 并将字典的 rehash 标识打开,让程序可以开始对字典进行 rehash
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;

/* 顺带一提,上面的代码可以重构成以下形式：

*/
}

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * 执行 N 步渐进式 rehash .
 *
 * 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表,
 * 返回 0 则表示所有键都已经迁移完毕.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table.
 *
 * 注意,每步 rehash 都是以一个哈希表索引（桶）作为单位的,
 * 一个桶里可能会有多个节点,
 * 被 rehash 的桶里的所有节点都会被移动到新哈希表.
 *
 * T = O(N)
 */
int dictRehash(dict *d, int n) {

// 只可以在 rehash 进行中时执行
if (!dictIsRehashing(d)) return 0;

// 进行 N 步迁移
// T = O(N)
while(n--) {
    dictEntry *de, *nextde;

    /* Check if we already rehashed the whole table... */
    // 如果 0 号哈希表为空,那么表示 rehash 执行完毕
    // T = O(1)
    if (d->ht[0].used == 0) {
        // 释放 0 号哈希表
        zfree(d->ht[0].table);
        // 将原来的 1 号哈希表设置为新的 0 号哈希表
        d->ht[0] = d->ht[1];
        // 重置旧的 1 号哈希表
        _dictReset(d->ht[1]);
        // 关闭 rehash 标识
        d->rehashidx = -1;
        // 返回 0 ,向调用者表示 rehash 已经完成
        return 0;
    /* Note that rehashidx can't overflow as we are sure there are more
     * elements because ht[0].used != 0 */
    // 确保 rehashidx 没有越界
    assert(d->ht[0].size > (unsigned)d->rehashidx);

    // 略过数组中为空的索引,找到下一个非空索引
    while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

    // 指向该索引的链表表头节点
    de = d->ht[0].table[d->rehashidx];
    /* Move all the keys in this bucket from the old to the new hash HT */
    // 将链表中的所有节点迁移到新哈希表
    // T = O(1)
    while(de) {
        unsigned int h;

        // 保存下个节点的指针
        nextde = de->next;

        /* Get the index in the new hash table */
        // 计算新哈希表的哈希值,以及节点插入的索引位置
        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;
    // 更新 rehash 索引
    d->rehashidx++;
return 1;
}

/*
 * 返回以毫秒为单位的 UNIX 时间戳
 *
 * T = O(1)
 */
long long timeInMilliseconds(void) {
struct timeval tv;

gettimeofday(tv,NULL);
return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
/*
 * 在给定毫秒数内,以 100 步为单位,对字典进行 rehash .
 *
 * T = O(N)
 */
int dictRehashMilliseconds(dict *d, int ms) {
// 记录开始时间
long long start = timeInMilliseconds();
int rehashes = 0;

while(dictRehash(d,100)) {
    rehashes += 100;
    // 如果时间已过,跳出
    if (timeInMilliseconds()-start > ms) break;
return rehashes;
}

/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * 在字典不存在安全迭代器的情况下,对字典进行单步 rehash .
 *
 * 字典有安全迭代器的情况下不能进行 rehash ,
 * 因为两种不同的迭代和修改操作可能会弄乱字典.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used.
 *
 * 这个函数被多个通用的查找、更新操作调用,
 * 它可以让字典在被使用的同时进行 rehash .
 *
 * T = O(1)
 */
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}

/* Add an element to the target hash table */
/*
 * 尝试将给定键值对添加到字典中
 *
 * 只有给定键 key 不存在于字典时,添加操作才会成功
 *
 * 添加成功返回 DICT_OK ,失败返回 DICT_ERR
 *
 * 最坏 T = O(N) ,平滩 O(1)
 */
int dictAdd(dict *d, void *key, void *val)
{
// 尝试添加键到字典,并返回包含了这个键的新哈希节点
// T = O(N)
dictEntry *entry = dictAddRaw(d,key);

// 键已存在,添加失败
if (!entry) return DICT_ERR;

// 键不存在,设置节点的值
// T = O(1)
    dictSetVal(d, entry, val);

// 添加成功
return DICT_OK;
}

/* Low level add. This function adds the entry but instead of setting
 * a value returns the dictEntry structure to the user, that will make
 * sure to fill the value field as he wishes.
 *
 * This function is also directly exposed to user API to be called
 * mainly in order to store non-pointers inside the hash value, example:
 *
 * entry = dictAddRaw(dict,mykey);
 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 * Return values:
 *
 * If key already exists NULL is returned.
 * If key was added, the hash entry is returned to be manipulated by the caller.
 */
/*
 * 尝试将键插入到字典中
 *
 * 如果键已经在字典存在,那么返回 NULL
 *
 * 如果键不存在,那么程序创建新的哈希节点,
 * 将节点和键关联,并插入到字典,然后返回节点本身.
 *
 * T = O(N)
 */
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;

// 如果条件允许的话,进行单步 rehash
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);

/* Get the index of the new element, or -1 if
 * the element already exists. */
// 计算键在哈希表中的索引值
// 如果值为 -1 ,那么表示键已经存在
// T = O(N)
if ((index = _dictKeyIndex(d, key)) == -1)
    return NULL;

// T = O(1)
/* Allocate the memory and store the new entry */
// 如果字典正在 rehash ,那么将新键添加到 1 号哈希表
// 否则,将新键添加到 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++;

/* Set the hash entry fields. */
// 设置新节点的键
// T = O(1)
    dictSetKey(d, entry, key);

return entry;
}

/* Add an element, discarding the old if the key already exists.
 *
 * 将给定的键值对添加到字典中,如果键已经存在,那么删除旧有的键值对.
 *
 * Return 1 if the key was added from scratch, 0 if there was already an
 * element with such key and dictReplace() just performed a value update
 * operation.
 *
 * 如果键值对为全新添加,那么返回 1 .
 * 如果键值对是通过对原有的键值对更新得来的,那么返回 0 .
 *
 * T = O(N)
 */
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, auxentry;

/* Try to add the element. If the key
 * does not exists dictAdd will suceed. */
// 尝试直接将键值对添加到字典
// 如果键 key 不存在的话,添加会成功
// T = O(N)
if (dictAdd(d, key, val) == DICT_OK)
    return 1;

/* It already exists, get the entry */
// 运行到这里,说明键 key 已经存在,那么找出包含这个 key 的节点
// T = O(1)
entry = dictFind(d, key);
/* Set the new value and free the old one. Note that it is important
 * reverse. */
// 先保存原有的值的指针
auxentry = *entry;
// 然后设置新的值
// T = O(1)
    dictSetVal(d, entry, val);
// 然后释放旧值
// T = O(1)
dictFreeVal(d, auxentry);

return 0;
}

/* dictReplaceRaw() is simply a version of dictAddRaw() that always
 * returns the hash entry of the specified key, even if the key already
 * exists and can't be added (in that case the entry of the already
 * existing key is returned.)
 *
 * See dictAddRaw() for more information. */
/*
 * dictAddRaw() 根据给定 key 释放存在,执行以下动作：
 *
 * 1) key 已经存在,返回包含该 key 的字典节点
 * 2) key 不存在,那么将 key 添加到字典
 *
 * 不论发生以上的哪一种情况,
 * dictAddRaw() 都总是返回包含给定 key 的字典节点.
 *
 * T = O(N)
 */
dictEntry *dictReplaceRaw(dict *d, void *key) {

// 使用 key 在字典中查找节点
// T = O(1)
dictEntry *entry = dictFind(d,key);

// 如果节点找到了直接返回节点,否则添加并返回一个新节点
// T = O(N)
return entry ? entry : dictAddRaw(d,key);
}

/* Search and remove an element */
/*
 * 查找并删除包含给定键的节点
 *
 * 参数 nofree 决定是否调用键和值的释放函数
 * 0 表示调用,1 表示不调用
 *
 * 找到并成功删除返回 DICT_OK ,没找到则返回 DICT_ERR
 *
 * T = O(1)
 */
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 */

// 进行单步 rehash ,T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);

// 计算哈希值
h = dictHashKey(d, key);

// 遍历哈希表
// T = O(1)
for (table = 0; table <= 1; table++) {

    // 计算索引值
    idx = h  d->ht[table].sizemask;
    // 指向该索引上的链表
    he = d->ht[table].table[idx];
    prevHe = NULL;
    // 遍历链表上的所有节点
    // T = O(1)
    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) {
            // 释放节点本身
                zfree(he);

            // 更新已使用节点数量
            d->ht[table].used--;

            // 返回已找到信号
            return DICT_OK;
        prevHe = he;
        he = he->next;
    // 如果执行到这里,说明在 0 号哈希表中找不到给定键
    // 那么根据字典是否正在进行 rehash ,决定要不要查找 1 号哈希表
    if (!dictIsRehashing(d)) break;
// 没找到
return DICT_ERR; /* not found */
}

/*
 * 从字典中删除包含给定键的节点
 *
 * 并且调用键值的释放函数来删除键值
 *
 * 找到并成功删除返回 DICT_OK ,没找到则返回 DICT_ERR
 * T = O(1)
 */
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0);
}

/*
 * 从字典中删除包含给定键的节点
 *
 * 但不调用键值的释放函数来删除键值
 *
 * 找到并成功删除返回 DICT_OK ,没找到则返回 DICT_ERR
 * T = O(1)
 */
int dictDeleteNoFree(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}

/* Destroy an entire dictionary */
/*
 * 删除哈希表上的所有节点,并重置哈希表的各项属性
 *
 * T = O(N)
 */
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
unsigned long i;

/* Free all the elements */
// 遍历整个哈希表
// T = O(N)
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;

    // 遍历整个链表
    // T = O(1)
    while(he) {
        nextHe = he->next;
        // 删除键
            dictFreeKey(d, he);
        // 删除值
            dictFreeVal(d, he);
        // 释放节点
            zfree(he);

        // 更新已使用节点计数
        ht->used--;

        // 处理下个节点
        he = nextHe;
/* Free the table and the allocated cache structure */
// 释放哈希表结构
zfree(ht->table);

/* Re-initialize the table */
// 重置哈希表属性
    _dictReset(ht);

return DICT_OK; /* never fails */
}

/* Clear  Release the hash table */
/*
 * 删除并释放整个字典
 *
 * T = O(N)
 */
void dictRelease(dict *d)
{
// 删除并清空两个哈希表
_dictClear(d,d->ht[0],NULL);
_dictClear(d,d->ht[1],NULL);
// 释放节点结构
    zfree(d);
}