我需要创建一个查找函数，其中(X，Y)对对应于特定的Z值。对此的一个主要要求是，我需要以尽可能接近O(1)的复杂度进行操作。我的计划是使用unordered_map。
我通常不使用哈希表进行查找，因为查找时间对我而言从来都不重要。我是否正确地认为只要构建无冲突的unordered_map，我的查找时间将是O(1)？
那么，我担心的是，如果无序映射中不存在 key ，那么复杂性将变得怎样。例如，如果我使用unordered_map::find():来确定哈希表中是否存在键，它将如何给我答案？它实际上遍历所有键吗？
我非常感谢您的帮助。
最佳答案
标准或多或少要求使用铲斗进行碰撞
分辨率，这意味着实际查找时间将
相对于元素中的元素数量可能是线性的
桶，无论元素是否存在。
可以将其设置为O(lg N)，但通常不会这样做，
因为存储桶中的元素数量应该少，
如果哈希表使用正确。
为确保存储桶中的元素数量少，您可以
必须确保哈希函数有效。什么
有效手段取决于要散列的类型和值。
(MS实现使用FNV，这是最好的方法之一
通用散列，但如果您对
您将看到的实际数据，您可能会做得更好。)
另一件事可以帮助减少每个元素的数量
铲斗是用来迫使更多的铲斗或使用较小的负载系数。
首先，您可以通过最小初始数量
存储桶作为构造函数的参数。如果你知道
您可以在 map 中显示的元素总数
通过这种方式控制负载系数。您也可以预备一个最小的
填满表格后，通过调用rehash。否则，有一个功能
您可以使用的std::unordered_map<>::max_load_factor。它
不保证可以做任何事情，但是可以合理地做
实现，它将。请注意，如果您已经在
填充unordered_map，您可能必须调用
之后是unordered_map<>::rehash。
(我对标准有几件事不了解
unordered_map:为什么加载因子是float而不是double;为什么不要求有效果；以及为什么
不会自动为您调用rehash。)