Java中ArrayList的removeAll方法详解

本文介绍的是关于Java中ArrayList的removeAll方法的相关内容，分享出来供大家参考学习，下面来一起看看详细的介绍：

在开发过程中，遇到一个情况，就是从所有骑手Id中过滤没有标签的骑手Id（直接查询没有标签的骑手不容易实现），

List<Integer> allRiderIdList = new ArrayList(); // 所有的骑手，大致有23W数据
List<Integer> hasAnyTagRiderId = new ArrayList(); // 有标签的骑手， 大致有21W数据
List<Integer> withoutAnyTagRiderList = allRiderIdList.removeAll(hasAnyTagRiderId);

逻辑很简单，就是取一个差集，这样子就拿到没有任何标签的骑手数据。

但是在实际开发过程中，removeAll这个动作很耗时，做测试大概要4分钟左右。查看ArrayList中removeAll的源码片段：

public boolean removeAll(Collection<?> c) {
 Objects.requireNonNull(c);
 return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
 final Object[] elementData = this.elementData;
 int r = 0, w = 0;
 boolean modified = false;
 try {
 for (; r < size; r++) // 循环原来的list
  if (c.contains(elementData[r]) complement) // 这里调用contains方法
  elementData[w++] = elementData[r];
 } finally {
 ....
 }
 return modified;
}

在循环过程中调用contains方法做比较，查一下ArrayList的contains方法，源代码片段如下：

public boolean contains(Object o) {
 return indexOf(o) >= 0;
}

public int indexOf(Object o) {
 if (o null) {
 for (int i = 0; i < size; i++)
  if (elementData[i]==null)
  return i;
 } else {
 for (int i = 0; i < size; i++)
  if (o.equals(elementData[i]))
  return i;
 }
 return -1;
}

这可以看出来，在比较的过程中，又调用了一次循环。

所以removeAll两层for循环，复杂度O(m*n)，所以在操作比较大的ArrayList时，这种方法是绝对不可取的。

下面看一下最终的实现方式：

private List<Integer> removeAll(List<Integer> src, List<Integer> target) {
 LinkedList<Integer> result = new LinkedList<>(src); //大集合用linkedlist
 HashSet<Integer> targetHash = new HashSet<>(target); //小集合用hashset
 Iterator<Integer> iter = result.iterator(); //采用Iterator迭代器进行数据的操作

 while(iter.hasNext()){
 if(targetHash.contains(iter.next())){
  iter.remove();
 }
 }
 return result;
}

同样数量级list, 整个过程只需要几十毫秒，简直天壤之别。

回过头来，比较一下两种实现方式，为什么差距这个大。

1、外层循环

一个是普通的for循环，一个迭代器遍历元素，二者相差不大

2、内层数据比较

前者通过index方法把整个数组顺序遍历了一遍;

后者调用HashSet的contains方法，实际上是调用HashMap的containKey方法，查找时是通过hash表查找，复杂度为O(1)。

接下来我们简单看一下hash表。

hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。可以简单理解为，以空间换时间，牺牲空间复杂度来换取时间复杂度。

hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为hash函数，而通过hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为hash地址。

上面的图大家应该都很熟悉，hash表的一种实现方式，是由数组+链表组成的。元素放入hash表的位置通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。

