数组列表和哈希集内存分配奇怪的测试结果

collections java scala performance-testing scalameter

2022-09-04 23:00:55

我受到以下主题的启发：List 和 Set 之间的性能和内存分配比较，以实际运行一些测试并测量和之间的性能差异。ArrayListHashSet

在提到的主题中，投票最多的答案引起了我的兴趣（链接），说：

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

在ScalaMeter的帮助下，我想确保这一点。

我做了两个简单的测试，将从元素添加到两个和.将初始大小设置为最大值不会更改结果。我用两种类型测试了这些集合：10000100000ArrayListHashSet

Int（将连续数字 0 设置为 100000）
String（使用Apache放置随机字符串RandomStringUtils)

该代码可在此处的存储库中找到。

运行这些，给了我这个结果：

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

对于收藏品持有：Int

对于大小为 10 的收藏夹：String

对于大小为 50 的收藏品：String

问题：

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

谢谢:)！

@andrzej答案后更新我再次更新了代码（和存储库）。结果越来越好，但结果仍然没有5.5倍的差异。我现在正在检查更多的东西。

答案 1

引用答案中提到的理论发生了什么变化？这是假的吗？

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

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

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

数组列表

元素存储在字段。所以的长度必须至少是。
假设您用实例化了列表，因此正是。然后，列表的大小是字节（其中是对象引用的大小）。在这里，我忽略了列表的字段和对象标题。transient Object[] elementData;elementDatannew ArrayList<>(n)elementData.lengthnn*ccsize

哈希地图

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

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

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

当哈希表中的条目数超过负载因子和当前容量的乘积时，将重新哈希表（即重建内部数据结构），以便哈希表的存储桶数大约是其两倍。

基于此，我将估计.
对哈希映射求和需要字节。table.length == 2*nn*2*c + n*(3*c + 4) = n*5*c + n*4

总结

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

因此，原始理论消耗的内存比看起来合理，并且似乎与您的测量结果不符。HashSetArrayList

答案 2

请添加测量对象作为返回值。

measure method "Int" in {
  using(sizes) curve listS in { i =>
    val c = new util.ArrayList[Int](i)
    (0 until i).map(t => c.add(t))
    c // return c
  }

  using(sizes) curve setS in { i =>
    val c = new util.HashSet[Int]()
    (0 until i).map(t => c.add(t))
    c // return c
  }
}