一个普遍被问及的问题是我们应该使用 unordered_map 还是 map 来加快访问速度。 这个问题最常见(相当古老)的答案是: 如果您想直接访问单个元素,请使用 unordered_map,但如果您想遍历元素(很可能以排序方式),请使用 map。
我们在做这样的选择时不应该考虑key的数据类型吗? 由于一种数据类型(例如 int)的哈希算法可能比其他数据类型(例如字符串)更容易发生冲突。
如果是这种情况(散列算法很容易发生冲突),那么我什至可能会使用 map 进行直接访问,因为在这种情况下,O(1) 常数时间(可能是大量输入的平均值) unordered_map 即使对于相当大的 N 值,映射也比 lg(N) 多。
最佳答案
你提出了一个很好的观点......但你关注的是错误的部分。
问题不在于 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
。它可能更慢(不确定),但更安全。
关于c++ - 根据键的类型选择 map 或 unordered_map,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13323683/