Boost C++ 库

...世界上最受推崇和设计最精良的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 编码标准

简介

boost::hash 是 C++11 指定为 std::hash 的哈希函数对象的增强实现。它是 Boost.Unordered、Boost.Intrusive 的无序关联容器、Boost.MultiIndex 的哈希索引和 Boost.Bimap 的 unordered_set_of 的默认哈希函数。

开箱即用，boost::hash 支持

标准整型类型（整数、字符类型和 bool）；
标准浮点类型（float、double、long double）；
指针（指向对象和函数的指针，但不包括指向成员的指针）和 nullptr；
枚举类型；
C 数组；
std::complex;
类似元组的类型，例如 std::pair、std::tuple 以及专门化 std::tuple_size 并提供 get<I> 的用户定义类型；
类似序列的类型，包括标准类型和用户定义类型（类似序列的类型具有返回迭代器的 begin() 和 end() 成员函数）；
无序序列，标准或用户定义的（哈希值不依赖于元素顺序的序列，例如 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 的要求，即对于两个不同的输入值，它们的对应哈希值要么保证不同，要么它们相同的概率（哈希冲突）很小。标准无序容器和基于哈希的 Boost 容器旨在与此类哈希函数良好地配合使用。

boost::hash 不符合通常在更通用上下文中对哈希函数提出的更严格的要求。特别是，哈希函数不是密码学安全的，不能抵抗有决心的攻击者的碰撞攻击，并且不一定具有良好的“雪崩”特性；也就是说，输入中的小（单比特）扰动不一定会导致输出中的大（一半比特改变）扰动。

特别是，传统上，boost::hash 对于所有适合 std::size_t 的整型类型都是恒等函数，因为这保证了不会发生冲突并且速度尽可能快。

教程

当使用 Boost 容器（例如 Boost.Unordered）时，您无需执行任何操作即可使用 boost::hash，因为它是默认设置。要了解如何使用用户定义的类型，请阅读关于为用户类型扩展 boost::hash 的部分。

如果您希望将 boost::hash 与标准无序关联容器一起使用，请将其作为模板参数传递

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 与 book 一起使用

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`。如果它基于对象的名称和作者，则哈希函数应将其考虑在内（如何在下一节中讨论）。

组合哈希值

假设您有一个 point 类，表示二维位置

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.Describe（并免费获得 operator== 的自动定义）向 point 添加 boost::hash 支持的一种更简单的方法是

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

重复调用以从多个变量增量创建哈希值。

效果

使用通过确定性地将其与 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) 的字节将合并并以未指定的方式进行哈希处理。这样做是为了提高哈希字符串时的性能。

备注

对于 char，当 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，对于 [first, last) 中的每个 i，使元素的顺序不影响最终结果。

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。特别是在 C++03 下（它没有 explicit 转换运算符），某些类型可转换为 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、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 比批量处理多个 char 的效率要低得多。

在 Boost 1.81 中，hash_range 已更改为一次处理四个 char、signed char、unsigned char、std::byte 或 char8_t 类型的元素。 uint32_t 由 first[0] 到 first[3] 组成，并且该 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, pages 215-223, Melbourne, Australia, April 1997.
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 位 Finalizer
David Stafford
https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html

描述了所谓的“variant 13”混合函数，它是对 MurmurHash3 的 fmix64 的改进，因其被 splitmix64 随机数生成器采用而闻名。

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

描述了 Moremur，它是对 MurmurHash3 fmix64 和 Stafford “variant 13”的改进。

改进的 mx3 和 RRC 测试
Jon Maiga
http://jonkagstrom.com/mx3/mx3_rev2.html

包含对 MurmurHash3 fmix64 和“variant 13”的另一项改进。这是当前 boost::hash_combine 在 std::size_t 为 64 位时使用的函数。

寻找哈希函数
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 库的包含路径。
手动写出元组重载，而不是使用预处理器生成它们。由于更好的错误消息和更轻松的调试，应该可以提高可用性。
修复教程示例 (#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

支持标准智能指针。
hash_value 现在使用 SFINAE 实现，以避免在调用它时隐式转换为内置类型。
已更新为使用新的配置宏。

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 时进行隐式转换。当对没有声明 hash_value 但具有到具有 hash_value 类型的隐式转换的类型使用 boost::hash 时，它将使用该隐式转换对其进行哈希。这有时可能会非常糟糕，例如使用转换为 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++ 中，始终对 long double 和 float 使用 C99 浮点函数，因为 C++ 重载并非总是可用。

Boost 1.36.0

停止使用 OpenBSD 可疑的 std::numeric_limits。
使用 boost typedefs 定义 long long 和 unsigned long long。
将扩展移动到它们自己的头文件中。

Boost 1.35.0

支持 long long、std::complex。
改进了浮点数哈希的算法
- 改进了可移植性，正如 Daniel Krügler 在 boost 用户列表的帖子中描述的那样。
- 在每个组合循环中容纳更多信息，这可以减少调用组合的次数，并有望提供更高质量的哈希函数。
- 改进了浮点数哈希的算法。
- 在 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 版分发。