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详解,看这篇就够了

    万次阅读 多人点赞 2018-02-26 22:38:45
    简介ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList,实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口...
    
    
    

    简介

    ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList,实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口,所以ArrayList 是支持快速访问、复制、序列化的。

    成员变量

    ArrayList 底层是基于数组来实现容量大小动态变化的。

    /**
    * The size of the ArrayList (the number of elements it contains).
    */
    private int size;  // 实际元素个数
    transient Object[] elementData; 

    注意:上面的 size 是指 elementData 中实际有多少个元素,而 elementData.length 为集合容量,表示最多可以容纳多少个元素。

    默认初始容量大小为 10;

    /**
    * Default initial capacity.
    */
    private static final int DEFAULT_CAPACITY = 10;

    这个变量是定义在 AbstractList 中的。记录对 List 操作的次数。主要使用是在 Iterator,是防止在迭代的过程中集合被修改。

    protected transient int modCount = 0;

    下面两个变量是用在构造函数里面的

    /**
    * 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 = {};

    两个空的数组有什么区别呢? We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. 简单来讲就是第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。

    构造函数

    无惨构造函数

    /**
    * Constructs an empty list with an initial capacity of ten.
    */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    注意:注释是说构造一个容量大小为 10 的空的 list 集合,但构造函数了只是给 elementData 赋值了一个空的数组,其实是在第一次添加元素时容量扩大至 10 的。

    构造一个初始容量大小为 initialCapacity 的 ArrayList

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
        }
    }

    由以上源码可见: 当使用无参构造函数时是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData。 当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData。 当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData。

    使用指定 Collection 来构造 ArrayList 的构造函数

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    将 Collection 转化为数组并赋值给 elementData,把 elementData 中元素的个数赋值给 size。 如果 size 不为零,则判断 elementData 的 class 类型是否为 Object[],不是的话则做一次转换。 如果 size 为零,则把 EMPTY_ELEMENTDATA 赋值给 elementData,相当于new ArrayList(0)。

    主要操作方法解析

    • add 操作
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    由此可见:每次添加元素到集合中时都会先确认下集合容量大小。然后将 size 自增 1。ensureCapacityInternal 函数中判断如果 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。这就是 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别所在。同时也验证了上面的说法:使用无惨构造函数时是在第一次添加元素时初始化容量为 10 的。ensureExplicitCapacity 中对 modCount 自增 1,记录操作次数,然后如果 minCapacity 大于 elementData 的长度,则对集合进行扩容。显然第一次添加元素时 elementData 的长度为零。那我们来看看 grow 函数。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

    很简单明了的一个函数,默认将扩容至原来容量的 1.5 倍。但是扩容之后也不一定适用,有可能太小,有可能太大。所以才会有下面两个 if 判断。如果1.5倍太小的话,则将我们所需的容量大小赋值给newCapacity,如果1.5倍太大或者我们需要的容量太大,那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容。然后将原数组中的数据复制到大小为 newCapacity 的新数组中,并将新数组赋值给 elementData。

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }
    
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
    
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
    
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
    
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    有以上源码可知,add(int index, E element),addAll(Collection

    public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }
    
    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;
    }
    
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

    当我们调用 remove(int index) 时,首先会检查 index 是否合法,然后再判断要删除的元素是否位于数组的最后一个位置。如果 index 不是最后一个,就再次调用 System.arraycopy() 方法拷贝数组。说白了就是将从 index + 1 开始向后所有的元素都向前挪一个位置。然后将数组的最后一个位置空,size - 1。如果 index 是最后一个元素那么就直接将数组的最后一个位置空,size - 1即可。 当我们调用 remove(Object o) 时,会把 o 分为是否为空来分别处理。然后对数组做遍历,找到第一个与 o 对应的下标 index,然后调用 fastRemove 方法,删除下标为 index 的元素。其实仔细观察 fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。

    • get操作
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

    由于 ArrayList 底层是基于数组实现的,所以获取元素就相当简单了,直接调用数组随机访问即可。
    迭代器 iterator

    有使用过集合的都知道,在用 for 遍历集合的时候是不可以对集合进行 remove操作的,因为 remove 操作会改变集合的大小。从而容易造成结果不准确甚至数组下标越界,更严重者还会抛出 ConcurrentModificationException。

    例子.png

    foreach 遍历等同于 iterator。为了搞清楚异常原因,我们还必须过一遍源码。

    public Iterator<E> iterator() {
        return new Itr();
    }

    原来是直接返回一个 Itr 对象。

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
    
        public boolean hasNext() {
            return cursor != size;
        }
    
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
    
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
    
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    从源码可以看出,ArrayList 定义了一个内部类 Itr 实现了 Iterator 接口。在 Itr 内部有三个成员变量。 cursor:代表下一个要访问的元素下标。 lastRet:代表上一个要访问的元素下标。 expectedModCount:代表对 ArrayList 修改次数的期望值,初始值为 modCount。

    下面看看 Itr 的三个主要函数。

    hasNext 实现比较简单,如果下一个元素的下标等于集合的大小 ,就证明到最后了。

    next 方法也不复杂,但很关键。首先判断 expectedModCountmodCount 是否相等。然后对 cursor 进行判断,看是否超过集合大小和数组长度。然后将 cursor 赋值给 lastRet ,并返回下标为 lastRet 的元素。最后将 cursor 自增 1。开始时,cursor = 0,lastRet = -1;每调用一次 next 方法, cursor 和 lastRet 都会自增 1。

    remove 方法首先会判断 lastRet 的值是否小于 0,然后在检查 expectedModCountmodCount 是否相等。接下来是关键,直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素。然后将 lastRet 赋值给 cursor ,将 lastRet 重新赋值为 -1,并将 modCount 重新赋值给 expectedModCount

    图一

    下面我们一步一步来分析 Itr 的操作。如图一所示,开始时 cursor 指向下标为 0 的元素,lastRet 指向下标为 -1 的元素,也就是 null。每调用一次 next,cursor 和lastRet 就分别会自增 1。当 next 返回 “C” 时,cursor 和 lastRet 分别为 3 和 2 [图二]。

    图二

    此时调用 remove,注意是 ArrayList 的 remove,而不是 Itr 的 remove。会将 D E 两个元素直接往前移动一位,最后一位置空,并且 modCount 会自增 1。从 remove 方法可以看出。[图三]。

    图三

    此时 cursor = 3,size = 4,没有到数组末尾,所以循环继续。来到 next 方法,因为上一步的 remove 方法对 modCount 做了修改 ,致使 expectedModCount 与 modCount 不相等,这就是 ConcurrentModificationException 异常的原因所在。从例子.png中也可以看出异常出自 ArrayList 中的内部类 Itr 中的 checkForComodification 方法。

    异常的解决:
    solve.png

    直接调用 iterator.remove() 即可。因为在该方法中增加了 expectedModCount = modCount 操作。但是这个 remove 方法也有弊端。

    1、只能进行remove操作,add、clear 等 Itr 中没有。
    2、调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
    3、next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1

    总结

    ArrayList 底层基于数组实现容量大小动态可变。 扩容机制为首先扩容为原始容量的 1.5 倍。如果1.5倍太小的话,则将我们所需的容量大小赋值给 newCapacity,如果1.5倍太大或者我们需要的容量太大,那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容。 扩容之后是通过数组的拷贝来确保元素的准确性的,所以尽可能减少扩容操作。 ArrayList 的最大存储能力:Integer.MAX_VALUE。 size 为集合中存储的元素的个数。elementData.length 为数组长度,表示最多可以存储多少个元素。 如果需要边遍历边 remove ,必须使用 iterator。且 remove 之前必须先 next,next 之后只能用一次 remove。

    转自:https://juejin.im/post/5a90c37af265da4e83267f8e

    这里写图片描述

    展开全文
  • 我是真的没想到,面试官会这样问我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。

    展开全文
  • List集合之ArrayList

    万次阅读 多人点赞 2018-06-24 11:43:19
    List集合之ArrayList深度解析 List集合之ArrayList深度解析 一、ArrayList解析 1.1、概览 1.1.1、java.io.Serializable接口的作用 1.1.2、讨论 RandomAccess 的作用。 1.1.3、 Cloneable接口的作用: 1.1.4、数组...

    List集合之ArrayList深度解析

    现在这篇主要讲List集合的三个子类:

    • ArrayList

      • 底层数据结构是数组。线程不安全
    • LinkedList

      • 底层数据结构是链表。线程不安全
    • Vector

      • 底层数据结构是数组。线程安全

    其中ArrayList和LinkedList都是用的非常多的

    一、ArrayList解析

    mark

    首先,我们来讲解的是ArrayList集合,它是我们用得非常非常多的一个集合~

    首先,我们来看一下ArrayList的属性:

    mark

    1.1、概览

    实现了 RandomAccess 接口,因此支持随机访问,这是理所当然的,因为 ArrayList 是基于数组实现的。

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

    1.1.1、java.io.Serializable接口的作用

    可以发现ArrayList实现了java.io.Serializable接口,该接口主要是在序列化的时候起作用,具体为什么需要序列化,请看我的文章对象序列化为何要定义serialVersionUID的来龙去脉

    实现的第一个接口RandomAccess的作用:RandomAccess 是 List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

    1.1.2、讨论 RandomAccess 的作用。

    如果 List 子类实现了 RandomAcce ss 接口,那表示它能快速随机访问存储的元素, 这时候你想到的可能是数组, 通过下标 index 访问, 实现了该接口的 ArrayList 底层实现就是数组, 同样是通过下标访问, 只是我们需要用 get() 方法的形式 , ArrayList 底层仍然是数组的访问形式。同时你应该想到链表, LinkedList 底层实现是链表, LinkedList 没有实现 RandomAccess 接口,发现这一点就是突破问题的关键点。数组支持随机访问, 查询速度快, 增删元素慢; 链表支持顺序访问, 查询速度慢, 增删元素快。所以对应的 ArrayList 查询速度快,LinkedList 查询速度慢, RandomAccess 这个标记接口就是标记能够随机访问元素的集合, 简单来说就是底层是数组实现的集合。

    为了提升性能,在遍历集合前,我们便可以通过 instanceof 做判断, 选择合适的集合遍历方式,当数据量很大时, 就能大大提升性能。

    随机访问列表使用循环遍历,顺序访问列表使用迭代器遍历。

    先看看 RandomAccess 的使用方式

    import java.util.*;
    public class RandomAccessTest {
        public static void traverse(List list){
    
            if (list instanceof RandomAccess){
                System.out.println("实现了RandomAccess接口,不使用迭代器");
    
                for (int i = 0;i < list.size();i++){
                    System.out.println(list.get(i));
                }
    
            }else{
                System.out.println("没实现RandomAccess接口,使用迭代器");
    
                Iterator it = list.iterator();
                while(it.hasNext()){
                    System.out.println(it.next());
                }
    
            }
        }
        public static void main(String[] args) {
            List<String> arrayList = new ArrayList<>();
            arrayList.add("a");
            arrayList.add("b");
            traverse(arrayList);
    
            List<String> linkedList = new LinkedList<>();
            linkedList.add("c");
            linkedList.add("d");
            traverse(linkedList);
        }
    }

    结论

    根据结果我们可以得出结论: ArrayList 使用 for 循环遍历优于迭代器,遍历 LinkedList 使用 迭代器遍历优于 for 循环遍历

    根据以上结论便可利用 RandomAccess 在遍历前进行判断,根据 List 的不同子类选择不同的遍历方式, 提升算法性能。

    1.1.3、 Cloneable接口的作用:

    它允许在堆中克隆出一块和原对象一样的对象,并将这个对象的地址赋予新的引用,这样显然我对新引用的操作,不会影响到原对象。

    Cloneable接口和Object的clone()方法

    Java中实现了Cloneable接口的类有很多,像我们熟悉的ArrayList、Calendar、Date、HashMap、Hashtable、HashSet、LinkedList等等。

    1、Cloneable接口

    (1)此类实现了Cloneable接口,以指示Object的clone()方法可以合法地对该类实例进行按字段复制

    (2)如果在没有实现Cloneable接口的实例上调用Object的clone()方法,则会导致抛出CloneNotSupporteddException

    (3)按照惯例,实现此接口的类应该使用公共方法重写Object的clone()方法,Object的clone()方法是一个受保护的方法

    2、Object的clone()方法

    创建并返回此对象的一个副本。对于任何对象x,表达式:

    (1)x.clone() != x为true(指向的是堆内存中的不同的区域)

    (2)x.clone().getClass() == x.getClass()为true(堆内存中的内容是相同的)

    (3)x.clone().equals(x)一般情况下为true,但这并不是必须要满足的要求

    浅克隆和深克隆

    浅克隆(shallow clone)和深克隆(deep clone)反映的是,当对象中还有对象的时候,那么:

    1、浅克隆,即很表层的克隆,如果我们要克隆对象,只克隆它自身以及它所包含的所有对象的引用地址

    2、深克隆,克隆除自身对象以外的所有对象,包括自身所包含的所有对象实例、

    那其实Object的clone()方法,提供的是一种浅克隆的机制,如果想要实现对对象的深克隆,在不引入第三方jar包的情况下,可以使用两种办法:

    1、先对对象进行序列化,紧接着马上反序列化出

    2、先调用super.clone()方法克隆出一个新对象来,然后在子类的clone()方法中手动给克隆出来的非基本数据类型(引用类型)赋值,比如ArrayList的clone()方法:

    public Object clone() {
    try {
        //1、第一句,浅拷贝出一个ArrayList,此时对象的引用地址还是原来的
        ArrayList<E> v = (ArrayList<E>) super.clone();
        //2、第二句,除了自身外,把Object[] elementData里面的对象全部拷贝一次,做了一次深拷贝(具体的原理需要深入的研究copyof方法的源码)
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
    }

    1.1.4、数组的默认大小

    private static final int DEFAULT_CAPACITY = 10;

    1.2、ArrayList的属性

    public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {  
        // 序列化id  
        private static final long serialVersionUID = 8683452581122892189L;  
        // 默认初始的容量  
        private static final int DEFAULT_CAPACITY = 10;  
        // 一个空对象(为什么是new Object[0]呢?)
        //用Object[0]来代替null 很多时候我们需要传递参数的类型,而不是传null,所以用Object[0]
        private static final Object[] EMPTY_ELEMENTDATA = new Object[0];  
        // 一个空对象,如果使用默认构造函数创建,则默认对象内容默认是该值  
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];  
        // 当前数据对象存放地方,当前对象不参与序列化(主要是关键字transient起作用的)  
        transient Object[] elementData;  
        // 当前数组长度  
        private int size;  
        // 数组最大长度  
        private static final int MAX_ARRAY_SIZE = 2147483639;  
    
        // 省略方法。。  
    }  

    关于属性中的 有几点需要说明的是:

    1:new Object[0]表示的意思:new Object[0]表示的是创建一个长度为0的Object类型的数组,也就是一个空的数组,为什么不用null表示的,因为很多的情况下,我们在使用的时候需要传入的是参数的类型,而不是传递的是null,所以使用的是new Object[0]

    2:EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA两者之间的区别:如果使用的是默认的构造函数创建的对象,则返回DEFAULTCAPACITY_EMPTY_ELEMENTDATA;如果是用户在指定容量的大小为0的时候返回的,则返回的是EMPTY_ELEMENTDATA

    1.3、ArrayList构造函数

    1.3.1、无参构造函数

    如果不传入参数,则使用默认无参构建方法创建ArrayList对象,如下:

    public ArrayList() {  
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }  

    注意:此时我们创建的ArrayList对象中的elementData中的长度是1,size是0,当进行第一次add的时候,elementData将会变成默认的长度:10.

    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  //确认内部容量
            elementData[size++] = e;
            return true;
        }
    
     private void ensureCapacityInternal(int minCapacity) {
            // 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //置默认大小 为DEFAULT_CAPACITY
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            //确定实际容量
            ensureExplicitCapacity(minCapacity);
        }
    
    
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // 如果超出了容量,进行扩展
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //右移运算符等价于除以2
            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);
        }
    
    上述代码块比较长,这里做个简单的总结:
    1、add(E e):添加元素,首先会判断 elementData 数组的长度,然后设置值
    2、ensureCapacityInternal(int minCapacity):判断 element 是否为空,如果是,则设置默认数组长度
    3、ensureExplicitCapacity(int minCapacity):判断预期增长数组长度是否超过当前容量,如果过超过,则调用grow()
    4、grow(int minCapacity):对数组进行扩展,默认的长度为10

    1.3.2、带int类型的构造函数

    如果传入参数,则代表指定ArrayList的初始数组长度,传入参数如果是大于等于0,则使用用户的参数初始化,如果用户传入的参数小于0,则抛出异常,构造方法如下:

    public ArrayList(int initialCapacity) {  
        if (initialCapacity > 0) {  
            this.elementData = new Object[initialCapacity];  
        } else if (initialCapacity == 0) {  
            this.elementData = EMPTY_ELEMENTDATA;  
        } else {  
            throw new IllegalArgumentException("Illegal Capacity: "+  
                                               initialCapacity);  
        }  
    } 

    注意在这里就可以看出来EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别,EMPTY_ELEMENTDATA是在带int类型的构造函数传入进来的int的数值为0的时候调用的。

    这里就有一个问题值得我们进行深入的思考,为什么这里当int 为0的时候创建的空的数组使用的是EMPTY_ELEMENTDATA而不使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    我自己的解答:DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的数组实例,和EMPTY_ELEMENTDATA空数组相比是用于了解添加元素时数组膨胀多少

    1.3.3、ArrayList(Collection c)

    Collection<T> c 中保存的数据,首先转换成数组形式(toArray()方法),然后判断当前数组长度是否为0,为 0 则只想默认数组(EMPTY_ELEMENTDATA);否则进行数据拷贝。

    public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

    可能有部分的人对于Arrays.copyof不是很了解,下面我把一段copyOf的源码拿出来,大概一看就能明白的:

    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) {  
        T[] copy = ((Object)newType == (Object)Object[].class)  
            ? (T[]) new Object[newLength]
            // 通过Java反射来处理数组需要用到java.lang.reflect.Array类。不要和Java集合中的java.util.Arrays类搞混淆了,数组类型可以通过getComponentType()获取的数组的class对象
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
        System.arraycopy(original, 0, copy, 0,  
                         Math.min(original.length, newLength));  
        return copy;  
    }  

    1.3.4 总结

    上述的三个构造方法可以看出,其实每个构造器内部做的事情都不一样,特别是默认构造器与 ArrayList(int initialCapacity) 这两个构造器直接的区别 ,我们是需要做一些区别的。

    • ArrayList():指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当列表使用的时候,才会进行初始化,会通过判断是不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个对象而设置数组默认大小。
    • ArrayList(int initialCapacity):当 initialCapacity >0 的时候,设置该长度。如果 initialCapacity =0,则指向 EMPTY_ELEMENTDATA 在使用的时候,并不会设置默认数组长度 。

    因此 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的本质区别就在于,会不会设置默认的数组长度。

    1.4、ArrayList的方法

    1.4.1、Add方法概览

    add方法可以说是ArrayList比较重要的方法了,我们来总览一下:

    ArrayList 添加了四种添加方法:

    • add(E element)
    • add(int i , E element)
    • addAll(Collection
       /**
         * 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) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

    我们再一次的来看看ensureCapacityInternal(size + 1)方法

     private void ensureCapacityInternal(int minCapacity) {
            // 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //置默认大小 为DEFAULT_CAPACITY
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            //确定实际容量
            ensureExplicitCapacity(minCapacity);
        }
    
    
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // 如果超出了容量,进行扩展
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //右移运算符等价于除以2,如果第一次是10,扩容之后的大小是15
            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);
        }

    结合默认构造器或其他构造器中,如果默认数组为空,则会在 ensureCapacityInternal()方法调用的时候进行数组初始化。这就是为什么默认构造器调用的时候,我们创建的是一个空数组,但是在注释里却介绍为 长度为10的数组。

    第二种就是已经存在元素了,当添加第11个元素的时候,minCapacity为11,此时的数组的长度为10,所以minCapacity - elementData.length > 0,需要进行扩容,int newCapacity = oldCapacity + (oldCapacity >> 1)如果第一次是10,扩容之后的大小是15,然后在再把之前的元素进行复制到新的数组中去 elementData = Arrays.copyOf(elementData, newCapacity);

    第一次扩容后,如果容量还是小于minCapacity(需要的最小的容量),就将容量扩充为minCapacity。

    #### 1.4.2、add(int index, E element)

    按照惯例还是先查看源码:

    public void add(int index, E element) {
        // 判断index 是否有效
            rangeCheckForAdd(index);
        // 计数+1,并确认当前数组长度是否足够
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index); //将index 后面的数据都往后移一位
            elementData[index] = element; //设置目标数据
            size++;
        }
    
    /**
     * A version of rangeCheck used by add and addAll.
     */
    private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    } 
    
    /**
      * Constructs an IndexOutOfBoundsException detail message.
      * Of the many possible refactorings of the error handling code,
      * this "outlining" performs best with both server and client VMs.
      */
        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+size;
    } 
    
    

    System提供了一个静态方法arraycopy(),System.arraycopy,JVM 提供的数组拷贝实现。这种方式为什么是非常的高效的我们可以参考文章《System.arraycopy为什么快》  我们可以使用它来实现数组之间的复制。其函数原型是:

    @HotSpotIntrinsicCandidate
    public static void (Object src,
                                 int srcPos,
                                 Object dest,
                                 int destPos,
                                 int length)
    src:源数组;     srcPos:源数组要复制的起始位置;
    dest:目的数组;  destPos:目的数组放置的起始位置;    length:复制的长度。
    注意:src and dest都必须是同类型或者可以进行转换类型的数组.

    @HotSpotIntrinsicCandidate这个注解是 HotSpot VM 标准的注解,被它标记的方法表明它为 HotSpot VM 的固有方法, HotSpot VM 会对其做一些增强处理以提高它的执行性能,比如可能手工编写汇编或手工编写编译器中间语言来替换该方法的实现。虽然这里被声明为 native 方法,但是它跟 JDK 中其他的本地方法实现地方不同,固有方法会在 JVM 内部实现,而其他的会在 JDK 库中实现。在调用方面,由于直接调用 JVM 内部实现,不走常规 JNI lookup,所以也省了开销。

    1.4.3 、addAll(Collection

    public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

    addAll() 方法,通过将collection 中的数据转换成 Array[] 然后添加到elementData 数组,从而完成整个集合数据的添加。在整体上没有什么特别之初,这里的collection 可能会抛出控制异常 NullPointerException 需要注意一下。

    #### 1.4.4、 addAll(int index,Collection

     public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
    
            int numMoved = size - index;
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                                 numMoved);
    
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
    }

    与上述方法相比,这里主要多了两个步骤,判断添加数据的位置是不是在末尾,如果在中间,则需要先将数据向后移动 collection 长度 的位置。

    #### 1.4.5、删除方法(Remove)

    ArrayList 中提供了 五种删除数据的方式:

    • remove(int i)
    • remove(E element)
    • removeRange(int start,int end)
    • clear()
    • removeAll(Collection c)

      1.4.6、remove(int i):

    删除数据并不会更改数组的长度,只会将数据从数组中移除,如果目标没有其他有效引用,则在GC 时会进行回收。

    国际惯例查看源码:

    public E remove(int index) {
            rangeCheck(index); // 判断索引是否有效
            modCount++;
            E oldValue = elementData(index);  // 获取对应数据
            int numMoved = size - index - 1;  // 判断删除数据位置
            if (numMoved > 0) //如果删除数据不是最后一位,则需要移动数组
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // 让指针最后指向空,进行垃圾回收
            return oldValue;
        }

    1.4.7、remove(E element):

    这种方式,会在内部进行 AccessRandom 方式遍历数组,当匹配到数据跟 Object 相等,则调用 fastRemove() 进行删除

    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;
        }
    

    fastRemove( ): fastRemove 操作与上述的根据下标进行删除其实是一致的。

     private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }

    1.4.8、removeRange(int fromIndex, int toIndex)

    该方法主要删除了在范围内的数据,通过System.arraycopy 对整部分的数据进行覆盖即可。

    protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
    
            // clear to let GC do its work
            int newSize = size - (toIndex-fromIndex);
            for (int i = newSize; i < size; i++) {
                elementData[i] = null;
            }
            size = newSize;
        }
    

    1.4.9、removeAll(Collection c)

     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++)
                    //根据 complement 进行判断删除或留下
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
                // 进行数据整理
                if (r != size) {
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {
                    // 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;
        }

    1.4.10、trimToSize()

    删除元素时不会减少容量,若希望减少容量则调用trimToSize()

    /**
         * Trims the capacity of this <tt>ArrayList</tt> instance to be the
         * list's current size.  An application can use this operation to minimize
         * the storage of an <tt>ArrayList</tt> instance.
         */
        public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

    1.4.11、toArray()

    ArrayList提供了2个toArray()函数:

    • Object[] toArray()
    • T[] toArray(T[] contents)

    调用 toArray() 函数会抛出“java.lang.ClassCastException”异常,但是调用 toArray(T[] contents) 能正常返回 T[]。

    toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组,将 Object[] 转换为其它类型(如如,将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常,因为Java不支持向下转型。

    toArray() 源码:

     public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
     }
    

    ### 1.5、ArrayList线程安全问题的研究

    先来回顾一下上面讲的ArrayList添加元素的操作:

    public boolean add(E e) {
    
        /**
         * 添加一个元素时,做了如下两步操作
         * 1.判断列表的capacity容量是否足够,是否需要扩容
         * 2.真正将元素放在列表的元素数组里面
         */
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    这样也就出现了第一个导致线程不安全的隐患,在多个线程进行add操作时可能会导致elementData数组越界。具体逻辑如下:

    1. 列表大小为9,即size=9
    2. 线程A开始进入add方法,这时它获取到size的值为9,调用ensureCapacityInternal方法进行容量判断。
    3. 线程B此时也进入add方法,它获取到size的值也为9,也开始调用ensureCapacityInternal方法。
    4. 线程A发现需求大小为10,而elementData的大小就为10,可以容纳。于是它不再扩容,返回。
    5. 线程B也发现需求大小为10,也可以容纳,返回。
    6. 线程A开始进行设置值操作, elementData[size++] = e 操作。此时size变为10。
    7. 线程B也开始进行设置值操作,它尝试设置elementData[10] = e,而elementData没有进行过扩容,它的下标最大为9。于是此时会报出一个数组越界的异常ArrayIndexOutOfBoundsException.

    另外第二步 elementData[size++] = e 设置值的操作同样会导致线程不安全。从这儿可以看出,这步操作也不是一个原子操作,它由如下两步操作构成:

    java
    elementData[size] = e;
    size = size + 1;

    1. 列表大小为0,即size=0
    2. 线程A开始添加一个元素,值为A。此时它执行第一条操作,将A放在了elementData下标为0的位置上。
    3. 接着线程B刚好也要开始添加一个值为B的元素,且走到了第一步操作。此时线程B获取到size的值依然为0,于是它将B也放在了elementData下标为0的位置上。
    4. 线程A开始将size的值增加为1
    5. 线程B开始将size的值增加为2

      这样线程AB执行完毕后,理想中情况为size为2,elementData下标0的位置为A,下标1的位置为B。而实际情况变成了size为2,elementData下标为0的位置变成了B,下标1的位置上什么都没有。并且后续除非使用set方法修改此位置的值,否则将一直为null,因为size为2,添加元素时会从下标为2的位置上开始。

    下面是一个简单的事例来说明这个问题:

    public static void main(String[] args) throws InterruptedException {
        final List<Integer> list = new ArrayList<Integer>();
    
        // 线程A将0-1000添加到list
        new Thread(new Runnable() {
            public void run() {
                for (int i = 0; i < 1000 ; i++) {
                    list.add(i);
    
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    
        // 线程B将1000-2000添加到列表
        new Thread(new Runnable() {
            public void run() {
                for (int i = 1000; i < 2000 ; i++) {
                    list.add(i);
    
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    
        Thread.sleep(1000);
    
        // 打印所有结果
        for (int i = 0; i < list.size(); i++) {
            System.out.println("第" + (i + 1) + "个元素为:" + list.get(i));
        }
    }

    部分的结果:

    7个元素为:38个元素为:10039个元素为:410个元素为:100411个元素为:null12个元素为:100513个元素为:6

    1.6、ConcurrentModificationException

    1.6.1、异常出现的原因

    Vector、ArrayList在迭代的时候如果同时对其进行修改就会抛出java.util.ConcurrentModificationException异常。下面我们就来讨论以下这个异常出现的原因以及解决办法。

    先看一段代码:

    public class test {
        public static void main(String[] args)  {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(2);
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                Integer integer = iterator.next();
                if(integer==2)
                    list.remove(integer);
            }
        }
    }

    mark

    从异常信息可以发现,异常出现在checkForComodification()方法中。

      我们先不看checkForComodification()方法的具体实现,我们先根据程序的代码一步一步看ArrayList源码的实现:

      首先看ArrayList的iterator()方法的具体实现,查看源码发现在ArrayList的源码中并没有iterator()这个方法,那么很显然这个方法应该是其父类或者实现的接口中的方法,我们在其父类AbstractList中找到了iterator()方法的具体实现,下面是其实现代码:

      public Iterator<E> iterator() {
            return new Itr();
    }

    从这段代码可以看出返回的是一个指向Itr类型对象的引用,我们接着看Itr的具体实现,在AbstractList类中找到了Itr类的具体实现,它是AbstractList的一个成员内部类,下面这段代码是Itr类的所有实现:

    private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;//表示下一个要访问的元素的索引
    
        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;//表示上一个访问的元素的索引
        int expectedModCount = modCount; //表示对ArrayList修改次数的期望值,它的初始值为modCount。
        public boolean hasNext() {
               return cursor != size();
        }
        public E next() {
               checkForComodification();
            try {
            E next = get(cursor);
            lastRet = cursor++;
            return next;
            } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
            }
        }
        public void remove() {
            if (lastRet == -1)
            throw new IllegalStateException();
               checkForComodification();
    
            try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
            }
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        }
    }

      这里是非常关键的地方:首先在next()方法中会调用checkForComodification()方法,然后根据cursor的值获取到元素,接着将cursor的值赋给lastRet,并对cursor的值进行加1操作。初始时,cursor为0,lastRet为-1,那么调用一次之后,cursor的值为1,lastRet的值为0。注意此时,modCount为0,expectedModCount也为0。

      接着往下看,程序中判断当前元素的值是否为2,若为2,则调用list.remove()方法来删除该元素。

      我们回顾一下在ArrayList中的remove()方法做了什么:

    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;
    }
    
    
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null; // Let gc do its work
    }

      在fastRemove()方法中,首先对modCount进行加1操作(因为对集合修改了一次),然后接下来就是删除元素的操作,最后将size进行减1操作,并将引用置为null以方便垃圾收集器进行回收工作

      那么注意此时各个变量的值:对于iterator,其expectedModCount为0,cursor的值为1,lastRet的值为0。

      对于list,其modCount为1,size为0;

    ​ 接着看程序代码,执行完删除操作后,继续while循环,调用hasNext方法()判断,由于此时cursor为1,而size为0, 那么返回true,所以继续执行while循环,然后继续调用iterator的next()方法:

      注意,此时要注意next()方法中的第一句:checkForComodification()。

      在checkForComodification方法中进行的操作是:

    final void checkForComodification() {
        if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }

    如果modCount不等于expectedModCount,则抛出ConcurrentModificationException异常。

      很显然,此时modCount为1,而expectedModCount为0,因此程序就抛出了ConcurrentModificationException异常。

    到这里,想必大家应该明白为何上述代码会抛出ConcurrentModificationException异常了。

    关键点就在于:调用list.remove()方法导致modCount和expectedModCount的值不一致。

    注意,像使用for-each进行迭代实际上也会出现这种问题

    1.6.2、单线程环境下的解决的办法

    既然知道原因了,那么如何解决呢?

    其实很简单,细心的朋友可能发现在Itr类中也给出了一个remove()方法:

    public void remove() {
        if (lastRet == -1)
        throw new IllegalStateException();
           checkForComodification();
    
        try {
        AbstractList.this.remove(lastRet);
        if (lastRet < cursor)
            cursor--;
        lastRet = -1;
        expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
        throw new ConcurrentModificationException();
        }
    }

    在这个方法中,删除元素实际上调用的就是list.remove()方法,但是它多了一个操作:

    expectedModCount = modCount;

    因此,在迭代器中如果要删除元素的话,需要调用Itr类的remove方法。

    将上述代码改为下面这样就不会报错了:

    public class Test {
        public static void main(String[] args)  {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(2);
            Iterator<Integer> iterator = list.iterator();
            while(iterator.hasNext()){
                Integer integer = iterator.next();
                if(integer==2)
                    iterator.remove();   //注意这个地方
            }
        }
    }

    1.6.2、多线程环境下的解决的办法

    面的解决办法在单线程环境下适用,但是在多线程下适用吗?看下面一个例子:

    public class Test {
        static ArrayList<Integer> list = new ArrayList<Integer>();
        public static void main(String[] args)  {
            list.add(1);
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            Thread thread1 = new Thread(){
                public void run() {
                    Iterator<Integer> iterator = list.iterator();
                    while(iterator.hasNext()){
                        Integer integer = iterator.next();
                        System.out.println(integer);
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                };
            };
            Thread thread2 = new Thread(){
                public void run() {
                    Iterator<Integer> iterator = list.iterator();
                    while(iterator.hasNext()){
                        Integer integer = iterator.next();
                        if(integer==2)
                            iterator.remove(); 
                    }
                };
            };
            thread1.start();
            thread2.start();
        }
    }

    有可能有朋友说ArrayList是非线程安全的容器,换成Vector就没问题了,实际上换成Vector还是会出现这种错误。

    mark

     原因在于,虽然Vector的方法采用了synchronized进行了同步,但是实际上通过Iterator访问的情况下,每个线程里面返回的是不同的iterator,也即是说expectedModCount是每个线程私有。假若此时有2个线程,线程1在进行遍历,线程2在进行修改,那么很有可能导致线程2修改后导致Vector中的modCount自增了,线程2的expectedModCount也自增了,但是线程1的expectedModCount没有自增,此时线程1遍历时就会出现expectedModCount不等于modCount的情况了。

    因此一般有2种解决办法:

      1)在使用iterator迭代的时候使用synchronized或者Lock进行同步;

      2)使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。

    如果向对多线程并发容器的了解的请自行进行查阅!

    后言

    看了源码才发现源码真的理解需要深厚的基础知识的,弄很多东西都顺手拈来,也是看了源码才知道一个类有哪些地方需要注意,甚至是有哪些地方可以优化,而不是一个API工程师

    参考文献

    Cloneable接口和Object的clone()方法
    RandomAccess 这个空架子有何用?
    Java 集合系列1、细思极恐之ArrayList
    Java ConcurrentModificationException异常原因和解决方法

    展开全文
  • java中Array和ArrayList区别

    万次阅读 2018-09-16 10:14:29
    java中Array和ArrayList区别 1)精辟阐述: 可以将 ArrayList想象成一种“会自动扩增容量的Array”。 2)Array([]):最高效;但是其容量固定且无法动态改变;  ArrayList: 容量可动态增长;但牺牲效率; 3)...
  • 用大白话告诉你ArrayList的底层原理

    万次阅读 多人点赞 2018-08-18 20:13:28
    一、ArrayList的数据结构 ArrayList的底层数据结构就是一个数组,数组元素的类型为Object类型,对ArrayList的所有操作底层都是基于数组的。 二、ArrayList的线程安全性 对ArrayList进行添加元素的操作的时候是...
  • ArrayList

    2020-02-13 15:00:56
    import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; public class Test { /** * @param args */ public static void ma...
  • ArrayList详解

    2018-08-31 11:11:40
    ArrayList是一个动态数组,也是我们常用的集合,它允许任何元素的插入,甚至包括null。每一个ArrayList都有一个初始化的容量(10),该容量代表了数组的大小,随着容器中容量的不断增加,容器的大小也会随着增加。在...
  • ArrayList

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

    万次阅读 多人点赞 2016-03-11 10:20:59
    ArrayList是Java集合框架中的一个重要的类,它继承于AbstractList,实现了List接口,是一个长度可变的集合,提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了RandomAccess接口,可以对元素进行...
  • ArrayList

    千次阅读 2017-08-27 02:06:27
    ArrayList ArrayList底层是维护了一个Object数组实现 的,使用无参构造函数时,Object数组默认的容量是10,当长度不够时,自动增长0.5倍。 ArrayList 非特有的方法即List接口的方法,具体代码示例可参考上一篇博客...
  • 今天在看别人的代码的时候,发现有 Yyy uu=new Xxx(){ public void aaa(){ //这里写代码。。。 } } 这种形式,以前偶尔看见过,也知道是匿名内部类的情况,但一直没有仔细去研究,今天特意花点时间去写了点很简单也...
  • [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初始默认容量(长度)

    万次阅读 多人点赞 2016-09-26 23:29:06
    每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知...
  • 深入理解ArrayList

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

    千次阅读 2010-08-08 22:31:00
    创建一个ArrayList 可以使用ArrayList类提供的三个构造器之一实例化一个ArrayList对象。 1、最简单的形式是无参数构造器: ArrayList courseTaken= new ArrayList(); 该构造器创建一个内容的、缺省容量为16个...
  • ArrayList和LinkedList区别及使用场景

    万次阅读 多人点赞 2018-09-07 18:51:40
    ArrayList和LinkedList区别及使用场景 1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的,LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的...
  • ArrayList是一个很常用的集合类,底层是一个数组,只不过ArrayList封装了数组,实现了一些好用的方法例如add()方法,size()方法,get()方法等一系列的方法,并且实现了动态的扩容数组。 new ArrayList();创建了一个...
  • ArrayList详解

    2014-09-12 15:34:35
    1、什么是ArrayList ArrayList就是传说中的动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了如下一些好处: 动态的增加和减少元素 实现了ICollection和IList接口 灵活的设置数组的大小 2、如何使用...
  • 简述ArrayList、Vector与LinkedList的异同点  Collection类的继承图如下:   从图中可以看出,LinkedList与ArrayList、ArrayDeque这三者都实现了List接口.所有使用方式也很相似,主要区别在于因为实现方式的不同,...

空空如也

1 2 3 4 5 ... 20
收藏数 974,127
精华内容 389,650
关键字:

arraylist