当初始化一个哈希集合时，哈希集合会如何处理内存？

Question

当初始化一个哈希集合时，哈希集合会如何处理内存？

9

我遇到了以下问题。
我想要一个包含1到100,000,000所有数字的哈希集合。我尝试了以下代码：

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

由于某个地方出现了内存溢出的问题，在大约4,900万次操作时，那段代码未能成功执行。而且，该方法速度较慢，且内存使用过多。

后来我尝试了这个方法。

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();

在我的系统中，仅用Enumerable.Range（）需要4个时钟周期，而填充tempList需要约800毫秒！我确实需要HashSet，否则查找值需要太长时间(我需要它是O(1)),如果可以以最快的方式完成就太好了。现在我的问题是：为什么前两种方法会导致内存溢出而第三种方法不会？HashSet在初始化时是否对内存进行了特殊处理？我的系统有16GB内存,所以当我遇到溢出异常时感到非常惊讶。

- Mixxiphoid

4

需要注意的一点是，Enumerable.Range 之所以如此快，是因为在运行时它实际上并不生成任何内容。只有当它被使用（例如在 ToHashSet 调用中）时，它才会开始生成数字。 - Chris

@Chris 不知道呢。谢谢 :)。 - Mixxiphoid

所有的Linq类型可枚举物品都是一样的。如果你在一个可枚举物品上执行了Where或Select或其他返回更多可枚举物品的操作，它们将推迟执行直到使用它们。知道这一点很有用，因为由于这种行为可能会出现一些意外情况（虽然我一时想不出简洁的例子）。 - Chris

你可能想看一下 why-cant-i-preallocate-a-hashsett-c-sharp。 - nawfal

4个回答

2

我猜测HashSet<T>，就像大多数.net集合一样，使用数组倍增策略进行增长。不幸的是，没有接受容量参数的构造函数重载。

但是，如果它检查了ICollection<T>并使用ICollection<T>.Count作为初始容量，您可以实现一个简陋的ICollection<T>实现，该实现实现GetEnumerator()和Count方法。这样，您就可以直接填充HashSet<T>，而无需形成临时的List<T>。

- CodesInChaos

1

如果你将1亿个整数放入哈希集中，那么它将占用1.5GB（我的机器）如果你创建一个bool[100000000]，在其中将每个数字设置为true，它只需要100MB，并且查找速度比哈希集更快。这假设整数范围从0到100000000。

- IvoTops

一个 HashSet 的查找速度是 O(1)，那么如何使用 bool 数组比它更快呢？ - Mixxiphoid

2

直接数组查找也是O(1)，但计算哈希并从桶中获取数据比在数组中查找条目更昂贵。而且使用15倍的内存（可能是因为哈希集将所有int包装成对象），这也不是可以忽略的差异。 - IvoTops

感谢您的详细说明。如果我要实现它，我将不得不大幅更改我的代码，但我一定会尝试。感谢您的建议。 - Mixxiphoid

0

HashSet 会通过倍增长来扩容，这样的分配会导致其超出可用内存。

在 64 位 系统上，HashSet 可以容纳多达 8900 万个项目。

在 32 位 系统上，限制约为 6170 万个项目。

这就是为什么您会收到内存溢出异常的原因。

更多信息请参见

http://blog.mischel.com/2008/04/09/hashset-limitations/

- Massimiliano Peluso

这不是真的。我实际上有一个包含1亿个项的HashSet。而且它是在x64平台/应用程序上运行的。 - Mixxiphoid

你能澄清一下你在这里的意思吗？原帖中最终可行的解决方案似乎是将1亿个项目放入其中。上述数字是否是指通过加倍策略遇到内存限制的时间？ - Chris

啊，抱歉我误解了你的回答。对于在循环中添加项目确实如此。（因此触发加倍） - Mixxiphoid

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe · Accepted Answer

像其他集合类型一样，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>构造函数。