从内存分配的角度看 ArrayList 与 LinkedList [英] ArrayList vs LinkedList from memory allocation perspective

问题描述

我需要存储大量信息，例如 Java 列表中的名称".项目的数量可以改变(或者简而言之，我无法预定义大小).我认为，从内存分配的角度来看，LinkedList 将是比 ArrayList 更好的选择，至于 ArrayList，一旦达到最大大小，内存分配会自动加倍，因此总是有可能分配比 ArrayList 更多的内存需要什么.

I need to store a large amount of information, say for example 'names' in a java List. The number of items can change (or in short I cannot predefine the size). I am of the opinion that from a memory allocation perspective LinkedList would be a better option than ArrayList, as for an ArrayList once the max size is reached, automatically the memory allocation doubles and hence there would always be a chance of more memory being allocated than what is needed.

我从这里的其他帖子中了解到，存储在 LinkedList 中的单个元素比 ArrayList 占用更多空间，因为 LinkedList 还需要存储节点信息，但我仍然猜测我定义 LinkedList 的场景可能是更好的选择.另外，我不想进入性能方面(获取、删除等)，因为已经讨论了很多.

I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.

推荐答案

LinkedList 可能会分配更少的条目，但这些条目比 ArrayList 的开销高出天文数字> -- 就内存而言，即使是最坏情况的 ArrayList 也足够便宜.

LinkedList might allocate fewer entries, but those entries are astronomically more expensive than they'd be for ArrayList -- enough that even the worst-case ArrayList is cheaper as far as memory is concerned.

(仅供参考，我认为您弄错了；ArrayList 在它已满时增长 1.5 倍，而不是 2 倍.)

(FYI, I think you've got it wrong; ArrayList grows by 1.5x when it's full, not 2x.)

参见例如https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList 每个元素消耗 24 个字节，而 ArrayList 在最好的情况下每个元素消耗 4 个字节，在最坏的情况下每个元素消耗 6 个字节元素.(结果可能因 32 位与 64 位 JVM 和压缩对象指针选项而异，但在这些比较中，LinkedList 成本至少为 36 字节/元素，而 ArrayList最多 8 分，最差 12 分.)

See e.g. https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList consumes 24 bytes per element, while ArrayList consumes in the best case 4 bytes per element, and in the worst case 6 bytes per element. (Results may vary depending on 32-bit versus 64-bit JVMs, and compressed object pointer options, but in those comparisons LinkedList costs at least 36 bytes/element, and ArrayList is at best 8 and at worst 12.)

更新:

我从这里的其他帖子中了解到，存储在 LinkedList 中的单个元素比 ArrayList 占用更多空间，因为 LinkedList 还需要存储节点信息，但我仍然猜测我定义 LinkedList 的场景可能是更好的选择.另外，我不想进入性能方面(获取、删除等)，因为已经讨论了很多.

I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.

需要明确的是，即使在最坏的情况，ArrayList 也比具有相同元素的 LinkedList 小 4 倍.使 LinkedList 获胜的唯一可能方法是通过使用故意夸大的值调用 ensureCapacity 来故意修复比较，或者从 ArrayList 添加后.

To be clear, even in the worst case, ArrayList is 4x smaller than a LinkedList with the same elements. The only possible way to make LinkedList win is to deliberately fix the comparison by calling ensureCapacity with a deliberately inflated value, or to remove lots of values from the ArrayList after they've been added.

简而言之，基本上不可能让LinkedList在内存比较中胜出，如果你在意空间，那就在ArrayList<上调用trimToSize()/code> 将立即使 ArrayList 再次以巨大优势获胜.严重地.ArrayList 获胜.

In short, it's basically impossible to make LinkedList win the memory comparison, and if you care about space, then calling trimToSize() on the ArrayList will instantly make ArrayList win again by a huge margin. Seriously. ArrayList wins.

这篇关于从内存分配的角度看 ArrayList 与 LinkedList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！