Boost C++ 函式庫

...是世界上最受推崇且設計最精良的 C++ 函式庫專案之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 編碼標準

簡介

boost::hash 是 C++11 所規範的雜湊函式物件 std::hash 的增強實作。它是 Boost.Unordered、Boost.Intrusive 的 unordered 關聯式容器、Boost.MultiIndex 的雜湊索引，以及 Boost.Bimap 的 unordered_set_of 的預設雜湊函式。

開箱即用，boost::hash 支援

標準整數型別（整數、字元型別和 bool）；
標準浮點數型別（float、double、long double）；
指標（指向物件和函式的指標，但不包含指向成員的指標）和 nullptr；
列舉型別；
C 陣列；
std::complex;
tuple-like 型別，例如 std::pair、std::tuple，以及特化 std::tuple_size 並提供 get<I> 的使用者定義型別；
sequence-like 型別，標準和使用者定義的皆可 (sequence-like 型別具有回傳迭代器的 begin() 和 end() 成員函式)；
unordered 序列，標準或使用者定義的皆可（雜湊值不依賴元素順序的序列，例如 std::unordered_set 和 std::unordered_map）；
描述的結構和類別 — 使用來自 Boost.Describe 的 BOOST_DESCRIBE_STRUCT 或 BOOST_DESCRIBE_CLASS 巨集註釋的結構和類別；
std::unique_ptr、std::shared_ptr；
std::type_index;
std::error_code、std::error_condition；
std::optional;
std::variant、std::monostate。

boost::hash 可擴充；使用者定義的型別 X 可透過定義適當的函式 hash_value 的多載，使其能夠經由 boost::hash<X> 進行雜湊。許多（如果不是大多數）Boost 型別已經包含必要的支援。

boost::hash 符合 C++11 標準中指定的 std::hash 的需求，也就是說，對於兩個不同的輸入值，它們對應的雜湊值要保證是不同的，或者它們相同的機率（雜湊衝突）很小。標準 unordered 容器和基於雜湊的 Boost 容器，都是設計為與此類雜湊函式良好搭配使用。

boost::hash 不符合通常在更廣泛的上下文中對雜湊函式提出的更嚴格要求。特別是，雜湊函式不是加密的，對於有決心的攻擊者來說不是抗衝突的，並且不一定具有良好的「雪崩」特性；也就是說，輸入中的小（單位元）擾動不一定會導致輸出中的大（一半位元改變）擾動。

特別是，boost::hash 傳統上對於所有適合 std::size_t 的整數型別都是身分函式，因為這保證了不會發生衝突，並且盡可能快。

近期變更

Boost 1.82.0

為 std::nullptr_t 新增了 hash_value 的多載。
新增了 is_tuple_like 和 tuple-like 型別的 hash_value 的多載。
變更了字串雜湊，以使用 mulxp1_hash，同時提升了品質和速度。這會變更字串類型的雜湊值（char、signed char、unsigned char、std::byte、char8_t 的範圍）。

Boost 1.81.0

重大更新。

boost::hash 的特化已被移除；現在它總是呼叫 hash_value。
已移除對 BOOST_HASH_NO_EXTENSIONS 的支援。擴充功能始終啟用。
現在支援所有標準容器。這包含 std::forward_list 和 unordered 關聯式容器。
現在支援使用者定義的容器（具有回傳迭代器的 begin() 和 end() 成員函式的型別）。
現在支援描述的結構和類別（使用 BOOST_DESCRIBE_STRUCT 或 BOOST_DESCRIBE_CLASS 註釋的結構和類別）。
hash_combine 已改進。這會變更複合（容器和 tuple）型別以及大於 size_t 的純量型別的雜湊值。
字串雜湊的效能（以及品質，由於上述變更）已提升。用於字串的 boost::hash 現在以 64 位元模式通過 SMHasher。
文件已大幅修訂，以反映這些變更。

Boost 1.78.0

修復了 hash_combine，使其行為不再取決於 size_t 是否與 boost::uint64_t 完全相同的型別（這在 macOS 上並非如此）。這會變更 macOS 上複合（容器和 tuple）型別的雜湊值。

教學

當使用 Boost 容器（例如 Boost.Unordered）時，您不需要執行任何操作即可使用 boost::hash，因為它是預設值。若要了解如何使用使用者定義的型別，請閱讀關於為使用者型別擴充 boost::hash 的章節。

如果您希望將 boost::hash 與標準 unordered 關聯式容器一起使用，請將其作為樣板參數傳遞

std::unordered_multiset<int, boost::hash<int> >
        set_of_ints;

std::unordered_set<std::pair<int, int>, boost::hash<std::pair<int, int> > >
        set_of_pairs;

std::unordered_map<int, std::string, boost::hash<int> > map_int_to_string;

若要直接使用 boost::hash，請建立一個執行個體並將其當作函式呼叫

#include <boost/container_hash/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;
    std::size_t h = string_hash("Hash me");
}

或者，也可以使用

#include <boost/container_hash/hash.hpp>

int main()
{
    std::size_t h = boost::hash<std::string>()("Hash me");
}

若要取得泛型使用範例，以下是一個產生向量的函式，其中包含容器元素雜湊值

template <class Container>
std::vector<std::size_t> get_hashes(Container const& x)
{
    std::vector<std::size_t> hashes;
    std::transform(x.begin(), x.end(), std::back_inserter(hashes),
        boost::hash<typename Container::value_type>());

    return hashes;
}

為使用者型別擴充 boost::hash

