Hashset内存开销

Question

在C#程序中，我同时拥有Queues，longs个元素的两个26M和HashSets，longs个元素的四个50M。因此，我的容器正在存储75M longs，该数据提供600MB数据。程序的内存使用量为3GB。

为什么这些容器需要那么多内存？ HashSet的存储复杂度是多少？即使所有结构的容量都加倍，它也会给出1.2GB，而不是3GB。

编辑：是的，我并不是说复杂性。 HashSet需要存储多少额外内存？简单的二进制堆不需要任何额外的内存。如果我需要降低内存使用率或需要自己实现一个内存，long是否有其他选择？

Answer 1

概述

HashSet每个插槽有12个字节的开销（可以包含一个项目，也可以为空）。在存储long的情况下，此开销比数据大小大150％。

[HashSet还为新数据保留了空插槽，示例中的项目数（每个HashSet约有1,250万个项目）仅由于空插槽而导致内存使用量增加了约66％。

如果您需要O（1）确认集合中的存在，则HashSet也许是您可以做的最好的事情。如果您对数据有一些特别的了解（例如，它连续包含数百个项目的“运行”），那么您也许可以提出一种更聪明的方式来表示此数据，而这需要更少的内存。如果不了解更多数据，就很难对此提出建议。

测试程序

HashSet

HashSet实现-Mono

插槽分配策略-在每次分配时将表的大小加倍。

    static void Main(string[] args)
    {
        var q = new Queue<long>();
        var hs = new []
        {
            new HashSet<long>(),
            new HashSet<long>(),
            new HashSet<long>(),
            new HashSet<long>()
        };

        for (long i = 0; i < 25000000; ++i)
        {
            q.Enqueue(i);

            if (i < 12500000)
            {
                foreach (var h in hs)
                {
                    h.Add(i);
                }
            }
        }

        Console.WriteLine("Press [enter] to exit");
        Console.ReadLine();
    }

HashSet实现-MSFT

插槽分配策略-使用素数进行分配。这可能会导致大量的空白空间，但会减少必须重新分配和重新整理表的次数。

https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs

内存使用情况-常规大小调整-Mono实现

• 初始大小：10个插槽
• 填充因子：90％全触发器调整大小
• 调整大小因子：达到填充因子时将大小加倍

内存使用率-每个插槽-两种实现方式>>

• 表：每个插槽1 x 4字节int = 4字节/插槽

链接：每个插槽2 x 4字节int = 8字节/插槽

Slots：1 x（sizeof T）字节= 8字节/插槽（对于T = long）

总计：20字节/插槽

示例中使用的插槽-单声道

该示例在每个HashSet中有1,250万个项目。

slots = 10 * 2 ^ ceiling（log2（items / 10））

log2（12,500,000 / 10）〜= 20.5

插槽〜= 2100万

示例中使用的内存-计算的-单声道

队列：2500万长* 8字节/长= 200 MB

每个哈希集：2100万个插槽* 20字节/插槽= 420 MB

所有哈希集：1.68 GB

总计：1.88 GB（大对象堆中有+空白）

示例中使用的内存-通过罢工观察-MSFT实现

。Net堆中的3.5 GB内存

400 MB Int32数组（由HashSet使用，不用于我们的数据存储）

2.5 GB HashSet插槽对象

注意：MSFT的Slot对象是8字节加上数据的大小（在这种情况下为8字节），总共16字节。 2.5 GB的插槽对象为1.56亿个插槽，仅可存储5000万个项目。

dumpheap -stat

http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs

eeheap -gc

!dumpheap -stat
Statistics:
              MT    Count    TotalSize Class Name
00007ffb549af228        1           24 System.Collections.Generic.GenericEqualityComparer`1[[System.Int64, mscorlib]]
[snip]
00007ffb53e80bd8      159         6926 System.String
00007ffb53e81250       27        36360 System.Object[]
00000042ed0a8a30       22     48276686      Free
00007ffb53f066f0        3    402653256 System.Int64[]
00007ffb53e83768       14    431963036 System.Int32[]
00007ffaf5e17e88        5   2591773968 System.Collections.Generic.HashSet`1+Slot[[System.Int64, mscorlib]][]
Total 343 objects