visual-c++ - 谷歌稀疏散列与杂音散列函数

Question

如何在谷歌稀疏散列图中使用杂音散列函数？你能否给我一步一步的说明如何使用杂音散列函数？我正在使用视觉 C++。

目前我在谷歌稀疏散列图中使用 std::hash 散列函数。使用 std::hash 和 murmur 哈希实现的 goole 稀疏哈希映射之间是否存在性能差异？

Answer 1

您需要为sparse_hash_map模板提供哈希函数。我检查了https://sites.google.com/site/murmurhash/；它的接口与 不同std::hash<>，因此您需要编写适配器类。这是一个工作示例（请记住，适配器仅涵盖某些情况）：

#include <iostream>
#include <sparsehash/sparse_hash_map>

using google::sparse_hash_map;      // namespace where class lives by default
using namespace std;

// 64-bit hash for 64-bit platforms
// copied from https://sites.google.com/site/murmurhash/
uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )
{
  const uint64_t m = 0xc6a4a7935bd1e995;
  const int r = 47;

  uint64_t h = seed ^ (len * m);

  const uint64_t * data = (const uint64_t *)key;
  const uint64_t * end = data + (len/8);

  while(data != end)
  {
    uint64_t k = *data++;

    k *= m; 
    k ^= k >> r; 
    k *= m; 

    h ^= k;
    h *= m; 
  }

  const unsigned char * data2 = (const unsigned char*)data;

  switch(len & 7)
  {
  case 7: h ^= uint64_t(data2[6]) << 48;
  case 6: h ^= uint64_t(data2[5]) << 40;
  case 5: h ^= uint64_t(data2[4]) << 32;
  case 4: h ^= uint64_t(data2[3]) << 24;
  case 3: h ^= uint64_t(data2[2]) << 16;
  case 2: h ^= uint64_t(data2[1]) << 8;
  case 1: h ^= uint64_t(data2[0]);
          h *= m;
  };

  h ^= h >> r;
  h *= m;
  h ^= h >> r;

  return h;
} 

// simple hash adapter for types without pointers
template<typename T> 
struct MurmurHasher {
    size_t operator()(const T& t) const {
        return MurmurHash64A(&t, sizeof(t), 0);
    }    
};

// specialization for strings
template<> 
struct MurmurHasher<string> {
    size_t operator()(const string& t) const {
        return MurmurHash64A(t.c_str(), t.size(), 0);
    }    
};

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

int main()
{
  sparse_hash_map<const char*, int, MurmurHasher<const char*>, eqstr> months;

  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;

  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;

  sparse_hash_map<string, int, MurmurHasher<string>> years;
  years["2012"] = 366;
  cout << "2012      -> " << years["2012"] << endl;
}

Performance will probably depend on your data patterns, so you should do the tests yourself.