java - 为什么 ArrayList 总是比 LinkedList 快

Question

昨天我在 Java 17 中运行了一个基准测试，在那里我反复创建了一个新的 Arraylist 和 Linkedlist 并向其中添加了 10.000.000 个元素。

从 LinkedList 的性质来看，添加元素（创建 LinkedObject 并将其放在末尾）应该比添加到 ArrayList 快得多。（将整个数组复制到另一个稍大的数组中。）

像 arraycopy() 这样的原生函数真的那么快吗？LinkedList 唯一擅长的是将两个 LinkedList 合并在一起。

标签： javaarraylistlinked-listbenchmarking

Answer 1

大多数情况下，添加到 anArrayList 不会分配新数组，因为当需要增长时，实现会将支持数组的大小增加 50%。

从内存的角度来看，这可能听起来很浪费，但即使是增长的最坏情况ArrayList使用的内存也比LinkedList链表中的每个条目花费一个对象头 + 3 个引用（上一个/值/下一个），而最坏的情况生长ArrayList每个条目只有 1.5 个引用（即，使用的数组单元，加上 50% 尚未使用）。

Anywho，根据我的计算，这意味着向默认启动的添加 1000 万个条目ArrayList将导致大约 35 个数组复制操作，这不是很多。（是的，System.arraycopy 很快。）

最后，如果您给数组的初始容量为10_000_000，则将生成零个数组副本。您可以尝试一下，看看复制的真正成本是多少。