🌸 dict

• hash & set 的底层数据结构

地址

• 添加、删除、查找 节点时会进行 渐进式 rehash 操作
• hash 冲突时，采用 拉链法，同一下标下的查找为 链表的查找

1. 数据结构

// 1.1 定义 节点类，存储单个节点的 k-v 
typedef struct dictEntry {
    void *key; // key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // val
    struct dictEntry *next;     // 数组同一下标下的下一个节点
    void *metadata[];           /* 允许 额外放一些 元数据 到节点中 */
} dictEntry;

// 1.2 定义 dictType 类，包含若干函数指针，用于 dict 的调用者对 key-val 的各种操作进行自定义
typedef struct dictType {
    // 1) 对 key 进行 hash 值计算的 hash 算法
    uint64_t (*hashFunction)(const void *key); 
    // 2) 对 key 的拷贝函数，用于需要时对 key 进行深拷贝，而不仅仅是传递对象指针
    void *(*keyDup)(dict *d, const void *key);
    // 3) 对 val 的拷贝函数，用于需要时对 val 进行深拷贝，而不仅仅是传递对象指针
    void *(*valDup)(dict *d, const void *obj);
    // 4) 两个 key 的比较操作，在根据 key 进行查找时会被用到
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    // 5) 对 key 的析构函数
    void (*keyDestructor)(dict *d, void *key);
    // 6) 对 val 的析构函数
    void (*valDestructor)(dict *d, void *obj);
    // 7) 
    int (*expandAllowed)(size_t moreMem, double usedRatio);
     // 8) 允许 dictEntry 节点类携带额外 被调用者声明的元数据，当 节点类初始化时，被赋值为 0
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

// 1.3 定义 dict 类
typedef struct dict dict;

// 2. 定义 dict 结构
struct dict {
    dictType *type; // 指向 dictType 类，里面有一些方法可以调用

    // 2 个 hash 表。在重 hash 的过程中，增量更新；平时情况下，ht_table[0] 有效，ht_table[1] 为空
    dictEntry **ht_table[2]; 
    // 记录 每个 hash 表中现有节点数
    unsigned long ht_used[2];

    // 重 hash 过程中，当前进行到的下标；若否，则为 -1
    long rehashidx; 

    // 若 > 0 说明 重 hash 过程 被暂停；若 < 0 说明出现错误；正常情况下应该 == 0
    int16_t pauserehash; 
    // size = 1<<exp 所以 exp 表示 1 左移多少位后为 当前数组长度
    signed char ht_size_exp[2]; 
};

 // 若 safe == 1 表示 迭代器是线程安全的，此时遍历时，可以调用 dictAdd, dictFind, and other functions
 // 否则，迭代器非线程安全，遍历时，只能调用 dictNext()
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    unsigned long long fingerprint;
} dictIterator;

2. 创建

/* Create a new hash table */
dict *dictCreate(dictType *type)
{
    dict *d = zmalloc(sizeof(*d)); // 分配空间

    _dictInit(d,type); // 赋初值
    return d;
}
/* 初始化 */
int _dictInit(dict *d, dictType *type)
{
    _dictReset(d, 0);
    _dictReset(d, 1);
    d->type = type;
    d->rehashidx = -1;
    d->pauserehash = 0;
    return DICT_OK;
}
/* 重置 hash 的 2 个表 */
static void _dictReset(dict *d, int htidx)
{
    d->ht_table[htidx] = NULL;
    d->ht_size_exp[htidx] = -1;
    d->ht_used[htidx] = 0;
}

3. 常见方法

1) 添加元素

// 1. 添加 key 节点，若已经存在 key，添加失败
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    // entry == null 说明 该 key 已经存在，返回 DICT_ERR
    if (!entry) return DICT_ERR;
    // entry != null 说明 不存在该 key，返回 DICT_OK
    dictSetVal(d, entry, val);
    return DICT_OK;
}

