概述
每个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.
Contains
),然后有时将处理过的状态添加到获胜或失败状态中。 - AriHashSet<long>
每个 long 大约需要 24 字节,并且在扩容时会将当前容量翻倍并舍入到下一个质数。所以 3GB 并不是那么不合理的。 - Scott Chamberlain