c++ - std::unordered_set 如何存在病理输入?

标签 c++ data-structures hashset unordered-set

我正在解决在给定数组中找到不同整数的数量的基本问题。
我的想法是声明一个 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是我测试程序的输入案例。它相当大,所以它可能会滞后一点。

最佳答案

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

关于c++ - std::unordered_set 如何存在病理输入?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63515655/

相关文章:

c++ - Objective-C适当使用autorelease?

java - Set.contains() 如何决定它是否是一个子集?

java - 在不循环的情况下随机获取 HashMap 或 HashSet 中的元素

c - C 函数栈顶实现

algorithm - 双哈希如何工作?

c# - 像队列这样的数据结构可以访问最后一个元素

Java HashSet 使用自定义类作为键 : "contains()" function always return false

c++ - QThread 来回传递数据

c++ - 了解一些 C++ 代码

c++ - 指向派生类型的基类指针