在Java中使用HashSets时，方法retainAll的时间和空间复杂度是多少？
例如，在下面的代码中：
public int commonTwo(String[] a, String[] b) { Set common = new HashSet(Arrays.asList(a)); common.retainAll(new HashSet(Arrays.asList(b))); return common.size(); } 让我们仔细阅读代码 。 方法retainAllinheritance自AbstractCollection并且（至少在OpenJDK中）如下所示：
public boolean retainAll(Collection c) { boolean modified = false; Iterator it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; }
这里有一个很重要的注意事项，我们遍历this.iterator()并调用c.contains 。 所以时间复杂度是n调用c.contains ，其中n = this.size() ，最多n调用it.remove() 。
这个重要的是在其他 Collection上调用contains方法，因此复杂性取决于其他Collection contains的复杂性。
所以，同时：
Set common = new HashSet<>(Arrays.asList(a)); common.retainAll(new HashSet<>(Arrays.asList(b)));
将是O(a.length) HashSet.contains O(a.length) ，因为HashSet.contains和HashSet.remove都是O(1) （摊销）。
如果你打电话
common.retainAll(Arrays.asList(b));
然后由于O(n) contains在Arrays.ArrayList这将成为O(a.length * b.length) – 即通过花费O(n)将数组复制到HashSet ，实际上你可以更快地调用retainAll 。
就空间复杂性而言， retainAll不需要额外的空间（超出Iterator ），但是你的调用实际上是非常昂贵的空间，因为你分配了两个新的HashSet实现，它们实际上是完全成熟的HashMap 。
还有两点可以注意：
- 没有理由从 – 中的元素中分配
HashSet– 也可以使用从中间删除O(1)的更便宜的集合，例如LinkedList。 （内存更便宜，也可以构建时间 – 不构建哈希表） - 在创建新的集合实例时，您的修改将丢失，并且仅返回
b.size()。
该实现可以在java.util.AbstractCollection类中找到。 它的实现方式如下：
public boolean retainAll(Collection c) { Objects.requireNonNull(c); boolean modified = false; Iterator it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; }
因此，它将迭代common集中的所有内容，并检查作为参数传递的集合是否包含此元素。
在你的情况下，两者都是HashSet ，因此它将是O（n），因为contains应该是O（1）摊销并且在你的common集上迭代是O（n）。
你可以做的一个改进就是不复制a新的HashSet ，因为无论如何它都会被迭代你可以保留一个列表。