谷歌稀疏哈希與雜音哈希函數

Question

如何在谷歌稀疏哈希映射中使用低噪聲哈希函數？ 你能否給我一步一步的指導如何使用雜音哈希函數？ 我正在使用visual C++。

目前我在谷歌稀疏哈希映射中使用std :: hash哈希函數。 使用std :: hash和murmur hash實現的goole sparse hash map是否有任何性能差異？

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

性能可能會取決於你的數據模式，所以你應該自己做測試。