boost::hash 是透過呼叫函式 hash_value 來實作的。未指定命名空間，以便它可以透過引數相關查找偵測多載。因此，如果使用者型別的相同命名空間中存在一個自由函式 hash_value，則會呼叫它。

如果您有一個結構 library::book，其中每本書都由其成員 id 唯一定義

namespace library
{
    struct book
    {
        int id;
        std::string author;
        std::string title;

        // ....
    };

    bool operator==(book const& a, book const& b)
    {
        return a.id == b.id;
    }
}

那麼您只需要編寫函式 library::hash_value

namespace library
{
    std::size_t hash_value(book const& b)
    {
        boost::hash<int> hasher;
        return hasher(b.id);
    }
}

現在您可以將 boost::hash 與書籍一起使用

library::book knife(3458, "Zane Grey", "The Hash Knife Outfit");
library::book dandelion(1354, "Paul J. Shanley",
    "Hash & Dandelion Greens");

boost::hash<library::book> book_hasher;
std::size_t knife_hash_value = book_hasher(knife);

// If std::unordered_set is available:
std::unordered_set<library::book, boost::hash<library::book> > books;
books.insert(knife);
books.insert(library::book(2443, "Lindgren, Torgny", "Hash"));
books.insert(library::book(1953, "Snyder, Bernadette M.",
    "Heavenly Hash: A Tasty Mix of a Mother's Meditations"));

assert(books.find(knife) != books.end());
assert(books.find(dandelion) == books.end());

完整範例可以在 examples/books.hpp 和 examples/books.cpp 中找到。

提示	當編寫雜湊函式時，請先查看相等函式的工作方式。相等的物件必須產生相同的雜湊值。當物件不相等時，它們應該產生不同的雜湊值。在這個物件中，相等性僅基於 `id`，因此雜湊函式僅雜湊 `id`。如果它基於物件的名稱和作者，則雜湊函式應該將它們納入考量（下一節將討論如何執行此操作）。

組合雜湊值

假設您有一個點類別，表示二維位置

class point
{
    int x;
    int y;

public:

    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}

    bool operator==(point const& other) const
    {
        return x == other.x && y == other.y;
    }
};

並且您希望將它用作 unordered_map 的索引鍵。您需要為此結構自訂雜湊。為此，我們需要組合 x 和 y 的雜湊值。提供函式 boost::hash_combine 來執行此操作

class point
{
    ...

    friend std::size_t hash_value(point const& p)
    {
        std::size_t seed = 0;

        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }

    ...
};

對 hash_combine 的呼叫會從 point 的不同成員逐步建構雜湊，它可以針對任意數量的元素重複呼叫。它會呼叫所提供元素的 hash_value，並將其與種子組合。

此範例的完整程式碼位於 examples/point.cpp。

請注意，當使用 boost::hash_combine 時，呼叫的順序很重要。

std::size_t seed = 0;
boost::hash_combine(seed, 1);
boost::hash_combine(seed, 2);

且

std::size_t seed = 0;
boost::hash_combine(seed, 2);
boost::hash_combine(seed, 1);

會在 seed 中產生不同的值。

若要計算迭代器範圍的雜湊，您可以使用 boost::hash_range

std::vector<std::string> some_strings;
std::size_t hash = boost::hash_range(some_strings.begin(), some_strings.end());

由於 hash_range 的工作原理是透過在範圍元素上重複呼叫 hash_combine，因此雜湊值也將取決於元素順序。

如果您要計算雜湊值的範圍資料順序無關緊要（例如 unordered_set），則可以使用 boost::hash_unordered_range 來代替。

std::unordered_set<std::string> set;
std::size_t hash = boost::hash_unordered_range(set.begin(), set.end());

當編寫樣板類別時，您可能不希望包含主要的 hash.hpp 標頭，因為它是一個非常昂貴的包含，會引入許多其他標頭，因此您可以改為包含 <boost/container_hash/hash_fwd.hpp> 標頭，該標頭會宣告 boost::hash、boost::hash_combine、boost::hash_range 和 boost::hash_unordered_range 的前向宣告。您需要在具現化 boost::hash 之前包含主要標頭。當使用使用 boost::hash 的容器時，它應該會為您執行此操作，因此您的型別將與 Boost 雜湊容器搭配使用。在 examples/template.hpp 和 examples/template.cpp 中有一個範例。

為了避免包含 hash_fwd.hpp (它仍然要求 Boost.ContainerHash 的內容實際存在)，您可直接將宣告從 hash_fwd.hpp (而且只有這些) 複製到您自己的標頭中。這是程式庫保證的特殊例外；一般而言，您不能在沒有在後續版本中發生中斷風險的情況下宣告程式庫函式（Boost 或其他）。

使用 Boost.Describe 雜湊使用者型別

讓我們再次看看我們的 point 類別

class point
{
    int x;
    int y;

public:

    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}
};

如果您使用的是 C++14 或更高版本，更輕鬆地將 boost::hash 支援新增至 point 的方式是使用 Boost.Describe（並免費取得 operator== 的自動定義）

#include <boost/describe/class.hpp>
#include <boost/describe/operators.hpp>

class point
{
    int x;
    int y;

    BOOST_DESCRIBE_CLASS(point, (), (), (), (x, y))

public:

    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}
};

using boost::describe::operators::operator==;
using boost::describe::operators::operator!=;

（此範例的完整程式碼位於 examples/point2.cpp。）

由於 point 類別已使用 BOOST_DESCRIBE_CLASS 註釋，程式庫可以列舉其成員（和基底類別），並自動合成適當的 hash_value 多載，而無需我們這樣做。

參考

<boost/container_hash/hash_fwd.hpp>

