hash jarang Google dengan fungsi hash murmur

Bagaimana cara menggunakan fungsi hash murmur di peta hash jarang Google? Bisakah Anda memberi saya petunjuk langkah demi langkah tentang cara menggunakan fungsi hash murmur? Saya menggunakan visual c++.

Saat ini saya menggunakan fungsi hash std::hash di peta hash jarang Google. Apakah ada perbedaan kinerja antara peta hash goole sparse yang diimplementasikan menggunakan std::hash dan hash murmur?


hashmap visual-c++ murmurhash
person user1815763    schedule 30.12.2012    source sumber
comment
Anda mungkin ingin membaca ini sebelum menggunakan MurmurHash3, khususnya online ketika keamanan mungkin menjadi masalah. emboss.github.io/blog /2012/12/14/   -  person Dave    schedule 15.03.2015

Jawaban (1)


arrow_upward
3
arrow_downward

Anda perlu menyediakan fungsi hash ke sparse_hash_map template. Saya telah memeriksa https://sites.google.com/site/murmurhash/; antarmukanya berbeda dari std::hash<>, jadi Anda harus menulis kelas adaptor. Berikut ini contoh yang berfungsi (perlu diingat bahwa adaptor hanya mencakup beberapa kasus):

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

Performanya mungkin bergantung pada pola data Anda, jadi Anda harus melakukan pengujian sendiri.

person rburny    schedule 30.12.2012
comment
Terima kasih banyak. Ini yang saya cari. Saya akan melakukan tes kinerja. - person user1815763; 31.12.2012
comment
Jawaban Anda menyelamatkan hari saya! Terima kasih! - person Pavlo Dyban; 26.02.2013
comment
Anda mungkin ingin membaca ini sebelum menggunakan MurmurHash3, khususnya online ketika keamanan mungkin menjadi masalah. emboss.github.io/blog /2012/12/14/ [ ups, ini seharusnya menjadi pertanyaan, bukan jawabannya! Saya tidak bisa memindahkannya, jadi saya mereplikasinya di sana sekarang. maafkan aku! ] - person Dave; 15.03.2015