哈希集合的内存开销

Question

哈希集合的内存开销

16

在 C# 程序中，我有两个 longs 的 Queue 和四个 longs 的 HashSet，共有 26M 个元素和 50M 个元素。因此，我的容器存储了 75M 个 longs，这就产生了 600MB 的数据。程序的内存使用量为 3GB。

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

编辑：是的，我没有意思是复杂度。 HashSet 需要多少额外的内存来存储 long？简单的二叉堆不需要任何额外的内存。如果我需要降低内存使用率或者需要自己实现一个，是否有任何替代方案可以使用？

- Ari

2

内存复杂度应该是O(n)。也许你想问的是HashSet的存储开销？（很抱歉，我不知道答案。） - user3553031

@ScottChamberlain 这个程序正在检查状态（longs），以确定是否存在获胜或失败。因此，当我处理一个状态时，我会检查连接的状态是否存在获胜或失败（使用 Contains ），然后有时将处理过的状态添加到获胜或失败状态中。 - Ari

4

你是如何测量所使用的内存的？仅因任务管理器显示你正在使用3GB内存并不意味着你的应用程序当前正在使用所有这些内存。这个数字可能会因系统可用内存大小以及当前运行的其他程序而大幅度变化。 - John Koerner

我做了计算，HashSet<long> 每个 long 大约需要 24 字节，并且在扩容时会将当前容量翻倍并舍入到下一个质数。所以 3GB 并不是那么不合理的。 - Scott Chamberlain

当您完成添加元素时，可以调用HashSet<T>.TrimExcess。但是，它是否将内存（硬盘空间）返回给操作系统取决于垃圾回收器的运行情况。 - Tom Blodget

显示剩余3条评论

1个回答

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

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

- huntharo · Accepted Answer

概述

每个HashSet插槽（可以包含项或为空）需要12字节的开销。在存储longs时，这种开销比数据大小大150％。

HashSet还为新数据保留空插槽，您示例中的项目数量（每个HashSet约1250万个项目）会导致空插槽导致的内存使用量增加约66％。

如果您需要O(1)集合中存在性的验证，则HashSet可能是您最好的选择。如果您对数据有特殊了解（例如，它包含连续数百项的“运行”），则您可能能够想出一种更聪明的方式来表示它，从而需要更少的内存。没有更多关于数据的了解，很难对此提出建议。

测试程序

    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实现-Mono

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

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

HashSet实现-MSFT

插槽分配策略-使用质数进行分配。这可能会导致大量的空间浪费，但可以减少必须重新分配和重新散列表格的次数。

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

内存使用-一般大小-Mono实现

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

每个插槽的内存使用-两种实现

表格：每个插槽1个4字节int = 4字节/插槽
链接：每个插槽2个4字节int = 8字节/插槽
插槽：每个插槽1个（sizeof T）字节= 8字节/插槽（对于T = long）
总计：每个插槽20字节

示例中使用的插槽-Mono

示例中每个HashSet有1250万个项。

插槽= 10 * 2 ^ ceiling(log2(items / 10))

log2(12,500,000 /10) ~= 20.5

插槽~=2100万

示例中使用的内存-计算-Mono

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

每个HashSet：2100万个插槽* 20字节/插槽= 420 MB

所有HashSets：1.68 GB

总计：1.88 GB（+大对象堆中的空间）

示例中使用的内存-使用Son of Strike观察-MSFT实现

.Net堆中的3.5 GB内存

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

2.5 GB的HashSet插槽对象

注意：MSFT的Slot对象是8字节加上数据的大小（在这种情况下为8字节），总共为16字节。存储仅50万个项的1560万个槽对象。

dumpheap -stat

!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

eeheap -gc

!eeheap -gc
Number of GC Heaps: 1
generation 0 starts at 0x00000042800472f8
generation 1 starts at 0x0000004280001018
generation 2 starts at 0x0000004280001000
ephemeral segment allocation context: none
 segment     begin allocated  size
0000004280000000  0000004280001000  000000428004b310  0x4a310(303888)
Large object heap starts at 0x0000004290001000
 segment     begin allocated  size
0000004290000000  0000004290001000  0000004290009728  0x8728(34600)
00000042dc000000  00000042dc001000  00000042e7717e70  0xb716e70(191983216)
000000433e6e0000  000000433e6e1000  000000434f9835b0  0x112a25b0(287974832)
00000043526e0000  00000043526e1000  000000435a6e1038  0x8000038(134217784)
000000435e6e0000  000000435e6e1000  0000004380c25c00  0x22544c00(575949824)
00000043826e0000  00000043826e1000  000000438826c788  0x5b8b788(95991688)
000000438a6e0000  000000438a6e1000  00000043acc25c00  0x22544c00(575949824)
00000043ae6e0000  00000043ae6e1000  00000043b426c788  0x5b8b788(95991688)
00000043b66e0000  00000043b66e1000  00000043d8c25c00  0x22544c00(575949824)
00000043da6e0000  00000043da6e1000  00000043e026c788  0x5b8b788(95991688)
00000043e26e0000  00000043e26e1000  0000004404c25c00  0x22544c00(575949824)
0000004298000000  0000004298001000  00000042a8001038  0x10000038(268435512)
Total Size:              Size: 0xcf1c1560 (3474724192) bytes.
------------------------------
GC Heap Size:            Size: 0xcf1c1560 (3474724192) bytes.