我有一组值,我用以下方式int
填充 a -HashSet<int>
var hashSet = new HashSet<int>(myIEnumerable);
假设迭代IEnumerable
is O(n)
,以这种方式创建 a的最坏情况HashSet<int>
复杂度是多少?
我有一组值,我用以下方式int
填充 a -HashSet<int>
var hashSet = new HashSet<int>(myIEnumerable);
假设迭代IEnumerable
is O(n)
,以这种方式创建 a的最坏情况HashSet<int>
复杂度是多少?
当集合达到其最大大小时,O(N^2)
您可以通过将所有散列到同一存储桶的对象提供最坏的情况。例如,如果您传递一个 17519的序列,构造为int
x[i] = i * 17519
在i
1 到 17519 之间(包括 1 和 17519),所有数字都将散列到 Microsoft 实现的初始存储桶中HashSet<int>
,O(N^2)
插入:
var h = new HashSet<int>(Enumerable.Range(1, 17519).Select(i => i*17519));
设置一个断点,并h
在调试器中检查。查看原始视图/非公共成员/m_buckets。观察初始存储桶有 17519 个元素,而其余 17518 个元素都为零。
简并哈希码(一个常数)的快速实验表明它是二次的。
for(int n=0;n<100;n++)
{
var start=DateTime.UtcNow;
var s=new HashSet<Dumb>(Enumerable.Range(0,n*10000).Select(_=>new Dumb()));
Console.Write(n+" ");
Console.WriteLine((int)((DateTime.UtcNow-start).TotalSeconds*10));
}
输出:
0 0
1 8
2 34
3 73
4 131
现在有些人声称您不会遇到HashCode
for int 的多次冲突。虽然这在技术上是正确的,但对性能而言重要的不是 HashCode 的冲突,而是桶索引的冲突。我认为HashSet<T>
使用类似bucket = (hash&0x7FFFFFFF)%Capacity
. 因此,如果您添加一个整数序列是首选存储桶大小的倍数,它仍然会非常慢。