引言
我们知道，对于集合（Collection）都有一个抽象方法removeAll(Collection<?> c)！
但是你可知道，在集合数据比较多的情况下， ArrayList.removeAll(Set)的速度远远高于ArrayList.removeAll(List)！
我简单测试了一下，从1百万数据中remove掉30万数据，前者需要0.031秒，后者需要1267秒！
这不是危言耸听，大家感兴趣可以去实测一下。
探究
类结构分析
先看一下大概的类结构图：
从图中可以看到，图中相关的集合类（HashSet、LinkedList、ArrayList），除了ArrayList自己实现了removeAll()方法外，其他两个集合都是借助父类（或超父类）的Iterator迭代器进行删除。
也许这也是为何ArrayList的removeAll()方法对于不同类型的参数，表现出“与众不同”的原因吧~！
细嚼代码
我们再来细看ArrayList类的removeAll()方法的实现。
为节省各位看官的时间，具体代码我就不贴出来，贴一个伪代码吧，更容易阅读：
如：list.removeAll(subList);//1.将list中不删除的元素移到数组前面（我们知道ArrayList的底层是数组实现）
int w=0; //w为不删除和要删除的分界线
for(var value in 该list的底层数组){if(!subList.contain(value)){该list的底层数组[w]=value;w++;}
}//2.将w后面的元素全部置为null
xxx
其中，我们可以看到影响速率关键的一步：subList.contain(value)！
所以速率的差异，其实也就在于参数集合.contain()方法的差异~
HashSet.contains() vs ArrayList.contains()
- ArrayList.contains()
实现很简单，即调用indexOf()，一个一个地遍历查找。最坏时间复杂度为
O(总数据量)。
- HashSet.contains()
我们知道，HashSet的底层是HashMap，因此，实际也就是调用
map.containKey()方法。
大家都知道，HashMap的查找速度非常快！
因此，到这里，我们也就解释题目的问题。同时也知道了，在数据量比较大的的情况下，使用arrayList.removeAll(subList)时，可以更改为：
- 将
subList封装为HashSet：arrayList.removeAll(new HashSet(subList)) - 将
arrayList改为LinkedList：new LinkedList(arrayList).removeAll(subList)
再聊HashMap.containKey()
都说到这儿了，不聊聊map的一点东西，也说不过去了。
先上图：
我们知道，HashMap的底层是数组+链表。而containsKey()底层其实也就是getEntry(key)，然后判断该Entry是否为null，来达到目的！
在JDK1.8中，getEntry()即getNode()。另外，get(key)方法的底层同样也是(e=getEntry(key))!=null?e.value:null。
说多了，我们回归正题。
图上，最顶行为一个数组，而每列是一个个链表。
每个元素put进来需要放在哪儿，大概需要这些步骤：
- 确定该key放在数组的哪一个索引下：
索引位置 = (数组.size-1) & hash(key.hashcode())
- 之前版本是将上面的位运算
&换成了取余%，效果都一样，都是为了防止hashcode值超出数组的长度。不过位运算效率肯定是大于取余的。
- 科普：
a & b = c，那么c<=min(a,b)，因此得到的索引始终小于数组.size-1，至于为何会小于等于c<=min(a,b)？
- 如：4 & 8 = 00000100 & 00001000，相同位置进行
与运算，与运算是两者均真才为真！因此我们看最小的那个数（00000100），任何数与它进行与运算，前面5位都不可能为1，那么结果只能小于等于4~
- 另外注意，上面用了一个hash()方法，是为了让所有key的hash保持均匀，为什么要这样做呢？
- 举个例子，你重写了hashcode方法，返回都是1。最后hashmap在存储这类对象时，全都放到同一个索引位置去了！
- 给Entry.next=null的Entry，变为Entry.next=new Node()
- 注意：如果数据过大，JDK1.8会自动切换链表为红黑树实现
因此，就containsKey()而言，最坏的时间复杂度为：O((总数据量/数组长度)*最长链表长度)
而这个数组长度到底有多长？链表有多长？它们和数据量成一个什么关系呢？
我们需要简单探究一下HashMap的实现：
由图可知，数组长度一般都是大于总数据量（负载因子<=1时）。因此最坏时间复杂度≈O(最长链表长度)。
那么链表长度有多长？
设想一下，数组长度>=总数据量，那么最好情况下（各数据的hash均匀分布），可能一个链表就一个元素，即时间复杂度可能为O(1)！
至少大多情况下，链表长度都不会太长，除非你就是那个重写hashcode，始终返回1的人！
