分析std :: map-由于空间复杂性，为什么使用map / hashset / hastable被认为不好用？

Question

我一直听说，最好避免使用哈希表/映射，因为它们具有很大的空间复杂性。地图的空间复杂度与矢量或N个元素的阵列有何不同？什么是使用地图的替代方法？当元素数量很大时，就空间复杂性而言，使用地图或矢量是否同样不好？为什么？

Answer 1

首选使用向量或数组的准则基于这样的假设，即地图中的项目数量通常很小（很少KB）。使用地图时，必须另外存储密钥。然后，verctor的内存较小，因此对堆更友好。有效地使用堆内存可以大大减少运行时间。

参考：https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#slcon2-prefer-using-stl-vector-by-default-unless-you-have-a-reason-to-use-a-different-container

您还必须牢记O-Natation的规则。我们仅考虑大的大N值。例如。项O（30N）简化为O（N）。对于较大的大N值，可以忽略30。但是，如果使用低N值，则“实际”复杂度比收敛值更为重要。