一个std::unordered_map的哈希值

Question

一个std::unordered_map的哈希值

9

根据标准，在std::hash类中不支持容器（更别说无序容器了）。因此，我想知道如何实现这一点。我的代码如下：

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

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

如何有效地完成这个任务？如果 map 中的顺序未定义，是否会有影响？

注意：我不想使用 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;
}

我真的不确定只用简单的异或运算是否足够。

- Mike Lischke

将s/concatenate/XOR，你就可以开始了。一个哈希函数必须能够为两个语义上等价的值生成相同的哈希，并在所有可能的哈希值集合中合理地分布其输出。 - The Paramagnetic Croissant

@dyp OP想要对容器本身进行哈希。 - The Paramagnetic Croissant

基本上，您的问题是如何为（无序的）一系列值获取哈希，并且实际上并不特定于std::unordered_map？ - Stephan Dollberg

"足够"是什么意思？你如何定义 "足够"？是完全没有冲突吗？ - BartoszKP

1

“足够”在这里的意思是它满足了与std :: hash定义相同的哈希函数的条件：http://en.cppreference.com/w/cpp/utility/hash。 - Mike Lischke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user123 · Accepted Answer

响应

如果你的意思是函数是否是单射的，答案是否定的。原因是你的函数可以输出的所有哈希值的基数为2^64，而输入空间要大得多。然而，这并不重要，因为考虑到你的输入的性质，你不能有一个单射的哈希函数。一个好的哈希函数具有以下特点：

它不容易反演。给定输出k，无法在宇宙寿命内计算出m，使得h(m) = k。
范围在输出空间上均匀分布。
很难找到两个输入m和m'，使得h(m) = h(m')

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

对于不相等的两个参数 k1 和 k2，std::hash<Key>()(k1) == std:：hash<Key>()(k2) 的概率应该非常小，接近于 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表示：

对于两个相等的参数k1和k2，std::hash<Key>()(k1) == std::hash<Key>()(k2)。

这是哈希函数的一个微不足道的要求。您的解决方案避免了这个问题，因为迭代顺序并不重要，因为XOR是可交换的。

可能的解决方案

如果您不需要加密安全性，可以稍微修改您的解决方案以消除对称性。这种方法在哈希表等实践中是可行的。这种解决方案与无序图中顺序未定义的事实无关。它使用了与您的解决方案相同的属性（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中，键值对哈希值只是键的哈希和值的哈希的线性组合。您可以构建更复杂的东西，但没有必要。