Java 使用 ArrayList 或 HashMap 提高速度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18862997/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using ArrayList or HashMap for better speed
提问by hieuxit
I need a 'List' or 'Map',... of object A. This list will be added from another ArrayList. Object A is considered to be equal to another when idparameter of A equals.
我需要一个“列表”或“地图”，...对象 A。这个列表将从另一个 ArrayList 添加。当idA 的参数等于时，对象 A 被认为等于另一个。
My problem is I only want add an object that does not exist in my List. I wonder between the two alternatives for implementation. Using ArrayList or HashMap
我的问题是我只想添加一个不存在于我的列表中的对象。我想知道两种实现方案之间的差异。使用 ArrayList 或 HashMap
1. ArrayList:
for (A a: source) {if (! (a in ArrayList)) addToArrayList();}
2. HashMap <id, A>
for (A a: source) {hasmap.put (a.id, a)}
Which will give better speed to add a large number (over 1000 objects, or bigger number of object) Is there a better pattern for my problem???
哪个可以更快地添加大量（超过 1000 个对象，或更多的对象）我的问题有更好的模式吗？？？
采纳答案by Makoto
First, I'm going to go out on a limb and state that these are two completely different data structures.A Listdeals with a linear representation of elements, and a Mapdeals with key-pair values.
首先，我要大胆地声明这是两种完全不同的数据结构。AList处理元素的线性表示，aMap处理密钥对值。
My gut feeling is that you're attempting to choose between a Listand a Set.
我的直觉是您正试图在 aList和 a之间进行选择Set。
If you wish to only enter uniqueelements, or to put it more succinctly, if you only care about unique values, then a Setof some kind is your best bet - probably HashSetif you don't care about ordering. It provides O(1) timefor the basic operations, such as add, remove, contains, and size.
如果您只想输入唯一元素，或者更简洁地说，如果您只关心唯一值，那么Set某种类型是您最好的选择 - 可能HashSet如果您不关心排序。 它为基本操作（例如添加、删除、包含和大小）提供 O(1) 时间。
(Interestingly enough, HashSetis backed by a HashMap, but provides an interface similar to ArrayList.)
（有趣的是，HashSet由 a 支持HashMap，但提供了一个类似于 的接口ArrayList。）
回答by andy256
The ArrayListhas O(n) performance for every search, so for n searches its performance is O(n^2).
将ArrayList有O（n）性能为每一个搜索，所以对于n搜索它的性能是O（n ^ 2）。
The HashMaphas O(1) performance for every search (on average), so for n searches its performance will be O(n).
在HashMap对每一个搜索（平均）O（1）性能，所以对于n搜索它的性能会为O（n）。
While the HashMapwill be slower at first and take more memory, it will be faster for large values of n.
虽然一开始HashMap会更慢并占用更多内存，但对于较大的 n 值会更快。
The reason the ArrayListhas O(n) performance is that every item must be checked for every insertion to make sure it is not already in the list. We will do n insertions, so it is O(n^2) for the whole operation.
ArrayList具有 O(n) 性能的原因是每次插入都必须检查每个项目，以确保它不在列表中。我们将进行 n 次插入，因此整个操作的复杂度为 O(n^2)。
The reason the HashMaphas O(1) performance is that the hashing algorithm takes the same time for every key and then the lookup to find the key also takes constant time. There can be occasions when the hash table exceeds its load factor and needs to be reallocated, and that it why it is constant on avarage.
HashMap具有 O(1) 性能的原因是散列算法对每个键花费相同的时间，然后查找键的查找也花费恒定的时间。有时哈希表超过其负载因子并需要重新分配，这就是为什么它在 avarage上保持不变的原因。
So finally, to answer your question, my advice is to use the HashMap.
所以最后，为了回答你的问题，我的建议是使用HashMap.
