以vector/string为键时std::map与unordered_map的查找复杂度问询

1. 用最大长度为N的vector作为std::map的键 #

std::map底层是红黑树，常规查找一个元素的时间是O(log M)（M为map内总元素数）。但vector作为键时，红黑树比较两个键的大小需要逐元素对比，最坏情况下要遍历整个vector的N个元素，这一步耗时O(N)。所以整体的查找/访问时间复杂度是O(N * log M)。

如果你的问题里“map规模为N”指的是元素总数为N，那复杂度就是O(N log N)，而非单纯的O(N)。

2. 用长度为N的string作为键的情况 #

std::map的情况 #

和vector作为键的逻辑一致：std::map的基础查找复杂度是O(log M)，而string的比较需要逐字符对比，最坏耗时O(N)。所以总查找复杂度为O(N * log M)。

unordered_map的情况 #

unordered_map基于哈希表实现，平均情况下基础查找耗时O(1)，极端哈希冲突时最坏为O(M)。但string作为键有两个关键步骤：

• 哈希值计算：需要遍历N个字符生成哈希，耗时O(N)；
• 哈希冲突时的键对比：若出现哈希碰撞，需逐字符对比两个string是否相等，最坏耗时O(N)。
  因此平均查找复杂度是O(N)，最坏情况为O(N * M)。

3. 当map规模为N且键为长度N的vector时 #

此时std::map的查找复杂度是O(N log N)，不是你猜测的O(N)。因为红黑树的查找本身就带有log N的开销，再加上vector对比的O(N)耗时，两者相乘才是最终的复杂度。

内容的提问来源于stack exchange，提问作者Bibhukalyan Sahoo