Redis(版本4.0)日记20210815--哈希表(hashtable)

// hashtable的数据结构
typedef struct dict {
    // 包含一个dictht的数组，里面有两个dictht，
    // ht[1]在rehash过程中使用
    dictht ht[2]; 
    void *privatedata;
    // 这个结构体包含了一些动态实现方法，
    // 比如hashfunction在不同场合
    // 下实现是不一样的
    dictType *type;
    // rehash时使用 rehashidx==-1
    // 时表示没有进行rehash，
    // rehash过程中则记录当前正在rehash的桶
    // 的索引信息
    long rehashidx;
} dict;


// 真正的hashtable体
typedef struct dictht {
    // 元素数组
    dictEntry **table;
    // 数组大小
    unsigned long size;
    // sizemask = size - 1 用于计算数据
    // 所属的index
    unsigned long sizemask; 
    // 当前table中元素个数
    unsigned long used;
} dictht;


typedef stuct dictEntry {
    void *key;
    // 这个union的val设计也是为了在不同场景
    // 下存储不同类型时使用的
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // hash冲突时记录下一个数据的指针
    struct dictEntry *next; 
} dictEntry;


// 这个dictType用于实现不同底层实现时
// 动态初始化hashtable
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;
复制

// 用于set底层实现时的dictType
dictType setDictType = {
    dictSdsHash,               /* hash function */
    NULL,                      /* key dup */
    NULL,                      /* val dup */
    dictSdsKeyCompare,         /* key compare */
    dictSdsDestructor,         /* key destructor */
    NULL                       /* val destructor */
};
// 用于hash底层实现时的dictType
/* Hash type hash table (note that small hashes are represented with ziplists) */
dictType hashDictType = {
    dictSdsHash,                /* hash function */
    NULL,                       /* key dup */
    NULL,                       /* val dup */
    dictSdsKeyCompare,          /* key compare */
    dictSdsDestructor,          /* key destructor */
    dictSdsDestructor,          /* val destructor */
    NULL                        /* allow to expand */
};
复制

#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d), _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 dictSetDoubleVal(entry, _val_) \
    do { (entry)->v.d = _val_; } while(0)
复制

void setExpire(client *c, redisDb *db, robj *key, long long when) {
    dictEntry *kde, *de;
    // ...
    dictSetSignedIntegerVal(de,when);
    // ...
}
复制

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
    // ...
    /* Try to do a rehashing work proportional to 'count'. */
    for (j = 0; j < count; j++) {
        if (dictIsRehashing(d))
            _dictRehashStep(d);
        else
            break;
    }
    // ...
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    // ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // ...
}
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    // ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // ...
}
dictEntry *dictFind(dict *d, const void *key)
{
    // ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // ...
}
dictEntry *dictGetRandomKey(dict *d)
{
    // ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // ...
}
复制

// dict.c中
// 看这个方法可以知道，渐进式rehash，每次调用这个方法只
static void _dictRehashStep(dict *d) {
    // 没有进行迭代时，才j进行rehash
    if (d->iterators == 0) dictRehash(d,1);
}
// dict.h中
// 判断rehashidx是否为-1
#define dictIsRehashing(d) ((d)->rehashidx != -1)
复制

// 返回1，表示还有key没有从H1移动到H2
// 返回0，表示已经rehash完成
// 入参数n表示要进行rehash的桶的个数
int dictRehash(dict *d, int n) {
    // 最多遍历的空桶数量
    int empty_visit = n*10;
    // 如果没有进行rehash，直接返回
    if (!dictIsRehashing(d)) return 0;
    
    // 遍历进行rehash
    // d->ht[0].used != 0保证了d->ht[0].size > d->rehashidx
    // 即rehashidx不会overflow
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        // 循环查找一个非空的桶，最多查找empty_visit次
        while (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visit == 0) return 1;
        }
        // 找到了一个非空的桶
        de = d->ht[0].table[d->rehashidx];
        // 遍历非空桶，将里面的数据转移到H1的指定桶中
        // 桶中装的是一个单链表
        while(de) {
            uint64_t h;
            
            nextde = de->next;
            // 得到在H1中桶的位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 将de的后继节点指向桶当前的节点
            de->next = d->ht[1].table[h];
            // 将桶的当前节点t替换成de
            d->ht[1].table[h] = de;
            // 增加H1的used
            d->ht[1].used++;
            // 减少H0的used
            d->ht[0].used--;
            // 继续下一轮遍历
            de = nextde;
        }
        // 将转移完的H0的table对应索引数据清空
        d->ht[0].table[d->rehashidx] = NULL;
        // 将rehashidx++,继续进行下一个桶的转移
        d->rehashidx++;
    }
    
    // 如果都转移完了
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table); // 释放ht[0]的数组
        d->ht[0] = d->ht[1]; // 将ht[0]指向ht[1]
        _dictReset(&d->ht[1]); // 重置ht[1]，备后续rehash使用
        d->rehashidx = -1; // 重置rehashidx为-1
        return 0;
    }
    // 还有需要进行转移的key
    return 1;
}
复制