引言

我们知道,对于集合(Collection)都有一个抽象方法removeAll(Collection<?> c)!

但是你可知道,在集合数据比较多的情况下, ArrayList.removeAll(Set)的速度远远高于ArrayList.removeAll(List)

我简单测试了一下,从1百万数据中remove掉30万数据,前者需要0.031秒,后者需要1267秒!

这不是危言耸听,大家感兴趣可以去实测一下。

探究

类结构分析

先看一下大概的类结构图:

从图中可以看到,图中相关的集合类(HashSetLinkedListArrayList),除了ArrayList自己实现了removeAll()方法外,其他两个集合都是借助父类(或超父类)的Iterator迭代器进行删除。

也许这也是为何ArrayListremoveAll()方法对于不同类型的参数,表现出“与众不同”的原因吧~!

细嚼代码

我们再来细看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封装为HashSetarrayList.removeAll(new HashSet(subList))
  • arrayList改为LinkedListnew 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的人!

更多文章,请关注:开猿笔记