ArrayList与HashSet中的removeAll()

我发现对于相当大的数组(超过1000个条目),这些方法比A.removeAll(B)a更快.HashSetArrayList

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

一个集合(因此HashSet也包含)最多包含一个元素,B因为HashSet使用散列,定位和删除该元素非常有效.因此,整体复杂性应该O(1)用于删除所有(即一个)B.

列表可以包含任何B位置的任意数量,因此删除所有B必须检查所有元素.总体复杂性是O(n)因为如果它是a,则必须检查每个元素B.

编辑:

如果B代表集合/阵列,即一组多个元素,你就应该在尺寸乘以上述复杂m的B,所以你会得到O(m)的HashSet,并O(n * m)为列表.

编辑2:

请注意,如果您有一个排序列表,复杂性可能会降低到O(log(n))或O(log(n) * m).为了实现这一点,删除实际元素的代码必须知道列表已经排序,因为ArrayList不保证排序它不能进行优化.