我需要创建一个查找函数，其中 (X,Y) 对对应于特定的 Z 值。对此的一个主要要求是我需要尽可能接近 O(1) 复杂度。我的计划是使用 unordered_map。
我通常不使用哈希表进行查找，因为查找时间对我来说从来都不重要。我是否正确地认为只要我构建了没有冲突的 unordered_map，我的查找时间将是 O(1)？
然后我担心的是，如果无序映射中不存在密钥，那么复杂性会变成什么。例如，如果我使用 unordered_map::find(): 来确定一个键是否存在于我的哈希表中，它将如何给我一个答案？它实际上是否遍历所有键？
我非常感谢帮助。
该标准或多或少要求使用存储桶解决冲突，这意味着实际查找时间可能与存储桶中的元素数量成线性关系，无论该元素是否存在。可以使它成为 O(lg N)，但通常不会这样做，因为如果正确使用哈希表，桶中的元素数量应该很少。
为了保证一个桶的元素数量少，必须保证散列函数是有效的。有效的手段取决于被散列的类型和值。（MS 实现使用 FNV，这是最好的通用散列之一，但如果您对将要看到的实际数据有专门的了解，您可能会做得更好。）另一件可以帮助减少数量的事情每个桶的元素数量是强制更多的桶或使用更小的负载因子。首先，您可以将最小初始桶数作为参数传递给构造函数。如果您知道地图中的元素总数，则可以通过这种方式控制负载因子。填满表格后，您还可以通过调用
rehash. 否则，有一个功能
std::unordered_map<>::max_load_factor你可以使用它。它不能保证做任何事情，但在任何合理的实施中，它会。请注意，如果您在已填充的 上使用它unordered_map，您可能必须在
unordered_map<>::rehash之后调用。
（关于标准 unordered_map 有几件事我不明白：为什么负载因子是 a float，而不是
double；为什么它不需要产生影响；以及为什么它不会自动调用rehash你。）
与任何哈希表一样，最坏的情况总是线性复杂性（编辑：如果您构建的地图没有任何冲突，就像您在原始帖子中所说的那样，那么您将永远不会看到这种情况）：
http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
复杂性 平均情况：常数。最坏的情况：容器大小呈线性关系。
返回值 如果找到指定的键值，则返回元素的迭代器；如果在容器中未找到指定的键，则返回 unordered_map::end。
但是，由于 unordered_map 只能包含唯一键，您将看到恒定时间的平均复杂度（容器首先检查哈希索引，然后迭代该索引处的值）。
我认为unordered_map::count函数的文档提供了更多信息：
在容器中搜索键为 k 的元素并返回找到的元素数。因为 unordered_map 容器不允许重复键，这意味着如果容器中存在具有该键的元素，则该函数实际上返回 1，否则返回 0。
在散列数据结构中没有冲突是非常困难的（如果不是不可能的给定散列函数和任何类型的数据）。它还需要一个与键数完全相等的表大小。不，它不需要那么严格。只要散列函数以相对统一的方式分配值，就会有O(1)查找复杂性。
哈希表通常只是带有处理冲突的链表的数组（这是链接方法 - 还有其他方法，但这可能是处理冲突最常用的方法）。因此，要查找某个值是否包含在存储桶中，它必须（可能）迭代该存储桶中的所有值。因此，如果散列函数为您提供均匀分布，并且有N桶和值的总数，则每个桶M应该（平均）有值。M/N只要该值不太大，就可以进行O(1)查找。
因此，作为对您的问题的一个冗长的回答，只要散列函数是合理的，您就会得到O(1)查找，它必须迭代（平均）O(M/N)键来给您一个“否定”的结果。