unordered_map比map慢？

时间：2025-01-13 17:24:22

先说结论：unordered_map不维护键的顺序，因此不能按顺序访问元素，因此如果你需要遍历表时若选用unordered_map就肯定比map慢

1. 数据结构与底层实现

  • unordered_map：基于 哈希表 实现。

    • 优点：平均情况下插入、查找和删除操作的时间复杂度为 O(1)O(1)O(1)。
    • 缺点：最坏情况下，时间复杂度可能退化为 O(n)O(n)O(n)（当哈希冲突严重时）。
    • 无序存储，不能按键排序。

  • map：基于 红黑树（自平衡二叉搜索树） 实现。

    • 优点：插入、查找和删除操作的时间复杂度始终为 O(log⁡n)O(\log n)O(logn)。
    • 缺点：由于需要维护树的平衡，常数因子较大。
    • 按键排序，支持有序遍历。

2. 插入和查找性能

  • unordered_map 优势：在大多数情况下，unordered_map 插入和查找的性能优于 map，因为其平均时间复杂度为 O(1)O(1)O(1)。
  • map 劣势：map 的插入和查找性能稍慢，时间复杂度为 O(log⁡n)O(\log n)O(logn)。

例外情况：

  1. 哈希冲突严重：如果 unordered_map 的哈希函数设计不佳或数据分布极端（如大量相同的哈希值），性能可能退化为 O(n)O(n)O(n)。
  2. 小规模数据：对于数据规模较小的情况，map 的性能可能优于 unordered_map，因为红黑树的实现有较少的额外开销。

3. 内存使用

  • unordered_map 缺点：由于哈希表需要额外的存储空间（如空槽和链表节点），unordered_map 通常比 map 占用更多内存。
  • map 优势：map 是基于树的实现，占用内存相对较少。

4. 顺序访问

  • unordered_map 缺点：unordered_map 不维护键的顺序，因此不能按顺序访问元素。
  • map 优势：map 自动按键的升序（或指定的比较函数）维护元素顺序，支持有序遍历。

5. 插入、删除时对迭代器的影响

  • unordered_map：当发生哈希表的重哈希（rehash）操作时，会使所有迭代器失效。
  • map：插入和删除元素只会影响相关位置的迭代器，其余迭代器不会失效。

6. 适用场景

场景 推荐使用容器 原因
快速查找/插入操作 unordered_map 平均时间复杂度 O(1)O(1)O(1)。
数据需要按键排序 map 支持有序遍历。
数据规模较小 map 红黑树常数因子较小。
内存有限 map unordered_map 占用内存较大。
哈希函数性能不佳或数据分布差 map unordered_map 性能退化明显。

7.举例

B. Gorilla and the Exam
代码：

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d %d", &n, &k);

        // 统计频次
        map<int, int> times;
        for (int i = 0; i < n; i++) {
            int c;
            scanf("%d", &c);
            times[c]++;
        }

        // 提取频次并排序
        vector<int> freq;
        for (auto it : times) {
            freq.push_back(it.second);
        }
        sort(freq.begin(), freq.end());

        // 计算移除最小的 k 次后剩余种类
        int m = freq.size();
        for (int i = 0; i < m; i++) {
            if (freq[i] > k) {
                printf("%d\n", m - i);
                goto next_case;
            }
            k -= freq[i];
        }
        printf("1\n");
    next_case:;
    }
    return 0;
}

若这个代码改为unordered_map将会超时，有兴趣的同学可以去提交试试！

总结

  • 如果需要快速插入、删除和查找操作且不关心顺序，优先选择 unordered_map。
  • 如果需要按键排序或者可能遇到哈希冲突问题，选择 map。
  • 如果内存占用敏感，选择 map。

相关文章