此標頭包含程式庫基本類型的前向宣告。這些宣告保證相對穩定，也就是說，我們會盡最大努力確保它們不會在版本之間變更，允許它們逐字複製到不希望實際依賴 Boost.ContainerHash 的使用者標頭中。

namespace boost
{

namespace container_hash
{

template<class T> struct is_range;
template<class T> struct is_contiguous_range;
template<class T> struct is_unordered_range;
template<class T> struct is_described_class;
template<class T> struct is_tuple_like;

} // namespace container_hash

template<class T> struct hash;

template<class T> void hash_combine( std::size_t& seed, T const& v );

template<class It> void hash_range( std::size_t& seed, It first, It last );
template<class It> std::size_t hash_range( It first, It last );

template<class It> void hash_unordered_range( std::size_t& seed, It first, It last );
template<class It> std::size_t hash_unordered_range( It first, It last );

} // namespace boost

<boost/container_hash/hash.hpp>

定義 boost::hash 和輔助函式。

namespace boost
{

template<class T> struct hash;

template<class T> void hash_combine( std::size_t& seed, T const& v );

template<class It> void hash_range( std::size_t& seed, It first, It last );
template<class It> std::size_t hash_range( It first, It last );

template<class It> void hash_unordered_range( std::size_t& seed, It first, It last );
template<class It> std::size_t hash_unordered_range( It first, It last );

// Enabled only when T is an integral type
template<class T>
  std::size_t hash_value( T v );

// Enabled only when T is an enumeration type
template<class T>
  std::size_t hash_value( T v );

// Enabled only when T is a floating point type
template<class T>
  std::size_t hash_value( T v );

template<class T>
  std::size_t hash_value( T* const& v );

template<class T, std::size_t N>
  std::size_t hash_value( T const (&v)[N] );

template<class T>
  std::size_t hash_value( std::complex<T> const& v );

template<class A, class B>
  std::size_t hash_value( std::pair<A, B> const& v );

// Enabled only when container_hash::is_tuple_like<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

// Enabled only when container_hash::is_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

// Enabled only when container_hash::is_contiguous_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

// Enabled only when container_hash::is_unordered_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

// Enabled only when container_hash::is_described_class<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

template<class T>
  std::size_t hash_value( std::shared_ptr<T> const& v );

template<class T, class D>
  std::size_t hash_value( std::unique_ptr<T, D> const& v );

std::size_t hash_value( std::type_index const& v );

std::size_t hash_value( std::error_code const& v );
std::size_t hash_value( std::error_condition const& v );

template<class T>
  std::size_t hash_value( std::optional<T> const& v );

std::size_t hash_value( std::monostate v );

template<class... T>
  std::size_t hash_value( std::variant<T...> const& v );

} // namespace boost

hash<T>

template<class T> struct hash
{
    std::size_t operator()( T const& v ) const;
};

operator()

std::size_t operator()( T const& v ) const;

傳回: hash_value(v).
擲回: 只有在 hash_value(v) 擲回時才會擲回。
備註: 對 hash_value 的呼叫是不合格的，因此會透過引數相關查找找到使用者提供的多載。

hash_combine

template<class T> void hash_combine( std::size_t& seed, T const& v );

重複呼叫以從多個變數逐步建立雜湊值。

效果

使用確定性方式將 seed 與 boost::hash<T>()(v) 的結果組合，產生新的雜湊值來更新 seed。

擲回

僅當 boost::hash<T>()(v) 拋出例外時才會拋出例外。若發生例外，seed 不會被更新。

備註

等同於 seed = combine(seed, boost::hash<T>()(v))，其中 combine(s, v) 是一個混合函數，接受兩個 std::size_t 型別的引數，並回傳 std::size_t，且具有以下理想特性：

對於一個常數 s，當 v 取所有可能的 size_t 值時，combine(s, v) 也應該取所有可能的 size_t 值，產生一個接近隨機的序列；也就是說，它應該是一個隨機排列。

這保證了對於給定的 seed，當 boost::hash<T>(v) 沒有產生雜湊碰撞時，combine 不會引入雜湊碰撞；也就是說，它不會遺失輸入的資訊。這也意味著 combine(s, v) 作為 v 的函數，具有良好的雪崩效應；也就是說，輸入 v 的微小擾動（例如單一位元的改變）會導致回傳值出現大幅擾動（平均而言，一半的輸出位元會改變）。
對於兩個不同的種子 s1 和 s2，將 combine(s1, v) 和 combine(s2, v) 視為 v 的函數，應該產生兩個不同的隨機排列。
combine(0, 0) 不應該為 0。由於 seed 的常見初始值為零，combine(0, 0) == 0 將意味著在任何零序列上應用 hash_combine，無論長度為何，都將產生零。這是不可取的，因為這會導致例如 std::vector<int>() 和 std::vector<int>(4) 具有相同的雜湊值。

目前的實作使用函數 mix(s + 0x9e3779b9 + v) 作為 combine(s, v)，其中 mix(x) 是一個高品質的混合函數，它是 std::size_t 值的雙射函數，形式如下：

x ^= x >> k1;
x *= m1;
x ^= x >> k2;
x *= m2;
x ^= x >> k3;

其中常數 k1、k2、k3、m1、m2 皆經過適當選擇。

請注意，mix(0) 為 0。這就是我們加入任意常數 0x9e3779b9 以滿足上述第三個要求的原因。

hash_range

template<class It> void hash_range( std::size_t& seed, It first, It last );

效果

當 typename std::iterator_traits<It>::value_type 不是 char、signed char、unsigned char、std::byte 或 char8_t 時，

