专栏首页程序猿杂货铺为什么arrayList.removeAll(set)的速度远高于arrayList.removeAll(list)?

为什么arrayList.removeAll(set)的速度远高于arrayList.removeAll(list)?

引言

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

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

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

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

探究

类结构分析

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

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

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

细嚼代码

我们再来细看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封装为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()方法,是为了让所有keyhash保持均匀,为什么要这样做呢?
  • 举个例子,你重写了hashcode方法,返回都是1。最后hashmap在存储这类对象时,全都放到同一个索引位置去了!

2.给Entry.next=nullEntry,变为Entry.next=new Node()

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

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

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

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

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

那么链表长度有多长?

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

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

本文分享自微信公众号 - 程序猿杂货铺(zhoudl_l),作者:localhost02

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【集合详解】ArrayList 源码解读之动态扩容

    ArrayList 是一个 Java 集合,它的底层数据结构实际上就是一个数组,只不过这个数组长度不固定,动态可变,其中数组元素的类型是 Object 类型的,...

    周三不加班
  • 【LeetCode题解-012】Integer to Roman

    Roman numerals are represented by seven different symbols: I, V, X, L, C, D and ...

    周三不加班
  • 一个字节的网络漫游故事独白

    大家好,给大家介绍一下,我是一个字节。相比于你们人类据说即将达到的百岁人生的寿命,我的一生简直不直一提(我只能存活零点几个毫秒)。

    周三不加班
  • Lync Server子域启用Lync功能

    正如标题如写,根域yangqs.com,子域child1.yangqs.com下用户johnson@child1.yangqs.com如何启用Lync呢?

    杨强生
  • PHP+fiddler抓包采集微信文章阅读数点赞数的思路详解

    分析接口知道要获取文章阅读数和点赞数必须有key和uin这两个关键参数,不同公众号key不一样(据说有万能微信key,不懂怎么搞到),同一个公众号key大概半小...

    砸漏
  • 绿盟科技2015 H1 DDoS态势报告:DDoS攻击两极分化

    绿盟科技发布了2015 H1 DDoS威胁报告。 报告发现近期的DDoS攻击呈现两极分化的局面: 大流量攻击不断增长,按照此趋势足以对互联网骨干网络造成威胁(>...

    FB客服
  • 公平的决断——扔硬币

    排列组合是我们在这本书中接触到的第一个概率论概念,也是我们在高中学过的一个概率学的入门概念。 概念记不清了也不要紧,我们回忆一下在中学学过的排列组合都有哪些经典...

    刀刀老高
  • DDoS攻击防护服务: 实施前考虑哪些事项

    在实施DDoS攻击防护服务之前,有几件事是企业应该考虑的。专家Ed Moyle讨论了提高安全性要采取的几个步骤。 一些MSSP中有这样一种说法,有两种客户:那些...

    静一
  • 诡异的iOS keep-alive bug

    https://bugs.webkit.org/show_bug.cgi?id=155632

    libo1106
  • 加快GitLabCI流水线构建的一些方法

    GitLab.com 提供共享的Runner程序供每个存储库使用,虽然这对于快速开始来说是很棒的,但我们发现最大的单项速度提升来自接待我们自己的Runner。对...

    泽阳

扫码关注云+社区

领取腾讯云代金券