用于`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);
}

但这种解决方案根本无法扩展：对于一个包含1000万个元素的vector<double>，它需要超过2.5秒的时间（根据VS的数据）。

在这种情况下，是否存在一种快速哈希函数的解决方案？

请注意，从向量引用中创建哈希值并不是可行的解决方案，因为相关的unordred_map将在不同的运行中使用，并且两个具有相同内容但不同地址的vector<double>将被映射到不同的位置（这对该应用程序来说是不希望的行为）。

- justHelloWorld

---

你会真的使用具有1000万个元素的double向量作为键吗？我有点怀疑。 - milleniumbug

1. 你确定编译时打开了所有优化选项吗？对于哈希/合并“double”类型的值需要250ns似乎太慢了。
2. 检查一下你的标准库中的std::hash<double>是否过于智能了，也许一个不那么花哨的实现（例如 *reinterpret_cast<const size_t *>(&v)）会更适合你的用法。

- user4815162342

Visual Studio 2.5秒？你试过使用Release构建而不是Debug编译吗？结果可能会让你惊讶。如果已经这样了，只需获取v.data()并在紧密循环中直接迭代元素，使用自己的内联哈希代码即可获得另一个巨大的性能提升。对于你所拥有的1000万个项目，函数调用开销太大了。 - selbie

你明显没有使用优化编译，检查一下这个 ideone 示例：它只需要大约50毫秒！ - BeyelerStudios

又一篇抱怨某个应用程序缓慢的文章，但是没有说明该应用程序是如何编译的，即是否进行了优化。如果您在没有进行优化的情况下进行测试，则这些发现是没有意义的。这些发现是没有意义的，因为Visual Studio的调试模式会在vector类中添加大量迭代器和边界检查——这不仅仅是在循环中展开几次而已。 - PaulMcKenzie

Answer 1

注意：根据评论，通过优化编译可以获得25-50倍的加速。首先进行此操作。如果仍然太慢，请参见下文。

---

我认为你能做的事情不多。你必须触及所有元素，而组合功能的速度已经尽可能快了。

一种选择是并行化哈希函数。如果你有8个核心，你可以运行8个线程来哈希向量的1/8，然后在最后组合8个结果值。对于非常大的向量，同步开销可能是值得的。

- Claudiu

---

好的，现在启用了发布配置后，只需要117毫秒。但是，如果我们必须重新哈希数百万个键（例如由于unordered_map中的负载因子不良），这仍然是一个不可接受的解决方案。因此，我认为我将尝试使用您的并行解决方案进一步改进它！谢谢！ - justHelloWorld

Answer 2

MSVC旧版哈希表采用的方法是较少采样。这意味着孤立的更改不会显示在您的哈希值中，但您要避免的是读取和处理整个80 MB的数据以便对向量进行哈希处理。不读取一些字符是相当不可避免的。

第二件事是不要为所有的vector专门定制std :: hash，这可能会使您的程序不合规（如缺陷解决方案所建议的），并且至少是一个糟糕的计划（因为std肯定会允许自己添加哈希组合和向量哈希）。

当我编写自定义哈希时，通常使用ADL（Koenig Lookup）使其易于扩展。

namespace my_utils {
  namespace hash_impl {
    namespace details {
      namespace adl {
        template<class T>
        std::size_t hash(T const& t) {
          return std::hash<T>{}(t);
        }
      }
      template<class T>
      std::size_t hasher(T const& t) {
        using adl::hash;
        return hash(t);
      }
    }
    struct hash_tag {};
    template<class T>
    std::size_t hash(hash_tag, T const& t) {
      return details::hasher(t);
    }
    template<class T>
    std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) {
      seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    template<class Container>
    std::size_t fash_hash_random_container(hash_tag, Container const& c ) {
      std::size_t size = c.size();
      std::size_t stride = 1 + size/10;
      std::size_t r = hash(hash_tag{}, size);
      for(std::size_t i = 0; i < size; i += stride) {
        r = hash_combine(hash_tag{}, r, c.data()[i])
      }
      return r;
    }
    // std specializations go here:
    template<class T, class A>
    std::size_t hash(hash_tag, std::vector<T,A> const& v) {
      return fash_hash_random_container(hash_tag{}, v);
    }
    template<class T, std::size_t N>
    std::size_t hash(hash_tag, std::array<T,N> const& a) {
      return fash_hash_random_container(hash_tag{}, a);
    }
    // etc
  }
  struct my_hasher {
    template<class T>
    std::size_t operator()(T const& t)const {
      return hash_impl::hash(hash_impl::hash_tag{}, t);
    }
  };
}

现在，my_hasher 是一个通用哈希器。它使用在 my_utils::hash_impl 中声明（适用于 std 类型）的哈希函数，或者调用名为 hash 的自由函数来哈希给定类型的内容。如果这些都失败了，就会尝试使用 std::hash<T>。如果还是失败，就会产生编译时错误。

根据我的经验，在要哈希的类型的命名空间中编写自由的 hash 函数要比打开 std 并专门为其特化 std::hash 要少烦。

该哈希器递归地理解向量和数组。对于元组和成对需要更多的工作。

它以约 10 倍的采样率对这些向量和数组进行采样。

（注意：hash_tag 既是个笑话，也是一种强制 ADL 的方法，以避免不得不在 hash_impl 命名空间中前向声明 hash 特化，因为这个要求很麻烦。）

采样的代价是可能会出现更多的冲突。

---

如果你有大量的数据，另一个方法是对它们进行一次哈希，并跟踪它们何时被修改。为此，使用在类型上下文中跟踪哈希是否最新的写时复制单子界面。现在一个向量只需要哈希一次；如果你修改它，哈希会被丢弃。

你可以更进一步，使用随机访问哈希（其中很容易预测在编辑给定值时哈希会发生什么），并调节访问向量的所有方式。这很棘手。

你也可以多线程进行哈希计算，但我猜想你的代码可能已经受到了内存带宽的限制，并且多线程不会有太大的帮助。还是值得一试的。

你可以使用比一个扁平向量更高级的结构（例如树形结构），其中值的更改以哈希类似的方式冒泡到根哈希值。这将增加所有元素访问的 lg(n) 开销。同样地，你必须将原始数据包装在控件中，以保持哈希计算的最新状态（或跟踪哪些范围是脏的，并需要更新）。

最后，因为你每次处理 1000 万个元素，请考虑转向强大的大规模存储解决方案，如数据库等。在 Map 中使用 80MB 的键对我来说似乎很奇怪。

- Yakk - Adam Nevraumont