9

我偶然发现了以下问题。
我想要一个包含从 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 内存，所以当我遇到溢出异常时我感到非常惊讶。

4

4 回答 4

10

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

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

这就是您在第三个示例中发生的情况 - 您正在添加 a List<T>which 也是 an 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>构造函数。

于 2012-07-19T08:54:07.677 回答
2

我想HashSet<T>，像大多数.net 集合一样，使用数组加倍策略来实现增长。不幸的是，没有占用容量的构造函数重载。

但是，如果它检查ICollection<T>并用作ICollection<T>.Count初始容量，您可以实现该工具的基本ICollection<T>实现GetEnumerator()和Count. 这样，您可以直接填充 ，HashSet<T>而无需实现临时List<T>.

于 2012-07-19T09:06:50.490 回答
1

如果您将 1 亿个整数放入将消耗 1.5GB 的哈希集（我的机器）如果您创建一个 bool[100000000] 并在其中设置您必须为真的每个数字，则它只需要 100MB 并且查找速度也比哈希集快。这假设整数范围为 0-100000000

于 2012-07-21T21:58:46.460 回答
0

HashSet通过加倍增长，并且该分配导致它超出可用内存。

在64 位系统上，一个 HashSet 可以容纳超过8900 万个项目。

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

这就是为什么你得到内存溢出异常

了解更多信息

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

于 2012-07-19T08:56:15.837 回答