一、ArrayList集合底层数据结构

1.ArrayList集合介绍

List集合的可调整大小数组实现。

2.数组结构介绍

• 增删快：每次增加删除元素，都需要更改数组长度、拷贝以及移除元素位置。
• 查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

二、ArrayList继承关系

首先我们来看一下ArrayList的继承关系图，如下：

由上图可知，ArrayList分别实现了RandomAccess、List、Cloneable、Serializable四个接口，那么我们分别来看一下他们分别的作用吧

2.1 Serializable标记性接口

介绍： 类的序列化由实现java.io.Serializable接口的类启动。不实现此接口的类将不会使任何状态序列化或反序列化。可序列化类的所有子类都是可序列化的。序列化接口没有方法和字段，仅用于标识可串行化的语义。

序列化：将对象的数据写入到文件（写对象）

反序列化：将文件中对象的数据读取出来（读对象）

2.2Cloneable标记性接口

介绍：一个类实现Cloneable接口来指示Object.clone（）方法，该方法对于该类的实列进行字段的复制是合法的。在不实现Cloneable接口的实例上调用对象的克隆方法会导致异常CloneNotSupportedException被抛出。简言之：克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝

克隆的前提条件

• 被克隆对象所在的类必须实现Cloneable接口
• 必须重写clone方法

2.3RandomAccess标记接口

1.介绍标记接口由list实现使用，以表明他们支持快速（通常为恒定时间）随机访问。

此接口的主要目的是允许算法更改其行为，以便在应用与随机访问列表或顺序访问列表时提供良好的性能。

用于操纵随机访问列表的最佳算法可以在应用与顺序访问列表时产生二次行为（如LinkedList）。鼓励通用列表算法在应用如果将其应用于顺序访问列表之前提供交差性能的算法时，检查给定义列表是否为instanceof，并且必要时更改其行为以保证可接受的性能。

人们认识到，随机访问和顺序访问之间的区别通常是模糊的。例如，一些LIst实现提供渐进的线性访问时间，如果它们在实践中获得巨大但是恒定的访问时间。这样的一个List实现通常应该实现这个接口。根据经验，List应实现此接口，如果对于类的经典实列，次循环；

for(int i = 0,n = list.size() ; i < n ; i++)
            list.get(i);

比这个循环运行得更快；

for（Iterator i = list.iterator;i.hasllext();)
            i.next();

2.4AbstractList抽象类

三、ArrayList源码分析

3.1构造方法

从上图可以看见，ArrayList是有三个构造方法（一个无参，俩个有参）

Constructor	Constructor描述
ArrayList()	构造一个初始容量为10的空容器
ArrayList(int initialCapacity)	构造具有指定初始容量的空列表
ArrayList(Collection<? extends E> c)	构造一个包含指定集合的元素的列表，按照他们由集合的迭代器返回的顺序

3.2 案例演示

案例一：

1.空参构造ArrayList（）

public static void main(String[] args){
    //new一个ArrayList真的可以构造一个初始容量为10的空列表吗？
    ArrayList<String> list = new ArrayList<String>();
}

那我们就来看看源码是怎么走的吧！

//首先空参构造
public ArrayList() {
    //赋值
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    //这个时候可以看出来在赋值
    //那么我们就去查看俩个属性
}

//看完以后发现是一个空容量的数组，长度为0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//集合真正存储数据的容器
transient Object[] elementData;

2.ArrayList(int initialCapacity)

public static void main(String[] args){
    //这行代码ArrayList底层做了什么
    ArrayList<String> list = new ArrayList<String>(5);
}

3.ArrayList(Collection<? extends E> c)

 //ArrayList(Collection<? extends E> c)构造一个包含指定集合的元素列表，按照他们由集合的迭代器返回的顺序
        ArrayList<String> list = new ArrayList<String>(5);
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");

        //这行代码做了什么
        ArrayList<String> list1 = new ArrayList<>(list);

        for (String s : list1) {
            System.out.println(s);
        }

由于这个源码比较复杂，所以将源码拷贝过来并且进行解释

    public ArrayList(Collection<? extends E> c) {
        //首先将list集合转换为数组，使用的是父接口Collection的方法
        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 {
            // 如果长度为0，就把空数组的地址赋值给集合存元素的数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3.3add添加方法

方法名	描述
public boolean add(E e)	将指定的元素添加到此列表的尾部。
public void add(int index, E element)	将指定的元素插入此列表中的指定位置。
public boolean addAll(Collection<? extends E> c)	按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。
public boolean addAll(int index, Collection<? extends E> c)	从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

• public boolean add(E e)添加单个元素

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("悦悦");
    }

如果俩个数组相等，则返回容量最大的那个

ArrayList初始默认的值是10

如果minCapacity参数大于数组长度，则进行扩容

注意：这里进行右移（>>）右移几位相当于除以2的几次幂；左移几位相当于乘以2的几次幂；
扩容的核心算法：原容量的1.5倍

进行判断赋值给一个新的数组容量

• public void add(int index, E element)在指定的索引上添加元素

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("悦悦");
        list.add("123");
        list.add("456");
        list.add(1,"789");
        System.out.println(list);
    }

