为什么 ArrayList 总是比 LinkedList 快 [英] Why is an ArrayList always faster than a LinkedList

问题描述

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

Yesterday I ran a benchmark in Java 17 where I repeatedly created a new Arraylist and Linkedlist and added 10.000.000 Elements to it.

根据 LinkedList 的性质，添加元素(创建 LinkedObject 并将其放在最后)应该比添加到 ArrayList 快得多.(将整个数组复制到另一个稍大的数组中.)

By the nature of a LinkedList adding elements (creating a LinkedObject an putting it at the end) should be much faster than adding to an ArrayList. (Copying whole array in anotherone that is slightly larger.)

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

Are native functions like arraycopy() really that much faster? The only thing the LinkedList was better at was merging two LinkedLists together.

推荐答案

大多数时候，添加到 ArrayList 不会 分配一个新数组，因为当需要增长时，实现将支持数组的大小增加了 50%.

Most of the time, adding to an ArrayList won't allocate a new array, since the implementation increases the size of the backing array by 50% when it needs to grow.

从内存的角度来看，这可能听起来很浪费，但即使是不断增长的 ArrayList 使用的内存比LinkedList 更少的最坏情况 - 链表中的每个条目都会消耗一个对象头 + 3 个引用(上一个/值/下一个)，而最坏情况下增长的 ArrayList 每个条目只有 1.5 个引用(即使用的数组单元格，加上 50%未使用).

This may sound wasteful from a memory perspective, but even a worst-case scenario for a growing ArrayList uses less memory than LinkedList - each entry in a linked list costs an object header + 3 references (prev/value/next), whereas a worst-case growing ArrayList has only 1.5 references per entry (i.e., the array cells used, plus 50% which are as-yet unused).

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

Anywho, according to my calculations, this means that adding 10 million entries to a default-initiated ArrayList will result in some 35 array-copying actions, which isn't very much. (And yes, System.arraycopy is fast.)

最后，如果您给阵列的初始容量为 10_000_000，则将创建零个阵列副本.您可以尝试一下，看看复制的实际成本是多少.

Finally, if you give your array an initial capacity of 10_000_000, there will be zero array copies made. You can try that to see how much the copying really costs.

这篇关于为什么 ArrayList 总是比 LinkedList 快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！