C++中的std::unordered_map复杂度

Question

我在stackoverflow上读了很多关于unordered_map的时间复杂度，但我没有找到我的问题的答案。

假设按整数进行索引（只是举例）：

插入/在函数中工作恒定（平均时间），因此该示例将需要O(1)。

std::unordered_map<int, int> mymap = {
            { 1, 1},
            { 100, 2},
            { 100000, 3 }
};

我好奇的是遍历（未排序的）map中所有存储值需要多长时间 - 例如

for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }

我能假设每个存储的值只被访问一次（或两次或常数次）吗？这意味着遍历所有值在N值映射中是O(N)。另一个可能性是，如果用数组表示，我的键为{1,10,100000}的示例可能需要多达1000000次迭代。

是否有其他容器可以按给定键进行线性迭代并恒定时间访问值？

我真正需要的是（伪代码）

myStructure.add(key, value) // O(1)
value = myStructure.at(key) // O(1)
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values

std::unordered_map是我需要的数据结构吗？

整数索引足够了，平均复杂度也行。

- petrbel

---

如果你担心枚举需要遍历你没有插入到容器中的配对，那么请放心，它不会这样做。使用常规的 map 还是 unordered_map 应该基于你是否需要保留键的相对严格弱排序。如果需要，则需要使用常规的 map。如果不需要，则 unordered_map 是最合适的选择（前提是键可以被散列为合理的分布）。 - WhozCraig

@WhozCraig：在选择 "map" 或 "unordered_map" 时需要考虑的另一个功能因素是，后者在 insert/emplace/[] 中触发重新哈希时使现有迭代器/引用/指针无效是否可接受，然后会有性能差异，通常更偏向于 unordered_map，但应该由那些工具分析/检测工具说真正关心的人来进行测量。 - Tony Delroy

Answer 1

无论它们如何实现，标准容器都提供满足迭代器要求的迭代器。迭代器的递增需要是常数时间，因此遍历任何标准容器中的所有元素的时间复杂度为O(N)。

- Pete Becker

---

我似乎找不到增量（或者说解引用）的复杂度要求。你有引用吗？ - jxh

根据 SGI 的“前向迭代器”概念，“前向迭代器上的操作复杂度保证为摊销常数时间”。C++ 标准的第 24.4.4 节仅指出，“对于输入、前向和双向迭代器[...]它们使用 ++ 来提供线性时间实现”。 - Escualo

对于unordered_map来说，“linear”的含义并不明确。它可以指“桶的数量”，也可以指“容器中元素的数量”。是否有更具体的内容表明是后者？ - jxh

@jxh: 我找到了以下内容：所有迭代器的类别只需要那些在给定类别中可以在常数时间（摊销）内实现的函数。因此，迭代器的要求表中没有复杂度列（参见24.2.1.8）。所以，我理解的是，对于容器中的元素，增量操作只需要摊销常数时间即可满足要求。 - Escualo

@TonyD：我曾经不知道load_factor的意义，但现在我已经变聪明了。不过还是谢谢你提供的信息！ - jxh

Answer 2

所有标准容器的复杂度保证已在C++标准文档中指定。 std::unordered_map的元素访问和元素插入平均复杂度要求为O(1)，最坏情况下为O(N)（参见23.5.4.3和23.5.4.4节；页面797-798）。

特定实现（即标准库的特定供应商实现）可以选择任何数据结构。但是，为了符合标准，它们的复杂度必须至少与规定的一样。

- Escualo

---

当使用迭代器时，复杂度在最坏情况下是否也是O(N)？（更具体地说，通过1递增一个迭代器？） - memo1288

正如上面所回答的那样，遍历所有容器需要是O(N)（std::unordered_map迭代器满足forward iterator概念）。访问特定元素或插入元素平均为O(1)，最坏情况为O(N)。 - Escualo

Answer 3

有几种不同的哈希表实现方式，如果您感兴趣，我建议您阅读更多相关内容，但主要有两种方法：链接和开放地址法。

第一种情况下，您有一个链表数组。数组中的每个条目都可能为空，哈希表中的每个项都将在某个存储桶中。因此迭代是沿着数组走，然后沿着其中的每个非空列表走。显然是O（N），但根据链表本身如何分配，可能会占用大量内存。

在第二种情况下，您只需拥有一个非常大的数组，其中有很多空槽位。在这里，迭代也明显是线性的，但如果表格大部分为空（应该是为了查找目的），则效率可能会低，因为实际存在的元素将位于不同的缓存行中。

无论哪种方式，您都将进行线性迭代，并且每次都将仅触摸每个元素一次。请注意，对于std :: map，这也是正确的，迭代也将是线性的。但在地图的情况下，迭代肯定比迭代向量要不太有效，所以请记住这一点。如果您的用例涉及需要快速查找和快速迭代，如果您预先插入所有元素并永远不会删除，那么实际上同时拥有地图和向量可能会更好。为添加的性能花费额外的空间。

- Barry