1

我正在寻找散列无序容器，例如unordered_mapand unordered_set。对于有序类型，如向量，boost::hash_range(v.begin(). v.end())效果很好，但它也依赖于顺序，例如

#include <boost/functional/hash.hpp>
#include <functional>
namespace std {
    template<>
    struct hash<std::vector<int>> {
        size_t operator ()(const std::vector<int>& v) const noexcept {
            return boost::hash_range(v.begin(), v.end());
        }
    };
}

这个工作的例子：https ://coliru.stacked-crooked.com/a/0544c1b146ebeaa0

boost.org说

如果您正在计算数据的哈希值，其中数据的顺序在比较中并不重要（例如一组），您将必须确保数据始终以相同的顺序提供。

好的，这看起来很容易——只需以某种方式对数据进行排序，但我不想每次散列时都这样做。使用正常map或set可以工作，但我需要做一些重写。

此外，这将要求我使用的每种类型都具有>、或定义<，以及和。<=>===std::hash

如何对容器进行哈希处理以使顺序无关紧要？

4

2 回答 2

1

这个要求似乎很合乎逻辑，因为散列函数以某种方式将先前元素散列与当前元素散列组合在一起，那么顺序很重要，因为

H(A, B, C)然后计算，H(H(H(A), B), C)以便将每个中间结果用作下一个元素的输入（考虑一个分组密码）。

要在不关心排序的情况下散列元素序列，您需要一个可交换散列函数，因此您将被限制为可交换操作（例如 XOR）。我不确定这样的散列函数有多强大，但对于您的特定情况，它可能就足够了。

于 2020-12-21T23:38:21.623 回答
0

在对各个容器元素的哈希值进行排序后，可以再次对排序后的哈希值列表进行哈希，得到无序容器的哈希值。

假设H1是单个元素H2的散列函数并且是散列值列表的散列函数，那么具有元素 A、B 和 C 的某个无序容器的散列值可以计算为H2(SORT(H1(A), H1(B), H1(C)))。通过构造，生成的哈希值将独立于顺序。这样，与使用交换操作组合单个哈希值相比，您还将获得更强的哈希值。

于 2021-10-10T16:03:25.243 回答