c++ - 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 的哈希函数整数的用途将它们映射到自身(至少在我的计算机上)，因此不同整数之间不会发生冲突。我使用写在 this link 上的代码访问了哈希函数.
我的问题是，输入本身是否可能导致 std::unordered_set到达附近后减速 53000元素插入？如果是这样，为什么？
Here是我测试程序的输入案例。它相当大，所以它可能会滞后一点。

Answer 1

您提供的输入文件由与 1 一致的连续整数组成。模107897 .因此，最有可能发生的情况是，当负载因子超过阈值时，您正在使用的特定库实现会使用带有 107897 的表来调整表的大小。条目，以便具有散列值的键 h将映射到存储桶 h % 107897 .由于每个整数的散列都是它自己，这意味着到目前为止表中的所有整数都突然映射到同一个桶。这种调整大小本身应该只需要线性时间。但是，该点之后的每个后续插入都将遍历包含所有现有值的链表，以确保它不等于任何现有值。所以每次插入都需要线性时间，直到下一次调整表的大小。
原则上unordered_set当任何一个桶变得太长时，实现也可以通过调整表的大小来避免这个问题。然而，这引发了一个问题，这是否是与合理的散列函数的散列冲突(因此需要调整大小)，或者用户只是被误导并将每个键散列为相同的值(在这种情况下，无论 table 大小)。所以也许这就是为什么它没有在这个特定的库实现中完成。
另见 https://codeforces.com/blog/entry/62393 (这种现象在 Codeforces 竞赛中获得积分的应用)。