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;
}

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

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

我已经阅读了O(N)如果发生大量冲突，散列集如何以插入结束，所以我认为输入在std::unordered_set.

然而，这是不可能的。std::unordered_set用于整数的哈希函数将它们映射到自身（至少在我的计算机上），因此不同整数之间不会发生冲突。我使用写在这个链接上的代码访问了哈希函数。

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

这是我测试我的程序的输入案例。它相当大，所以它可能会滞后一点。

Answer 1

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

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

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

Answer 2

您的程序运行良好。散列算法、冲突或类似的东西没有任何问题。

当您尝试将 200000 个数字粘贴到窗口中时，您看到的问题来自控制台 i/o。这就是它窒息的原因。从文件重定向，它工作正常，几乎立即返回结果。

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

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