C++中以vector为键/值的map与unordered_map时间复杂度咨询

先明确前提：用vector<int>作为unordered_map的键时，C++标准库没有提供默认的哈希函数，你需要自己实现合法的哈希函数才能编译通过，以下时间复杂度分析均基于哈希函数正确实现的情况。

一、各容器的操作时间复杂度 #

所有map类型（无论值是int还是vector<int>） #

map的时间复杂度仅与键的比较成本相关，和值的类型无关：

• 插入：O(log n * K)，其中n是容器内已有元素数量，K是作为键的vector<int>的元素个数（比较两个vector需逐元素对比，这个过程耗时O(K)）
• 查找：O(log n * K)
• 删除：O(log n * K)

所有unordered_map类型（无论值是int还是vector<int>） #

哈希表性能依赖哈希函数与数据分布，分两种情况：

• 插入：平均O(K)，最坏O(n*K)（计算vector的哈希值需遍历所有元素，成本为O(K)；最坏情况是大量键发生哈希冲突，哈希表退化为链表，遍历链表耗时O(n)）
• 查找：平均O(K)，最坏O(n*K)
• 删除：平均O(K)，最坏O(n*K)

二、map与unordered_map的时间复杂度差异 #

1. 底层结构带来的量级区别

   • map基于红黑树（平衡二叉搜索树），所有操作的时间复杂度均为对数级O(log n)乘以键的比较成本O(K)，性能稳定，不会出现突然的性能暴跌。
   • unordered_map基于哈希表，平均情况下是常数级O(1)乘以键的哈希计算成本O(K)，平均性能优于map，但如果哈希函数设计不佳或数据大量冲突，最坏情况会退化到和线性遍历一样慢。

2. 键的操作成本差异

   • map需要对键执行比较操作（vector<int>默认按字典序逐元素比大小），每次比较成本为O(K)。
   • unordered_map需要对键计算哈希值（自定义哈希函数需遍历vector所有元素），成本同样为O(K)，但哈希计算的常数开销和比较操作不同，具体取决于哈希函数的实现。

3. 性能稳定性

   • map的操作时间是确定的，无论数据分布如何，都能保证O(log n * K)的耗时。
   • unordered_map的平均性能更优，但存在性能波动风险，极端情况下会大幅变慢。

内容的提问来源于stack exchange，提问作者PRASHANT JHA