集合
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
一、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;
    }


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

  
你知道的越多，你不知道的越多
  
点赞再看，养成习惯
  
本文 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、LinkedList、HashMap、HashSet -----源码解读之ArrayList

一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之LinkedList

一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之HashMap

一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之HashSet 
关于HashMap的源码是这样定义的

其中的Cloneable和Serializable接口在前面的 ArrayList源码解读有讲解
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 

HashMap继承了AbstractMap并实现Map接口

HashMap的内容比较多，方便更好的解读源代码，先对HashMap进行内部结构的简化

请先看我另一篇文章对HashMap的注释和简化，方便记忆
文章传送 ==》简化HashMap
在JDK1.2源码的数据结构
jdk1.2中HashMap底层是链表+数组

真正存储数据的结构如下
private transient Entry table[];//数组

private static class Entry implements Map.Entry {
	int hash;		// key的hash值
	Object key;		// 键
	Object value;	// 值
	Entry next;		// 下一个节点

	Entry(int hash, Object key, Object value, Entry next) {
	    this.hash = hash;
	    this.key = key;
	    this.value = value;
	    this.next = next;
	}
}

早期的HashMap用链表结构解决索引值相同以及hash冲突来存储相同索引但value不同的数据，之所以设计成链表+数组的原因是将数据存的更紧凑，节省内存空间，并且方便扩容。
put方法的逻辑流程图

更详细的源码解读看这篇：简化HashMap源码结构