c# - 初始化集合时，哈希集对内存有什么作用？

Question

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

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

那段代码没有成功，因为我在 4900 万左右发生了内存溢出。这也很慢，内存增长过快。

然后我尝试了这个。

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 毫秒来填充 Enumerable.Range() 只需要 4 个滴答声的 tempList!

我确实需要那个 HashSet，否则查找值需要很长时间(我需要它是 O(1))，如果我能以最快的方式做到这一点，那就太好了。

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

HashSet 在初始化时对内存有什么特殊作用吗？

我的系统有 16GB 内存，所以当我遇到溢出异常时我很惊讶。

Answer 1

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

如果您使用带有 IEnumerable<T> 的构造函数对其进行初始化，它将检查 IEnumerable<T>实际上是 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>对于大量元素，最有效的方法可能是首先将元素添加到数组或 List<T>具有适当的容量，然后将此数组或列表传递给 HashSet<T>构造函数。