C++ - 无序映射复杂度

Question

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

通常我不使用哈希表进行查找，因为查找时间从来都不重要。如果我构建的unordered_map没有冲突，那么我的查找时间是否会是O(1)？

那么我的疑虑就是，如果key不在unordered_map中，复杂度会变成什么？例如，如果我使用unordered_map :: find()来确定键是否存在于哈希表中，它将如何给我答案？它真的会遍历所有的键吗？

非常感谢您的帮助。

- user1764386

Answer 1

标准要求使用“桶”来解决冲突，这意味着实际查找时间可能会与元素数量成线性关系，无论元素是否存在。虽然可以将其变为O(lg N)，但通常不这样做，因为如果哈希表使用正确，桶中的元素数量应该很小。 为确保桶中的元素数量很小，必须确保散列函数有效。有效意味着取决于被哈希的类型和值。(MS的实现使用FNV，这是最好的通用哈希之一，但如果您对实际数据有特殊了解，可能能够做得更好。) 另一个有助于减少每个桶中元素数量的方法是强制使用更多桶或使用较小的负载因子。对于第一个方法，可以将最小初始桶数作为参数传递给构造函数。如果知道图中的元素总数，则可以通过此方式控制负载因子。在填充表后，还可以通过调用rehash来强制设置桶的最小数量。否则，可以使用std::unordered_map<>::max_load_factor函数。不能保证它会有任何效果，但在任何合理的实现中，都会有所作为。请注意，如果在已填充的unordered_map上使用它，则可能需要随后调用unordered_map<>::rehash。 （对于标准unordered_map，有一些我不理解的事情：为什么负载因子是浮点型，而不是双精度型;为什么没有必要发挥作用;为什么它不会自动为您调用rehash。）

- James Kanze

Answer 2

与任何哈希表一样，最坏情况下的复杂度始终是线性的（编辑：如果您按照原始帖子中所述构建映射而没有发生任何冲突，则永远不会看到这种情况）：http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

复杂度 平均情况：常数。 最坏情况：与容器大小成线性关系。

返回值 如果在容器中找到指定的键值，则返回指向该元素的迭代器；否则返回 unordered_map::end。

然而，由于unordered_map只能包含唯一的键，因此您将看到平均复杂度为常数时间（容器首先检查哈希索引，然后迭代该索引处的值）。

我认为unordered_map::count函数的文档更具信息量：

在容器中搜索其键为k的元素，并返回找到的元素数量。由于unordered_map容器不允许重复的键，因此这意味着如果容器中存在具有该键的元素，则该函数实际上返回1，否则返回0。

- AndyG

---

我现在对jakar在这里的回答感到困惑： https://dev59.com/wm855IYBdhLWcg3wXC1-我会理解这个评论是说可以完成。那不是这种情况吗？ - user1764386

@user1764386：如果find无法返回值的迭代器，那么它必须返回something，因此unordered_map::end是最好的选择。 - AndyG

谢谢您的帮助。我的意思是，我对他的回答有点困惑，因为我理解为如果键不在unordered_map中，复杂度会比O(N)更好。 - user1764386

@user1764386 平均来说应该不会出现这种情况。但如果所有输入的哈希值都相同，数据结构就必须遍历整个列表来查找。 - AndyG

您能否详细解释一下吗？我能避免任何两个键映射到相同的值吗？我正在根据输入数据一次性构建unordered_map。我以后不会再添加任何内容。 - user1764386

在最坏的情况下，不行。这完全取决于您使用的哈希函数。如果您愿意，可以为unordered_map提供自己的哈希函数（http://www.cplusplus.com/reference/unordered_map/unordered_map/）。请搜索Google哈希函数以获取更多信息。 - AndyG

Answer 3

在哈希数据结构中避免碰撞是非常困难的（如果给定的哈希函数和任何类型的数据都不可能）。这还需要一个表大小恰好等于键的数量。不，它并不需要那么严格。只要哈希函数以相对均匀的方式分配值，您将具有O(1)的查找复杂度。

哈希表通常只是带有链表的数组来处理冲突（这是链式法 - 还有其他方法，但这可能是处理冲突最常用的方法）。因此，为了确定值是否包含在桶中，它将必须（潜在地）迭代该桶中的所有值。因此，如果哈希函数为您提供均匀的分布，并且有N个桶和总共M个值，则每个桶应平均具有M/N个值。只要此值不太大，这就允许O(1)查找。

因此，作为对您问题的一种冗长的回答，只要散列函数合理，您将获得O(1)的查找，而它必须迭代（平均）O(M/N)个键才能给出“否定”结果。

- Yuushi