std::unordered_set 怎么可能存在病态输入？

Question

我正在解决寻找给定数组中不同整数数量的基本问题。

我的想法是声明一个std::unordered_set，将所有给定的整数插入到集合中，然后输出集合的大小。这是我实现此策略的代码：

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    int input;
    unordered_set <int> S;
    for(int i = 0; i < N; ++i){
        cin >> input;
        S.insert(input);
    }
    
    cout << S.size() << endl;

    return 0;
}

此策略几乎适用于所有输入。在其他输入情况下，超时。

我很好奇 为什么 我的程序超时，所以我在 for 循环中添加了 cout << i << endl; 行。我发现，当我进入输入案例时，循环的第一个 53000 左右迭代几乎立即通过，但之后每秒只会发生几次 100 迭代。

我已经了解了如果发生大量冲突，哈希集如何以 O(N) 插入结束，所以我认为输入在 std::unordered_set 中引起了很多冲突.

但是，这是不可能的。 std::unordered_set 用于整数的散列函数将它们映射到自身（至少在我的计算机上），因此不同整数之间不会发生冲突。我使用写在 this link.

上的代码访问了哈希函数

我的问题是，输入本身是否有可能导致 std::unordered_set 在碰到插入的 53000 个元素后变慢？如果是，为什么？

Here 是我测试程序的输入案例。它很大，所以它可能会有点滞后。

Answer 1

您的程序运行良好。哈希算法、冲突或类似的东西都没有问题。

当您尝试将 200000 个数字粘贴到 window 时，您看到的限制来自控制台 i/o。这就是它窒息的原因。从文件重定向，它工作正常并且 returns 几乎立即得到结果。

C:\Users\selbie\source\repos\ConsoleApplication126\Debug>ConsoleApplication126.exe  < d:/test.txt
200000

测试输入文件中的所有数字都是唯一的，因此输出为 200000。

Answer 2

您提供的输入文件包含与 1 模 107897 一致的连续整数。所以最有可能发生的是，在负载因子超过阈值的某个时刻，您正在使用的特定库实现调整 table 的大小，使用 table 和 107897 条目，这样具有散列值 h 的键将映射到存储桶 h % 107897。由于每个整数的散列都是它自己，这意味着到目前为止 table 中的所有整数突然映射到同一个桶。这种调整本身应该只需要线性时间。但是，该点之后的每个后续插入都将遍历包含所有现有值的链表，以确保它不等于任何现有值。因此，每次插入都将花费线性时间，直到下一次调整 table 的大小。

原则上，unordered_set 实现可以通过在任何一个存储桶变得太长时也调整 table 的大小来避免此问题。然而，这引发了一个问题，即这是否是与合理哈希函数的哈希冲突（因此需要调整大小），或者用户只是被误导并将每个键哈希为相同的值（在这种情况下，无论table 尺寸）。所以也许这就是为什么没有在这个特定的库实现中完成的原因。

另见 https://codeforces.com/blog/entry/62393（应用此现象在 Codeforces 竞赛中获得积分）。

std::unordered_set 怎么可能存在病态输入？

How can a pathological input exist for an std::unordered_set?

c++

hashset

unordered-set

data-structures