Redis 3.0.4 字典

redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表，而每个哈希表节点就保存了字典中的一个键值对。

1.哈希表　　　　

typedef struct dictht {  //哈希表
    dictEntry **table;      //存放一个数组的地址，数组存放着哈希表节点dictEntry的地址
    unsigned long size;     //哈希表table的大小.初始化大小是4
    unsigned long sizemask; //用于将哈希值映射到table的位置索引,它的值总是等于size-1
    unsigned long used;     //记录哈希表已有的节点的数值
} dictht;

2.哈希表节点

typedef struct dictEntry {
    void *key;          //key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; //value
    struct dictEntry *next; //指向下一个节点的指针
} dictEntry;

3.字典

typedef struct dict {
    dictType *type; //指向dictType结构，dictType结构中包含自定义的函数，这些函数使得key和value能够存储任何类型的数据。
    void *privdata; //私有数据
    dictht ht[2];    //ht[0] ht[1] 
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
typedef struct dictType {
    unsigned int (*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;

哈希结构图如图：

4.哈希算法

　　要将一个键值加入到字典里面，程序会先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组指定索引上面。

　　1.用于计算整型值的hash算法

/* Thomas Wang‘s 32 bit Mix Function */
unsigned int dictIntHashFunction(unsigned int key)
{   
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}

　　2.MurmurHash2哈希算法

　　优点是：即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快

//MurmurHash2哈希算法
unsigned int dictGenHashFunction(const void *key, int len) {
    /* ‘m‘ and ‘r‘ are mixing constants generated offline.
     They‘re not really ‘magic‘, they just happen to work well.  */
    uint32_t seed = dict_hash_function_seed;
    const uint32_t m = 0x5bd1e995;
    const int r = 24;

    /* Initialize the hash to a ‘random‘ value */
    uint32_t h = seed ^ len;

    /* Mix 4 bytes at a time into the hash */
    const unsigned char *data = (const unsigned char *)key;

    while(len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    /* Handle the last few bytes of the input array  */
    switch(len) {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0]; h *= m;
    };

    /* Do a few final mixes of the hash to ensure the last few
     * bytes are well-incorporated. */
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return (unsigned int)h;
}

　　3.djb哈希算法

　　　　算法的思想是利用字符串中的ascii码值与一个随机seed，通过len次变换，得到最后的hash值。

//djb哈希算法
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)dict_hash_function_seed;

    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
    return hash;
}

5.解决键冲突

　　如果是有键值对被分配到哈希表数组的同一个索引上面，redis的哈希表利用链表地址法，每一个哈希表节点都有一个next指针，多个哈希表节点都有一个next指针，多个哈希表可以用next指针构成一个单链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。也就是哈希链表(忘记是在那本书上看到过还是哪个学长讲过)

6.rehash

　　rehash是随着操作的不断执行，哈希表保存的键值对会逐渐增多或减少，为了使哈希表的负载因子维持在一个合理的范围内，当哈希表保存饿键值对数量太多或者太少时，程序都要对哈希表进行rehash。

　　rehash分为三步：

　　　　1.为ht[1]分配合适空间大小；

　　　　　　如果是执行的扩容操作ht[1]分配的空间大小是第一个大于等于ht[0].used*2的 pow(2,n);

　　　　　　如果是执行的缩容操作ht[1]分配的空间大小是第一个大于等于ht[0].used的pow(2,n);

　　　　2.将ht[0]中所有的键值对重新计算键的hash值和索引值，然后将键值对放置到ht[1]上；

　　　　3.当所有的ht[0]都迁移到ht[1]之后，释放ht[0],将ht[1]置为ht[0]，并给ht[1]新创建一个空的hash表

　　程序会自动rehash操作：

　　　　1.服务器目前没有在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于1；

　　　　2.服务器目前在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于5；

　　负载因子load_factor = ht[0].used / ht[0].size

//根据size调整d的哈希表
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size); // 获取第一个pow(2,x) 大于size的数


    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    //dictIsRehashing查看当前dict是否在rehash
    //已有键值对的数量大于size
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    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. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

7.渐进式rehash

哈希表渐进式rehash步骤:

　　1.为ht[1]分配空间，让字典同时拥有ht[0]和ht[1]两个哈希表；

　　2.在字典中维持一个索引计数器变量，rehashidx,并将值值为0，表示rehash开始；

　　3.在rehash期间，每次对字典执行增删查改操作时，程序除了执行指定的操作，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash完成后，程序将rehashidx属性值增一；

　　4.随着字典操作的不断执行，最终在某个时间点上ht[0]的所有键值对都会被rehash到ht[1]，这时程序会讲rehashidx属性值为-1；

　　渐进式rehash将rehash键值所需的计算工作均摊到对字典的操作上，从而避免集中式rehash带来庞大的计算量。

//单步迭代  只有在dict的索引为0时开始
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}
//n步进行rehash
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;

        /* Note that rehashidx can‘t overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        //dictEntry[rehashidx] 不为空
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        //遍历hash table[rehashidx]的全链表
        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++;
    }

    /* Check if we already rehashed the whole table... */
    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;
    }

    /* More to rehash... */
    return 1;
}