// 2. 添加 key 节点，若已经存在，覆盖原值
// 若是新节点，返回 1；若是覆盖原值，返回 0
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    entry = dictAddRaw(d,key,&existing); // 这里 *existing 之前并没有初始化，因此为 null 
    // entry != null 说明是 添加新节点
    if (entry) { 
        dictSetVal(d, entry, val);
        return 1;
    }

    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    auxentry = *existing;
    dictSetVal(d, existing, val);
    dictFreeVal(d, &auxentry);
    return 0;
}
/* 
 * 若 key 已经存在，返回 null，且若 **existing != null 则覆盖旧值；若 **existing == null 则不覆盖旧值
 * 若 key 不存在，添加新节点，并返回 新节点
 */
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    int htidx;

    // 1. 若正在重哈希过程中，协助 重哈希
    if (dictIsRehashing(d)) _dictRehashStep(d);

     // 2. 获得 key 对应的数组下标，若下标为 -1 说明不存在，返回 null
     // 在此过程中，可能触发 扩容操作
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

     // 3. 采用 头插法，基于 新数据接下来被访问的概率比较高 这一假设，这样查找起来更快一些
     // 判断是否在重哈希中，若是，插入到 h[1]；若否，插入到 h[0]
    htidx = dictIsRehashing(d) ? 1 : 0;
    size_t metasize = dictMetadataSize(d); // 如果有额外元数据，还需要存放元数据的空间
    entry = zmalloc(sizeof(*entry) + metasize); // 给节点分配内存
    if (metasize > 0) {
        memset(dictMetadata(entry), 0, metasize);
    }
    entry->next = d->ht_table[htidx][index];
    d->ht_table[htidx][index] = entry; // 头插法
    d->ht_used[htidx]++; // 节点数量 ++

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

 // 重哈希，当且仅当 pauserehash == 0 时才会触发 重哈希
static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

// 判断 dict 是否处于 重哈希 中
#define dictIsRehashing(d) ((d)->rehashidx != -1)

/* 
 * 每次该方法的调用，负责迁移 n 个节点
 * 若在迁移过程中遇到 10n 个节点，也返回
 * 若全部迁移完成，返回 0；若本次调用迁移工作完成，返回 1
 * */
int dictRehash(dict *d, int n) {
    // 最多遇到 10n 个空节点后，直接返回
    int empty_visits = n*10; 
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht_used[0] != 0) {
        dictEntry *de, *nextde;

        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        // 遇到 null 节点，直接增加步数，此时若累积达到 10n 个空节点，直接返回
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            // 本线程工作迁移完成，返回 1，但是 d->ht_used[0] != 0 说明还存在节点等待重哈希
            if (--empty_visits == 0) return 1; 
        }
        // 说明遇到非空节点，且自己需要负责前移该节点的工作
        de = d->ht_table[0][d->rehashidx]; // 当前下标的头节点
        while(de) {
            uint64_t h;

            nextde = de->next;
            // 获取当前 key 对应新数组的 下标
            h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            // 迁移
            de->next = d->ht_table[1][h];
            d->ht_table[1][h] = de;
            d->ht_used[0]--;
            d->ht_used[1]++;
            de = nextde;
        }
        d->ht_table[0][d->rehashidx] = NULL; // 清空
        d->rehashidx++;
    }

    /* 本线程迁移工作完成后，判断是否全部迁移完成，若是，释放 h[0] 内存，交换 h[0] & h[1] 并重置 h[1] */
    if (d->ht_used[0] == 0) {
        zfree(d->ht_table[0]);
        /* Copy the new ht onto the old one */
        d->ht_table[0] = d->ht_table[1];
        d->ht_used[0] = d->ht_used[1];
        d->ht_size_exp[0] = d->ht_size_exp[1];
        _dictReset(d, 1);
        d->rehashidx = -1;
        return 0;
    }

    /* 还有节点需要迁移 */
    return 1;
}

