c++ - 使用 std::unordered_map 是否有意义而不是 std::map?

Question

应该std::unordered_map<int, int>比 std::map 快吗？我不关心顺序，只是快速查找，所以我认为我应该使用哈希表。但是后来我想也许它会尝试另外散列我的密钥或类似的东西（我不需要）？

还有一个相关的问题：我需要按键检索一个int值int。我应该使用unordered_map<int, int>or unordered_set<pair<int, int> >（在这种情况下，我需要为我的配对正确实现散列函数）？

Answer 1

map<T,K>a和 an之间的区别在于unordered_map<T,K>，第一个实现依赖于树，而第二个实现依赖于 hashmap。

这意味着基本操作（get 和 set）的复杂性对于 a 是对数，对于 a 是map常数unordered_map。

无论如何，还有其他方面：unordered_map当达到其负载因子时可能需要重新散列（这需要时间并且可能是不可预测的），而正常map不涉及此类问题。此外，该unordered_map实现可以使用带有桶的分离链接，因此如果碰巧有很多冲突，复杂性将变为常数+线性以检索密钥。

我建议您使用与您需要的模式相似的一些数据对这两种结构进行基准测试，这将使您做出选择。

你不需要为它定义你自己hash<int>的，unordered_map因为它已经实现了。