Tah*_*lil 5 c++ unordered-map map time-complexity space-complexity
我发现有关的复杂很多职位map和unordered_map.据说unordered_map最坏的情况是复杂的O(N).为了我的目的,我将输入作为排序值,如1 2 5 6 9 11 12...我需要插入或查找并删除一个值.我将不得不经常插入/删除.我想到了set在所有情况下都使用log(n)的复杂性.然后我偶然发现了具有最佳O(1)复杂度的unordered_map.但我需要了解在我的场景中我将面对unordered_map的最坏情况吗？会是什么情景？
编辑:在我的情况下,所有的值都是唯一的.
unordered_map 最糟糕的情况通常发生在哈希函数为地图中的每个插入产生冲突时.
我说"通常"是因为标准只规定了最坏情况的复杂性,而不是它何时或如何发生,所以理论上你的问题的答案是它是实现定义的.
由于您的所有值都是唯一的,并且显然是整数(表示非常好的散列,可能是最佳的_这也是依赖于实现的),因此您不会遇到这种最糟糕的情况.insert/find/delete将是O(1),所以它看起来是一个合理的选择.