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 不满足在更一般的上下文中对哈希函数提出的更严格的要求。特别是，该哈希函数不是加密的，不能抵抗 determined adversary 的碰撞，并且不一定具有良好的“雪崩”特性；也就是说，输入中的微小（单比特）扰动不一定会导致输出中的大（半比特变化）扰动。

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

合并哈希值

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

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

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

效果

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

备注

对于字符，当前实现使用 mulxp1_hash（当 std::size_t 为 64 位时）和 mulxp1_hash32（当它为 32 位时）。

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

效果: 使用 [first, last) 中每个 i 的 boost::hash<typename std::iterator_traits<It>::value_type>()(*i) 的值更新 seed，这样元素的顺序不会影响最终结果。

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

该库的初始实现基于库扩展技术报告问题列表（第 63-67 页）的第 6.18 号问题，该问题提出了以下 `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”在 Chris Wellons 的 Hash Prospector 存储库的 Github 问题中提出的混合函数

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
在澳大利亚墨尔本举行的国际高级应用数据库系统会议论文集中，第 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 库的包含路径。
手动编写元组重载，而不是使用预处理器生成它们。由于更好的错误消息和更容易的调试，应该提高可用性。
修复教程示例（#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

针对最近删除了 `std::unary_function` 和 `std::binary_function` 的 Visual C++ 版本的修复程序（#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

工单 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

工单 6771：避免 gcc 的 `-Wfloat-equal` 警告。
工单 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` 但具有到已声明类型的隐式转换的类型使用 `boost::hash` 时，它将使用该隐式转换进行哈希计算。这有时可能会导致非常错误的结果，例如，使用到 `bool` 的转换并且只哈希到 2 个可能的值。由于修复此问题是一个破坏性更改，并且在发布周期中很晚才提出，讨论很少，因此目前选择加入。此选项，或类似的选项，将在未来的版本中成为默认选项。

Boost 1.43.0

工单 3866：使用 gcc 的并行库时不要前向声明容器，允许用户通过定义 `BOOST_DETAIL_NO_CONTAINER_FWD` 宏来停止前向声明。
工单 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 子目录，在旧位置留下一个转发头文件。您仍然应该使用旧位置，新位置主要用于实现和可能的模块化。
工单 2412：删除已弃用的头文件。
工单 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

工单 2264：在 Visual C++ 中，始终对 long double 和 float 使用 C99 浮点函数，因为 C++ 重载并非始终可用。

Boost 1.36.0

停止使用 OpenBSD 不稳定的 `std::numeric_limits`。
使用 boost 类型定义 `long long` 和 `unsigned long long`。
将扩展移动到它们自己的头文件中。

Boost 1.35.0

支持 `long long`、`std::complex`。
改进了用于哈希浮点数的算法。
- 正如 Daniel Krügler 在Boost 用户列表中的帖子中所述，提高了可移植性。
- 在每个组合循环中放入更多信息，这可以减少调用 combine 的次数，并有望提供更高质量的哈希函数。
- 改进了哈希浮点数的算法。
- 在 Cygwin 上对浮点数使用二进制哈希函数，因为 Cygwin 没有针对 `long double` 的合适的浮点函数。
- 从不使用不支持 `long double` 的 `fpclass`。
- 工单 1064：删除了不必要的 errno 使用。
为更多内置类型显式重载。
对文档进行了细微改进。
一些错误和警告修复。
- 工单 1509：抑制另一个 Visual C++ 警告。
- 一些针对 Sun 编译器的解决方法。

Boost 1.34.1

工单 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 分发。