引言

我们知道，对于集合（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()方法的实现。

为节省各位看官的时间，具体代码我就不贴出来，贴一个伪代码吧，更容易阅读：

1
2
3
4
5
6
7
8
9
10
11
12
13
如：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()

  1. ArrayList.contains()

    实现很简单，即调用indexOf()，一个一个地遍历查找。最坏时间复杂度为O(总数据量)。

  2. 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进来需要放在哪儿，大概需要这些步骤：

  1. 确定该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在存储这类对象时，全都放到同一个索引位置去了！

  2. 给Entry.next=null的Entry，变为Entry.next=new Node()

    • 注意：如果数据过大，JDK1.8会自动切换链表为红黑树实现

因此，就containsKey()而言，最坏的时间复杂度为：O((总数据量/数组长度)*最长链表长度)

而这个数组长度到底有多长？链表有多长？它们和数据量成一个什么关系呢？

我们需要简单探究一下HashMap的实现：

由图可知，数组长度一般都是大于总数据量（负载因子<=1时）。因此最坏时间复杂度≈O(最长链表长度)。

那么链表长度有多长？

设想一下，数组长度>=总数据量，那么最好情况下（各数据的hash均匀分布），可能一个链表就一个元素，即时间复杂度可能为O(1)！

至少大多情况下，链表长度都不会太长，除非你就是那个重写hashcode，始终返回1的人！

更多文章，请关注：开猿笔记