for( ; first != last; ++first )
{
    boost::hash_combine<typename std::iterator_traits<It>::value_type>( seed, *first );
}

否則，來自 [first, last) 的位元組會以未指定的方式合併並雜湊。這樣做是為了提高雜湊字串時的效能。

備註

對於字元，當 std::size_t 為 64 位元時，目前實作使用 mulxp1_hash，當它是 32 位元時，使用 mulxp1_hash32。

template<class It> std::size_t hash_range( It first, It last );

效果

size_t seed = 0;
boost::hash_range( seed, first, last );
return seed;

hash_unordered_range

template<class It> void hash_unordered_range( std::size_t& seed, It first, It last );

效果: 使用 boost::hash<typename std::iterator_traits<It>::value_type>()(*i) 的值更新 seed，其中 i 為 [first, last) 中的每個元素，因此元素的順序不會影響最終結果。

template<class It> std::size_t hash_unordered_range( It first, It last );

效果

size_t seed = 0;
boost::hash_unordered_range( seed, first, last );
return seed;

hash_value

// Enabled only when T is an integral type
template<class T>
  std::size_t hash_value( T v );

傳回: 當 v 的值可以放入 std::size_t 時（當 T 為無號型別時），或放入 ssize_t 時（當 T 為有號型別時），則為 static_cast<std::size_t>(v)。

否則，則為透過混合 v 的值位元所取得的未指定值。

// Enabled only when T is an enumeration type
template<class T>
  std::size_t hash_value( T v );

傳回: static_cast<std::size_t>(v).
備註: hash_value(std::to_underlying(v)) 會更好，但 C++03 的相容性要求目前的實作。

// Enabled only when T is a floating point type
template<class T>
  std::size_t hash_value( T v );

傳回: 透過混合 v 的值位元所取得的未指定值。
備註: 當 sizeof(v) <= sizeof(std::size_t) 時，v 的位元會原封不動地回傳（除了 -0.0 的情況，它會被視為 +0.0）。

template<class T>
  std::size_t hash_value( T* const& v );

傳回: 衍生自 reinterpret_cast<std::uintptr_t>(v) 的未指定值。

template<class T, std::size_t N>
  std::size_t hash_value( T const (&v)[N] );

傳回: boost::hash_range( v, v + N ).

template<class T>
  std::size_t hash_value( std::complex<T> const& v );

傳回: 衍生自 boost::hash<T>()(v.real()) 和 boost::hash<T>()(v.imag()) 的未指定值，且如果 v.imag() == 0，則該值等於 boost::hash<T>()(v.real())。
備註: 更直接的實作方式只需對 v.real() 和 v.imag() 使用 hash_combine，但歷史上保證實值複數的雜湊值應與其實部的雜湊值相符，因此排除此選項。

此保證可能會在未來版本中取消，因為它的實用性值得懷疑。

template<class A, class B>
  std::size_t hash_value( std::pair<A, B> const& v );

效果

std::size_t seed = 0;

boost::hash_combine( seed, v.first );
boost::hash_combine( seed, v.second );

return seed;

// Enabled only when container_hash::is_tuple_like<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

效果

std::size_t seed = 0;

using std::get;

boost::hash_combine( seed, get<0>(v) );
boost::hash_combine( seed, get<1>(v) );
// ...
boost::hash_combine( seed, get<N-1>(v) );

return seed;

其中 N 為 std::tuple_size<T>::value。

備註

只有當 container_hash::is_range<T>::value 為 false 時，才會啟用此多載。

// Enabled only when container_hash::is_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

傳回: boost::hash_range( v.begin(), v.end() ).
備註: 只有當 container_hash::is_contiguous_range<T>::value 和 container_hash::is_unordered_range<T>::value 皆為 false 時，才會啟用此多載。

它會處理所有非連續或無序的標準容器，例如 std::deque、std::list、std::set、std::map。

// Enabled only when container_hash::is_contiguous_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

傳回: boost::hash_range( v.data(), v.data() + v.size() ).
備註: 此多載會處理所有標準的連續容器，例如 std::string、std::vector、std::array、std::string_view。

// Enabled only when container_hash::is_unordered_range<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

傳回: boost::hash_unordered_range( v.begin(), v.end() ).
備註: 此多載會處理標準的無序容器，例如 std::unordered_set 和 std::unordered_map。

// Enabled only when container_hash::is_described_class<T>::value is true
template<class T>
  std::size_t hash_value( T const& v );

效果

std::size_t seed = 0;

boost::hash_combine( seed, b1 );
boost::hash_combine( seed, b2 );
// ...
boost::hash_combine( seed, bM );

boost::hash_combine( seed, m1 );
boost::hash_combine( seed, m2 );
// ...
boost::hash_combine( seed, mN );

return seed;

其中 bi 是 v 的基底，而 mi 是其成員。

template<class T>
  std::size_t hash_value( std::shared_ptr<T> const& v );

template<class T, class D>
  std::size_t hash_value( std::unique_ptr<T, D> const& v );

傳回: boost::hash<T*>( v.get() ).

std::size_t hash_value( std::type_index const& v );

傳回: v.hash_code().

std::size_t hash_value( std::error_code const& v );
std::size_t hash_value( std::error_condition const& v );

效果

std::size_t seed = 0;

boost::hash_combine( seed, v.value() );
boost::hash_combine( seed, &v.category() );

return seed;

template<class T>
  std::size_t hash_value( std::optional<T> const& v );

傳回: 對於未參與的 v，為未指定的常數值；否則為 boost::hash<T>()( *v )。

