C++ 无序映射常量时间访问？

Question

我正在研究 C++ unordered_map 容器类型。我只是在使用 operator[] 验证我从 C++ 网站上读到的有关元素访问的内容。 .

它说时间复杂度通常是常数，但最坏情况是线性时间。由于我的应用程序必须保证持续访问此 map 内部的元素，因此我想验证我对这个容器的理解。

每当我的应用程序访问这个 unordered_map 中的元素时，它正在寻找的对象肯定存在，因此容器永远不会尝试添加缺失的元素。因为我只是在做查找，这是否意味着 unordered_map 将始终给我恒定时间访问？ 线性时间 情况仅适用于将发生插入 的特定情况，对吗？

编辑:unordered_map 中的元素保证是唯一的。它们保存存在于内存中的几个唯一对象的地址。

Answer 1

查找取决于是否存在任何现有元素的散列冲突，在这种情况下，元素将被放入同一个桶中，并且必须使用相等比较进行线性搜索。最坏的情况是所有东西都在同一个桶里。

因此您可以拥有一个具有线性查找时间复杂度的只读映射，但是如果您可以保证现有元素不会发生冲突，那么您可以保证 O(1) 查找.