std :: unordered_map的哈希值

Question

根据标准,std::hash课堂上不支持容器(更不用说无序容器)了.所以我想知道如何实现这一点.我有的是:

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

我想过迭代条目,计算键和值的单个哈希值(via 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,而输入的空间要大得多.但是,这并不重要,因为根据输入的性质,你不能有一个单射散列函数.一个好的哈希函数具有以下特性:

• 它不容易颠倒.给定输出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是可交换的.

可能的解决方案

如果您不需要加密安全的东西,您可以稍微修改您的解决方案以消除对称性.对于散列表等,这种方法在实践中是可行的.该解决方案也与a中的顺序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我写的示例中,键值对散列值只是键的散列和值的散列的线性组合.你可以构造一些更复杂的东西,但没有必要.