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

performance hashmap java arraylist

2022-09-02 02:11:07

我需要一个“列表”或“地图”,...的对象 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个对象，或更大数量的对象）对于我的问题是否有更好的模式???

答案 1

对于每个搜索，都有 O（n）性能，因此对于 n 个搜索，其性能为 O（n^2）。ArrayList

每个搜索（平均）都有O（1）性能，因此对于n个搜索，其性能将是O（n）。HashMap

虽然一开始会更慢并占用更多内存，但对于 n 的大值，它会更快。HashMap

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

具有 O（1）性能的原因是哈希算法对每个密钥花费相同的时间，然后查找以查找密钥也需要恒定的时间。在某些情况下，哈希表可能会超过其负载因子并需要重新分配，并且它为什么它在 avarage 上是常量。HashMap

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

答案 2

首先，我将提出一个肢体，并指出这是两个完全不同的数据结构。A 处理元素的线性表示，a 处理键对值。ListMap

我的直觉是，你试图在a和a之间做出选择。ListSet

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

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