Java中集合与Java中列表的性能

Question

考虑下面的代码

List<Integer> l=new ArrayList();
Set<Integer> l=new HashSet();

以下哪个 for 循环是最佳的

for(Integer i: some arrray){
    if(!l.contains(i))
    l.add(i);
}

或者

 for(Integer i :some array){
   s.add(i);
}

Answer 1

AHashSet为该方法提供了恒定的时间性能add（它HashMap在幕后使用了 a）。假设 的大小some arrray为m- 总体时间复杂度为O(m)。

如果您使用 an ，则 inArrayList最坏情况的复杂性（其中是 list 中的元素数量）。所以，总体时间复杂度为containsO(n)nlO(n * m)

所以 aSet在这里更好（基于发布的代码片段） - 但取决于您之后用它做什么以及 Set 是否可以支持它。