std::size_t hash_value( std::monostate v );

傳回: 未指定的常數值。

template<class... T>
  std::size_t hash_value( std::variant<T...> const& v );

效果

std::size_t seed = 0;

boost::hash_combine( seed, v.index() );
boost::hash_combine( seed, x );

return seed;

其中 x 是 v 中目前包含的值。

擲回

當 v.valueless_by_exception() 為 true 時，則為 std::bad_variant_access。

<boost/container_hash/is_range.hpp>

定義特徵 boost::container_hash::is_range。

namespace boost
{

namespace container_hash
{

template<class T> struct is_range;

} // namespace container_hash

} // namespace boost

is_range<T>

template<class T> struct is_range
{
    static constexpr bool value = /* see below */;
};

當對於類型 T 的常數值 x，x.begin() 和 x.end() 回傳相同類型 It 的迭代器（且 std::iterator_traits<It> 是有效的特化）時，is_range<T>::value 為 true。

如果預設行為無法推斷出正確的值，則允許使用者為自己的類型特化 is_range。

<boost/container_hash/is_contiguous_range.hpp>

定義特徵 boost::container_hash::is_contiguous_range。

namespace boost
{

namespace container_hash
{

template<class T> struct is_contiguous_range;

} // namespace container_hash

} // namespace boost

is_contiguous_range<T>

template<class T> struct is_contiguous_range
{
    static constexpr bool value = /* see below */;
};

當 is_range<T>::value 為 true 且當對於類型 T 的常數值 x，x.data() 回傳一個指標，指向與 x.begin() 和 x.end() 回傳的迭代器的 value_type 相符的類型，且 x.size() 回傳一個整數型別的值時，is_contiguous_range<T>::value 為 true。

如果預設行為無法推斷出正確的值，則允許使用者為自己的類型特化 is_contiguous_range。

<boost/container_hash/is_unordered_range.hpp>

定義特徵 boost::container_hash::is_unordered_range。

namespace boost
{

namespace container_hash
{

template<class T> struct is_unordered_range;

} // namespace container_hash

} // namespace boost

is_unordered_range<T>

template<class T> struct is_unordered_range
{
    static constexpr bool value = /* see below */;
};

當 is_range<T>::value 為 true 且當 T::hasher 是有效的類型時，is_unordered_range<T>::value 為 true。

如果預設行為無法推斷出正確的值，則允許使用者為自己的類型特化 is_unordered_range。

<boost/container_hash/is_described_class.hpp>

定義特徵 boost::container_hash::is_described_class。

namespace boost
{

namespace container_hash
{

template<class T> struct is_described_class;

} // namespace container_hash

} // namespace boost

is_described_class<T>

template<class T> struct is_described_class
{
    static constexpr bool value = /* see below */;
};

當 boost::describe::has_describe_bases<T>::value 為 true、boost::describe::has_describe_members<T>::value 為 true，且 T 不是聯集時，is_described_class<T>::value 為 true。

如果預設行為無法推斷出正確的值，則允許使用者為自己的類型特化 is_described_class。

<boost/container_hash/is_tuple_like.hpp>

定義特徵 boost::container_hash::is_tuple_like。

namespace boost
{

namespace container_hash
{

template<class T> struct is_tuple_like;

} // namespace container_hash

} // namespace boost

is_tuple_like<T>

template<class T> struct is_tuple_like
{
    static constexpr bool value = /* see below */;
};

當 std::tuple_size<T>::value 有效時，is_tuple_like<T>::value 為 true。

如果預設行為無法推斷出正確的值，則允許使用者為自己的類型特化 is_tuple_like。

設計與實作注意事項

雜湊函式的品質

許多雜湊函數都力求輸入值和輸出值之間沒有關聯性。它們試圖對非常相似的輸入值均勻地分佈輸出值。此雜湊函數並未做出此類嘗試。事實上，對於整數，雜湊函數的結果通常只是輸入值。因此，相似但不同的輸入值通常會產生相似但不同的輸出值。這表示它不適合作為通用的雜湊函數。例如，雜湊表可能會捨棄雜湊函數的位元，導致很可能發生碰撞，或者當雜湊值聚集在一起時，可能會發生不良的碰撞解決方案。在這種情況下，此雜湊函數的效能會很差。

但標準對雜湊函數沒有此類要求，它僅要求兩個不同值的雜湊不大可能發生碰撞。設計為使用標準雜湊函數的容器或演算法必須實作為當雜湊函數的輸出與其輸入相關時仍能良好運作。由於它們正在付出這個代價，因此更高品質的雜湊函數將會是浪費。

hash_value 客製化點

針對使用者類型自訂標準 std::hash 函數物件的方式是透過特化。boost::hash 選擇了不同的機制 — 使用者命名空間中自由函數 hash_value 的多載，該多載是透過引數相依查找找到的。

這兩種方法各有優缺點。特化函數物件更嚴格，因為它僅適用於精確的類型，而不適用於衍生或可轉換的類型。另一方面，定義函數更容易且更方便，因為它可以直接在類型定義中作為 inline friend 進行。

透過轉換可以呼叫多載的事實，在早期版本的函式庫中確實引起了問題，該函式庫為所有整數類型（包括 bool）分別定義了 hash_value。特別是在沒有 explicit 轉換運算子的 C++03 下，某些類型會轉換為 bool，以便在例如 if 陳述式中測試它們，這導致它們雜湊為 0 或 1，這通常不是人們所期望或想要的。

