Lenky个人站点

学计算机的童鞋，应该没有人不清楚什么是哈希函数，在大多数实际项目中，对于哈希函数的选择，往往并不怎么在意，讲究的是能用就行，但在性能追求极致的环境里，哈希函数却还是一个考察重点。
在Web服务器lighttpd里，使用的是一个非常流行的DJB hash function，即俗称“Times33”的哈希算法，这个算法很简单，就是不断的乘33。

看实际代码：

/* the famous DJB hash function for strings */
static uint32_t hashme(buffer *str) {
        uint32_t hash = 5381;
        const char *s;
        for (s = str->ptr; *s; s++) {
                hash = ((hash << 5) + hash) + *s;
        }

        hash &= ~(1 << 31); /* strip the highest bit */

        return hash;
}

初始值为什么是5381？看这里：http://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function
结构体buffer的定义如下：

typedef struct {
        char *ptr;

        size_t used;
        size_t size;
} buffer;

因此，可以看到函数hashme()就是将一个字符串哈希成一个整型值，在很多场景下都有这种需求，比如Hash Map，其key值为字符串（以方便人看懂），而内部实际使用的是整型值（以方便机器操作），在lighttpd这里也是这样，它需要把一个文件路径名转换为一个整型哈希值。

对于一个哈希函数，我们总是期望它有更少的冲突，怎样判断一个哈希函数在冲突方面的好坏，貌似有一个名为avalanche test（雪崩测试）的密码学概念，关于它的具体含义，我暂且也不甚了了，但在nginx的1.0.1里用到了一个名为MurmurHash2算法，据说它有更少的冲突，代码如下：

uint32_t
ngx_murmur_hash2(u_char *data, size_t len)
{
    uint32_t  h, k;

    h = 0 ^ len;

    while (len >= 4) {
        k  = data[0];
        k |= data[1] << 8;
        k |= data[2] << 16;
        k |= data[3] << 24;

        k *= 0x5bd1e995;
        k ^= k >> 24;
        k *= 0x5bd1e995;

        h *= 0x5bd1e995;
        h ^= k;

        data += 4;
        len -= 4;
    }

    switch (len) {
    case 3:
        h ^= data[2] << 16;
    case 2:
        h ^= data[1] << 8;
    case 1:
        h ^= data[0];
        h *= 0x5bd1e995;
    }

    h ^= h >> 13;
    h *= 0x5bd1e995;
    h ^= h >> 15;

    return h;
}

这个，逻辑真心有点复杂，而且现在已有更进一步的改进版MurmurHash3，嘛，算了，不管它，呵呵。在这里：https://sites.google.com/site/murmurhash/avalanche可以看到一些哈希函数的雪崩测试结果，因为Google经常被墙，直接把结果转载过来：

Hsieh SuperFastHash：Some clear spots of bias, but nothing major.

Jenkins lookup3：Only a few slightly biased bits.

MurmurHash 1.0：Murmur 1.0′s mixing function has a bias of under 0.5%, so all the bits appear nearly black.

MurmurHash 2.0：MurmurHash 2.0′s mix also has a bias of under 0.5% – everything’s nearly black.

Bernstein：While it may be acceptable for hashing text, it doesn’t mix well – you’d be better off with something else.

FNV：This is why you probably shouldn’t use FNV. Both low bits of the hash and end bits of the key aren’t thorougly mixed.

ModifiedFNV：A lot better than I expected. One-byte-at-a-time hashes are harder to screw up, though.

引用说明：

I’ve changed the way the diagrams are generated so that input bits go from left (low bits, beginning of key) to right (high bits, end of key) and output bits go from bottom (low, beginning of hash) to top (high bits, end of hash). These diagrams are for 16-byte keys with 4-byte hashes.

The color scheme is also modified –
0% bias is black – the output bit flips exactly 50% of the time
5% bias is green – the output bit flips between 47.5% and 52.5% of the time
33% bias is yellow – the output bit flips between 33% and 66% of the time
100% bias is red – the output bit flips either 0% or 100% of the time.

也就是说结果图片要越黑越好，为什么这样呢？以黑色和红色做考虑，我的理解是，黑色表示输出位的最终结果均衡的受到各输入位的影响，即都是50%。而红色则表示输出位只受某些输入位的影响，即某些输入位对它的影响是0%，而某些输入位对它的影响却又是100%，决定性太大。假设2位输入，2位输出，如果是红色，又假设第1位输入对输出不起作用，即为0%，那么输入
0 0
和
1 0
它们的输出结果就冲突了，这样理解不知道对不对，下次再翻翻专业学术解释后再回来补充。
从测试结果可以看到，MurmurHash算法的确不错。

完全参考：
https://sites.google.com/site/murmurhash/avalanche
其它资料：
http://www.byvoid.com/blog/string-hash-compare/

转载请保留地址：http://lenky.info/archives/2012/12/30/2150 或 http://lenky.info/?p=2150

---

备注：如无特殊说明，文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限，虽力求内容正确无误，但仍然难免出错，请勿见怪，如果可以则请留言告之，并欢迎来讨论。另外值得说明的是，Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享，特别是一些带有完全参考的文章，其后附带的链接内容也许更直接、更丰富，而我只是做了一下归纳&转述，在此也一并表示感谢。关于本站的所有技术文章，欢迎转载，但请遵从CC创作共享协议，而一些私人性质较强的心情随笔，建议不要转载。

法律：根据最新颁布的《信息网络传播权保护条例》，如果您认为本文章的任何内容侵犯了您的权利，请以或书面等方式告知，本站将及时删除相关内容或链接。