Google разреженный хэш с хеш-функцией бормотания

Как использовать хэш-функцию бормотания в разреженной хеш-карте Google? Не могли бы вы дать мне пошаговые инструкции о том, как использовать хеш-функцию бормотания? Я использую визуальный С++.

В настоящее время я использую хэш-функцию std::hash в разреженной хэш-карте Google. Есть ли разница в производительности между разреженными хеш-картами Google, которые реализованы с использованием std::hash и бормотания?


hashmap visual-c++ murmurhash
person user1815763    schedule 30.12.2012    source источник
comment
Вы можете прочитать это перед использованием MurmurHash3, особенно в Интернете, когда безопасность может быть проблемой. emboss.github.io/blog /2012/12/14/   -  person Dave    schedule 15.03.2015

Ответы (1)


arrow_upward
3
arrow_downward

Вам необходимо указать хеш-функцию для шаблона 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;
}

Производительность, вероятно, будет зависеть от ваших шаблонов данных, поэтому вам следует проводить тесты самостоятельно.

person rburny    schedule 30.12.2012
comment
Большое спасибо. Это то, что я искал. Я проведу тест производительности. - person user1815763; 31.12.2012
comment
Ваш ответ спас мой день! Спасибо! - person Pavlo Dyban; 26.02.2013
comment
Вы можете прочитать это перед использованием MurmurHash3, особенно в Интернете, когда безопасность может быть проблемой. emboss.github.io/blog /2012/12/14/ [ упс, это должно было быть в вопросе, а не в ответе! Я не могу его переместить, поэтому сейчас копирую его там. извиняюсь рбурни! ] - person Dave; 15.03.2015