c++ - 使用 std::unordered_map 而不是 std::map 有意义吗？

Question

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

还有一个相关问题:我需要检索一个 int值 int key 。我应该使用 unordered_map<int, int> 吗？或 unordered_set<pair<int, int> > (在这种情况下，我需要正确地为我的对实现哈希函数)？

Answer 1

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

这意味着基本操作(获取和设置)的复杂性对于 map 是对数的和常数 unordered_map .

无论如何还有其他方面:unordered_map当达到其负载因子时可能需要重新散列(这需要时间并且可能无法预测)，而正常的 map不涉及此类问题。此外 unordered_map实现可以使用带桶的分离链接，这样如果它碰巧有很多冲突，复杂性就变成常量+线性来检索 key 。

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

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