如何爲用戶定義的類型專門化std :: hash <T>？

Question

問題

什麼是性病的一個很好的專業化::散在性病的第三個模板參數:: unordered_map或std :: unordered_set針對其所有成員的數據類型已經有一個用戶定義的類型使用std :: hash的一個很好的特化？

對於這個問題，我將「好」定義爲實現和理解起來很簡單，合理高效並且不太可能產生散列表衝突。商品的定義不包括任何有關安全的陳述。

什麼是Google'able

此刻的國家，兩種StackOverflow的問題對谷歌搜索「STD哈希專業化」的第一個命中。

第一個How to specialize std::hash::operator() for user-defined type in unordered containers?解決打開標準名稱空間和添加模板專用化是否合法的問題。

第二個，How to specialize std::hash for type from other library，基本上解決了同樣的問題。

這留下了當前的問題。假定C++標準庫的實現爲標準庫中的原始類型和類型定義了哈希函數，那麼爲用戶定義的類型專門化std :: hash的簡單而有效的方法是什麼？有沒有一種好的方法來結合標準庫實現提供的散列函數？

（編輯感謝dyp。）Another question StackOverflow地址如何組合一個對散列函數。

Google的其他結果沒有任何幫助。

This Dr. Dobbs的文章指出，兩個令人滿意的散列的XOR會產生新的令人滿意的散列。

This文章似乎是從知識發言，並暗示很多事情，但對細節輕描淡寫。它在第一個例子中與Dobbs博士的文章相矛盾，他說使用XOR結合散列函數會導致散列函數的弱化。

因爲應用於任何兩個相等值的XOR結果爲0，所以我可以看到爲什麼XOR本身很弱。

元問題

一個良好的理由的回答解釋爲什麼這個問題是無效的，不能籠統地回答也將受到歡迎。

Answer 1

一個簡單的方法是使用boost::hash庫和extend it for your type。它有一個很好的擴展函數hash_combine（std::hash缺乏），可以輕鬆組成結構中各個數據成員的哈希值。

換句話說：

1. 超載boost::hash_value爲自己的類型。
2. 爲您自己的類型專門設計std::hash並使用boost::hash_value來實現它。

這樣你就可以得到最好的std和boost世界，std::hash<>和boost::hash<>都適合你的類型。

---

更好的方法是使用N3980 Types Don't Know #中提議的新的散列基礎結構。這種基礎設施使得hash_combine不必要。

Answer 2

，直到我們得到的標準庫，以幫助這個：

1. 下載一個現代化的散列器，像SpookyHash：http://burtleburtle.net/bob/hash/spooky.html。
2. 在std::hash<YourType>的定義中，創建一個SpookyHash實例，並且Init它。請注意，在進程啓動或std::hash構建中選取一個隨機數，並將其作爲初始化將使用make it slightly harder to DoS your program, but doesn't fix the problem。
3. 以您的結構中的每個字段爲貢獻operator==（「顯着字段」），並將其填入SpookyHash::Update。
   • 當心類型，如double：他們有2個申述char[]是比較==：-0.0和0.0。還要小心有填充的類型。在大多數機器上，int沒有，但很難說是否會有struct。 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html#is_contiguously_hashable討論了這一點。
   • 如果你有子結構，你會得到一個更快，質量更高的散列值遞歸地提供他們的字段到同一SpookyHash實例。但是，這需要向這些結構添加方法或手動提取突出字段：如果您無法執行此操作，只需將std::hash<>值填充到頂級SpookyHash實例即可。
4. 返回SpookyHash::Final的輸出從std::hash<YourType>。

Answer 3

首先，Dr. Dobbs的文章中說，XOR的兩個 令人滿意的散列會產生令人滿意的散列，簡直就是 錯誤。對於可憐的哈希來說，這是一個好的方法。一般來說，要創建一個好的散列，您首先將對象分解爲 子對象，其中每個子對象都存在一個很好的散列，並將合併爲散列。這樣做的一個簡單的方法是什麼 這樣的：

class HashAccumulator 
{ 
    size_t myValue; 
public: 
    HashAccumulator() : myValue(2166136261U) {} 
    template <typename T> 
    HashAccumulator& operator+=(T const& nextValue) 
    { 
     myValue = 127U * myValue + std::hash<T>(nextHashValue); 
    } 
    HashAccumulator operator+(T const& nextHashValue) const 
    { 
     HashAccumulator results(*this); 
     results += nextHashValue; 
     return results; 
    } 
}; 

（這已被設計成可以使用std::accumulate如果 你有值的序列。）

當然，這應該是所有的子類型具有很好的 實現std::hash。對於基本類型和 字符串，這是給定的;對於你自己的類型，只需遞歸應用 以上規則，專門std::hash在其子類型上使用 HashAccumulator。對於標準容器 這是一個基本類型，這有點棘手，因爲您不允許（正式地，至少爲 ）專門化標準庫中 類型的標準模板;您可能必須創建 直接使用HashAccumulator的類，並且明確地指定 指定如果您需要此類容器的散列。

Answer 4

你的操作is required到

• 返回size_t
• 類型的值與==操作一致。
• 對不等值的散列衝突概率較低。

沒有明確要求散列值均勻分佈在整數的範圍內。 cppreference.com notes該

一些實施方式[標準庫]使用瑣碎（同一性）的散列函數，其的整數映射到自身

再加上有弱點避免哈希衝突意味着的std::hash用於專業化您的類型應該從不只需使用（快速）按位異或（^）來組合數據成員的子散列。考慮下面的例子：

struct Point { 
    uint8_t x; 
    uint8_t y; 
}; 

namespace std { 
    template<> 
    struct hash<Point> { 
     size_t operator()(const Point &p) const { 
      return hash<uint8_t>(p.x)^hash<uint8_t>(p.y); 
     } 
    }; 
} 

的p.x的哈希值將在範圍[0,255]，等會的p.y散列。因此，Point的散列值也將在[0,255]範圍內，其中256（= 2^8）個可能值。有256 * 256（= 2^16）個唯一的Point對象（std::size_t通常會支持2^32或2^64的值）。所以散列函數的哈希碰撞概率應該大約爲2 ^（ - 16）。我們的函數給出了剛好在2 ^（ - 8）以下的哈希碰撞概率。這太糟糕了：我們的散列只提供8位信息，但好的散列應該提供16位信息。

如果數據成員的散列函數僅提供std::size_t範圍的低部分中的散列值，則必須在組合散列之前對其進行「移位」，以便它們各自貢獻獨立的信息位。做一個左明智的轉變看似簡單

 return (hash<uint8_t>(p.x) << 8)^hash<uint8_t>(p.y); 

，但將丟棄信息（由於溢出）如果hash<uint8_t>的實現（在這種情況下）嘗試在std::size_t範圍內蔓延的哈希碼值。

使用乘用貸和相加的方法，如typically done in Java積累組件哈希碼值，可能更好地工作一般：

namespace std { 
    template<> 
    struct hash<Point> { 
     size_t operator()(const Point &p) const { 
      const size_t prime = 257; 
      size_t h {hash<uint8_t>(p.x)}; 
      h = h * prime + hash<uint8_t>(p.y); 
      return h; 
     } 
    }; 
}