使用ArrayList或HashMap以获得更快的速度

Question

我需要一个'列表'或'地图',...对象 A。此列表将从另一个数组列表添加。当 A 的参数等于时id对象 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） 性能的原因是哈希算法对每个键花费相同的时间，然后查找键也需要恒定的时间。在某些情况下，哈希表可能会超过其负载因子并需要重新分配，以及它为什么在平均值上保持不变。

所以最后，要回答你的问题，我的建议是使用 HashMap .

Answer 2

首先，我将冒昧地声明这是两种完全不同的数据结构。 List处理元素的线性表示形式，Map处理键对值。

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

如果您

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

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