ArrayList vs HashSet中的removeAll（）

Question

我发现对于相当大的数组（超过1000个条目），方法A.removeAll(B)在HashSet上比在ArrayList上快得多。

您是否了解如何实施这些方法以及如何解释这种差异？

Answer 1

一组（并因此HashSet以及）包含B至多一个元件，并且自HashSet使用散列这是相当有效的定位和移除元件。因此，总体复杂性应该是O(1)，用于删除全部（即一个）B。

一个列表可以在任何位置包含任意数量的B，因此全部移除B必须检查所有元素。总体复杂度为O(n)，因为如果它是B，则必须检查每个元素。

编辑：

如果B代表的集合/阵列，即一组多个元素，你就应该由大小Bm乘以上述的复杂性，所以你会得到O(m)为HashSet和O(n * m)为名单。

编辑2：

请注意，如果你有一个排序列表的复杂性可能会降低到O(log(n))或O(log(n) * m)。对于这个工作代码删除实际元素将不得不知道列表虽然排序虽然ArrayList不保证排序它不能进行优化。

Answer 2

基本上两者的原因是这些特定实现尝试为它们的专有操作实现时间复杂性。

为ArrayList remove方法的时间复杂度为O(n - index)source from When to use LinkedList over ArrayList?

虽然HashSet的remove方法提供了恒定的时间复杂度O(1)source from Hashset vs Treeset