使用ArrayList或HashMap提高速度

Question

我需要一个“列表”或“地图”，。。。此列表将从另一个ArrayList中添加。当A的参数等于时，对象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

首先，我要指出这是两种完全不同的数据结构。列表处理元素的线性表示，映射处理键对值。

我的直觉是，你试图在列表和集合之间进行选择。

如果您只想输入唯一的元素，或者更简洁地说，如果您只关心唯一的值，那么某种类型的集是您的最佳选择-如果您不关心排序，可能是哈希集。它为添加、删除、包含和大小等基本操作提供了O（1）时间。

^{（有趣的是，HashSet由HashMap支持，但提供了一个类似于ArrayList的接口。）}

Answer 2

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）性能的原因是散列算法对每个键花费相同的时间，然后查找键也需要恒定的时间。哈希表可能会超过其负载因子并需要重新分配，这就是它在平均水平上保持不变的原因。

最后，为了回答您的问题，我的建议是使用HashMap。