leveldb源码学习--hash
2017-02-06 本文已影响0人
icecity96
leveldb
中的哈希函数采用的是MurMurHash
的一种变体(=.=不知道这种变体比原版优势在哪,如果有大佬知道,球指导一下)。
这种哈希是一种高效低碰撞的非加密型哈希函数,相对于MD5/SHA1
,其开销低,hadoop/memcached之类都在用。
小伙伴们要是自己需要实现哈希函数,不妨参考一下leveldb
中的实现
源码
uint32_t Hash(const char* data, size_t n, uint32_t seed) {
// Similar to murmur hash
const uint32_t m = 0xc6a4a793;
const uint32_t r = 24;
const char* limit = data + n;
uint32_t h = seed ^ (n * m);
// Pick up four bytes at a time
while (data + 4 <= limit) {
uint32_t w = DecodeFixed32(data);
data += 4;
h += w;
h *= m;
h ^= (h >> 16);
}
// Pick up remaining bytes
switch (limit - data) {
case 3:
h += static_cast<unsigned char>(data[2]) << 16;
FALLTHROUGH_INTENDED;
case 2:
h += static_cast<unsigned char>(data[1]) << 8;
FALLTHROUGH_INTENDED;
case 1:
h += static_cast<unsigned char>(data[0]);
h *= m;
h ^= (h >> r);
break;
}
return h;
}