首先判断索引是否大于集合的长度或者索引是否小于0，如果为true则会抛出一个异常，返回；

后面的逻辑就和添加单个元素是一样的

当ensureCapacityInternal方法走完以后，调用拷贝方法

• public boolean addAll(Collection<? extends E> c)将集合中的所有元素一次性添加到集合中

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("悦悦");
        list.add("123");
        list.add("456");
        ArrayList<String> list1 = new ArrayList<>();
        list1.addAll(list);
        System.out.println(list);
        System.out.println(list1);
    }

首先将有数据的集合转换为数组

再将有数据的数组长度赋值给numNew变量

再创建一个新的数组

将有数据的数组进行拷贝到新的数组

给新数组从新定义长度

• public boolean addAll(int index, Collection<? extends E> c)将指定集合中的所有元素插入到此列表中，从指定的位置开始。

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("悦悦");
        list.add("123");
        list.add("456");
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("大胖子");
        list1.add("想变帅");
        list1.addAll(1,list);
        System.out.println(list);
        System.out.println(list1);
    }

首先进行校验索引

将有参数的集合（数据源）转换为数组

记录数据源的长度赋值给numNew

再给存储数据的数组进行扩容

numMoved:代表要移动元素的个数--》移动一个；数据目的（集合list1）的长度-调用addAll的第一个参数（索引1）

再进行判断移动的个数是否大于0；根据不同的结果调用不同的方法

从新给集合大小进行赋值

图解详细过程

arraycopy的时候Ox777发生变化，首先进行占位，然后将内容拷贝进去

add元素移动位置的代码复原

3.4转换方法

• public String toString()把集合所有数据转换成字符串

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        list.add("789");
        String s = list.toString();
        System.out.println(s);
    }

注意看：

1.这里并没有直接进入ArrayList里面，而是找到了ArrayList的父类AbstractCollection的toString方法中，原因是ArrayList里面并没有重写toString方法，所以找到了父类的toString方法

2.这里的循环查看，使用的是迭代器，并没有使用for循环！！！！

3.5迭代器

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        list.add("789");
        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }

创建一个内部类的对象

注意：Object[] elementData = ArrayList.this.elementData;这里是将ArrayList的数组从新赋值使用

迭代器中进行集合元素的删除

写的代码看似没有问题，但是却抛出了java.util.ConcurrentModificationException的异常！

那这个异常又是什么呢？那就是并发修改异常

那这个异常原因又是什么呢？

在add的时候会有一个标记，添加一个元素会自增1；

在迭代器里面，将标记值赋给一个新的变量

在next的方法中进行判断实际的修改次数是不是不等于预期修改的次数。但是删除一个元素以后，预期修改值就不等了，所以抛出异常！

注意：如果要删除的元素在倒数第二个位置的时候，不会抛出异常

为什么呢？

因为在调用hasNext方法的时候，光标的值和集合的长度一样，那么就会返回false，因此就不会再次调用next的方法获取集合的元素，既然不会调用next方法，那么底层就不会产生并发修改异常

迭代器删除元素

我们可以很清晰的看到，使用迭代器的remove方法删除元素是不会产生异常的

迭代器的remove方法删除元素，其实底层还是调用集合的remove方法，但是调用迭代器的remove方法，每次都会给预期的修改次数的方法进行从新赋值，因此不管怎么修改，都不会产生并发修改异常。

四、面试题

4.1 ArrayList是如何扩容的？

看add方法

第一次扩容10

以后每次都是原容量的1.5倍

4.2ArrayList频繁扩容导致添加性能急速下降，如何处理？

需求：在已有集合的基础上还需要添加10w条数据

    @Test
    public void test(){
        ArrayList<String> list = new ArrayList<>();
        list.add("123");
        list.add("456");
        list.add("789");

        long startTime = System.currentTimeMillis();
        for(int i = 0 ; i < 100000 ; i++ ){
            list.add(i + "");
        }
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }
//用时30毫秒
//分析：看起来程序没有任何问题，但是如果从深层次挖掘存在很大问题
//第一：扩容n次
//第二：性能低

