文章目录

ArrayList

ArrayList概述

ArrayList底层是一个Object数组,而数组在内存是连续的空间,所以使用ArrayList存储的元素与添加时的顺序是一致的,每一个ArrayList都有一个容量大小,当添加的元素数量大于该数组的容量时,ArrayList会自动扩容。

ArrayList具体框架图

ArrayList继承于AbstractList,实现了RandomAccess，Cloneable,Serializable这些接口。

实现RandomAccess接口,意味着ArrayList支持随机方法,即可以像数组一样通过下标快速的访问某一元素。

实现了Cloneable接口,意味着可以被克隆

实现Serializable,意味着可以被序列化

属性

/**
     * 序列化ID
     */
    private static final long serialVersionUID = 8683452581122892189L;
    /**
     * 默认初始化的容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * 共享空数组实例用于默认大小的空实例。我们将它与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     *保存ArrayList元素的数组
     */
    transient Object[] elementData; 
    /**
     * 
     *
     * ArrayList中元素的个数
     */
    private int size;

通过查看源码可知,ArrayList有2个Object数组,那么这2两数组有啥区别呢?这个问题得继续往下看。

构造方法

无参构造方法

    /**
     * 默认无参构造函数
     *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0,也就是说明初始其实是空数组,当添加第一个元素的时候数组容量才变成10,当容量超过10时,会扩大1.5倍
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

当创建使用无参构造方法创建一个ArrayList对象时, elementData引用所指向的数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

带初始容量的构造方法

    /**
     * 带初始容量参数的构造函数（使用者可以在创建ArrayList对象时自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        //初始的大小大于0则分配一个该大小的数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //初始的大小为0,分配一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //小于0抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

当创建使用带初始容量参构造方法创建一个ArrayList对象时,如果初始的容量initialCapacity大于0则分配一个相应大小的数组，如果初始的容量initialCapacity等于0则

elementData引用指向EMPTY_ELEMENTDATA,如果小于0则抛出异常。

带集合参数的构造方法

/**
     * 利用其他 Collection 构建 ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        //将集合转换成数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
            //如果elementData是不是Object类型
            if (elementData.getClass() != Object[].class)
                //将原来不是Object类型的数组赋值给新的Object数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            //如果elementData数组的长度为0,直接给个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

上述代码,首先将传入的集合转换成数组并赋值给 elementData,再将elementData的长度赋值为size，然后判断是否为0,如果不为0,则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。如果为0则将EMPTY_ELEMENTDAT赋值给elementData。

扩容机制

通过上述无参构造方法创建的ArrayList对象,该数组分配的是一个空数组,所以容量大小为0,当添加元素或者数组满了的时候会触发扩容机制。接下来就先看看add()方法。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1); //添加第一个元素时size为0
        elementData[size++] = e;
        return true;
    }

向ArrayList添加一个元素

package com.kc.demo;
import java.util.ArrayList;
public class Demo2 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("叶秋涵");
    }
}

根据add方法在添加元素之前,会对容量进行判断已经满了,如果满了自然要扩容,下面就来看看ensureCapacityInternal()方法。

   private void ensureCapacityInternal(int minCapacity) {//添加第一个元素时minCapacity为1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

ensureCapacityInternal方法参数minCapacit的含义为所需最小的容量,ensureCapacityInternal的方法体中又调用了calculateCapacity()方法。

  private static int calculateCapacity(Object[] elementData, int minCapacity) {//minCapacity为1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY为10
        }
        return minCapacity;
    }

ensureExplicitCapacity()方法会判断当前数组的引用是否为空数组,如果是就返回DEFAULT_CAPACITY(默认容量为10)以及minCapacity的最大值。否则返回minCapacity。

然后ensureExplicitCapacity()方法根据返回的最小容量与数组长度进行扩容

    private void ensureExplicitCapacity(int minCapacity) {//minCapacity为10
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//10>0
            grow(minCapacity);
    }

如果最小的容量大于数组长度时就需要调用grow()方法进行扩容

private void grow(int minCapacity) {//minCapacity 为10
        // overflow-conscious code
        int oldCapacity = elementData.length;//0
        int newCapacity = oldCapacity + (oldCapacity >> 1);//原数组的1.5倍-->0
        if (newCapacity - minCapacity < 0)//0<10
            newCapacity = minCapacity;// newCapacity = 10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

grow()方法会先计算出原数组大小的1.5倍,如果扩容后的长度比最小容量小,则newCapacity为最小容量,如果newCapacity比整数的最大值还要大,就会调用hugeCapacity()方法进行调整。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

hugeCapacity()方法会对minCapacity进行判断,如果它小于0则抛出异常。最终的newCapacity取决于minCapacity和MAX_ARRAY_SIZE,如果前者大于后者则返回

Integer.MAX_VALUE,否则返回ArrayList定义的数组最大的容量。

ArrayList有2个Object数组的区别?

看完构造方法、添加方法、扩容方法之后，new ArrayList(),elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,new ArrayList(0),会将 EMPTY_ELEMENTDATA赋值给elementData,当EMPTY_ELEMENTDATA扩容时,传入的参数是多少就是多少,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA初次扩容之后的容量为10。

常用方法

在指定位置插入元素

    /**
     * 先将原来该位置的元素以及后面的元素整体往后移动,再把这个位置的元素插入
     */
    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++;
    }

将指定集合元素追加到ArrayList末尾

    /**
     *将指定集合元素追加到ArrayList末尾
     */
    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;
    }

删除 index 位置元素

   /**
     * 删除指定位置的元素,返回值为已删除的元素
     *
     */
    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;
    }

删除遇到的第一个元素

    /**
     *删除从某个元素,删除成功返回true,否则返回false。
     */
    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;
    }

获取下标 index 位置元素

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

将下标 index 位置元素设置为 element

    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

清空

 public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

判断元素是否在ArrayList中

    /**
     * 判断集合是否包含指定的元素,有则返回true
     */
    public boolean contains(Object o) {
        //调用indexOf()方法进行寻找,该方法会从集合头一直到尾去寻找指定的元素,找到就返回首次出现的索引,没有找到就返回-1
        return indexOf(o) >= 0;
    }

返回第一个元素所在下标

    /**
     * 从列表头到开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1
     */
    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;
    }

返回最后一个元素的下标

    /**
     * 从列表尾到头开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

总结

ArrayList底层的数据结构是数组
ArrayList可以自动扩容，不传初始容量或者初始容量是0，都会初始化一个空数组，但是如果添加元素，会自动进行扩容。
ArrayList是线程不安全的,在单线程可以使用,多线程环境下可以使用CopyOnWriteArrayList

各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！

《JavaSE-第十六章》之ArrayList源码与扩容机制