今天读leveldb代码，看到murmur散列方法，突然想起以前公司关于hash的故事。所在产品线的一套代码十几年，一直在维护，新需求来了就是在上面增加模块，不带第三方库毫不夸张几十万行，记得某个文件没重构之前3w行。经手的人一多，加上产品线平台基础库推广力度不够，就是各种造轮子。
其中用的最多的哈希表 初始化是这个样子的，（当然hash表的实现也很多） ：
//** bucket_cnt ：桶的个数
//** hash_key_func_t：哈希函数指针
//** hash_compare_t ：键值比较函数指针
//** hash_destroy_func_t：释放节点中data数据的函数指针
//** hash_nodesize_cnt_t：哈希节点占用内存大小计算函数指针
//** bucket_depth ：桶的深度，设置为0表示不做限制
//**************************************************************************
hash_t *hash_init ( int bucket_cnt,
hash_key_func_t key_func,
hash_compare_t compare_func,
hash_destroy_func_t destroy_node_func,
hash_nodesize_cnt_t nodesize_cnt_func = NULL,
int bucket_depth = 0);
感觉接口设计挺好的，但，hash函数需要自己实现，导致系统种各种散列函数的存在，加乘异或移位，其中当然有好的实现，但是那么一两个我竟然看到了&，为什么没出事我也不太清楚，可能是数据不多。
某一天，系统（DPDK收包然后处理）出现丢包现象，最后的定位问题是哈希表散列性不好，导致某些桶特别深，查询出现热点，相当于在一个相当长的list上遍历比较，一直返回不了，数据量一大就出现丢包，最后修改散列函数后改善。此事之后凡是用到哈希表，单元测试都要求对其随机分布性做测试。
Leveldb使用的murmur hash变种，redis也有用到murmur hash。
MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。–wiki
在这里贴一下leveldb的源码：
#ifndef FALLTHROUGH_INTENDED
#define FALLTHROUGH_INTENDED do { } while (0)
#endif
namespace 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;
}
} // namespace leveldb