响应
如果你的意思是函数是否是单射的,答案是否定的。原因是你的函数可以输出的所有哈希值的基数为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
中,键值对哈希值只是键的哈希和值的哈希的线性组合。您可以构建更复杂的东西,但没有必要。
s/concatenate/XOR
,你就可以开始了。一个哈希函数必须能够为两个语义上等价的值生成相同的哈希,并在所有可能的哈希值集合中合理地分布其输出。 - The Paramagnetic Croissantstd::unordered_map
? - Stephan Dollberg