初始化集合时,hashset对内存有什么作用？

Question

我偶然发现了以下问题.
我想要一个所有数字从1到100.000.000的哈希集.我尝试了以下代码:

var mySet = new HashSet<int>();
for (var k = 1; k <= 100000000; k++)
     mySet.Add(k);

那个代码没有成功,因为我在49mil附近的内存溢出.这也很慢,内存增长过度.

然后我尝试了这个.

var mySet = Enumerable.Range(1, 100000000).ToHashSet();

其中ToHashSet()是以下代码:

public static HashSet<T> ToHashSet<T>(this IEnumerable<T> source)
{
    return new HashSet<T>(source);
}

我再次获得了内存溢出但我能够使用前面的代码输入更多数字.

有效的方法如下:

var tempList = new List<int>();
for (var k = 1; k <= 100000000; k++)
     tempList.Add(k);

var numbers = tempList.ToHashSet();

我的系统需要大约800毫秒来填充tempList,其中Enumerable.Range()只需要4个滴答!

我确实需要HashSet,否则它需要花费很多时间来查找值(我需要它是O(1)),如果我能以最快的方式做到这一点会很棒.

现在我的问题是:
为什么前两种方法导致内存溢出,而第三种方法没有？

在初始化时,HashSet是否有特殊的内存？

我的系统有16GB的内存,所以当我得到溢出异常时我感到非常惊讶.

Answer 1

与其他集合类型一样,HashSet会在您添加元素时根据需要自动增加其容量.添加大量元素时,将导致大量重新分配.

如果使用带有a的构造函数初始化它IEnumerable<T>,它将检查IEnumerable<T>实际上是否为a ICollection<T>,如果是,则将HashSet的容量初始化为集合的大小.

这就是你在第三个例子中发生的事情 - 你正在添加一个List<T>也是一个ICollection<T>,所以你的HashSet的初始容量等于列表的大小,从而确保不需要重新分配.

如果使用List<T>带有容量参数的构造函数,则效率会更高,因为这将避免在构建列表时重新分配:

var noElements = 100000000;
var tempList = new List<int>(noElements); 
for (var k = 1; k <= noElements; k++) 
     tempList.Add(k); 

var numbers = tempList.ToHashSet(); 

至于你的系统内存; 检查这是32位还是64位进程.32位进程最多可提供2GB内存(如果使用/ 3GB启动开关,则为3GB).

与其他集合类型(例如List<T>,Dictionary<TKey,TValue>)不同,HashSet<T>没有使用capacity参数来设置初始容量的构造函数.如果要HashSet<T>使用大量元素初始化a ,最有效的方法可能是首先将元素添加到数组或List<T>具有适当的容量,然后将此数组或列表传递给HashSet<T>构造函数.