std::unordered_map 的哈希值

Question

根据标准，std::hash class 中不支持容器（更不用说无序容器了）。所以我想知道如何实现它。我有的是：

std::unordered_map<std::wstring, std::wstring> _properties;
std::wstring _class;

我考虑过迭代条目，计算键和值的各个哈希值（通过 std::hash<std::wstring>）并以某种方式连接结果。

执行此操作的好方法是什么？如果未定义地图中的顺序，这有关系吗？

注意：我不想使用 boost。

有人建议一个简单的异或，所以它会是这样的：

size_t MyClass::GetHashCode()
{
  std::hash<std::wstring> stringHash;
  size_t mapHash = 0;
  for (auto property : _properties)
    mapHash ^= stringHash(property.first) ^ stringHash(property.second);

    return ((_class.empty() ? 0 : stringHash(_class)) * 397) ^ mapHash;
}

?

我真的不确定那个简单的 XOR 是否足够。

Answer 1

回应

如果足够的话，你的意思是你的函数是否是单射的，答案是否定的。推理是你的函数可以输出的所有哈希值的集合具有基数 2^64，而 space 的输入比 大得多 。然而，这并不重要，因为考虑到输入的性质，您不能拥有单射哈希函数。一个好的散列函数具有这些品质：

不容易翻转。给定输出 k，在宇宙的生命周期内找到满足 h(m) = k 的 m 在计算上是不可行的。
范围均匀分布在输出 space。
很难找到两个输入 m 和 m' 使得 h(m) = h(m')

当然，这些的范围实际上取决于您是想要加密安全的东西，还是想要获取一些任意数据块并只向它发送一些任意 64 位整数。如果您想要加密安全的东西，那么自己编写它并不是一个好主意。在这种情况下，您还需要保证函数对输入的微小变化敏感。 std::hash 函数对象不需要密码安全。它存在于与哈希表同构的用例中。 CPP Rerefence 说：

For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().

我将在下面说明您当前的解决方案如何不能真正保证这一点。

碰撞

我将针对您的解决方案的变体提供一些我的观察结果（我不知道您的 _class 成员是什么）。

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) {
    std::hash<std::string> h;
    std::size_t result = 0;
    for (auto&& p : m) {
        result ^= h(p.first) ^ h(p.second);
    }
    return result;
}

容易产生碰撞。考虑以下地图：

std::unordered_map<std::string, std::string> container0;
std::unordered_map<std::string, std::string> container1;
container0["123"] = "456";
container1["456"] = "123";
std::cout << hash_code(container0) << '\n';
std::cout << hash_code(container1) << '\n';

在我的机器上，使用 g++ 4.9.1 编译，输出：

1225586629984767119
1225586629984767119

关于这是否重要的问题出现了。相关的是您将多久拥有一次键和值颠倒的映射。这些冲突将发生在键和值集相同的任何两个映射之间。

迭代顺序

具有完全相同键值对的两个 unordered_map 实例不一定具有相同的迭代顺序。 CPP Rerefence 说：

For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2).

这是哈希函数的一个微不足道的要求。您的解决方案避免了这种情况，因为迭代顺序无关紧要，因为 XOR 是可交换的。

一个可能的解决方案

如果您不需要加密安全的东西，您可以稍微修改您的解决方案以消除对称性。这种方法在实践中适用于哈希表等。此解决方案也与 unordered_map 中的顺序未定义这一事实无关。它使用与您使用的解决方案相同的属性（XOR 的交换性）。

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) {
    const std::size_t prime = 19937;
    std::hash<std::string> h;
    std::size_t result = 0;
    for (auto&& p : m) {
        result ^= prime*h(p.first) + h(p.second);
    }
    return result;
}

在这种情况下，哈希函数所需要的只是一种将键值对映射到任意好的哈希值的方法，以及一种使用交换运算组合键值对的哈希值的方法。这样，顺序并不重要。在我写的例子hash_code中，键值对哈希值只是键的哈希和值的哈希的线性组合。您可以构建更复杂的东西，但没有必要。

std::unordered_map 的哈希值

Hash value for a std::unordered_map

c++

hash

unordered-map

c++11

回应

碰撞

迭代顺序

一个可能的解决方案