美文网首页
leveldb源码学习--hash

leveldb源码学习--hash

作者: icecity96 | 来源:发表于2017-02-06 10:52 被阅读0次

    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;
    }
    

    相关文章

      网友评论

          本文标题:leveldb源码学习--hash

          本文链接:https://www.haomeiwen.com/subject/dnmyittx.html