c++11 - 提高不变的无序映射的查询访问性能

Question

我正在寻找改进无序地图查询时间访问的建议。我的代码基本上只包含两个步骤。第一步，我填充无序地图。在第一步之后，不再向地图添加条目。第二步，只查询无序地图。由于地图本质上是不变的，有什么办法可以加快查询时间吗？例如，stl 是否提供任何可以调整映射中的内部分配以改善查询时间访问的功能？换句话说，有可能不止一个键被映射到无序映射中的同一个桶。如果为映射分配了更多内存，则可以减少发生此类冲突的机会。从这个意义上说，

标签： c++11unordered-map

Answer 1

您有两个可以扭动的旋钮：哈希函数和地图中的桶数。一个在编译时固定（散列函数），另一个您可以在运行时修改（有些）。

一个好的散列函数会给你很少的冲突（具有相同散列值的不相等值）。如果您有很多冲突，那么您实际上无法做很多事情来改善您的查找时间。最坏的情况（所有输入散列到相同的值）为您提供 O(N) 查找时间。所以这就是你要集中精力的地方。

一旦你有一个好的散列函数，那么你就可以用桶的数量（通过）玩游戏，rehash这可以进一步减少冲突。