Boost C++ 库

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

Boost.ContainerHash - Boost 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 是可扩展的；用户可以定义 `hash_value` 函数的适当重载，来使自定义类型 `X` 可以通过 `boost::hash<X>` 进行哈希。许多（如果不是大多数）Boost 类型已经包含必要的支持。

boost::hash 满足 C++11 标准中为 `std::hash` 指定的要求，即对于两个不同的输入值，它们对应的哈希值要么保证不同，要么它们相同的概率（哈希碰撞）很小。标准无序容器以及基于哈希的 Boost 容器被设计为与此类哈希函数良好配合。

boost::hash 不满足在更通用场景下对哈希函数通常提出的更强要求。特别是，该哈希函数不是加密的，不能抵抗有决心的攻击者产生的碰撞，并且不一定具有良好的“雪崩”特性；也就是说，输入中的微小（例如单比特）扰动不一定会导致输出中的较大（例如半比特改变）扰动。

特别是，`boost::hash` 传统上是所有适合 `std::size_t` 的整型类型的标识函数，因为这保证了无碰撞且速度最快。

近期更新

Boost 1.89.0

  • 添加了 hash_is_avalanching 特性类。

Boost 1.84.0

  • 不再支持 C++03。

Boost 1.82.0

  • 为 `std::nullptr_t` 添加了 `hash_value` 的重载。

  • 添加了 `is_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` 和无序关联容器。

  • 现在开箱即用支持用户定义容器（具有返回迭代器的 `begin()` 和 `end()` 成员函数的类型）。

  • 现在开箱即用支持描述过的结构体和类（使用 `BOOST_DESCRIBE_STRUCT` 或 `BOOST_DESCRIBE_CLASS` 注释过的）。

  • `hash_combine` 已得到改进。这改变了复合类型（容器和元组）以及大于 `size_t` 的标量类型的哈希值。

  • 提高了字符串哈希的性能（以及因此带来的质量）。字符串的 `boost::hash` 现在可以在 64 位模式下通过 SMHasher 测试。

  • 文档已大幅修改以反映这些更改。

Boost 1.78.0

  • 修复了 `hash_combine`，使其行为不再依赖于 `size_t` 是否与 `boost::uint64_t` 是完全相同的类型（在 macOS 上情况并非如此）。这改变了 macOS 上复合类型（容器和元组）的哈希值。

教程

当使用 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);

and

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::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 的内容 — 您可以将其声明（仅限声明）直接复制到您自己的头文件中。这是库提供的一个特殊例外；一般来说，您不能在没有后续版本中断风险的情况下声明库函数，无论是否是 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 或更高版本，为 `point` 添加 `boost::hash` 支持的一个更简单的方法是使用 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 );

template<class Hash> struct hash_is_avalanching;

} // 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`，具有以下理想属性：

  1. 对于一个常量 `s`，当 `v` 取所有可能的 `size_t` 值时，`combine(s, v)` 也应该取所有可能的 `size_t` 值，产生一个接近随机的序列；也就是说，它应该是一个随机排列。

    这保证了对于给定的 `seed`，`combine` 不会在 `boost::hash<T>(v)` 没有产生碰撞的情况下引入哈希碰撞；也就是说，它不会丢失输入信息。这也意味着 `combine(s, v)` 作为 `v` 的函数，具有良好的雪崩特性；也就是说，输入 `v` 的微小（例如单比特）扰动会导致返回值的较大扰动（平均而言，输出的半数比特会改变）。

  2. 对于两个不同的种子 `s1` 和 `s2`，`combine(s1, v)` 和 `combine(s2, v)`，作为 `v` 的函数，应该产生两个不同的随机排列。

  3. `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` 中当前包含的值。

抛出

`std::bad_variant_access` 当 `v.valueless_by_exception()` 为 `true` 时。

<boost/container_hash/​hash_is_avalanching.hpp>

定义特质 `boost::hash_is_avalanching`。

namespace boost
{

template<class Hash> struct hash_is_avalanching;

} // namespace boost

hash_is_avalanching<Hash>

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

hash_is_avalanching<Hash>::value 是

  • 如果 `Hash::is_avalanching` 不存在，则为 `false`；

  • 如果存在且可在编译时转换为 `bool`，则为 `Hash::is_avalanching::value`；

  • 如果 `Hash::is_avalanching` 为 `void`（此用法已弃用），则为 `true`；

  • 否则为 ill-formed。

哈希函数被称为具有“雪崩特性”，如果输入的微小变化导致返回的哈希码发生巨大变化——理想情况下，输入值表示中的一个比特翻转会导致哈希码中的每个比特以 50% 的概率翻转。像 Boost.Unordered 这样的库会查询此特质来确定提供的哈希函数是否高质量。`boost::hash` 对于 `std::basic_string<Ch>` 和 `std::basic_string_view<Ch>`，当 `Ch` 是整型时（这包括 `std::string` 和 `std::string_view` 等），此特质设置为 `true`。用户可以通过以下方式为特定的 `Hash` 类型设置此特质：

  • 如果在类定义中可以访问其源代码，则在类定义中插入嵌套的 `is_avalanching` 类型定义。

  • 为 `Hash` 编写 `boost::hash_is_avalanching` 的特化。

请注意，此特质的使用不限于通过 Boost.ContainerHash 生成的哈希函数。

<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()` 返回一个指向其 `begin()` 和 `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

该库的初始实现基于 Library Extension Technical Report Issues List（第 63-67 页）的 Issue 6.18，该列表提出了以下 `hash_combine` 的实现：

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

取自论文 "Methods for Identifying Versioned and Plagiarised Documents"，作者是 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 位下，我们使用 Chris Wellons 的 Hash Prospector 的 GitHub issue 中 "TheIronBorn" 提出的混合函数

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` 类型的元素。一个 `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，第 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

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

更强，更好，更多，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 位混合函数，当前 boost::hash_combine 实现使用 std::size_t 为 32 位时。

致谢

该库基于 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

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 时发生隐式转换。当使用 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++ 中，始终为 long double 和 float 使用 C99 float 函数，因为 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 用户列表的帖子中所述。

    • 每个 combine 循环可以容纳更多信息，这可以减少调用 combine 的次数，并有望提供更高质量的哈希函数。

    • 改进了浮点数哈希算法。

    • 在 Cygwin 上使用二进制浮点数哈希函数，因为 Cygwin 没有对 long double 的良好浮点函数。

    • 从不使用不支持 long double 的 fpclass。

    • Ticket 1064：移除了不必要的 errno 使用。

  • 为更多内置类型显式重载。

  • 文档的小幅改进。

  • 一些 bug 和警告修复

    • 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

  • 修复了 points 示例，这是由 沈慧峰 指出的。

Boost 1.33.0

  • 初始发布

本文档

  • Copyright 2005-2008 Daniel James

  • Copyright 2022 Peter Dimov

并根据 Boost Software License, Version 1.0 分发。