ArrayList简介

作者: Sincerity_ | 来源:发表于2020-04-08 15:26 被阅读0次

ArrayList的源码分析（一）【转载】
ArrayList源码分析(jdk1.8)
Java学习——day 09
ArrayList简介
ArrayList简介
ArrayList简介
ArrayList简介
Java学习笔记之ArrayList基本用法
Java集合源码分析 - ArrayList
深入浅出！阿里P7架构师带你分析ArrayList集合源码，建议

ArrayList概述

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

ArrayList继承关系.png

ArrayList是线程不安全的,如果在多线程中使用,建议用CopyOnWriteArrayList或者用Collections中的synchronizedList方法将其包装成一个线程安全的List

预热

System.arraycopy()和Arrays.copyOf()

  //System.arraycopy()
   @FastNative
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
//Arrays.copyOf()
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

从源码可以看出
- arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
- copyOf()是系统自动在内部新建一个数组，调用arraycopy()将original内容复制到copy中去，并且长度为newLength。返回copy; 即将原数组拷贝到一个长度为newLength的新数组中，并返回该数组。
- Array.copyOf()可以看作是受限的System.arraycopy(),它主要是用来将原数组全部拷贝到一个新长度的数组，适用于数组扩容。

看看源码怎么说

/*******************************ArrayList中重要的常量*********************************************/
    //序列化id
    private static final long serialVersionUID = 8683452581122892189L;
    //容器默认初始化大小 
    private static final int DEFAULT_CAPACITY = 10;
    //一个空对象
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //一个空对象，如果使用默认构造函数创建ArrayList，则默认对象内容是该值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //ArrayList存放对象的容器，后面的添加、删除等操作都是基于该属性来进行操作
    transient Object[] elementData; 
    //当前列表已使用的长度
    private int size;
    //数组最大长度（2147483639），这里为什么是Integer.MAX_VALUE - 8是因为有些虚拟机在数组中保留了一些头部信    息，防止内存溢出
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //这个是从AbstractList继承过来的，代表ArrayList集合修改的次数
    protected transient int modCount = 0;

transient^xr1关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程。

作用

Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的

构造函数

    //1.我们常用的无参构造 
    public ArrayList() {
        //构造一个空数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //2.带初始长度的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);
        }
    }
    //3.带Collection对象的构造函数
    public ArrayList(Collection<? extends E> c) {
        //把Collection转为数组对ArrayList初始容器进行数组地址的拷贝
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //把Collection对象的内容copy(可以理解为深拷贝)到elementData中，并且这些元素是按照该collection的              迭代器返回它们的顺序排列的
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换成空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

构造函数总结

如果不传递参数默认会构建一个空数组,
传递int值表示创建初始的数组长度
传递collection对象,默认会把这个对象转为数组,如果这个collection对象不是object类型,就会进行一次深拷贝

增加元素Add

boolean add(E e);

//将指定的元素附加到此列表的末尾
public boolean add(E e) {
        //判断是否需要对数组进行扩容
        ensureCapacityInternal(size + 1);  
        //进行元素赋值
        elementData[size++] = e;
        return true;
}
//获取Arraylist最小容量 
private void ensureCapacityInternal(int minCapacity) {
        //如果原来的数组是空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //minCapacity =(0+1) DEFAULT_CAPACITY默认是10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //先进行数组的扩容
        ensureExplicitCapacity(minCapacity);
}
//判断是否满足扩容条件
private void ensureExplicitCapacity(int minCapacity) {
      //扩容次数
        modCount++;
      //对数组的最小容量和ArrayList存放对象的数组长度进行比较
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}
//进行数组扩容
private void grow(int minCapacity) {
        //的到ArrayList的长度
        int oldCapacity = elementData.length;
        //新的数组长度=原始长度+原始长度/2 右移一位就相当于除以2的一次方
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //处理数组长度溢出 
            newCapacity = hugeCapacity(minCapacity);
        //对数组长度进行一次深拷贝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
//这里并不会到MAX_ARRAY_SIZE,这个值取决于虚拟机内存
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

关于add(E e)总结

确保数组已使用长度（size）加1后可以存入下一个元素。

修改次数modCount标识自增1，如果当前数组已使用长度+1后大于当前数组长度，则调用grow()方法，扩容数组，grow()会将当前数组的长度变为原来容量的1.5倍

确保新加的元素有地方存储后，则将新元素添加到位于size++的位置上。

返回添加成功的布尔值。

void add(int index, E element);

  //指定位置添加数据
public void add(int index, E element) {
        //step1: 索引检测
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //step2:判断是否需要扩容
        ensureCapacityInternal(size + 1);  
        //step3:对源数组进行复制处理（位移），从index + 1到size - index
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        //step4:数组指定的位置进行赋值
        elementData[index] = element;
        size++;
    }

boolean addAll(Collection<? extends E> c);

 public boolean addAll(Collection<? extends E> c) {
        //把Collection对象转为数组
        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;
    }

boolean addAll(Collection<? extends E> c);

public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew); 
        //得到需要移动到的位置
        int numMoved = size - index;
        //将当前索引等于index和大于index的元素往后移numMoved个位置
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //将数组添加到列表尾部
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

E set(int index, E element);

public E set(int index, E element) {
    //判断插入位置是否正确，如果大于列表长度会抛出异常
    if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //获取插入位置的当前元素
        E oldValue = elementData(index);
        //将新的元素替换当前插入位置的元素
        elementData[index] = element;
        //返回插入位置老的值
        return oldValue;
    }

删除元素

boolean remove(Object o);

//删除对象
public boolean remove(Object o) {
        //空对象
        if (o == null) {
            //遍历出所有的的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)
            //如果不是最后一个位置将删除位置后的元素向左移numMoved个位置进行复制
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //置空最后一个位置元素
        elementData[--size] = null; 
 }

E remove(int index);

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //扩充++
        modCount++;
        //得到原数组
        E oldValue = (E) elementData[index];
        //得到移除元素后的位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        //将元素最后一个位置置空
        elementData[--size] = null; 
        return oldValue;
    }

boolean removeAll(Collection<?> c);

 //删除传递过来的对象 
public boolean removeAll(Collection<?> c) {
        //判断传递的对象是否为空
        Objects.requireNonNull(c);
        //删除对象
        return batchRemove(c, false);
    }
//保留传递对来的对象,如果ArrayList中有这个对象之外的数据将会被删除
public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //保留对象删除
        return batchRemove(c, true);
    }
