c++ - 根据键的类型选择 map 或 unordered_map

Question

一个普遍被问及的问题是我们应该使用 unordered_map 还是 map 来加快访问速度。这个问题最常见(相当古老)的答案是:如果您想直接访问单个元素，请使用 unordered_map，但如果您想遍历元素(很可能以排序方式)，请使用 map。

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

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

Answer 1

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

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

字典排序简单:如果你告诉我你想根据结构的 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。它可能更慢(不确定)，但更安全。