java - 使用 ArrayList 或 HashMap 以获得更好的速度

Question

我需要对象 A 的“列表”或“ map ”...。该列表将从另一个 ArrayList 添加。当 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。