Hash 散列函数

今天读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

此条目发表在C/C++分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注