ArrayList和HashSet内存分配奇怪的测试结果

Question

我受到了这个主题的启发:List和Set之间的性能和内存分配比较实际上运行了一些测试并测量ArrayList和之间的性能差异HashSet.

在上述主题中,最受欢迎的答案引起了很多关注(链接),他说:

对于相同数量的元素,HashSet比ArrayList消耗大约5.5倍的内存

在ScalaMeter的帮助下,我想确保这一点.

我做了两个简单的测试,从添加10000到100000元素都ArrayList和HashSet.将初始大小设置为最大值不会更改结果.我用两种类型测试了这些集合:

• Int (将连续数字0到100000)
• String(使用Apache放置随机字符串RandomStringUtils)

该代码可以在我的仓库在这里.

并运行那些,给了我这样的结果:

• X轴 - 尺寸 - >集合的大小
• Y轴 - 值 - >使用的kB量

对于收藏品Int:

对于持有String10号的藏品:

对于持有String50码的藏品:

问题:

在引用的答案中提到的理论发生了什么？这是假的吗？或者我的身边可能有些错误？

谢谢 :)!

@andrzej回答后 更新我再次更新了代码(和存储库).结果越来越好,但结果仍然不是5.5倍.我现在正在检查更多的东西.

Answer 1

引用的答案中提到的理论发生了什么？难道是假的吗？

我们可以做一些计算来得到一个估计：

让我们看一下ArrayList和HashMap的 OpenJDK 源代码（因为HashSet它只是 ArrayList 和 HashMap 的包装HashMap）以获取提示。

假设您有要n存储的元素。

数组列表

元素存储在字段中transient Object[] elementData;。所以 的长度elementData必须至少为n。
假设您用 实例化了列表new ArrayList<>(n)，所以elementData.length正是n。那么列表的大小是n*c字节（其中c是对象引用的大小）。这里我忽略了列表的size字段和对象头。

哈希映射

HashMap 将元素存储在transient Node<K,V>[] table;节点有字段的位置

final int hash;
final K key;
V value;
Node<K,V> next;

然后，为了存储n元素，您需要n节点或n*(3*c + 4)字节，即每个节点有 3 个对象引用 -3*c字节 - 和一个int- 4 字节。
根据HashMap javadoc：

当哈希表中的条目数超过负载因子与当前容量的乘积时，哈希表将被重新哈希（即重建内部数据结构），使得哈希表的桶数大约为两倍。

基于此我会估计table.length == 2*n。
总结哈希图需要n*2*c + n*(3*c + 4) = n*5*c + n*4字节。

概括

现在假设您有一个 64 位 JVM，并且对象引用的大小是 8 个字节（即c = 8）（让我们忽略诸如压缩 oops 之类的东西）。然后n*5*c + n*4 = n*5*8 + n*4 = n*44和n*c = n*8。
最后n*44 / n*8 = 5.5

因此，最初的理论HashSet消耗的内存大约是 5.5 倍，ArrayList这似乎很合理，而且您的测量结果似乎有问题。