快速哈希爲std :: set <int>的兩個值？

我正在使用std::set<int>作爲std映射的鍵（std::unordered_map<std::Set<int>,float>）。我需要這個集合的散列。快速哈希爲std :: set <int>的兩個值？

設定將永遠只有兩個整數，其值可高達200萬。

如性能是至關重要的這樣一個關鍵的又好又快哈希任何想法？

來源

2010-09-02 zenna

我是否理解正確嗎？你使用'std :: set'作爲'TR1：unordered_map'的關鍵嗎？ – wheaties 2010-09-02 19:19:33

這是正確的 – zenna 2010-09-02 19:20:23

如果只有兩個整數，你爲什麼不使用'標準::對'爲你的鑰匙？ – 2010-09-02 19:21:25

我會溝組的想法（這是內存和時間存儲在std::set兩個整數的浪費），並與一對走。然後定義

template <class A> 
struct unordered_pair_hash 
{ 
    std::size_t operator()(const std::pair<A, A>& p) const { 
    using std::min; 
    using std::max; 
    return std::hash<A>()(min(p.first, p.second))+ 
     17*std::hash<A>()(max(p.first, p.second)); 
    } 
}; 

template <class A> 
struct unordered_pair_eq 
{ 
    bool operator()(const std::pair<A, A>& p1, const std::pair<A, A>& p2) const { 
    using std::min; 
    using std::max; 
    return min(p1.first, p1.second)==min(p2.first, p2.second) && 
      max(p1.first, p1.second)==max(p2.first, p2.second); 
    } 
};

然後用自定義散列和相等性聲明該映射。

std::unordered_map<std::pair<int, int>, float, unordered_pair_hash<int>, unordered_pair_eq<int> > ...

來源

2010-09-02 19:38:10 jpalecek

爲什麼17作爲第二個值的倍數？ – zenna 2010-09-03 15:57:29

更簡單的散列函數：'std :: hash 散列;返回散列（p.first）+散列（p.second）;'。當需要交換性時，無符號的加法是一個很好的散列組合器（在這種情況下，因爲{1,0}和{0,1}需要散列到相同的值）。 – 2015-05-01 05:16:22

你可以使用boost :: hash_combine（）：http://www.boost.org/doc/libs/1_44_0/doc/html/hash/combine.html

來源

2010-09-02 19:41:29 usta

你沒有確切說明您的查詢的目的是，但也許你應該（或不應該）：

簡單地使用結構{詮釋A，b; }作爲重點 - 你控制成員插入（確保a <= b）
使用Sparse Matrix實現

問候

RBO

來源

2010-09-02 19:54:47

快速哈希爲std :: set <int>的兩個值？

回答

相關問題