然而，透過宣告內建的 hash_value 多載為範本，並受限於例如 std::is_integral 或其等效項目，解決了這個問題。這會導致可轉換為整數的類型不再匹配，從而避免了問題。

雜湊值穩定性

一般而言，函式庫不保證雜湊值在不同版本之間保持不變（否則將無法進行改進）。然而，從歷史上看，值一直相當穩定。在 1.81 版之前，之前的變更發生在 1.56 版（更好的 hash_combine）和 1.78 版（macOS 特定的 hash_combine 變更）。

程式碼通常不應依賴特定的雜湊值，但對於那些願意承擔因雜湊值變更而偶爾發生中斷風險的人來說，函式庫現在有一個測試，會針對許多類型的參考值檢查雜湊值 (test/hash_reference_values.cpp)，其版本歷史可以作為雜湊值何時變更以及針對哪些類型變更的粗略指南。

hash_combine

此函式庫的初始實作是基於函式庫擴充技術報告問題列表的第 6.18 號問題 (第 63-67 頁)，其中提出了以下 hash_combine 的實作方式：

template<class T>
void hash_combine(size_t & seed, T const & v)
{
    seed ^= hash_value(v) + (seed << 6) + (seed >> 2);
}

取自 Timothy C. Hoad 和 Justin Zobel 的論文「用於識別版本化和抄襲文件的方法」。

在 Boost 的正式審查期間，Dave Harris 指出此實作存在所謂的「零陷阱」；如果 seed 最初為 0，且所有輸入都是 0（或雜湊為 0），則無論組合多少輸入值，seed 都會保持為 0。

這是一個不良的屬性，因為它會導致由零組成的容器，無論其大小為何，都具有零的雜湊值。

為了修正這個問題，在計算中加入了任意常數 0x9e3779b9（32 位元定點表示法的黃金比例），產生了

