c++ - 比较两个无序集的相等性有多昂贵？

Question

给定两个std::sets，可以简单地同时遍历两个集合并比较元素，从而产生线性复杂度。这对 s 不起作用std::unordered_set，因为元素可以按任何顺序存储。a == b那么到底有多贵std::unordered_set呢？

Answer 1

最坏的情况是 O(n²)。

但无序集实际上是按哈希排序的。因此可以比较散列（如果失败，集合不能相等），然后验证相同的散列（线性）在后面具有相同的值（对于具有相同散列的不同值，O(n²)）。

在最好的情况下，这是 O(n)。

通常，如果散列函数“好”（不同的对象 -> 总是不同的散列），复杂度趋于 O(n)，如果散列函数“坏”（一切总是具有相同的散列值），复杂度趋于 O(n²)

Answer 2

和的复杂operator==性operator!=：

平均情况下的线性复杂度。N ²在最坏的情况下，其中 N 是容器的大小。

标准§23.2.5，第 11 点中的更多详细信息：

对于unordered_set和unordered_map，operator==（即，调用 的==运算符、value_type返回的谓词 key_equal()和返回的哈希器的次数）在平均情况下与 N ²hash_function()成正比，在最坏情况下与 N 2 成正比，其中.NNa.size()