std::unordered_map<int, int>比std::map更快吗？我不关心顺序，只关心快速查找，所以我认为应该使用散列表。但是我想也许它会尝试额外地对我的键进行哈希处理或类似的操作（这并不需要）？相关问题：我需要通过 key检索值。我应该使用
unordered_map<int，int>还是unordered_set<pair<int，int>>（如果这样的话，我需要正确实现对我的pair的哈希函数）？使用std::unordered_map<int, int>代替std::map<int, int>有意义吗？（涉及IT技术）
4
相关问题：我需要通过 key检索值。我应该使用
- Violet Giraffe
1个回答
13
map<T,K>和unordered_map<T,K>之间的区别在于前者依赖于树，而后者依赖于哈希表。这意味着对于基本操作（获取和设置），
map的时间复杂度为对数级别，而unordered_map的时间复杂度为常数级别。当然还有其他方面：当负载因子达到时，
unordered_map可能需要重新哈希（这需要时间并且不可预测），而普通的map则不存在这样的问题。此外，unordered_map实现可能使用分离链接和桶，因此如果出现许多冲突，则检索键的复杂度将变为常数+线性级别。建议您使用与所需模式类似的数据对两个结构进行基准测试，以便做出选择。
您不需要为
unordered_map定义自己的hash<int>，因为它已经被实现了。- Jack
3
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 std::cout用于map<string, int>吗？
- 4 std::unordered_map::begin(int n)的行为表现
- 25 emplace_back与std::vector<std::map<int, int>>不兼容，无法正常工作。
- 6 为什么我不能在std::unordered_map<std::pair<int,int>, int>中使用operator[]，但是可以在相同键值对的std::map中使用呢？
- 8 std::map<int, int>和std::map<const int, int>之间有区别吗？
- 536 在C++中初始化静态std::map<int, int>
- 14 使用std::optional<int>和使用int一样有效吗？
- 5 用boost序列化std::unordered_map<int，std::unordered_set<int>>
- 3 无法使用std::initializer_list<int>构造std::initializer_list<int const>。
- 13 std::greater<int>() 和 std::greater<int> 有什么区别？
2<<(sizeof(int)*8)，这样每个int值才能被映射到自己的单元格，否则您并没有为哈希映射表提供哈希值。但在这种情况下，一个int[2<<(sizeof(int)*8)]数组就足够了。而问题将与数据缓存有关，而不再是数据结构的性能问题。 - Jackunordered_map提供自己的哈希函数。但是，在这样做之前，请务必了解其中的陷阱和注意事项。 - rwong