使用 std::unordered_map<int, int> 而不是 std::map<int, int> 有意义吗？

Question

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

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

Answer 1

amap<T,K>和 an之间的区别在于unordered_map<T,K>，第一个实现依赖于树，而第二个实现依赖于哈希图。

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

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

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

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