c++ - 仅在 boost::hash_combine 中运行一个程序期间保证确定性

Question

在为整数寻找一些确定性(多次运行，多台机器)哈希器时，我偶然发现了 boost::hash_combine(size_t & seed, T const& v)。不幸的是，在 documentation据说

This hash function is not intended for general use, and isn't guaranteed to be equal during separate runs of a program - so please don't use it for any persistent storage or communication.

然而，在查看实现时，我没有看到任何可能在单独运行中导致不同行为的可疑代码 - 只是一些乘法和加法(可能会溢出)、位移位和异或运算，所有这些都使用常量。更重要的是，hasher 在多次执行时表现一致。

那么，禁止在整个运行过程中保证确定性的实际问题在哪里？

下面粘贴最有趣的部分:

template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    boost::hash<T> hasher;
    return boost::hash_detail::hash_combine_impl(seed, hasher(v));
}

template <typename T>
typename boost::hash_detail::basic_numbers<T>::type hash_value(T v)
{
    return static_cast<std::size_t>(v);
}

inline void hash_combine_impl(boost::uint64_t& h,
        boost::uint64_t k)
{
    const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
    const int r = 47;

    k *= m;
    k ^= k >> r;
    k *= m;

    h ^= k;
    h *= m;

    // Completely arbitrary number, to prevent 0's
    // from hashing to 0.
    h += 0xe6546b64;
}

Answer 1

原因是散列表中经常使用散列。试图攻击服务(使用涉及哈希表的 C++ 代码)的恶意用户可能会通过强制对插入哈希表的项目进行哈希冲突来大幅降低其性能(普通操作的性能从 O(1) 到 O(N) ).通过让每次运行都使用不同的哈希函数，这变得更加困难。

std::hash 也是这样标准化的。引用https://en.cppreference.com/w/cpp/utility/hash :

Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision DoS attacks. (since C++ 14)