c++ - `std::vector` 的快速哈希函数

Question

我实现了此解决方案以从 vector<T> 获取哈希值:

namespace std
{
    template<typename T>
    struct hash<vector<T>>
    {
        typedef vector<T> argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& in) const
        {
            size_t size = in.size();
            size_t seed = 0;
            for (size_t i = 0; i < size; i++)
                //Combine the hash of the current vector with the hashes of the previous ones
                hash_combine(seed, in[i]);
            return seed;
        }
    };
}

//using boost::hash_combine
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

但这个解决方案根本无法扩展:使用 vector<double> 1000 万个元素需要超过 2.5 秒(根据 VS)。

是否存在针对这种情况的快速哈希函数？

请注意，从 vector 引用创建哈希值不是可行的解决方案，因为相关的 unordred_map将在不同的运行中使用，此外还有两个 vector<double>内容相同但地址不同的映射方式不同(此应用程序的不良行为)。

Answer 1

注意: As per the comments ，您可以通过优化编译获得 25-50 倍的加速。这样做，首先。 然后，如果还是太慢，请看下面。

---

我认为您无能为力。您必须触摸所有元素，并且该组合函数的速度与它得到的一样快。

一个选项可能是并行化哈希函数。如果您有 8 个核心，则可以运行 8 个线程来对 vector 的每个哈希 1/8 进行处理，然后在最后组合 8 个结果值。对于非常大的 vector ，同步开销可能是值得的。