// 获取 key 所在数组下标
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing);

/* 数组扩容，若内存分配失败，则返回 错误 */
int dictExpand(dict *d, unsigned long size) {
    return _dictExpand(d, size, NULL);
}

// 数组扩容
// 若 malloc_failed != null --> malloc_failed = 0 --> 允许内存分配失败，无论如何都要分配内存给新数组
// 若 malloc_failed == null --> 内存分配失败，返回 错误
// 
// 新数组大小，可以看出，变为原来的 2 倍
// 负载因子 = 节点数 / 数组长度
// 1. 若 负载因子 >= 1 && 没有在执行 bgsave | bgrewiteaof，会执行 rehash
// 2. 若 Redis 正在执行 bgsave | bgrewiteaof，只有当节点数 >= 5 * 数组长度时，才会进行 强制扩容
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    // 重哈希中 | 数组节点数与 size 关系不正确时，返回 错误
    if (dictIsRehashing(d) || d->ht_used[0] > size)
        return DICT_ERR;

    dictEntry **new_ht_table; // 存放扩容后的数组
    unsigned long new_ht_used;
    signed char new_ht_size_exp = _dictNextExp(size);

    size_t newsize = 1ul<<new_ht_size_exp; // 新数组大小，可以看出，变为原来的 2 倍
    if (newsize < size || newsize * sizeof(dictEntry*) < newsize)
        return DICT_ERR;

    /* 左移位数和原来一样，返回 错误 */
    if (new_ht_size_exp == d->ht_size_exp[0]) return DICT_ERR;

    /* 给新数组分配内存 */
    if (malloc_failed) {
        new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*)); // 尝试分配内存
        *malloc_failed = new_ht_table == NULL;
        if (*malloc_failed) // 内存分配失败，返回 错误
            return DICT_ERR;
    } else
        new_ht_table = zcalloc(newsize*sizeof(dictEntry*)); // 无论如何都要分配内存

    new_ht_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. */
    if (d->ht_table[0] == NULL) {
        d->ht_size_exp[0] = new_ht_size_exp;
        d->ht_used[0] = new_ht_used;
        d->ht_table[0] = new_ht_table;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = new_ht_used;
    d->ht_table[1] = new_ht_table;
    d->rehashidx = 0;
    return DICT_OK;
}

2) 删除元素

/* 删除元素，删除成功，则返回 DICT_OK；若不存在该元素，返回 DICT_ERR  */
// 当 元素个数 < 0.1 * 数组长度时，Redis 会进行 缩容处理，不论是否处于 bgsave 状态
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

/* 删除 key，若存在，返回原节点；若不存在，返回 null
 * nofree == 0 说明需要释放删除的节点内存 */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    /* 1. dict 为空，直接返回 null */
    if (dictSize(d) == 0) return NULL;

    /* 2. 重哈希中，协助重哈希 */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    h = dictHashKey(d, key); // 获取 key 对应的 hash 值

    // 3. 分别在 h[0] & h[1] 中查找
    for (table = 0; table <= 1; table++) {
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]); // 获取对应数组下标
        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) {
                    dictFreeUnlinkedEntry(d, he);
                }
                d->ht_used[table]--;
                return he; // 找到即可返回
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break; // 若不在重哈希中，h[0] 找完也没有找到，无需继续找 h[1]
    }
    return NULL; 
}

/* 清空，释放空间 */
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
    if (he == NULL) return;
    dictFreeKey(d, he);
    dictFreeVal(d, he);
    zfree(he);
}

3) 查找元素

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    // 1. dict 为空，直接返回 null
    if (dictSize(d) == 0) return NULL; 
    
    // 2. 重哈希中，协助迁移
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    h = dictHashKey(d, key); // 计算 hash 值
    
    for (table = 0; table <= 1; table++) {
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he; // 找到，即可返回
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL; // 若不在重哈希中，只需查找 h[0]
    }
    return NULL;
}