template<class T>
void hash_combine(size_t & seed, T const & v)
{
    seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

這就是 Boost 1.33（包含此函式庫的第一個版本）中發行的版本。

這個函式在當時對於品質和速度之間取得了合理的妥協，當時的輸入是由 char 組成的，但它不太適合組合任意的 size_t 輸入。

在 Boost 1.56 中，它被衍生自 Austin Appleby 的 MurmurHash2 雜湊函式輪的函式所取代。

在 Boost 1.81 中，它再次被更改為等同於 mix(seed + 0x9e3779b9 + hash_value(v)) 的形式，其中 mix(x) 是一個高品質的混合函式，它是 size_t 值的對射，形式為

x ^= x >> k1;
x *= m1;
x ^= x >> k2;
x *= m2;
x ^= x >> k3;

這種混合函式最初由 Austin Appleby 設計為他的 MurmurHash3 雜湊函式的「最終混合」部分。他使用了

x ^= x >> 33;
x *= 0xff51afd7ed558ccd;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53;
x ^= x >> 33;

作為 64 位元函式 fmix64，並使用

x ^= x >> 16;
x *= 0x85ebca6b;
x ^= x >> 13;
x *= 0xc2b2ae35;
x ^= x >> 16;

作為 32 位元函式 fmix32。

David Stafford、David Stafford、Pelle Evensen 和 Jon Maiga 後續提出了幾種 64 位元函式的改進方案。我們目前使用 Jon Maiga 的函式

x ^= x >> 32;
x *= 0xe9846af9b1a615d;
x ^= x >> 32;
x *= 0xe9846af9b1a615d;
x ^= x >> 28;

在 32 位元下，我們使用「TheIronBorn」在 Github 問題中提出的混合函式，該問題位於 Chris Wellons 的 Hash Prospector 的儲存庫中

x ^= x >> 16;
x *= 0x21f0aaad;
x ^= x >> 15;
x *= 0x735a2d97;
x ^= x >> 15;

有了這個改進的 hash_combine，字串的 boost::hash 現在通過了 Austin Appleby 的 SMHasher 測試套件 (對於 64 位元 size_t)。

hash_range

hash_range(seed, first, last) 的傳統實作一直是

for( ; first != last; ++first )
{
    boost::hash_combine<typename std::iterator_traits<It>::value_type>( seed, *first );
}

(需要顯式範本參數來支援具有代理傳回型別的迭代器，例如 std::vector<bool>::iterator。)

這是合乎邏輯、一致且直接的。在 typename std::iterator_traits<It>::value_type 為 char 的常見情況下，也就是 boost::hash<std::string> 的常見情況下，這會留下許多效能未被利用，因為單獨處理每個 char 的效率遠低於批量處理多個。

在 Boost 1.81 中，hash_range 已變更為一次處理四個 char、signed char、unsigned char、std::byte 或 char8_t 類型的元素。從 first[0] 到 first[3] 組成一個 uint32_t，然後將該 uint32_t 傳遞給 hash_combine。

在 Boost 1.82 中，這些類型的 hash_range 已變更為使用 mulxp1_hash。這提高了字串雜湊的品質和速度。

請注意，hash_range 傳統上也保證了相同的元素序列會產生相同的雜湊值，無論迭代器類型為何。在變更為 char 範圍雜湊之後，此屬性仍然有效。應用於 char 序列 { 'a', 'b', 'c' } 的 hash_range，無論該序列來自 char[3]、std::string、std::deque<char> 或 std::list<char>，都會產生相同的值。

連結

將雜湊表新增至標準函式庫的提案
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1456.html

雜湊表提案說明了大部分的設計。雜湊函式物件在 D 節中討論。

C++ 標準函式庫技術報告
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf

在 6.3.2 節中包含雜湊函式規範。

函式庫擴充技術報告問題列表
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf

該函式庫實作了第 6.18 號問題 (第 63-67 頁) 中描述的擴充功能。

用於識別版本化和抄襲文件的方法
Timothy C. Hoad, Justin Zobel
https://people.eng.unimelb.edu.au/jzobel/fulltext/jasist03thz.pdf

包含 boost::hash_combine 初始實作所基於的雜湊函式。

字串雜湊函式的實際效能
M.V. Ramakrishna, J. Zobel
在 Proc. Int. Conf. on Database Systems for Advanced Applications，第 215-223 頁，澳洲墨爾本，1997 年 4 月。
https://www.comp.nus.edu.sg/~lingtw/dasfaa_proceedings/DASFAA97/P215.pdf

在上述論文中被引用為雜湊函式的來源。

MurmurHash3 雜湊函式來源
Austin Appleby
https://github.com/aappleby/smhasher/blob/61a0530f28277f2e850bfc39600ce61d02b518de/src/MurmurHash3.cpp#L65-L90

Austin Appleby 的 32 位元和 64 位元最終混合函式，引入了「xmxmx」的一般形式，這是一種高品質的對射轉換，近似於隨機排列。

SMHasher 雜湊函式測試套件
Austin Appleby
https://github.com/aappleby/smhasher

包含用於評估雜湊函式的一系列測試。目前的 64 位元字串 boost::hash 實作通過了 SMHasher。先前的迭代沒有通過。

更好的位元混合 - 改進 MurmurHash3 的 64 位元最終器
David Stafford
https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html

描述了所謂的「變體 13」混合函式，它是對 MurmurHash3 的 fmix64 的改進，因為被 splitmix64 隨機數產生器採用而聞名。

更強大、更好、更 Moremur；更好的 Murmur3 類型混合器
Pelle Evensen
https://mostlymangling.blogspot.com/2019/12/stronger-better-morer-moremur-better.html

描述了 Moremur，它是對 MurmurHash3 fmix64 和 Stafford「變體 13」的改進。

改進的 mx3 和 RRC 測試
Jon Maiga
http://jonkagstrom.com/mx3/mx3_rev2.html

包含對 MurmurHash3 fmix64 和「變體 13」的另一個改進。這是目前 std::size_t 為 64 位元時 boost::hash_combine 的實作方式。

雜湊函式的探勘
Chris Wellons
https://nullprogram.com/blog/2018/07/31/

描述了 Hash Prospector，這是一個用於發現和評估混合函式的工具。

最新已知最佳函式
「TheIronBorn」
https://github.com/skeeto/hash-prospector/issues/19

描述了一個良好的 32 位元混合函式，當 std::size_t 為 32 位元時，目前的 boost::hash_combine 實作會使用它。

致謝

此函式庫基於 Peter Dimov 的設計。在初始開發期間，Joaquín M López Muñoz 提出了許多有用的建議並貢獻了修正。

正式審查由 Thorsten Ottosen 管理，並且該函式庫由以下人員審查：David Abrahams、Alberto Barbati、Topher Cooper、Caleb Epstein、Dave Harris、Chris Jefferson、Bronek Kozicki、John Maddock、Tobias Swinger、Jaap Suter、Rob Stewart 和 Pavel Vozenilek。自那時起，Daniel Krügler、Alexander Nasonov 和沈慧峰提出了進一步的建設性批評。

指標的雜湊函式實作基於 Alberto Barbati 和 Dave Harris 提出的建議。Dave Harris 也提出了一個重要的改進方案，並應用於 boost::hash_combine。

Daniel Krügler 提出了一些有用的浮點雜湊演算法改進方案。

原始實作來自 Jeremy B. Maitin-Shepard 的雜湊表函式庫，但這是一個完全重寫的版本。

文件由 Christian Mazakas 從 Quickbook 轉換為 AsciiDoc。

變更紀錄

Boost 1.67.0

將函式庫移至其自己的模組 container_hash 中。
移動新模組名稱的標頭，現在位於：<boost/container_hash/hash.hpp>、<boost/container_hash/hash_fwd.hpp>、<boost/container_hash/extensions.hpp>。
新增轉發標頭以支援舊的標頭位置。
支援 std::string_view、std::error_code、std::error_condition、std::optional、std::variant、std::monostate (如果可用)。
更新來自其他 Boost 函式庫的包含路徑。
手動寫出 tuple 多載，而不是使用預處理器來產生它們。由於更好的錯誤訊息和更輕鬆的偵錯，應該可以提高可用性。
修正教學範例 (#11017)。
在使用 libc++ 時，快速修正雜湊 vector<bool> 的問題。將嘗試在下一個版本中引入更通用的修正。

Boost 1.66.0

在使用 Clang 時避免浮點比較警告 - 這個因應措施已經適用於 GCC，並且在 Clang 假裝是 GCC 時使用，但是當在其他環境中執行 Clang 時，警告會出現。

Boost 1.65.0

支援 char16_t、char32_t、u16string、u32string

Boost 1.64.0

修復了 Visual C++ 最新版本已移除 std::unary_function 和 std::binary_function 的問題 (#12353)。

Boost 1.63.0

修正了一些警告。
僅在我們知道有 wchar_t 時才定義 std::wstring 的雜湊。否則，會出現編譯錯誤，因為沒有多載可供雜湊寬字串中的字元 (#8552)。

Boost 1.58.0

修復了嚴格別名違規 (GitHub #3)。

Boost 1.56.0

移除了一些 Visual C++ 6 因應措施。
正在進行改進 hash_combine 的工作。這變更了先前在參考文件中定義的組合函式。

Boost 1.55.0

簡化 SFINAE 檢查，使其有望在 Sun 5.9 上運作 (#8822)。
抑制 Visual C++ 無限迴圈警告 (#8568)。

Boost 1.54.0

Ticket 7957：修正了一個錯字。

Boost 1.53.0

新增對 boost::int128_type 和 boost::uint128_type 的支援 (如果可用) - 目前僅適用於某些 gcc 版本的 __int128 和 unsigned __int128。
在已知具有標準浮點函式的平台上，請勿使用自動偵測 - 如果有多義的多載，可能會中斷。
修復使用二進位 float 雜湊時未定義的行為 (Thomas Heller)。

Boost 1.52.0

還原上一個版本中意外移除的 enum 支援。
新的浮點雜湊器 - 將在更多平台上雜湊二進位表示法，這樣應該會更快。

Boost 1.51.0

支援標準智慧型指標。
現在使用 SFINAE 實作 hash_value，以避免在呼叫時隱式轉換為內建類型。
更新為使用新的組態巨集。

Boost 1.50.0

Ticket 6771：避免 gcc 的 -Wfloat-equal 警告。
Ticket 6806：支援 std::array 和 std::tuple (如果可用)。
將已長期棄用的 boost/container_hash/detail/container_fwd.hpp 新增棄用警告。

Boost 1.46.0

避免使用 gcc 的 -Wconversion 旗標時產生的警告。

Boost 1.44.0

新增選項，透過定義 BOOST_HASH_NO_IMPLICIT_CASTS 來防止在呼叫 hash_value 時進行隱式轉換。當使用 boost::hash 處理沒有宣告 hash_value 但可以隱式轉換為具有 hash_value 宣告的類型的類型時，它會使用該隱式轉換來雜湊它。這有時可能會出錯，例如，使用轉換為 bool 並僅雜湊為 2 個可能的值。由於修正此問題是一項重大變更，並且僅在發布週期中稍晚才進行，因此目前是選擇加入。此或類似的行為將在未來的版本中成為預設行為。

Boost 1.43.0

Ticket 3866：在使用 gcc 的平行函式庫時不要轉發宣告容器，允許使用者透過定義 BOOST_DETAIL_NO_CONTAINER_FWD 巨集來停止轉發宣告。
Ticket 4038: 避免將 0.5 和 0 雜湊到相同的值。
停止使用已棄用的 BOOST_HAS_* 巨集。

Boost 1.42.0

減少 Visual C++ 警告等級 4 的警告數量。
一些程式碼格式變更，以將程式碼行調整為 80 個字元。
重新命名內部命名空間。

Boost 1.40.0

使用樣板元程式設計自動配置 float 函數，而不是嘗試手動配置每種可能性。
當 STLport 不支援 long double 時的解決方案。

Boost 1.39.0

將 hash_fwd.hpp 的實作移至 hash 子目錄，在舊位置保留一個轉發標頭。您仍然應該使用舊位置，新位置主要用於實作和可能的模組化。
Ticket 2412: 移除已棄用的標頭。
Ticket 2957: 修正 vxworks 的設定。

Boost 1.38.0

將已棄用標頭中的警告從 1.34.0 版變更為錯誤。這些警告將在 Boost 的未來版本中移除。
將 detail 標頭移出 boost/container_hash/detail，因為它們是 functional/hash 的一部分，而不是 container_hash。 boost/container_hash/detail/container_fwd.hpp 已移至 boost/detail/container_fwd.hpp，因為它在此函式庫之外使用，其他標頭已移至 boost/functional/hash/detail。

Boost 1.37.0

Ticket 2264: 在 Visual C++ 中，始終使用 C99 float 函數來處理 long double 和 float，因為 C++ 的多載函數並不總是可用。

Boost 1.36.0

停止使用 OpenBSD 不穩定的 std::numeric_limits。
使用 boost 的 typedef 來處理 long long 和 unsigned long long。
將擴充功能移至其自己的標頭。

Boost 1.35.0

支援 long long、std::complex。
改進雜湊浮點數的演算法
- 如 Daniel Krügler 在給 boost 使用者列表的貼文中所述，改善可移植性。
- 將更多資訊放入每個 combine 迴圈，這可以減少 combine 被呼叫的次數，並希望提供更好的雜湊函數品質。
- 改進雜湊浮點數的演算法。
- 在 Cygwin 上，對浮點數使用二進位雜湊函數，因為 Cygwin 沒有適用於 long double 的適當浮點函數。
- 永遠不使用不支援 long double 的 fpclass。
- Ticket 1064: 移除不必要的 errno 使用。
為更多內建類型明確地多載。
對文件進行少量改進。
一些錯誤和警告修復
- Ticket 1509: 抑制另一個 Visual C++ 警告。
- 一些針對 Sun 編譯器的解決方案。

Boost 1.34.1

Ticket 952: 抑制 Visual C++ 上不正確的 64 位元警告。

Boost 1.34.0

為標準類別使用宣告，以便函式庫不需要包含它們的所有標頭
已棄用 <boost/functional/hash/*.hpp> 標頭。現在使用單一標頭 <boost/functional/hash.hpp>。
新增對 BOOST_HASH_NO_EXTENSIONS 巨集的支援，這會停用對 TR1 的擴充功能。
對浮點數的雜湊函數進行少量改進。
更新可移植範例，希望更具普遍可移植性。

Boost 1.33.1

修正沈慧峰指出的點範例。

Boost 1.33.0

初始版本

版權與授權

此文件為

並依據 Boost 軟體授權條款，版本 1.0 散佈。