使用ArrayList或HashMap可以提高速度

Question

我需要一个对象A的'List'或'Map',...这个列表将从另一个ArrayList中添加.当idA的参数等于时,对象A被认为等于另一个.

我的问题是我只想添加一个我的列表中不存在的对象.我想知道两种替代方案之间的实施.使用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)}

哪个会提供更好的速度来添加大量(超过1000个对象,或更大数量的对象)是否有一个更好的模式我的问题???

Answer 1

在ArrayList每一个搜索有O(n)性能,所以对于n搜索它的性能是O(n ^ 2).

将HashMap有O(1)每一个搜索(平均)的性能,所以对于n搜索它的性能会为O(n).

虽然HashMap最初会慢一些并占用更多内存,但对于较大的n值,它会更快.

ArrayList具有O(n)性能的原因是每次插入时必须检查每个项目以确保它不在列表中.我们将进行n次插入,因此对于整个操作它是O(n ^ 2).

HashMap具有O(1)性能的原因是散列算法对于每个密钥花费相同的时间,然后查找以找到密钥也需要恒定的时间.有时候哈希表超出了它的加载因子并需要重新分配,这就是为什么它在avarage上是常量的.

最后,为了回答你的问题,我的建议是使用HashMap.

Answer 2

首先,我要说明这两个完全不同的数据结构. A List处理元素的线性表示,以及Map处理键对值.

我的直觉是你试图在a List和a 之间做出选择Set.

如果你只想输入独特的元素,或者更简洁地说,如果你只关心独特的价值观,那么Set某种类型是你最好的选择 - 可能HashSet你不关心订购. 它为基本操作提供了O(1)时间,例如添加,删除,包含和大小.

^{(有趣的是,HashSet由a支持HashMap,但提供类似的接口ArrayList.)}