arraylist 订阅
ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处 展开全文
ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处
信息
属    性
动态数组
外文名
arraylist
位于API文档
java.util.ArrayList
中文名
Array的复杂版本
实现了
ICollection和IList接口
arraylist定义
List接口的大小可变数组的实现,位于API文档的java.util.ArrayList。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector类,除了此类是不同步的。) [1]  size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行,也就是说,添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行(大体上讲)。与用于 LinkedList实现的常数因子相比,此实现的常数因子较低。每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须 保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:List list = Collections.synchronizedList(new ArrayList(...));此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的 remove 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测 bug。
收起全文
精华内容
下载资源
问答
  • Arraylist

    千次阅读 多人点赞 2019-12-04 21:54:45
    ArrayList: 特点: 有序、不唯一 数据结构: Object数组 ArrayList:包装类 作用一:ArrayList是基于Object[]实现的,所以该只能装引用数据类型,基本数据类型要想装进集合,需要将基本数据类型进行类的包装。 ...

    集合

    List接口: 有序的、不唯一

    ArrayList:

    特点: 有序、不唯一

    数据结构: Object数组

    ArrayList:包装类

    作用一:ArrayList是基于Object[]实现的,所以该只能装引用数据类型,基本数据类型要想装进集合,需要将基本数据类型进行类的包装。
    
    作用二:包装类中有将String类型转换为对应的基本数据类型的方法。
    

    ArrayList的基本用法和特点

    特点:
        有序的:按照添加的顺序
        不唯一:同一个元素可以装多次
    1:如何创建泛型对象
    ArrayList<泛型> list=new ArrayList<>();
    
    2:如何添加元素:
    一次添加一个元素:
    list.add(元素);
    一次添加多个元素:
    Collections.addAll(集合,元素,元素,...);
    3:得到集合元素的个数
    list.size();
    4:得到某一个元素
    list.get(下标);
    5:如何判断集合里面是否出现指定元素
    list.contains();
    6:遍历
    for+下标
    for(int x=0;x<list.size();x++){
        //x->下标
        //list.get(元素);
    }
    foreache
    for(集合的泛型 x :list){
        //x->元素
    }
    迭代器********(重点)
    for(得到迭代器对象;判断迭代器上面是否还有下一个元素;){
    				取出下一个元素
    			  }
    
    for(Iterator<泛型>car=list.iterator();car.hasNext;){
        car.next();->元素
    }
    
    

    ArrayList 如何删除元素:

    list.remove(int 下标);
    下标指向谁就删除谁,如果下标不存在就抛出异常。
    清空集合:list.clear();
    list.remove(元素->参照物);
    指定元素进行删除
    *:一个remove只能删除一个对象。
    
    

    ArrayList

    1:ArrayList类里面的remove(元素)的方法
    		底层需要尊重equals比较机制
    
    		当我们想要删除一个元素的时候 底层拿着这个元素
    		和集合里面的每一个元素做equals比较
    
    2:谁主张谁举证
    		要被删除的对象会主动调用他自己类的equals方法
    		和集合里面的每一个元素做比较 
    
    3:当我们使用迭代器遍历集合的过程中 不允许对集合
    		的整体进行添加、删除操作 否则出发CME异常
    
    		如果想要在遍历的过程中进行删除
    		只能使用迭代器的删除方法:car.remove();
    
    4:构造方法:
    		ArrayList list = new ArrayList(int 数组空间大小);
    		ArrayList list = new ArrayList();//数组默认开辟10块空间
    
    		集合会自动扩容:
    			jdk6.0及之前	x * 3 / 2 + 1
    							10 -> 16 -> 25....
    
    			jdk7.0及之后	x + (x >> 1)
    							10 -> 15 -> 22....
    
    		在项目开发的时候 尽量避免扩容:
    			1:创建一个更大的新的数组对象
    			2:将老数组里面的元素复制到新数组里面
    			3:改变引用指向
    			4:回收老数组对象
    			5:继续添加元素
    
    		扩容:list.ensureCapacity(数组空间)
    		缩容:list.trimToSize()
    
    *****
    Vector语法和ArrayList一模一样的
    *********************
    面试题:
    ArrayList和Vector之间的区别?
    1:同步特性不同
    Vector同一时间允许一个线程进行访问,效率较低,但是不会发生并发错误。
    ArrayList同一时间允许多个线程进行访问,效率高,但是可能会发生并发错误。
    ***********************
    jdk5.0开始 集合的工具类[Collections]里面提供一个方法synchronizedList
    	   可以将线程不安全的ArrayList集合变成线程安全的集合对象
    	   于是Vector渐渐被淘汰了
    2:扩容不同
    ArrayList:分版本
    		jdk6.0及之前	x * 3 / 2 + 1
    		jdk7.0及之后	x + (x >> 1)
    
    Vector:分构造方法
    		Vector(10) -> 2倍扩容	10 -》 20 -》 40...
    		Vector(10,3) -> 定长扩容 10 -》 13 -》 16...
    
    3:出现的版本不同
    	  Vector:since jdk1.0
    	  ArrayList:since jdk1.2
     **************************************
     LinkedList语法和ArrayList一模一样
    	面试题: 
        ArrayList和LinkedList之间的区别?
         ArrayList和LinkedList底层数据结构不同 导致优劣势不同 
         ArrayList:底层是基于数组实现的
        优点:随机访问 遍历查找效率高
        缺点:添加删除元素的时候效率低
         LinkedList:底层是基于链表实现的
    
         优点:添加删除元素的时候效率高。
         缺点:随机访问 遍历查找效率低[从下标0开始找起]
    **************************
    Stack: 用数组模拟栈结构
    
    

    代码1

    import java.util.*;
    public class Daycare{
       public static void main(String[] args){
    	   //ArrayList  Collections.addAll(集合,元素,....)
    	   //创建一个集合对象装名字
    	   ArrayList<String> list=new ArrayList<>();
    	   //一次添加一个元素的方式:添加:Andy   Lee
    	   Collections.addAll(list,"Andy","Lee");
    	   //统计集合里面有几个人的姓名
    	   System.out.println("人的个数:"+list.size());
    	   //打印第一个人的姓名
    	   System.out.println("第一个人的名字:"+list.get(0));
    	   //判断集合里面是否出现Lee的名字
    	   System.out.println(list.contains("Lee"));
    	   //使用两种不同的方式打印 所有以A开头的名字
    	   for(String name:list){
    		   if(name.charAt(0)=='A'){
    			   System.out.println(name);
    			   }
    		   }
           for(String name:list){
    		   if(name.startsWith("A")){
    			   System.out.println(name);
    			   }
    		   }
          //用迭代器
          for(Iterator<String> car=list.iterator();car.hasNext();){
    		  String name=car.next();
    		  if(name.startsWith("A")){
    			  System.out.println(name);
    			  }
    
    		  }
    	   }
    }
    

    代码2

    import java.util.*;
    public class Daycare{
       public static void main(String[] args){
    	   //老筐 里面装的水果 有些重复的
    	   ArrayList<Integer> list=new ArrayList<>();
    	   Collections.addAll(list,56,77,77,90,56,28);
    	   ArrayList<Integer>list1=new ArrayList<>();
    	   //将重复元素去除
    	   for(Integer i:list){
    		   if(!(list1.contains(i))){
    		       list1.add(i);
    		   }
    		 }
    		System.out.println(list1);
    	   }
    }
    

    代码3

    import java.util.*;
    public class Daycare{
       public static void main(String[] args){
    	  ArrayList<Teacher> list = new ArrayList<>();
    	  Teacher t1 = new Teacher("周老师",30,5000.0);
    	  Teacher t2 = new Teacher("王老师",22,5500);
    	  Teacher t3 = new Teacher("周老师",22,5500.0);
    	  Teacher t4 = new Teacher("周老师",30,5500);
    	  //要求将t1 t2 t3三个老师装进集合里面
    	  Collections.addAll(list,t1,t2,t3);
    	  //要求删除t4
    	  //删除t4的操作 将集合里面的t3删掉
    	  list.remove(t4);
    	  System.out.println(list);
      }
    
    }
    class Teacher{
    	String name;
    	int age;
    	double salary;
    	public Teacher(String name,int age,double salary){
    			this.name = name;
    			this.age = age;
    			this.salary = salary;
    	}
    @Override
    public String toString(){
    	return name+" "+age+" "+salary;
    	}
    @Override
    public boolean equals(Object obj){
    	if(obj==null)return false;
    	if(!(obj instanceof Teacher) )return false;
    	if(obj==this)return true;
    	return this.name.equals(((Teacher)obj).name)&&this.salary==((Teacher)obj).salary;
    	}
    }
    

    代码4

    import java.util.*;
    public class Daycare{
       public static void main(String[] args){
    	 ArrayList<Food> list = new ArrayList<>();
    	 Food f1 = new Food("凉拌黃瓜",18,"凉菜");
    	 Food f2 = new Food("皮蛋豆腐",22,"凉菜");
    	 Food f3 = new Food("辣椒炒肉",28,"热菜");
    	 Food f4 = new Food("凉拌海带",19,"凉菜");
    	 Food f5 = new Food("小鸡炖蘑菇",45,"热菜");
    	// Food f6 = new Food("小鸡炖蘑菇",45,"l菜");
         //将所有的菜全部装进集合里面
         Collections.addAll(list,f1,f2,f3,f4,f5);
         //由于天气太冷了 删除集合里面的第三道凉菜
         int count=0;
         for(Iterator<Food> car=list.iterator();car.hasNext();){
    		 Food f=car.next();
    		 if(f.type.equals("凉菜")){
    			 count++;
    			 /**
    			 if(count==3){
    				 car.remove();
    				 }
    			 */
    			 }
    	     if(count==3){
    			 car.remove();
    			 break;
    			 }
    		 }
    
         //最终打印集合对象 显示
    	 //[凉拌黄瓜:凉菜,皮蛋豆腐:凉菜,辣椒炒肉:热菜,小鸡炖蘑菇:热菜]
    
       }
    }
    class Food{
    	String name;
    	double price;
    	String type;
    	public Food(String name,double price,String type){
    		this.name=name;
    		this.price=price;
    		this.type=type;
    		}
    	}
    

    代码5

    
    import java.util.*;
    public class Daycare{
       public static void main(String[] args){
    	String str = "张三:66 李四:82 王五:59 张三丰:77";
    	//将班级总分算出来
    	int sum=0;
    	String[]str1=str.split(" ");
    	for(String x:str1){
    		String[]str2=x.split(":");
    		int a=Integer.parseInt(str2[1]);
    		sum+=a;
    		}
    	System.out.println(sum);
    	//统计有几个人的成绩 > 平均分
    	int count=0;
    	for(String x:str1){
    			String[]str2=x.split(":");
    			int a=Integer.parseInt(str2[1]);
    			if(a>(sum/str.length())){
    				count++;
    				}
    		}
    		System.out.println(count+"个");
    		//打印最高分和他的名字
    		int max=0;
    		String name=" ";
    		for(String x:str1){
    		  String[]str2=x.split(":");
    		  int a=Integer.parseInt(str2[1]);
    		  if(a>max){
    			 max=a;
    			 name=x;
    			  }
    		}
    		System.out.println("姓名:"+name+"分数:"+max);
       }
    }
    
    
    

    代码6

    import java.util.*;
    public class Exec68{
    	public static void main(String[] args){
    	ArrayList<String> list=new ArrayList<>();
    	list.add("天王盖地虎[45]少盐");
    	list.add("斩青龙[18]多放蒜");
    	list.add("辣椒炒肉[23]不放肉");
    	list.add("西红柿鸡蛋汤[20]放两个鸡蛋");
    	list.add("米饭[2]8");
    	//向厨师展示信息:
    	//菜名字 :菜要求
    	//由于今天西红柿断货 所有和西红柿有关的菜全部删除
    	//由于出门钱带的不多 删除价格>30的菜
    	//计算这顿饭花费多少钱
    	for(String str:list){
    		int a=str.indexOf("[");
    		int b=str.indexOf("]");
    		String str1=str.substring(0,a);
    		String str2=str.substring(b+1);
    		String str3=str1+" "+str2;
    		System.out.println(str3);
    		}
        for(Iterator<String> car=list.iterator();car.hasNext();){
    		 String a=car.next();
    		 if(a.contains("西红柿")){
    			 car.remove();
    			 }
    		 }
    		 System.out.println(list);
        for(Iterator<String> car=list.iterator();car.hasNext();){
    		String g=car.next();
    		int s=g.indexOf("[");
    		int d=g.indexOf("]");
    		String str5=g.substring(s+1,d);
    		int a=Integer.parseInt(str5);
    		if(a>30){
    			car.remove();
    			}
    		}
         System.out.println(list);
         int sum=0;
        for(Iterator<String> car=list.iterator();car.hasNext();){
    		String h=car.next();
    		int q=h.indexOf("[");
    	    int w=h.indexOf("]");
    		String str5=h.substring(q+1,w);
    		int e=Integer.parseInt(str5);
    		if(e==2){
    			e=2*8;
    			}
    		sum+=e;
    		}
    		System.out.println("一共花了"+sum);
    	}
    }
    
    展开全文
  • ArrayList

    千次阅读 2019-09-10 19:34:24
    ArrayList 一、ArrayList简介 1.1ArrayList概述 ArrayList是可以动态增长和缩减的索引序列,它是基于数组实现的List类 封装了一个动态再分配的Object[] 数组 /** * Default initial capacity. *一个类对象都有一个...

    ArrayList

    一、ArrayList简介

    1.1ArrayList概述

    ArrayList是可以动态增长和缩减的索引序列,它是基于数组实现的List类

    封装了一个动态再分配的Object[] 数组

    /**
    * Default initial capacity.
    *一个类对象都有一个capacity属性,表示它们所封装的Object[]数组的长度,当向ArrayList中添加元素时,该属性值会自动增加。
    */
    private static final int DEFAULT_CAPACITY = 10;
    

    如果想ArrayList中添加大量元素,可使用ensureCapacity方法一次性增加capcacity,可以减少增加重分配的次数提高性能 。

    /**
         * Default initial capacity.
         *
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    
    /**
         * Increases the capacity of this <tt>ArrayList</tt> instance, if
         * necessary, to ensure that it can hold at least the number of elements
         * specified by the minimum capacity argument.
         *
         * @param   minCapacity   the desired minimum capacity
         */
        public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;//这里的值为10
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
    

    ArrayList的用法和Vector的区别是:ArrayList是线程不安全的,当多条线程访问同一个ArrayList集合时,程序需要手动保证该集合的同步性,而Vector则是线程安全的。

    ArrayList和Collection的关系

    在这里插入图片描述

    1.2 ArrayList的数据结构

    分析一个类的时候,数据结构往往是它的灵魂所在,理解底层的数据结构其实就理解了该类的实现思路。

    具体的实现细节再具体分析。

    ArrayList的数据结构是:
    在这里插入图片描述

    底层的数据结构就是数组,数组元素类型为Object类型,即可以存放所有类型数据

    我们对ArrayList类的实例的所有的操作底层都是基于数组的。

    二、ArrayList源码分析

    2.1继承结构和层次关系

    这里先说一下怎么使用idea查看类的继承结构图:Navigate -> Type Hierarchy

    在这里插入图片描述
    在这里插入图片描述

    可以看到:

    ArrayList extends AbstractList

    AbstractList extends AbstractCollection

    所有类都继承Object 所以ArrayList的继承结构就是上图所示。

    分析:

    1)为什么要先继承AbstractList,而让AbstractList先实现List? 而不是让ArrayList直接实现List?

    这里是有一个思想,**接口中全部是抽象的方法,而抽象类中可以有抽象方法,还可以有具体的实现方法,**正是利用了这一点,让AbstractList是实现接口中一些通用的方法,而具体的类,如ArrayList就继承这个AbstractList类,拿到一些通用的方法,然后自己在实现一些自己特有的方法,这样一来,让代码更简洁,就继承结构最底层的类中通用的方法都抽取出来,先一起实现了,减少重复代码。

    所以一般看到一个类上面还有一个抽象类,应该就是这个作用。

    2)ArrayList实现了哪些接口?

    • List接口:我们会出现这样一个疑问,在查看了ArrayList的父类AbstractList也实现了List接口,那为什么子类ArrayList还是去实现一遍呢?

      这其实是一个mistake,因为他写这代码的时候觉得这个会有用处,但是其实并没什么用,但因为没什么影响,就一直留到了现在。

    • RandomAccess接口:这个是一个标记性接口,通过查看api文档,它的作用就是**用来快速随机存取,有关效率的问题,在实现了该接口的话,那么使用普通的for循环来遍历,性能更高,**例如arrayList。而没有实现该接口的话,使用Iterator来迭代,这样性能更高,例如linkedList。所以这个标记性只是为了让我们知道用什么样的方式去获取数据性能更好。

    • Cloneable接口:实现了该接口,就可以使用Object.Clone()方法了。

    • Serializable接口:实现该**序列化接口,表明该类可以被序列化。**什么是序列化?简单的说,就是能够从类变成字节流传输,然后还能从字节流变成原来的类。

    2.2 类中的属性

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
    	// 版本号
        private static final long serialVersionUID = 8683452581122892189L;
    
        // 缺省容量
        private static final int DEFAULT_CAPACITY = 10;
    
        // 空对象数组
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        // 缺省空对象数组
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        // 元素数组
        transient Object[] elementData; // non-private to simplify nested class access
    
        // 实际元素大小, 默认为0
        private int size;
        
        // 最大数组容量
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    }
    

    2.3 构造方法

    ArrayList有三个构造方法:

    在这里插入图片描述

    1)无参构造方法

    /**
         * Constructs an empty list with an initial capacity of ten.这里就说明了默认会给10的大小,所以说一开始arrayList的容量是10
         */
    	//ArrayList中存储数据的其实就是一个数组,这个数组就是elementData,也就是之前的 private transient Object[] elementData;
        public ArrayList() {
            //调用父类中的无参构造方法,父类中的是个空的构造方法
            super();
            //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是个空的Object[],将elementData初始化,elementData也是个Object[]类型,空的Object[]会给默认大小10,之后解释什么时候赋值
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    

    2)有参构造函数

        /**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
        public ArrayList(int initialCapacity) {
            // 父类中空的构造方法
            super();
            //判断自定义大小的容量情况,>0正常创建,=0直接赋值EMPT_ELEMENTDATA,<0抛出异常
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    

    3)有参构造方法(不常用)

    	//这个构造方法不常用,举个例子就能明白什么意思
    	/*
    		Student extends Person
    		ArrayList<Person>、Person这里就是泛型
    		还有一个Collection<Student>、由于这个Student继承了Person,那么根据下面这个构造方法,就可以把这个Collection<Student>转换为ArrayList<Student>
    		这就是这个构造方法的作用
    	*/
        public ArrayList(Collection<? extends E> c) {
            //转换为数组,并且赋值给elementData元素数组
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                //每个集合的toarray()的实现方法不一样,所以需要判断一下,如果不是Object[].class类型
                //如果不是Object[].class类型,那么就需要使用ArrayList中的方法去改造一下
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // 如果没有一个元素,将空的数组EMPTY_ELEMENTDATA赋值给elementData
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    
    

    总结:arrayList的构造方法就做一件事情,就是初始化一下储存数据的容器,其实本质上就是一个数组,在其中就叫elementData

    2.4 核心方法

    2.4.1 add()方法(4个)

    在这里插入图片描述

    1)boolean add(E); //默认直接在末尾添加元素

       /**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            //确定内部容量是否够了,size是数组中数据的个数,因为要添加一个元素,所以size+1
            //先判断size+1的这个数 数组能否放得下,就在这个方法中去判断是否数组.length够用了
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //在数据中正确的位置上放上元素e,并且size++
            elementData[size++] = e;
            return true;
        }
    

    分析:

    ensureCapacityInternal(xxx);确定内部容量的方法

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        //判断初始化的elementData是不是空的数组,也即没有长度
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
            //如果是空的话,minCapacity=size+1;其实就是等于1,空的数组没有长度就存放不了,所以就将minCapacity变成10,也就是默认大小,但是到这来们还没有真正的初始化这个elementData的大小
            return Math.max(DEFAULT_CAPACITY, minCapacity);    
        }    
        return minCapacity;    
    }
    
    /**
    *确认实际的容量,上面只是将minCapacity=10,这个方法就是真正的判断elementData是否够用
    */
    private void ensureExplicitCapacity(int minCapacity) {    
        modCount++;    
        
        // overflow-conscious code    
        //minCapacity如果大于了实际elementData的长度,那么就说明elementData数组的长度不够用,不够用那么就要增加elementData的length。
        if (minCapacity - elementData.length > 0)        
            //arrayList能自动扩展大小的关键方法就在这里了
            grow(minCapacity);
    }
    

    grow(xxx);arrayList核心的方法,能扩展数组大小的真正秘密

    
        private void grow(int minCapacity) {
            // overflow-conscious code
            //将扩充前的elementData大小给oldCapacity
            int oldCapacity = elementData.length;
            //newCapacity就是1.5倍的oldCapacity,因为向右移1位代表除以2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                //这句话就是适应elementData空数组的时候,length=0,那么oldCapacity=0,newCapacity=0,所以这个判断成立,在这里就是真正的初始化elementData的大小了,前面的工作都是准备工作。
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                //如果newCapacity超过了最大的容量的限制,就调用hugeCapacity,也就是能给的最大值给newCapacity
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            //新的容量大小已经确定好了,就copy数组,改变容量大小
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    

    hugeCapacity();

    /**
    *很简单,就是用来赋最大值
    */
    private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
        //如果minCapacity都大于MAX_ARRAY_SIZE,那么就Integer.MAX_VALUE返回。因为maxCapacity是三倍的minCapacity,可能扩充的太大了,就用minCapacit来判断了。
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
    

    2.4.2 删除方法

    其实这几个删除方法都是类似的。我们选择几个讲,其中fastRemove(int)方法是private的,是提供给remove(Object)这个方法用。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    1)remove(int n): 通过删除指定位置上的元素

      public E remove(int index) {
            // 检查index的合理性
            rangeCheck(index);
    		
            // 这个作用很多,比如用来检测快速失败的一种标志
            modCount++;
            //通过索引直接找到该元素
            E oldValue = elementData(index);
    		
            // 计算要移动的位数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                // 用来移动元素的
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            // 将--size上的位置赋值为null,让gc(垃圾回收机制)更快的回收它
            elementData[--size] = null; // clear to let GC do its work
    		// 返回删除的元素
            return oldValue;
        }
    

    2)remove(Object):这个方法可以看出来,arrayList是可以存放null值的

    //通过元素来删除该元素,就依次遍历,如果有这个元素,就将该元素的索引传给fastRemove(index),使用这个方法来删除该元素
    //fastRemove(index)方法的内部跟remove(index)的实现几乎一样,这里最主要是知道arrayList可以存储null值
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
    1. clear():将elementData中每个元素都赋值为null,等待垃圾回收将这个给回收掉,所以叫clear
    
        public void clear() {
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }
    

    4)removeAll(Collection<?> c)

    
        public boolean removeAll(Collection<?> c) {
            //如果C为空,抛出空指针异常
            Objects.requireNonNull(c);
            // 批量删除
            return batchRemove(c, false);
        }
    

    5)batchRemove(Collection<?> c, boolean complement):用于两个方法

    • removeAll():它只清楚指定集合中的元素,当complement为false
    • retainAll():用来测试两个集合是否有交集,当complement为true
    /**
    *这个方法用于两处地方:
    *如果complement为false:用于removeAll()
    *如果complement为true :用于retainAll():这个方法是用来检测两个集合是否有交集的。
    */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        	// 将原集合,记名为A
            final Object[] elementData = this.elementData;
        	// r用来控制循环,w是记录有多少个交集
            int r = 0, w = 0;
            boolean modified = false;
            try {
                for (; r < size; r++)
                    //参数中的集合C一次检测集合A中的元素是否有
                    if (c.contains(elementData[r]) == complement)
                        // 有的话,就给集合A
                        elementData[w++] = elementData[r];
            } finally {
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                //如果contains方法使用过程报异常
                if (r != size) {
                    // 将剩下的元素都赋值给集合A
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {
                    // 这里有两个用途,在removeAll()时,w一直为0,就直接跟clear一样,全是null
                    // retainAll():没有一个交集返回true,有交集但不全交也返回true,有两个集合相等的时候,返回false,所以不能根据返回值来确认两个集合是否有交集,而是通过原集合的大小是否发生改变来判断,如果原集合中还有元素,则代表有交集,而元集合没有元素了,说明两个集合没有交集。
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }
    

    总结:remove函数用户移除指定下标的元素,此时会指定下标到数组末尾的元素向前移动一个单位。,并且会把数组最后一个元素设置为null,这样是为了方便之后将整个数组不被使用时,会被GC,可以作为小的技巧使用。

    2.4.3 set()方法

    	public E set(int index, E element) {
            // 检验索引是否合法
            rangeCheck(index);
    		// 旧值
            E oldValue = elementData(index);
            // 赋新值
            elementData[index] = element;
            // 返回旧值
            return oldValue;
        }
    

    说明:设定指定下标索引的元素值

    2.4.4 indexOf()方法

    	// 从首开始查找数组里面是否存在指定元素
    	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;
        }
    

    说明:从头开始查找与指定元素相等的元素,注意,是可以查找null元素的,意味着ArrayList中可以存放null元素的。与此函数对应的lastIndexOf,表示从尾部开始查找。

    2.4.5 get()方法

    
        public E get(int index) {
            // 检验索引是否合法
            rangeCheck(index);
    
            return elementData(index);
        }
    

    说明:get函数会检查索引值是否合法(只检查是否大于size,而没有检查是否小于0),值得注意的是,在get函数中存在element函数,element函数用于返回具体的元素,具体函数如下:

    	E elementData(int index) {
            return (E) elementData[index];
        }
    

    说明:返回的值经过了向下转型(Object -> E),这些是对我们应用程序屏蔽的小细节。

    三、总结

    • arrayList可以存放null
    • arrayList本质上就是一个elementData数组
    • arrayList区别于数组的地方在于能够自动扩展大小,其中关键的方法就是gorw()方法
    • arrayList中removeAll(Collection c)和clear()的区别就是removeAll可以删除批量指定的元素,而clear是全是删除集合中的元素
    • arrayList由于本质是数组,所以它在数据的查询方面会很快,而在插入删除这些方面,性能下降很多,有移动很多数据才能达到应有的效果
    • arrayList实现了RandomAccess,所以在遍历它的时候推荐使用for循环

    注明,参考 https://www.cnblogs.com/zhangyinhua/p/7687377.html

    展开全文
  • 我是真的没想到,面试官会这样问我ArrayList

    你知道的越多,你不知道的越多

    点赞再看,养成习惯

    本文 GitHub https://github.com/JavaFamily 已收录,有一线大厂面试点思维导图,也整理了很多我的文档,欢迎Star和完善,大家面试可以参照考点复习,希望我们一起有点东西。

    前言

    作为一个在互联网公司面一次拿一次Offer的面霸,打败了无数竞争对手,每次都只能看到无数落寞的身影失望的离开,略感愧疚(请允许我使用一下夸张的修辞手法)。

    于是在一个寂寞难耐的夜晚,我痛定思痛,决定开始写互联网技术栈面试相关的文章,希望能帮助各位读者以后面试势如破竹,对面试官进行360°的反击,吊打问你的面试官,让一同面试的同僚瞠目结舌,疯狂收割大厂Offer!

    所有文章的名字只是我的噱头,我们应该有一颗谦逊的心,所以希望大家怀着空杯心态好好学,一起进步。

    正文

    一个婀娜多姿,穿着衬衣的小姐姐,拿着一个精致的小笔记本,径直走过来坐在我的面前。

    看着眼前这个美丽的女人,心想这不会就是Java基础系列的面试官吧,真香。

    不过看样子这么年轻应该问不出什么深度的吧,嘻嘻。(哦?是么😏)

    帅丙,上次面试到现在都过去2个星期你才过来,为啥鸽了这么久?

    美丽迷人的面试官您好,因为之前得了流感,差点就没了,还有最近年底忙年会和年终review的事情,实在太忙了,不好意思。

    还做了一波导演(其实是打杂)去拍摄蘑菇街的年会视频了,实在忙到爆炸,周末也没能怼出文章哈哈。

    好吧那我理解了,下次这种情况记得提前跟我说,对了,多喝热水。

    面试官最后的多喝热水,直接触动我内心的防线,居然还有人这么关心我,帅丙的眼角,又湿了……

    ArrayList有用过吗?它是一个什么东西?可以用来干嘛?

    有用过,ArrayList就是数组列表,主要用来装载数据,当我们装载的是基本类型的数据int,long,boolean,short,byte…的时候我们只能存储他们对应的包装类,它的主要底层实现是数组Object[] elementData。

    与它类似的是LinkedList,和LinkedList相比,它的查找和访问元素的速度较快,但新增,删除的速度较慢。

    小结:ArrayList底层是用数组实现的存储。

    特点:查询效率高,增删效率低,线程不安全。使用频率很高。

    为啥线程 不安全还使用他呢?

    因为我们正常使用的场景中,都是用来查询,不会涉及太频繁的增删,如果涉及频繁的增删,可以使用LinkedList,如果你需要线程安全就使用Vector,这就是三者的区别了,实际开发过程中还是ArrayList使用最多的。

    不存在一个集合工具是查询效率又高,增删效率也高的,还线程安全的,至于为啥大家看代码就知道了,因为数据结构的特性就是优劣共存的,想找个平衡点很难,牺牲了性能,那就安全,牺牲了安全那就快速。

    Tip:这里还是强调下大家不要为了用而用,我记得我以前最开始工作就有这个毛病。就是不管三七二十一,就是为了用而用,别人用我也用,也不管他的性能啊,是否线程安全啥的,所幸最开始公司接触的,都是线下的系统,而且没啥并发。

    现在回想起来还有点后怕,而且我第一次出去面试就被一个算法的大佬给虐得体无完肤,其实他问的我都会用,但是就是说不上来为啥用,为啥这么做。

    回想起一年前的第一次面试,我又想到了那时候的点滴,那时候我身边还有女人,那时候我还有头发,那时候……我的眼角又湿了。

    您说它的底层实现是数组,但是数组的大小是定长的,如果我们不断的往里面添加数据的话,不会有问题吗?

    ArrayList可以通过构造方法在初始化的时候指定底层数组的大小。

    通过无参构造方法的方式ArrayList()初始化,则赋值底层数Object[] elementData为一个默认空数组Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}所以数组容量为0,只有真正对数据进行添加add时,才分配默认DEFAULT_CAPACITY = 10的初始容量。

    大家可以分别看下他的无参构造器和有参构造器,无参就是默认大小,有参会判断参数。

    数组的长度是有限制的,而ArrayList是可以存放任意数量对象,长度不受限制,那么他是怎么实现的呢?

    其实实现方式比较简单,他就是通过数组扩容的方式去实现的。

    就比如我们现在有一个长度为10的数组,现在我们要新增一个元素,发现已经满了,那ArrayList会怎么做呢?

    第一步他会重新定义一个长度为10+10/2的数组也就是新增一个长度为15的数组。

    然后把原数组的数据,原封不动的复制到新数组中,这个时候再把指向原数的地址换到新数组,ArrayList就这样完成了一次改头换面。

    Tip:很多小伙伴说,你举例干嘛用10这么长的数组举例,这样画都要多画一点格子了,帅丙我会做无意义的事情?因为我们在使用ArrayList的时候一般不会设置初始值的大小,那ArrayList默认的大小就刚好是10。

    然后你们也可以看到,他的构造方法,如果你传入了初始值大小,那就使用你传入的参数,如果没,那就使用默认的,一切都是有迹可循的。

    能具体说下1.7和1.8版本初始化的时候的区别么?

    arrayList1.7开始变化有点大,一个是初始化的时候,1.7以前会调用this(10)才是真正的容量为10,1.7即本身以后是默认走了空数组,只有第一次add的时候容量会变成10。

    ArrayList的默认数组大小为什么是10?

    其实我也没找到具体原因。

    据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研,结果就是10这个长度的数组是最常用的最有效率的。也有说就是随便起的一个数字,8个12个都没什么区别,只是因为10这个数组比较的圆满而已。

    我记得你说到了,他增删很慢,你能说一下ArrayList在增删的时候是怎么做的么?主要说一下他为啥慢。

    诶卧*,这个我想一下,大学看的有点忘记了,我想想。

    嗯嗯好的,我分别说一下他的新增的逻辑吧。

    他有指定index新增,也有直接新增的,在这之前他会有一步校验长度的判断ensureCapacityInternal,就是说如果长度不够,是需要扩容的。

    在扩容的时候,老版本的jdk和8以后的版本是有区别的,8之后的效率更高了,采用了位运算,右移一位,其实就是除以2这个操作。

    1.7的时候3/2+1 ,1.8直接就是3/2。

    指定位置新增的时候,在校验之后的操作很简单,就是数组的copy,大家可以看下代码。

    不知道大家看懂arraycopy的代码没有,我画个图解释下,你可能就明白一点:

    比如有下面这样一个数组我需要在index 5的位置去新增一个元素A

    那从代码里面我们可以看到,他复制了一个数组,是从index 5的位置开始的,然后把它放在了index 5+1的位置

    给我们要新增的元素腾出了位置,然后在index的位置放入元素A就完成了新增的操作了

    至于为啥说他效率低,我想我不说你也应该知道了,我这只是在一个这么小的List里面操作,要是我去一个几百几千几万大小的List新增一个元素,那就需要后面所有的元素都复制,然后如果再涉及到扩容啥的就更慢了不是嘛。

    我问你个真实的场景,这个问题很少人知道,你可要好好回答哟!

    ArrayList(int initialCapacity)会不会初始化数组大小?

    这是什么问题?卧槽问个ArrayList还能问到知识盲区?

    不要慌,我记得丙丙说过:无论我们遇到什么困难都不要害怕,战胜恐惧最好的办法就是面对他!!!奥利给!!!…

    会初始化数组大小!但是List的大小没有变,因为list的大小是返回size的。

    而且将构造函数与initialCapacity结合使用,然后使用set()会抛出异常,尽管该数组已创建,但是大小设置不正确。

    使用sureCapacity()也不起作用,因为它基于elementData数组而不是大小。

    还有其他副作用,这是因为带有sureCapacity()的静态DEFAULT_CAPACITY。

    进行此工作的唯一方法是在使用构造函数后,根据需要使用add()多次。

    大家可能有点懵,我直接操作一下代码,大家会发现我们虽然对ArrayList设置了初始大小,但是我们打印List大小的时候还是0,我们操作下标set值的时候也会报错,数组下标越界。

    其实数组是初始化了,但是List没,那size就没变,set下标是和size比较的那就报错了。

    再结合源码,大家仔细品读一下,这是Java Bug里面的一个经典问题了,还是很有意思的,大家平时可能也不会注意这个点。

    ArrayList插入删除一定慢么?

    取决于你删除的元素离数组末端有多远,ArrayList拿来作为堆栈来用还是挺合适的,push和pop操作完全不涉及数据移动操作。

    那他的删除怎么实现的呢?

    删除其实跟新增是一样的,不过叫是叫删除,但是在代码里面我们发现,他还是在copy一个数组。

    为啥是copy数组呢?

    继续打个比方,我们现在要删除下面这个数组中的index5这个位置

    那代码他就复制一个index5+1开始到最后的数组,然后把它放到index开始的位置

    index5的位置就成功被”删除“了其实就是被覆盖了,给了你被删除的感觉。

    同理他的效率也低,因为数组如果很大的话,一样需要复制和移动的位置就大了。

    ArrayList是线程安全的么?

    当然不是,线程安全版本的数组容器是Vector。

    Vector的实现很简单,就是把所有的方法统统加上synchronized就完事了。

    你也可以不使用Vector,用Collections.synchronizedList把一个普通ArrayList包装成一个线程安全版本的数组容器也可以,原理同Vector是一样的,就是给所有的方法套上一层synchronized。

    ArrayList用来做队列合适么?

    队列一般是FIFO(先入先出)的,如果用ArrayList做队列,就需要在数组尾部追加数据,数组头部删除数组,反过来也可以。

    但是无论如何总会有一个操作会涉及到数组的数据搬迁,这个是比较耗费性能的。

    结论:ArrayList不适合做队列。

    那数组适合用来做队列么?

    这个女人是魔鬼么?不过还是得微笑面对!

    数组是非常合适的。

    比如ArrayBlockingQueue内部实现就是一个环形队列,它是一个定长队列,内部是用一个定长数组来实现的。

    另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列,具体原理不做解释,比较复杂。

    简单点说就是使用两个偏移量来标记数组的读位置和写位置,如果超过长度就折回到数组开头,前提是它们是定长数组。

    ArrayList的遍历和LinkedList遍历性能比较如何?

    论遍历ArrayList要比LinkedList快得多,ArrayList遍历最大的优势在于内存的连续性,CPU的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销。

    能跟我聊一下LinkedList相关的东西么?

    可以呀,不然今天天色已晚,不然我们下次再聊?

    好吧,每次你都找借口,下次可以集合最后章节了,我们好好聊聊,你好好准备吧。

    总结

    ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处。

    面试里面问的时候没HashMap,ConcurrentHashMap啥的这么常问,但是也有一定概率问到的,还是那句话,不打没把握的仗

    我们在源码阅读过程中,不需要全部都读懂,需要做的就是读懂核心的源码,加深自己对概念的理解就好了,用的时候不至于啥都不知道,不要为了用而用就好了。

    ArrayList常用的方法总结

    • boolean add(E e)

    将指定的元素添加到此列表的尾部。

    • void add(int index, E element)

    将指定的元素插入此列表中的指定位置。

    • boolean addAll(Collection c)

    按照指定 collection 的迭代器所返回的元素顺序,将该 collection 中的所有元素添加到此列表的尾部。

    • boolean addAll(int index, Collection c)

    从指定的位置开始,将指定 collection 中的所有元素插入到此列表中。

    • void clear()

    移除此列表中的所有元素。

    • Object clone()

    返回此 ArrayList 实例的浅表副本。

    • boolean contains(Object o)

    如果此列表中包含指定的元素,则返回 true。

    • void ensureCapacity(int minCapacity)

    如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。

    • E get(int index)

    返回此列表中指定位置上的元素。

    • int indexOf(Object o)

    返回此列表中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1。

    • boolean isEmpty()

    如果此列表中没有元素,则返回 true

    • int lastIndexOf(Object o)

    返回此列表中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1。

    • E remove(int index)

    移除此列表中指定位置上的元素。

    • boolean remove(Object o)

    移除此列表中首次出现的指定元素(如果存在)。

    • protected void removeRange(int fromIndex, int toIndex)

    移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素。

    • E set(int index, E element)

    用指定的元素替代此列表中指定位置上的元素。

    • int size()

    返回此列表中的元素数。

    • Object[] toArray()

    按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组。

    • T[] toArray(T[] a)

    按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。

    • void trimToSize()

    将此 ArrayList 实例的容量调整为列表的当前大小。

    絮叨

    另外,敖丙把自己的面试文章整理成了一本电子书,共 1630页!目录如下

    现在免费送给大家,在我的公众号三太子敖丙回复 【888】 即可获取。

    我是敖丙,一个在互联网苟且偷生的程序员。

    你知道的越多,你不知道的越多人才们的 【三连】 就是丙丙创作的最大动力,我们下期见!

    注:如果本篇博客有任何错误和建议,欢迎人才们留言!


    文章持续更新,可以微信搜索「 三太子敖丙 」第一时间阅读,回复【资料】有我准备的一线大厂面试资料和简历模板,本文 GitHub https://github.com/JavaFamily 已经收录,有大厂面试完整考点,欢迎Star。

    展开全文
  • 深入理解ArrayList

    万次阅读 多人点赞 2019-11-21 10:31:52
    什么是ArrayListArrayList的实现原理其实就是数组(动态数组),ArrayList的介绍及简单使用方法 动态数组与一般数组有什么区别? 与Java中的数组相比,ArrayList的容量能动态地增长 ArrayList效率怎么样? ...

    什么是ArrayList?

    ArrayList的实现原理其实就是数组(动态数组),ArrayList的介绍及简单使用方法

    动态数组与一般数组有什么区别?

    与Java中的数组相比,ArrayList的容量能动态地增长

    ArrayList效率怎么样?

    ArrayList不是线程安全的,所以效率比较高 ,但是只能用于单线程的环境中,那多线程呢?别急,文末会讲到

    ArrayList主要继承哪些类实现了哪些接口?

    ArrayList主要继承了AbstractList类,实现了List、RandomAccess、Cloneable、Serializable接口

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    

    RandomAccess的意思是其拥有快速访问的能力,ArrayList可以以 O(1)[^1]的时间复杂度去根据下标访问元素。由于ArrayList底层结构是数组,所以它占据了一块连续的内存空间,其长度就是数组的大小,因此它也有数组的缺点,在空间效率不高,但是也有它的优点,就是查询速度快,时间效率较快

    ArrayList的常量与变量有哪些?

    // 序列ID
    private static final long serialVersionUID = 8683452581122892189L;
    
    // ArrayList默认的初始容量大小
    private static final int DEFAULT_CAPACITY = 10;
    
    // 空对象数组,用于空实例的共享空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    // 空对象数组,如果使用默认的构造函数创建,则默认对象内容是该值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    // 存放当前数据,不参与序列化
    transient Object[] elementData; // non-private to simplify nested class access
    
    // list大小
    private int size;
    

    当集合中的元素超出数组规定的长度时,数组就会进行扩容操作,扩容操作就是ArrayList存储操作缓慢的原因,尤其是当数据量较大的时候,每次扩容消耗的时间会越来越多

    ArrayList的构造方法有哪些?

    一、ArrayList(int initialCapacity)

    所以当我们要使用ArrayList时,可以 new ArrayList(大小)构造方法来指定集合的大小,以减少扩容的次数,提高写入效率,该构造函数的源码如下:

    // 自定义初始容量的构造方法
    public ArrayList(int initialCapacity) {
    
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 如果初始容量小于0,则会出现 IllegalArgumentException 异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    

    这个构造函数还是比较好理解的,因为涉及到的代码也不多,而且都是一些基础的代码,相信聪明的你肯定看得懂的

    二、ArrayList()

    这个就更简单了,只有两行代码

    // 默认的构造方法,构造一个初始容量为10的空列表
    public ArrayList() {
        // elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    三、ArrayList(Collection<? extends E> c)

    // 构造一个包含指定元素的列表集合,按集合的返回顺序迭代器
    // 传入参数为Collection对象
    // c要将其元素放入此列表的集合
    public ArrayList(Collection<? extends E> c) {
        
        // 调用toArray()方法将Collection对象转换为Object[]
        elementData = c.toArray();
        
        // 判断size的大小,如果size值为0,则会抛出NullPointerException异常
        // 如果size > 0 ,则执行以下代码
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                
                // 执行Arrays.copyOf,把Collection对象的内容copy到elementData中
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

    ArrayList的方法有哪些?

    add()

    单个add()
    // 添加单个元素,添加元素之前会先检查容量,如果容量不足则调用grow方法
    public boolean add(E e) {
        // 判断添加后的长度是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 然后在数组末尾添加当前元素,并且修改size的大小
        elementData[size++] = e;
        // 返回布尔值true
        return true;
    }
    

    add()方法中主要用到了一个新的方法——ensureCapacityInternal,来看下ensureCapacityInternal的源码:

    // 判断是否需要扩容
    private void ensureCapacityInternal(int minCapacity) {
        // 执行 calculateCapacity
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    

    而 ensureCapacityInternal 主要调用的是 ensureExplicitCapacity 方法和 calculateCapacity 方法,我们先看下calculateCapacity 方法

    // 判断是否是第一次初始化数组
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        // 判断当前数组是否等于空的数组
        // 注意:这里的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 并不是 EMPTY_ELEMENTDATA,不过并无太大差别,只是为了		       区分何时需要扩容而已
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            
            // 取其中最大的值作为判断本次是否需要扩容的依据,由于第一次数组是空的,所以默认要使数组扩容到10的长度
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    

    点击ensureCapacityInternal中的ensureExplicitCapacity,可以看到来到了 ensureExplicitCapacity 方法,而 ensureExplicitCapacity 主要调用的就是上面所说的 grow 方法,源码如下:

    // 判断扩容的方法
    private void ensureExplicitCapacity(int minCapacity) {
        
        // 如果需要扩容modCount自增,这个参数是指当前列表的结构被修改的次数
        modCount++;
    
        // overflow-conscious code
        // 判断当前数据量是否大于数组的长度,如果是,进行扩容
        if (minCapacity - elementData.length > 0)
            // 执行扩容操作
            grow(minCapacity);
    }
    

    grow方法源码如下:

    // grow扩容方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        // 记录扩容前的数组长度
        int oldCapacity = elementData.length;
        
        // 将原数组的长度扩大1.5倍作为扩容后数组的长度(如果扩容钱数组长度为10,那么经过扩容后的数组长度应该为15)
        // 这里涉及到异或运算,不懂的朋友可以看下这篇文章 https://blog.csdn.net/Woo_home/article/details/103146845
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        // 如果扩容后的长度小于当前的数据量
        if (newCapacity - minCapacity < 0)
            //那么就将当前的数据量的长度作为本次扩容的长度
            newCapacity = minCapacity;
        
        // 判断新数组的长度是否大于可分配数组的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 将扩容长度设置为最大可用长度
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // 拷贝,扩容,构建一个新的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

    grow方法调用的hugeCapacity源码如下:

    //如果新数组长度超过当前数组定义的最大长度时
    private static int hugeCapacity(int minCapacity) {
        
        // 抛出OOM异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        
        // 将扩容长度设置为Interger.MAX_VALUE,也就是int的最大长度
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
    }
    

    copyOf(T[] original, int newLength) 扩容方法

    public static <T> T[] copyOf(T[] original, int newLength) {
    	return (T[]) copyOf(original, newLength, original.getClass());
    }
    
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
    
    指定add()
    public void add(int index, E element) {
        //判断下标是否越界,如果是则抛出IndexOutOfBoundsException异常
        rangeCheckForAdd(index);
        
    	// 判断是否需要扩容,上面讲到过,这里不再解释
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        
        // 拷贝数组,将下标后面的元素全部向后移动一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        
        // 将元素插入到当前下标的位置
        elementData[index] = element;
        size++;
    }
    

    rangeCheckForAdd方法

    // 判断下标是否越界,如果是则抛出IndexOutOfBoundsException异常
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    添加多个元素addAll()
    // 添加多个元素
    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }
    
    // 添加多个元素到指定下标
    public boolean addAll(int index, Collection<? extends E> c) {
        
        // 判断下标是否越界,上面提到过
        rangeCheckForAdd(index);
        
        // 判断c的大小是否大于0
        int cSize = c.size();
        
        // 如果等于0 返回 false
        if (cSize==0)
            return false;
    
        checkForComodification();
        
        // 将元素插入到数组中
        parent.addAll(parentOffset + index, c);
        
        // 将修改次数赋值给 modCount
        this.modCount = parent.modCount;
        
        // size大小加一
        this.size += cSize;
        return true;
    }
    
    private void checkForComodification() {
        // 如果修改的次数不相等
        if (ArrayList.this.modCount != this.modCount)
            // 则抛出ConcurrentModificationException(并发修改)异常
            throw new ConcurrentModificationException();
    }
    

    总结:

    在进行 add 操作时先判断下标是否越界,是否需要扩容,如果需要扩容,就复制数组,然后设置对应的下标元素值

    扩容:默认扩容一半,如果扩容一半不够的话,就用目标的size作为扩容后的容量

    get()

    // 先判断下标索引
    public E get(int index) {
        // 调用rangeCheck判断是否超出了Object数组长度
        rangeCheck(index);
    
        // 调用 elementData 方法
        return elementData(index);
    }
    
    private void rangeCheck(int index) {
        // 如果超出了Object数组的长度
        if (index >= size)
            // 则抛出 IndexOutOfBoundsException(数组下标越界)异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    // 通过下标索引找到对应的元素值,返回指定元素
    E elementData(int index) {
        return (E) elementData[index];
    }
    

    set()

    public E set(int index, E element) {
        // 调用rangeCheck判断是否超出范围,上面讲到过,不懂的同学往上翻翻
        rangeCheck(index);
    
        // 返回指定元素,上面也讲到过
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    

    remove()

    // 删除元素
    public E remove(int index) {
        // 调用rangeCheck方法判断是否超出范围,上面讲到过
        rangeCheck(index);
        
        modCount++;
        // 位置访问操作
        E oldValue = elementData(index);
    
        // 计算移除元素后需要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 通过 System.arraycopy 方法将后面的元素往前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        
        // 最后一位赋值为null
        elementData[--size] = null; // clear to let GC do its work
    
        // 返回移除后元素的值
        return oldValue;
    }
    
    // 删除对象
    public boolean remove(Object o) {
        // 如果对象为null
        if (o == null) {
            // 遍历整个list去匹配移除的值
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    

    fastRemove源码如下:

    /**
      * 私有删除方法,跳过边界检查并且不返回删除的值。
      */
    private void fastRemove(int index) {
        modCount++;
        // 位置访问操作
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 通过 System.arraycopy 方法将后面的元素往前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
    

    Iterator

    // ArrayList中的迭代器
    public Iterator<E> iterator() {
        // 主要返回一个Itr类
        return new Itr();
    }
    

    Itr类源码如下:

    private class Itr implements Iterator<E> {
        int cursor;       // 下一个要返回的元素的索引
        int lastRet = -1; // 返回的最后一个元素的索引; -1(如果没有)
        int expectedModCount = modCount;
    
        Itr() {}
    
        // 判断是否还有下一个元素
        public boolean hasNext() {
            // 通过判断以下一个下标是否为数组大小,返回布尔值
            return cursor != size;
        }
    
        @SuppressWarnings("unchecked")
        // 获取下一个元素
        public E next() {
            // 调用checkForComodification方法检查修改的次数是否一致
            checkForComodification();
            
            // 定义下一个元素的下标
            int i = cursor;
            
            // 判断下标,如果下标大于ArrayList包含的元素个数
            if (i >= size)
                // 抛出 NoSuchElementException (没有这样的元素异常)异常
                throw new NoSuchElementException();
            
            // 定义elementData 为ArrayList的数组
            Object[] elementData = ArrayList.this.elementData;
            
            // 再次判断下标,如果此次判断不一致则说明数组被修改过
            if (i >= elementData.length)
                // 抛出 ConcurrentModificationException (并发修改)异常
                throw new ConcurrentModificationException();
            
            // 定义下一个元素的下标
            cursor = i + 1;
            
            // 将lastRet定义为下一个元素的下标(返回的最后一个元素的下标),然后返回下标对应的值
            return (E) elementData[lastRet = i];
        }
    
        // 移除当前元素
        public void remove() {
            // 如果没有元素
            if (lastRet < 0)
                // 则抛出 IllegalStateException 异常
                throw new IllegalStateException();
            // 又来了,调用 checkForComodification,上面讲到过,用于判断修改次数是否一致
            checkForComodification();
    
            try {
                // 调用ArrayList的remove方法
                //如果在遍历外remove会导致Itr中的expectedModCount没有修改则抛出异常
                ArrayList.this.remove(lastRet);
                
                // 定义下一个元素的下标为当前下标
                cursor = lastRet;
                
                // 定义上个遍历下标为-1
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
    
    final void checkForComodification() {
        // 判断当前Itr修改次数和ArrayList是否一致
        if (modCount != expectedModCount)
            // 不一致则抛出ConcurrentModificationException(并发修改异常)异常
            throw new ConcurrentModificationException();
    }
    

    ArrayList是线程安全的吗?

    不,ArrayList不是线程安全的,而且ArrayList允许元素为null

    ArrayList如何实现线程安全?

    上上面说过ArrayList不是线程安全的,所以效率较高,但是只能适用于单线程,那么多线程怎么办呢?, 多线程可以使用 Collections.synchronizedList(List list) 函数返回一个线程安全的 ArrayList 集合,或者使用 concurrent 并发包下的CopyOnWriteArrayList,如下:

    //使用Collections.synchronizedList(List list)方法实现线程安全
    List<?> list = Collections.synchronizedList(new ArrayList<>());
    

    关注我的公众号,一起进步
    在这里插入图片描述

    展开全文
  • 一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之ArrayList 一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之LinkedList 一文搞定ArrayList、LinkedList、HashMap、HashSet -----...
  • Java集合01_ArrayList、LinkedList 和 Vector

    万次阅读 2020-09-01 17:06:52
    Java集合 数组的优点: 元素连续分配空间,根据下标访问元素(随机访问效率高) ...ArrayList 底层数据结构是数组,查询快,增删慢,线程不安全,效率高 add()、size()、isEmpty() contains()、indexOf()、
  • ArrayList和LinkedList区别及使用场景

    万次阅读 多人点赞 2018-09-07 18:51:40
    ArrayList和LinkedList区别及使用场景 1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的,LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的...
  • 一般想知道List 与ArrayList 的区别可能大部分都是看到了 List list = new ArrayList(); 和 ArrayList arrayList = new ArrayList<>(); 想知道它们的区别? List 是一个接口,如果忘记点击List 跳转到源码里面看...
  • ArrayList嵌套ArrayList

    2017-05-12 16:08:50
    import java.util.ArrayList; import com.heima.bean.Person; /** * @author 作者 HouQiang: * @version 创建时间:2017年5月12日 下午4:00:27 * 类说明 */ public class Demo3_...
  • 深度剖析ArrayList

    万次阅读 2020-12-05 09:29:10
    ArrayList是集合的一种实现,实现了接口List,List接口继承了Collection接口。 ArrayList 是java 中最常用的集合类型,这是因为它使用起来非常简单,而且它提供了非常丰富的功能,并且性能非常好,这里需要注意的是...
  • ArrayList 源码

    千次阅读 2020-06-27 20:24:15
    ArrayList 源码 ArrayList概览 基本概念 ArrayList 的结构较为简单,就是一个数组。结构如下图所示。ArrayList中有一些重要概念、属性: index:当前下标 elementData:数组,该数组的大小,经常与 ArrayList 的...
  • ArrayList arrayList=new ArrayList(); arrayList.add(new ArrayList()); arrayList.add(new ArrayList()); 可以用 ArrayList x=(ArrayList)arrayList.get(0); x.get(1); 这样可以...
  • Java ArrayList

    千次阅读 2020-10-02 18:47:27
    Java 集合框架ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素。 ArrayList 继承了 AbstractList ,并实现了 List 接口。 ArrayList 类位于 java....
  • ArrayList扩容机制以及线程安全性

    万次阅读 2020-05-06 20:49:10
    ArrayList作为动态数组,其内部元素以数组形式顺序存储的,所以非常适合随机访问的场合。除了尾部插入和删除元素,往往性能会相对较差,比如我们在中间位置插入一个元素,需要移动后续所有元素。 源码分析 先把...
  • List list=new ArrayList()和ArrayList arrayList = new ArrayList()区别 初次学习,不对的请大家指教List是接口,ArrayList是List的实现类(ArrayList不是继承List接口,是实现了List接口)List是接口,它是不可以...
  • ArrayList al=null 和ArrayList al=new ArrayList()有什么区别
  • [Java] ArrayList

    万次阅读 多人点赞 2018-06-27 15:42:19
    java.util.ArrayList&amp;amp;amp;amp;amp;lt;E&amp;amp;amp;amp;amp;gt; 从书中各种代码来看,java.util.ArrayList&amp;amp;amp;amp;amp;lt;E&amp;amp;amp;amp;amp;gt; 是非常重要的一个类,在...
  • 集合嵌套之ArrayList嵌套ArrayList A:案例演示 集合嵌套之ArrayList嵌套ArrayList 案例: 我们学科,学科又分为若干班级 整个学科是一个大集合 若干个班级分为每一个小集合 package com.heima.jdk5; import ...
  • 这篇博客通过解析ArrayList 的底层源码,对ArrayList 进行深入的理解。
  • java底层原理---ArrayList源码分析

    万次阅读 2020-12-23 11:50:31
    java底层原理—ArrayList源码分析 引言 学习底层是为了更好的选择合适数据结构进行开发,这篇是为了讲解ArrayList底层原理的,同时也是总结一下自己的学习成果。 太多的文字让人看得眼花缭乱,废话不多说,上图解。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 186,289
精华内容 74,515
热门标签
关键字:

arraylist