解决办法：在new ArrayList集合的时候直接固定好容量

    @Test
    public void test(){
        ArrayList<String> list1 = new ArrayList<>();
        long startTime1 = System.currentTimeMillis();
        //需求：还需要添加10w条数据
        for(int i = 0 ; i < 100000 ; i++ ){
            list1.add(i+"");
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println(endTime1 - startTime1);
        System.out.println("-------------------");
        ArrayList<String> list = new ArrayList<>(100000);
        long startTime = System.currentTimeMillis();
        //需求：还需要添加10w条数据
        for(int i = 0 ; i < 100000 ; i++ ){
            list.add(i+"");
        }
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }
结果：
35
-------------------
10

4.3ArrayList插入或者删除元素一定比LinkedList慢吗？

• 根据索引删除

  案例：ArrayList和LinkedList对比

        //创建ArrayList集合对象
        ArrayList<String> list = new ArrayList<>();
      //添加500w个元素
        for (int i = 0; i < 5000000; i++) {
            list.add(i+"悦悦");
        }
        //获取开始时间
        long startTime = System.currentTimeMillis();
        //根据索引删除ArrayList集合元素
        //删除索引50000对应的元素
        String remove = list.remove(50000);
        System.out.println(remove);
        //获取结束时间
        long endTime = System.currentTimeMillis();
        System.out.println(endTime-startTime);
  
        LinkedList<String> strings = new LinkedList<>();
        //添加500w个元素
        for (int i = 0; i < 5000000; i++) {
            strings.add(i+"悦悦");
        }
        //获取开始时间
        startTime = System.currentTimeMillis();
        //删除索引50000对应的元素
        String remove1 = strings.remove(50000);
        System.out.println(remove1);
        //获取结束时间
        endTime = System.currentTimeMillis();
        System.out.println(endTime-startTime);

  结果为：

  50000悦悦
  3
  50000悦悦
  2

我们可以看到基本都差不多，有的时候会是一样的，那我们就一起来看看LinkedList的删除操作吧，查找原因

这里进行索引校验，如果满足就返回true。

进行查找要删除的元素，

首先进行判断索引是否小于集合长度的一半

如果小于，那么就第一个节点赋值给x

进行遍历查找

返回节点

如果索引大于集合长度的一半

把最后一个节点赋值给x

从最后一位往前找

获取前一个节点

返回找到的节点

然后进行解绑，所以说，LinkedList不一定比ArrayList删除一个元素要快

4.4ArrayList是线程安全的吗？

• ArrayList不是线程安全的

首先创建一个CollectionTask类实现Runnable接口

    //通过构造方法共享一个集合
    private List<String> list;

    public CollectionTask(List<String> list) {
        this.list = list;
    }

    @Override
    public void run() {
        try {
            Thread.sleep(50);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        //把当前线程名字加入到集合当中
        list.add(Thread.currentThread().getName());
    }

在创建一个测试类

        @Test
        public void test() throws InterruptedException {
            //创建集合
            ArrayList<String> list = new ArrayList<>();
            //创建线程任务
            CollectionTask collectionTask = new CollectionTask(list);
            //开启50条线程
            for (int i = 0; i < 50; i++) {
                new Thread(collectionTask).start();
            }

            //确保子线程执行完毕
            Thread.sleep(3000);

            //遍历集合
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }

            System.out.println("集合长度："+list.size());
        }

结果为：

null
Thread-1
Thread-12
Thread-15
Thread-14
Thread-11
Thread-19
Thread-13
Thread-16
Thread-10
null
null
Thread-8
Thread-3
Thread-2
null
Thread-4
Thread-22
Thread-17
Thread-21
Thread-23
Thread-20
Thread-24
Thread-27
Thread-26
Thread-30
Thread-28
Thread-25
Thread-29
Thread-32
Thread-39
Thread-35
Thread-31
Thread-33
Thread-34
Thread-42
Thread-43
Thread-36
Thread-37
Thread-46
Thread-41
Thread-47
Thread-44
Thread-45
Thread-40
Thread-48
Thread-49
集合长度：47

上面结果可以看出来，有的元素为null，并且最后的长度也不对，因此可以证明ArrayList集合是线程不安全的。

解决方法，在run方法里面加锁（或者使用Collections.synchronizedList()方法）

    //通过构造方法共享一个集合
    private List<String> list;

    public CollectionTask(List<String> list) {
        this.list = list;
    }

    @Override
    public void run() {
        synchronized (this) {
            try {
                Thread.sleep(50);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            //把当前线程名字加入到集合当中
            list.add(Thread.currentThread().getName());
        }
    }

再次运行的结果为：

Thread-0
Thread-49
Thread-48
Thread-47
Thread-46
Thread-45
Thread-44
Thread-43
Thread-42
Thread-41
Thread-40
Thread-39
Thread-38
Thread-37
Thread-36
Thread-35
Thread-33
Thread-34
Thread-32
Thread-31
Thread-30
Thread-29
Thread-28
Thread-27
Thread-26
Thread-25
Thread-24
Thread-23
Thread-22
Thread-21
Thread-20
Thread-19
Thread-17
Thread-18
Thread-16
Thread-15
Thread-14
Thread-13
Thread-12
Thread-11
Thread-10
Thread-9
Thread-8
Thread-7
Thread-6
Thread-5
Thread-4
Thread-3
Thread-2
Thread-1
集合长度：50

集合长度与预期一致，并且中间没有null

4.5如何复制某个ArrayList到另外一个ArrayLiist中去

• 使用clone（）方法
• 使用ArrayList构造方法
• 使用addAll方法

4.6已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时如何保证还可以正常的写入数据到集合？

普通集合ArrayList

创建CollectionTask类

    private static  ArrayList<String> list = new ArrayList<>();
    static {
        list.add("123");
        list.add("456");
        list.add("789");
    }

    @Override
    public void run() {
        for (String s : list) {
            System.out.println(s);
            //在读取数据的同时又向集合写入数据
            list.add("coco");
        }
    }

创建测试类

        @Test
        public void test() throws InterruptedException {
            //创建线程任务
            CollectionTask collectionTask = new CollectionTask();

            //创建10条线程
            for (int i = 0; i < 10; i++) {
                new Thread(collectionTask).start();
            }
        }

运行以后发现抛出异常

解决方法：使用CopyOnWriteArrayList集合

这个时候就不存在并发异常了。

4.7ArrayList和LinkList区别？

• ArrayList

  • 基于动态数组的数据结构
  • 对于随机访问的set和get，ArrayList要优于LinkedList
  • 对于随机操作的add和remove，ArrayList不一定比LinkedList慢（ArrayList底层是由动态数组，因此并不是每次add和remove的时候都需要创建新数组）
• LinkedList
  • 基于链表的数据结构
  • 对于顺序操作，LinkedList不一定比ArrayList慢
  • 对于随机操作，LinkedList效率明显较低

五、自定义ArrayList

@SuppressWarnings("all")
public class MyArrayList<E> {
    //定义数组，用于存储集合的元素
    private Object[] elementData;
    //定义变量，用于记录数组的个数
    private int size;
    //定义空数组，用于在创建对象的时候给elementData初始化
    private  Object[] emptyArray = {};
    //定义常量，用于记录集合的容量
    private final int DEFAULT_CAPACITY = 10;

    //构造方法
    public MyArrayList() {
        //给elementData初始化
        elementData = emptyArray;
    }

    //定义add方法
    public boolean add(E e){
        //调用的时候判断是否需要扩容
        grow();
        //将元素添加到集合
        elementData[size++] = e;
        return true;
    }

    //简单扩容
    private void grow(){
        //判断集合存储元素的数组是否等于emptyArray
        if (elementData == emptyArray){
            //第一次扩容
            elementData = new Object[DEFAULT_CAPACITY];
        }
        //核心算法 1.5倍
        //如果size==集合存元素数组的长度，就需要扩容
        if (size == elementData.length){
            //先定义变量记录老容量
            int oldCapacity = elementData.length;
            //核心算法 1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //创建一个新的数组，长度就newCapacity
            Object[] obj = new Object[newCapacity];
            //拷贝元素
            System.arraycopy(elementData,0,obj,0,elementData.length);
            //把新数组的地址赋值给elementData
            elementData = obj;
        }
    }

    //转换方法
    public String toString(){
        //建议对集合进行判断，如果没有内容直接返回"[]"
        if (size == 0){
            return "[]";
        }

        //创建StringBuilder
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        //循环遍历数组
        for (int i = 0; i < size; i++) {
            //判断i是否等于size-1
            if (i == size-1){
                //追加元素，还需要追加]
                sb.append(elementData[i]).append("]");
            }else {
                sb.append(elementData[i]).append(", ");
            }
        }
        //把sb中的所有数据转换为一个字符串，且返回
        return sb.toString();
    }

    //修改方法
    public E set(int index, E element){
        //建议先对方法的参数索引进行预判
        checkIndex(index);
        //把index索引对应的元素取出来
        E value =(E) elementData[index];
        //替换元素
        elementData[index] = element;
        return value;
    }

    private void checkIndex(int index) {
        if (index >= size || index < 0){
            //制造一个异常
            throw new IndexOutOfBoundsException("索引越界了！");
        }
    }

    //删除方法
    public E remove(int index){
        //索引检验
        checkIndex(index);
        //取出元素
        E value = (E) elementData[index];
        //计算出要移动元素的个数
        int numMoved = size - index - 1;
        //判断要移动的个数是否大于0
        if (numMoved > 0){
            System.arraycopy(elementData,index+1,elementData,index,numMoved);
        }
        //把最后一个位置上的元素置为null;
        elementData[--size] = null;
        return value;
    }

    //根据索引获取元素
    public E get(int index){
        //索引校验
        checkIndex(index);
        //查询元素
        return (E) elementData[index];
    }

    //获取集合的长度
    public int size(){
        return size;
    }
}