［Redis源码阅读］dict字典的实现

> set msg "hello"

> hset people name "hoohack"

/* 字典结构 每个字典有两个哈希表，实现渐进式哈希时需要用在将旧表rehash到新表 */
typedef struct dict {
    dictType *type; /* 类型特定函数 */
    void *privdata; /* 保存类型特定函数需要使用的参数 */
    dictht ht[2]; /* 保存的两个哈希表，ht[0]是真正使用的，ht[1]会在rehash时使用 */
    long rehashidx; /* rehashing not in progress if rehashidx == -1 rehash进度，如果不等于-1，说明还在进行rehash */
    unsigned long iterators; /* number of iterators currently running 正在运行中的遍历器数量 */
} dict;

/* 哈希表结构 */
typedef struct dictht {
    dictEntry **table; /* 哈希表节点数组 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /* 哈希表大小掩码，用于计算哈希表的索引值，大小总是dictht.size - 1 */
    unsigned long used; /* 哈希表已经使用的节点数量 */
} dictht;

/* 哈希表节点 */
typedef struct dictEntry {
    void *key; /* 键名 */
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; /* 值 */
    struct dictEntry *next; /* 指向下一个节点, 将多个哈希值相同的键值对连接起来*/
} dictEntry;

/* 保存一连串操作特定类型键值对的函数 */
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;

／* 实现渐进式的重新哈希，如果还有需要重新哈希的key，返回1，否则返回0
 *
 * 需要注意的是，rehash持续将bucket从老的哈希表移到新的哈希表，但是，因为有的哈希表是空的，
 * 因此函数不能保证即使一个bucket也会被rehash，因为函数最多一共会访问N*10个空bucket，不然的话，函数将会耗费过多性能，而且函数会被阻塞一段时间
 */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

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

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        /* 找到非空的哈希表下标 */
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        
        /* 实现将bucket从老的哈希表移到新的哈希表 */
        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;
        d->rehashidx++;
    }

    /* 如果已经完成了，释放旧的哈希表，返回0 */
    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;
    }

    /* 继续下一次rehash */
    return 1;
}

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

    ／* 如果正在rehash，顺带执行rehash操作 */
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* 获取新元素的下标，如果已经存在，返回-1 */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 如果正在进行rehash操作，返回ht[1],否则返回ht[0]
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

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