【LevelDB源码阅读】Hash
是什么
是一种哈希函数,采用的是MurMurHash的一种变体,是一种高效低碰撞的非加密型哈希函数。
为什么要用
- 具有较高的平衡性与低碰撞率
学到什么
- 对于大块数据,可以分多个小的部分进行哈希计算
源码分析
主要就一个hash接口
uint32_t Hash(const char *data, size_t n, uint32_t seed);
具体实现如下:
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<uint8_t>(data[2]) << 16; FALLTHROUGH_INTENDED; case 2: h += static_cast<uint8_t>(data[1]) << 8; FALLTHROUGH_INTENDED; case 1: h += static_cast<uint8_t>(data[0]); h *= m; h ^= (h >> r); break; } return h; }
其中FALLTHROUGH_INTENDED定义如下:
// The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through // between switch labels. The real definition should be provided externally. // This one is a fallback version for unsupported compilers. #ifndef FALLTHROUGH_INTENDED #define FALLTHROUGH_INTENDED do { } while (0) #endif
相关推荐
guangyacyb 2020-06-14
adwen00 2020-06-09
tmshasha 2019-12-15
Finnnnnnn 2019-11-05
longzuo 2019-07-09
longzuo 2012-04-03
tmshasha 2019-07-09
adwen00 2019-07-01
tmshasha 2015-03-24
江沐涵 2019-06-28
tmshasha 2019-06-28
guangyacyb 2019-06-26
longzuo 2019-05-27
江沐涵 2018-07-24
tmshasha 2019-04-29
YENCSDN 2017-12-21
guangyacyb 2011-08-09