//进行批量删除
 private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            //遍历数组，并检查这个集合是否包含对应的值，移动要保留的值到数组前面，w最后值为要保留的元素的数量
            //若保留，就将相同的元素移动到前段；不删除，就将不同元素移动到前段
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 确保异常抛出前的部分可以完成期望的操作，而被遍历的部分会被接到后面
            //r不等于size表示可能出错了
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
              //如果w等于size，表示全部元素都保留了，所以也就没有删除操作发生，所以会返回false；反之，返true，并更改数组
            //而w不等于size的时候，即使try块抛出异常，也能正确处理异常抛出前的操作，因为w始终为要保留的前段部分的长度，数组也不会因此乱序
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

关于iterator遍历ArrayList

public Iterator<E> iterator() {
        return new Itr();
    }
 private class Itr implements Iterator<E> {
     ...
         public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
         ...
 }

一般的话，调用完iterator之后，我们会使用iterator做遍历，这里使用next做遍历的时候有个需要注意的地方，就是调用next的时候，可能会引发ConcurrentModificationException，当修改次数，与期望的修改次数（调用iterator方法时候的修改次数）不一致的时候，会发生该异常，

expectedModCount这个值是在用户调用ArrayList的iterator方法时候确定的，但是在这之后用户add，或者remove了ArrayList的元素，那么modCount就会改变，那么这个值就会不相等，将会引发ConcurrentModificationException异常，这个是在多线程使用情况下，比较常见的一个异常。

解决办法

多线程中使用Iterator来遍历时候,可以在线程中给ArrayList加一个同步锁,锁住ArrayList来保证modCount变量的同步
使用CopyOnWriteArrayList本质上是对array数组的一个封装，一旦CopyOnWriteArrayList对象发生任何的修改都会new一个新的Object[]数组newElement，在newElement数组上执行修改操作，修改完成后将newElement赋值给array数组（array=newElement）。因为array是volatile的，因此它的修改对所有线程都可见

 //CopyOnWriteArrayList
private transient volatile Object[] array;
//ArrayList
transient Object[] elementData;

为什么说ArrayList线程不安全

</a>
在给ArrayList添加数据的时候有一段代码elementData[size++] = e; 赋值的过程可以分为两个步骤1.elementData[size] = e; 2.size++;我们分别使用两个线程来模拟插入过程.例如有两个线程,分别加入数字1与2.这里会出现三种情况

输出值为null; 此处导致了某些值为null的问题.因为原size=1, 但是因为线程1与线程2都将值赋值给了element[1],导致了element[2]内没有值,被跳过了.指针index指向了3.所以,导致了某些情况下值为null的情况
数组越界异常;
- 线程1 赋值 element[1] = 1; 随后因为时间片用完而中断;
- 线程2 赋值 element[1] = 2; 随后因为时间片用完中断;
某些线程没有输出值
- 线程1 自增 size++; (size=2)
- 线程2 自增 size++; (size=3)

解决方案

使用Vector类进行替换
使用Collections.synchronizedList(List)
使用CopyOnWriteArrayList

总结

ArrayList自己实现了序列化和反序列化，因为它实现了writeObject和readObject方法。
ArrayList基于数组实现，会自动扩容。
添加元素时会自己判断是否需要扩容，最好指定一个大概的大小，防止后面多次扩容带来的内存消耗；删除元素时不会减少容量，删除元素时，将删除掉的位置元素置为null，下次gc就会自动回收这些元素所占的空间。
ArrayList是线程不安全的。
使用iterator遍历可能会引发多线程异常

transient关键字

ArrayList的源码分析（一）【转载】
ArrayList简介 ArrayList核心源码 ArrayList源码分析System.arraycopy()...
ArrayList源码分析(jdk1.8)
1.ArrayList简介 ArrayList继承关系如下图： ArrayList继承了AbstractList类...
Java学习——day 09
主要内容容器的简介 ArrayList简介手写模仿ArrayList 手写模仿LinkedList 笔记详情 ...
ArrayList简介
ArrayList简介 ArrayList实现了List接口，内部以数组存储数据，允许重复的值。由于内部是数组实现...
ArrayList简介
ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元...
ArrayList简介
ArrayList简介 ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量...
ArrayList简介
ArrayList概述 ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了动态...
Java学习笔记之ArrayList基本用法
申明：非原创，转载自 Java学习笔记之ArrayList基本用法 ArrayList简介 ArrayList是一...
Java集合源码分析 - ArrayList
ArrayList简介 ArrayList概述 ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现...
深入浅出！阿里P7架构师带你分析ArrayList集合源码，建议
ArrayList简介 ArrayList 是 Java 集合框架中比较常用的数据结构了。ArrayList是可以...