Redis 哈希表的实现要点

2016-3-29 | 发布者:数据库开发

(点击上方公号,可快速关注)


转自:大CC

网址:http://www.cnblogs.com/me115/p/4975960.html


哈希算法的选择


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


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


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;

}


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


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


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;

}


一个好的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,对整型和字符串使用不同的存储对象;


// 键

void *key;


// 值

union {

    void *val;

    uint64_t u64;

    int64_t s64;

} v;



【今日微信账号推荐】

更多推荐请看值得关注的技术和设计公众号


其中推荐了包括技术设计极客 和 IT相亲相关的热门公众号。技术涵盖:Python、Web前端、Java、安卓、iOS、PHP、C/C++、.NET、Linux、数据库、运维、大数据、算法、IT职场等。点击《值得关注的技术和设计公众号》,发现精彩!



热门文章

更多

财经迷

上海精准的把自身引爆点调拨到了2020年

上海精准的把自身引爆点调拨到了2020年

卢俊有位好朋友,经常游走在各个政府部门里,经常会接触到各种消息,再加上之前是房地产出身,逻辑紧密且留心各种细节,所以经常会时不时和我说一些猛料。这两天,他和我说了一个最猛的故事以下所有内容我不能告...
真叫卢俊的地产观 • 
东北特钢违约,你在看热闹,我在等机会

东北特钢违约,你在看热闹,我在等机会

天威违约,打破央企金身,东北特钢违约顶翻地方国企信仰。 “违约”呼啸而来。其情形好像债市已经成为是非之地,不宜久留了。这种恐惧似曾相识。记得去年三季度,股市杠杆恐惧的转移效用,使得有声音高喊“债市5...
好买财富 • 
资本狂人如何“搅局”健康产业

资本狂人如何“搅局”健康产业

原标题:美年大健康CEO俞熔独家专访:资本狂人如何“搅局”健康产业投资出身的俞熔更善于资本运作,通过连续并购、借壳上市,带领美年大健康成为体检行业的龙头老大。对于未来的健康产业布局,他野心勃勃 《投资...
投资者报 • 
温州老王13年炒房血泪史:已经到了末日

温州老王13年炒房血泪史:已经到了末日

去年3月以来,国家与地方相关政策连续释放利好消息,温州的老王又重新恢复了炒房的信心和勇气。然而,忙活了近一年,期望东山再起的老王还是失望了。去年以来,老王囤积了多套温州房子,以备房价上涨时出售谋利...
腾讯房产 • 
40天巨亏32万,这种坑为何还有人跳

40天巨亏32万,这种坑为何还有人跳

上周末,一位好友拜访小黄人。闲聊中,朋友透露他的一位朋友想代理一个**石油交易所的业务,这个交易所号称有国务院审批。朋友说,这么明显的骗局为什么要去玩?如果真想干,干嘛去代理,还不如自己开个交易所,...
我的理财师 • 
加载更多

 更多潮人帮