另外hash表大小的确定也很关键，如果hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。
当然，关于hash表要说的话太多，先简单到此吧~~~

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • java并发容器CopyOnWriteArrayList实现原理及源码分析

    java并发容器CopyOnWriteArrayList实现原理及源码分析

    CopyOnWriteArrayList是Java并发包中提供的一个并发容器,它是个线程安全且读操作无锁的ArrayList,写操作则通过创建底层数组的新副本来实现,是一种读写分离的并发策略,我们也可以称这种容器为"写时复制器",Java并发包中类似的容器还有CopyOnWriteSet.本文会对CopyOnWriteArrayList的实现原理及源码进行分析. 实现原理 我们都知道,集合框架中的ArrayList是非线程安全的,Vector虽是线程安全的,但由于简单粗暴的锁同步机制,

  • Java中Arraylist动态扩容方法详解

    Java中Arraylist动态扩容方法详解

    前言 本文主要给大家介绍了关于Java中Arraylist动态扩容的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. ArrayList 概述 ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长.ArrayList不是线程安全的,只能用在单线程环境下.实现了Serializable接口,因此它支持序列化,能够通过序列化传输:实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问:实现了Cloneable接口,能被克隆.

  • Java 中模仿源码自定义ArrayList

    Java 中模仿源码自定义ArrayList 最近看了下ArrayList的源码,抽空根据ArrayList的底层结构写了一个功能简单无泛型的自定义ArrayLsit,帮助自己更好理解ArrayList:,其实现的底层数据结构为数Object组,代码如下: /** * 自己实现一个ArrayList * */ public class MyArrayList { private Object[] elementData; private int size; public int size(){

  • Java集合删除元素ArrayList实例详解

    Java集合删除元素ArrayList实例详解

    Java集合删除元素ArrayList实例详解 AbstractCollection集合类中有一个remove方法,该方法为了适配多种不同的集合,允许删除空的元素,看这部分代码的时候产生了疑问,为什么这里直接用it.remove()就直接删除了? public boolean remove(Object o) { Iterator<E> it = iterator(); if (o==null) { while (it.hasNext()) { if (it.next()==null) { i

  • Java中ArrayList去除重复元素（包括字符串和自定义对象）

    1.去除重复字符串 package com.online.msym; import java.util.ArrayList; import java.util.Iterator; @SuppressWarnings({ "rawtypes", "unchecked" }) public class Demo1_ArrayList { public static void main(String[] args) { ArrayList list = new Array

  • 对arraylist中元素进行排序实例代码

    rrayList中的元素进行排序,主要考查的是对util包中的Comparator接口和Collections类的使用. 实现Comparator接口必须实现compare方法,自己可以去看API帮助文档. 创建一个Comparator实例后,用Collections.sort(List,<E>)对List中的元素进行排序. 下面是实现代码: 以下文件必须引入util包: package com.test; import Java.util.*; Emp.java文件如下: class Emp

  • Java中ArrayList的removeAll方法详解

    Java中ArrayList的removeAll方法详解

    本文介绍的是关于Java中ArrayList的removeAll方法的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍: 在开发过程中,遇到一个情况,就是从所有骑手Id中过滤没有标签的骑手Id(直接查询没有标签的骑手不容易实现), List<Integer> allRiderIdList = new ArrayList(); // 所有的骑手,大致有23W数据 List<Integer> hasAnyTagRiderId = new ArrayList(); // 有标签

  • java 中迭代器的使用方法详解

    java 中迭代器的使用方法详解 前言: 迭代器模式将一个集合给封装起来,主要是为用户提供了一种遍历其内部元素的方式.迭代器模式有两个优点:①提供给用户一个遍历的方式,而没有暴露其内部实现细节:②把元素之间游走的责任交给迭代器,而不是聚合对象,实现了用户与聚合对象之间的解耦. 迭代器模式主要是通过Iterator接口来管理一个聚合对象的,而用户使用的时候只需要拿到一个Iterator类型的对象即可完成对该聚合对象的遍历.这里的聚合对象一般是指ArrayList,LinkedList和底层实现为数

  • Java实现ArrayList排序的方法详解

    目录 简介 法1:JDK8的stream 法2:Comparator#compare() 法3:Comparable#compareTo() 简介 说明 本文用示例介绍Java的ArrayList排序的方法. List排序方法 主要有三种方法(按推荐度排序): JDK8的stream Comparator#compare() Comparable#compareTo() 法1:JDK8的stream 见:一文详解Java中Stream流的使用 法2:Comparator#compare() 需求

  • java 中enum的使用方法详解

    java 中enum的使用方法详解 enum 的全称为 enumeration, 是 JDK 1.5 中引入的新特性,存放在 java.lang 包中. 下面是我在使用 enum 过程中的一些经验和总结. 原始的接口定义常量 public interface IConstants { String MON = "Mon"; String TUE = "Tue"; String WED = "Wed"; String THU = "Thu

  • Java中的== 和equals()方法详解与实例

    Java中的== 和equals()方法: Java中的数据类型,可分为两类: 1.基本数据类型,也称原始数据类型. byte,short,char,int,long,float,double,boolean,他们之间的比较,应用双等号(==),比较的是他们的值. 2.引用数据类型(类) 当它们用(==)进行比较的时候,比较的是他们在内存中的存放地址,所以,除非是同一个new出来的对象,他们的比较后的结果为true,否则比较后结果为false. Java当中所有的类都是继承于Object这个基类

  • java中set接口使用方法详解

    java中的set接口有如下的特点: 不允许出现重复元素: 集合中的元素位置无顺序: 有且只有一个值为null的元素. 因为java中的set接口模仿了数学上的set抽象,所以,对应的数学上set的特性为: 互异性:一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次. 无序性:一个集合中,每个元素的地位都是相同的,元素之间是无序的.集合上可以定义序关系,定义了序关系后,元素之间就可以按照序关系排序.但就集合本身的特性而言,元素之间没有必然的序. 空集的性质:空集是一切集合的子集 S

  • Java中终止线程的方法详解

    Java中终止线程的方式主要有三种: 1.使用stop()方法,已被弃用.原因是:stop()是立即终止,会导致一些数据被到处理一部分就会被终止,而用户并不知道哪些数据被处理,哪些没有被处理,产生了不完整的"残疾"数据,不符合完整性,所以被废弃.So, forget it! 2.使用volatile标志位 看一个简单的例子: 首先,实现一个Runnable接口,在其中定义volatile标志位,在run()方法中使用标志位控制程序运行 public class MyRunnable i

  • Java中常用加密/解密方法详解

    安全问题已经成为一个越来越重要的问题,在Java中如何对重要数据进行加密解密是本文的主要内容. 一.常用的加密/解密算法 1.Base64 严格来说Base64并不是一种加密/解密算法,而是一种编码方式.Base64不生成密钥,通过Base64编码后的密文就可以直接"翻译"为明文,但是可以通过向明文中添加混淆字符来达到加密的效果. 2.DES DES是一种基于56位密钥的对称算法,1976年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),随后在国际上广泛流传开来.现在DE

  • java中封装的实现方法详解

    1.封装是什么?以及为什么要进行封装? 通常情况下可以给成员变量赋值一些合法但不合理的数值,这种情况在编译阶段和运行阶段都不会报错或给出任何的提示信息,此数值虽然合法但与现实生活不符:为了避免上述问题的发生,就需要对成员变量进行密封包装处理来保证该成员变量的合法合理性,这种机制就叫做封装.封装可以被认为是一个保护屏障,防止该类的代码和数据被外部类定义的代码随机访问.要访问该类的代码和数据,必须通过严格的接口控制. 2.如何进行封装? (1)私有化成员变量,使用private关键字修饰: (2)提

随机推荐