为什么将字符串插入 unordered_map 的时间复杂度平均为常数？

Question

如果我们有一个长度为 n 的字符串，那么将它插入 unordered_map (C++) 的时间不应该是 O(n) 吗？但是在 cplusplus.com 网站上：

如下写：

那么，正确的时间复杂度是多少？谢谢！

Answer 1

在这种情况下，恒定时间指的是地图中元素的数量，而不是关于这些元素的任何内容。

如果您有一个大小为 的字符串n，并将其插入到一个大小为的映射中m，则O(n)插入在m.