std::unordered_map 查询时间复杂度

C++ 中的 std::unordered_map 是基于哈希表实现的，因此查询一个元素的时间复杂度通常是 O(1)，即常数时间复杂度。但是，在最坏情况下，所有的元素都会被哈希到同一个桶里，此时查询一个元素的时间复杂度会退化为 O(n)，其中 n 是 std::unordered_map 中元素的个数。因此，std::unordered_map 的查询时间复杂度是具有不确定性的，但是在平均情况下，查询一个元素的时间复杂度是比较优秀的。需要注意的是，std::unordered_map 在性能上通常比 std::map 更优秀，但是其元素的顺序不是按照插入顺序或者键值的大小排序的。

相关问题

cpp11std::unordered_map和std::unordered_set

cpp11std::unordered_map和std::unordered_set是C++11中引入的两个新容器。

cpp11std::unordered_map是一个无序关联容器，类似于std::map，但是它的元素是无序的。它使用哈希表来实现元素的存储和访问，因此它的查找和插入操作的时间复杂度为O(1)。它的元素可以是任意类型的，但是必须提供一个哈希函数和一个相等比较函数。

std::unordered_set也是一个无序容器，类似于std::set，但是它的元素是无序的。它也使用哈希表来实现元素的存储和访问，因此它的查找和插入操作的时间复杂度为O(1)。它的元素可以是任意类型的，但是必须提供一个哈希函数和一个相等比较函数。

这两个容器的使用方法与std::map和std::set类似，但是由于它们是无序的，因此它们的迭代器不支持比较操作。此外，它们还提供了一些特殊的操作，例如bucket_count()和load_factor()，用于查询哈希表的大小和负载因子。

std::unordered_map相对于std::map的优势

`std::unordered_map` 是 C++ 标准库中的一种关联容器，它使用哈希表（Hash Table）作为底层数据结构，而 `std::map` 则是基于红黑树的实现。两者在功能上都是用来存储键值对，但它们在性能和适用场景上有所不同：

1. **查找速度**：`unordered_map` 的优势在于查找、插入和删除操作的时间复杂度通常为 O(1)，如果哈希函数设计得当，能够快速定位到键对应的值。相比之下，`map` 的查找、插入和删除操作平均时间复杂度为 O(log n)。

2. **空间效率**：由于哈希表不保证元素有序，`unordered_map` 需要额外的空间来存储哈希表的桶和散列函数，可能会占用更多内存。而 `map` 可以利用红黑树的性质保持元素有序，所以内存占用相对较少。

3. **插入顺序**：`map` 会保持元素插入的顺序，如果插入顺序很重要，应该选择它。而 `unordered_map` 没有这个保证，元素的位置依赖于哈希值。

4. **随机访问**：如果你经常需要直接通过键获取值，且不需要保持元素顺序，那么 `unordered_map` 更适合。如果需要频繁进行范围查询或迭代操作，`map` 的有序性可能更有用。

5. **冲突处理**：`unordered_map` 使用哈希函数解决冲突，当两个键哈希到同一个位置时，会进行开放寻址或链地址法处理。`map` 则通过平衡二叉搜索树避免冲突，但可能会导致更高的复杂性。