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

Question

我需要对象 A 的“列表”或“地图”...。此列表将从另一个 ArrayList 添加。当 A 的参数相等时，对象 A 被认为等于另一个id。

我的问题是我只想添加一个列表中不存在的对象。我想知道这两种实施方案之间的关系。使用 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 个对象或更多对象）我的问题有更好的模式吗？？？

score 63 · Accepted Answer

每次搜索都有 O(n)的ArrayList性能，因此对于 n 次搜索，它的性能是 O(n^2)。

每次搜索（平均）都有 O(1)的HashMap性能，因此对于 n 次搜索，它的性能将是 O(n)。

虽然HashMap起初会较慢并占用更多内存，但对于较大的 n 值会更快。

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

具有 O(1) 性能的原因HashMap是散列算法对每个密钥都花费相同的时间，然后查找密钥的查找也需要恒定的时间。有时哈希表会超过其负载因子并需要重新分配，这就是为什么它在 varage上保持不变的原因。

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

score 25 · Accepted Answer

首先，我要冒昧地声明这是两种完全不同的数据结构。 AList处理元素的线性表示，而 aMap处理键对值。

我的直觉是你试图在 aList和 a之间进行选择Set。

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

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

2 回答 2