3

一个普遍被问到的问题是我们是否应该使用 unordered_map 或 map 来加快访问速度。这个问题最常见（相当古老）的答案是：如果您想直接访问单个元素，请使用 unordered_map 但如果您想迭代元素（很可能以排序方式）使用 map。

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

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

4

3 回答 3

3

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

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

字典排序很简单：如果你告诉我你想根据它的 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. 它可能更慢（不确定），但它更安全。

于 2012-11-10T16:43:36.663 回答
2

没有真正的冲突对象这样的东西，因为这个东西取决于你使用的散列函数。假设对象不相同 - 有一些功能可用于创建要使用的信息散列函数。

假设您对您的数据有一些了解——并且您知道某些散列函数可能会发生很多冲突h1()——那么您应该找到并使用h2()更适合此任务的不同散列函数。

也就是说，还有其他问题以及为什么偏爱基于树的数据结构而不是哈希库（例如延迟和集合的大小），我在这个线程中的回答涵盖了一些问题。

于 2012-11-10T16:21:11.890 回答
1

试图对此过于聪明是没有意义的。与往常一样，分析、比较、优化（如果有用）。涉及的因素很多——其中相当多的因素没有在标准中指定，并且会因编译器而异。有些事情在特定硬件上可能会更好或更差。如果您对这些东西感兴趣（或付费假装感兴趣），您应该更系统地了解这些东西。您可以先了解一些实际的散列函数及其特征。很难找到一个哈希函数——对于所有实际目的——不比随机但可重复的值更容易发生冲突——只是有时接近那个点比处理一些额外的冲突要慢。

于 2012-11-10T17:07:58.463 回答