C ++无序地图恒定时间访问？

Question

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

它说时间复杂度通常是恒定的，但最坏的情况是线性时间。由于我的应用程序必须保证可以恒定时间访问此映射内的元素，因此我想验证对容器的理解。

每当我的应用程序访问此unordered_map内的元素时，它所寻找的对象肯定存在，因此容器将永远不会尝试添加缺少的元素。由于我只进行查找，这是否意味着unordered_map将始终为我提供恒定的访问时间？的线性时间的情况下只适用于某些情况下，一个插入会发生，是正确的吗？

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

Answer 1

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

因此，您可以拥有具有线性查找时间复杂度的只读映射，但是如果可以确保现有元素没有冲突，则可以保证O（1）查找。