基于键类型的选择map或unordered_map

Question

一个普遍的问题是，在快速访问时我们应该使用unordered_map还是map。这个问题最常见（而且很古老）的答案是：如果你想直接访问单个元素，请使用unordered_map，但如果你想迭代元素（最有可能以排序方式进行），请使用map。

在做出这样的选择时，我们不应该考虑键的数据类型吗？因为哈希算法对于一种数据类型（比如int）可能比其他类型（比如字符串）更容易产生冲突。

如果是这种情况（哈希算法非常容易发生冲突），那么即使是直接访问，我也可能会使用map，因为在这种情况下，unordered_map的O(1)常数时间（可能平均大量输入）可能会比lg(N)更高，甚至对于相当大的N值。

- Rampal Chaudhary

Answer 1

你提出了一个很好的观点... 但你关注的部分是错误的。

问题并不在于键的类型本身，而在于用于为该键派生哈希值的哈希函数。

按字典顺序排序很容易：如果你告诉我你想要根据结构体的3个字段来排序（它们已经支持自己的排序），那么我只需要写：

bool operator<(Struct const& left, Struct const& right) {
    return boost::tie(left._1,  left._2,  left._3)
         < boost::tie(right._1, right._2, right._3);
}

我完成了！

然而，编写哈希函数很困难。您需要了解数据的分布（统计学），可能需要防范特别制作的攻击等等...老实说，我不认为有很多人能够创造出一个好的哈希函数。但最糟糕的是，组合也很难！给定两个独立的字段，正确地组合它们的哈希值是很难的（提示：boost::hash_combine）。

因此，确实，如果您不知道自己在做什么，并且正在处理用户制作的数据，请坚持使用 map。它可能会更慢（不确定），但更加安全。

- Matthieu M.

Answer 2

实际上不存在所谓的“易碰撞对象”，因为这取决于您使用的哈希函数。假设这些对象不相同-有一些特征可以用来创建信息丰富的哈希函数。

假设您对数据有一些了解-并且知道某个哈希函数h1()可能会产生许多冲突-那么您应该找到并使用另一个更适合此任务的哈希函数h2()。

---

话虽如此，还有其他问题也是为什么要优先选择基于树的数据结构而不是基于哈希的（例如延迟和集合大小），其中一些问题在我的答案中涵盖。

- amit

Answer 3

在这方面过于聪明是没有意义的。像往常一样，进行配置文件、比较和优化（如果有用）。涉及到许多因素，其中相当多的因素没有在标准中指定，并且会因编译器而异。某些事情在特定硬件上可能会更好或更差。如果您对此感兴趣（或被迫假装感兴趣），您应该更系统地了解这些事情。您可以从学习一些实际哈希函数及其特性开始。几乎不可能找不到一个哈希函数，它在所有实际目的上都没有比可重复但随机值更容易发生冲突的倾向，只是有时接近这一点比处理一些额外的冲突要慢。

- Tony Delroy