Redis 哈希表的实现要点

问题导读：
1.  选择哈希算法时主要考虑哪些因素？
2.  rehash是什么?
3.  渐进式rehash是什么？




哈希算法的选择

针对不同的key使用不同的hash算法，如对整型、字符串以及大小写敏感的字符串分别使用不同的hash算法；

整型的Hash算法使用的是Thomas Wang's 32 Bit / 64 Bit Mix Function ，这是一种基于位移运算的散列方法。基于移位的散列是使用Key值进行移位操作。通常是结合左移和右移。每个移位过程的结果进行累加，最后移位的结果作为最终结果。这种方法的好处是避免了乘法运算，从而提高Hash函数本身的性能。

[mw_shl_code=c,true]    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;
    }[/mw_shl_code]

字符串使用的MurmurHash算法，MurmurHash算法具有高运算性能，低碰撞率的特点，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。

murmur是 multiply and rotate的意思，因为算法的核心就是不断的乘和移位（x *= m; k ^= k >> r;）

[mw_shl_code=c,true]    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;
    }[/mw_shl_code]

一个好的hash算法需要满足两个条件：

1) 性能高，运算足够快；

2) 相邻的数据hash后分布广；即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性；

比如：murmur计算"abc"是1118836419，"abd"是413429783。而使用Horner算法，"abc"是96354， "abd"就比它多1（96355）；


rehash

负载因子 = 当前结点数/桶的大小，超过1表示肯定有碰撞了；碰撞的结点，通过链表拉链起来；

所有哈希表的初始桶的大小为4，根据负载因子的变化进行rehash，重新分配空间（扩展或收缩）

当hash表的负载因子超过1后，进行扩展（小于0.01时，进行收缩）；

所谓扩展，就是新建一个hash表2，将桶的数量增大（具体增大为：第一个大于等于usedSize的2的n次冥）；然后将hash表1中结点都转移到hash表2中；

rehash的触发条件：

当做BGSAVE或BGREWRITEEOF时，负载因子超过5时触发rehash，

没有BGSAVE或BGREWRITEEOF时，负载因子超过1时触发rehash；

在BGSAVE或BGREWRITEEOF时，使用到Linux的写时复制，如果这时候做rehash，将会好用更多的内存空间（没有变化的结点用一份，变化的结点复制一份）


渐进式rehash

一个hash表中的数据可能有几百上千万，不可能一次rehash转移完，需要分批逐渐转移；

在rehash的过程中，对redis的查询、更新操作首先会在hash0中查找，没有找到，然后转到hash1中操作；

对于插入操作，直接插入到hash1中；最终目标是将hash表1变为空表，rehash完成；

value的存储键值对的实现，value 是一个union，对整型和字符串使用不同的存储对象；
[mw_shl_code=c,true]
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;[/mw_shl_code]