c++ - unordered_map 复杂度

Question

我需要创建一个查找函数，其中 (X,Y) 对对应于特定的 Z 值。对此的一个主要要求是我需要尽可能接近 O(1) 复杂度。我的计划是使用 unordered_map。

我通常不使用哈希表进行查找，因为查找时间对我来说从来都不重要。我是否认为只要我构建没有冲突的 unordered_map，我的查找时间就是 O(1)？

然后我担心的是，如果无序映射中不存在 key ，那么复杂性会变成什么。例如，如果我使用 unordered_map::find(): 来确定一个键是否存在于我的哈希表中，它将如何给我一个答案？它实际上会遍历所有键吗？

非常感谢您的帮助。

Answer 1

标准或多或少需要使用桶进行碰撞分辨率，这意味着实际查找时间将可能与元素数量成线性关系桶，无论元素是否存在。有可能使它成为 O(lg N)，但通常不会这样做，因为桶中元素的数量应该很少，如果哈希表使用正确。

为确保存储桶中的元素数量较少，您必须确保散列函数有效。什么有效的方法取决于被散列的类型和值。(MS 实现使用 FNV，这是最好的之一通用哈希，但如果你有特殊的知识您将看到的实际数据，您可能会做得更好。)另一件事可以帮助减少每个元素的数量bucket是强制更多的bucket或使用更小的负载因子。首先，您可以通过最小初始数量buckets 作为构造函数的参数。如果你知道将在 map 中的元素总数，您可以以这种方式控制负载系数。您也可以设置一个最小值表被填满后的桶数，通过调用 rehash .否则，有一个功能 std::unordered_map<>::max_load_factor你可以使用它。它不保证做任何事情，但在任何合理的执行，它会。请注意，如果您已经在已填 unordered_map ，你可能不得不打电话 unordered_map<>::rehash之后。

(关于标准有几件事我不明白unordered_map:为什么负载因子是 float ， 代替 double ;为什么它不需要产生影响；以及为什么不会自动调用 rehash给你。)