【Java集合】ArrayList源码分析

【Java集合】ArrayList源码分析

ArrayList是日常开发中经常使用到的集合,其底层采用数组实现,因此元素按序存放。其优点是可以使用下标来访问元素,时间复杂度是O(1)。其缺点是删除和增加操作需要使用System.arraycopy()来移动部分受影响的元素,时间复杂度为O(N)。同时ArrayList由于是采用数组来存放数据,因此会有容量限制,在使用时需要扩容,当插入操作超出数组长度,就会进行扩容,扩容后数组的长度为原来的1.5倍,默认的数组长度是10。

为了更好的掌握ArrayList,因此阅读并仿照ArrayList源代码,实现一个具有增删改查以及自动扩容功能的简易版MyArrayList(代码几乎与ArrayList源码一致)。

首先新建一个class,命名为MyArrayList

public class MyArrayList<E> {
}

由于ArrayList是通过数组来存储元素的,因此我们定义一个Object类型的数组elementData来存储数据,再定义一个变量size,用来记录数组中的元素个数,其默认值为0。

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数
	
}

接下来就是构造函数,有两种,第一种是未指定初始容量的构造函数,默认容量为10;第二种是在构造函数中传入指定容量。

先说第一种构造函数,ArrayList在默认情况下,其容量为10。因此我们定义一个常量DEFAULT_CAPACITY = 10作为默认容量。同时,还定义一个常量数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}用于对elementData进行初始赋值。

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数

	private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
	private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList对象数组的默认初始化

	/**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
}

需要注意的是这里的默认容量10并不是在构造函数中直接使用,而是在第一次插入进行扩容时才会使用。

第二种构造函数,传入指定的容量。根据传入的容量参数,我们有以下三种结果:
①传入的容量参数大于0:则以该参数为容量创建对象数组
②存入的容量参数等于0:则需要创建一个空的对象数组,因此定义一个常量数组EMPTY_ELEMENTDATA = {}用于传入容量为0时的初始化。
③传入的容量参数小于0:明显这是非法的,因此抛出参数异常IllegalArgumentException()

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数

	private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
	private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList对象数组的默认初始化
	private static final Object[] EMPTY_ELEMENTDATA = {}; //传入容量为0时的初始化

	/**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 传入指定初始容量的构造函数
     * @param initialCapacity 传入的初始化容量
     */
    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("非法的容量: "+
                    initialCapacity);
        }
    }
}

好了,构造函数构建完毕,接下来就是增删改查功能的实现,实现的方法如下:

//增,将元素放到数组末尾元素的后面,e为待插入元素,返回boolean
boolean add(E e)

//删,删除指定位置的元素,index为待删除元素的位置,返回被删除的元素
E remove(int index)

//改,替换指定位置的元素,index为被替换元素的位置,e为替换的元素,返回被替换的元素
E set(int index, E e)

//查,查询指定位置的元素,index为查询的位置,返回查到的元素
E get(int index)

首先是add(E e)方法,由于数组容量有限制,因此我们新增一个元素,都有可能要进行扩容,所以我们需要编写一个函数ensureCapacityInternal来判断是否需要自动扩容,若需要则进行扩容。

 	/**
     * ArrayList的add方法
     * 将元素放到数组末尾元素的后面
     * @param e 待插入的元素
     * @return 
     */
    boolean add(E e){
        //1、自动扩容机制,传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);
    }

ensureCapacityInternal函数中,需要传入目前需要的最小容量。同时我们还要判断对象数组elementData是否为空数组,若是,则将传入的目前需要的最小容量与默认容量10进行对比,取其中的最大值作为本次扩容的容量。

/**
     * 判断原数组是否为空数组
     * 是:则选默认容量和目前需要的最小容量二者中的最小值
     * 否:则继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组,则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比,取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

接下来,我们判断是否需要进行扩容。如果目前需要的最小容量大于原数组的长度,才进行扩容,否则不进行扩容,该功能写入函数 ensureExplicitCapacity

    /**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度,才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容,否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

然后,若进行扩容,则执行扩容函数grow。在grow中,我们需要进行如下操作:
①获取原数组的容量oldCapacity,然后计算出值为oldCapacity1.5倍的新容量newCapacity

int oldCapacity = elementData.length;
//扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

②将扩容1.倍后的新容量newCapacity与目前需要的最小容量minCapacity进行对比,若新容量小于目前需要的最小容量,则新容量的值取目前需要的最小容量。

if (newCapacity - minCapacity < 0) newCapacity = minCapacity;

③将新容量newCapacity与所允许的数组的最大长度进行对比,数组最大长度定义为常量MAX_ARRAY_SIZE = Integer.MAX_VALUE,值为整数的最大值。如果新容量newCapacity大于数组最大长度MAX_ARRAY_SIZE ,则取目前需要的最小容量minCapacity与数组最大长度MAX_ARRAY_SIZE 两者中的最小值作为新容量newCapacity的值。

 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

④使用Arrays.copyOf(原数组, 新长度)进行数组的复制,即实现数组扩容

elementData = Arrays.copyOf(elementData,newCapacity);

完成扩容任务的函数grow如下:

 /**
     * 扩容函数:如何进行扩容(扩多少)
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量,则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度,则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位,即相当于除2,最后加原长度,则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量,则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度,则看传入的最小容量与数组最大长度对比,取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度),返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

至此,就完成了新增时,判断是否需要扩容,并且完成扩容功能。接下来我们只需要将新增元素插入数组元素末尾位置的下一个位置,并返回true即可。

boolean add(E e){
        //1、自动扩容机制,传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕,将元素存入
        elementData[size++] = e;

        return true;
}

最终,新增add方法和自动扩容有关的函数编写完成:

	/**
     * ArrayList的add方法
     * 将元素放到数组末尾元素的后面
     * @param e 待插入的元素
     * @return 
     */
boolean add(E e){
        //1、自动扩容机制,传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕,将元素存入
        elementData[size++] = e;

        return true;
}

	/**
     * 判断原数组是否为空数组
     * 是:则选默认容量和目前需要的最小容量二者中的最小值,然后接着往下判断
     * 否:则直接继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组,则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比,取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

 	/**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度,才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容,否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

	/**
     * 扩容函数:如何进行扩容(扩多少)
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量,则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度,则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位,即相当于除2,最后加原长度,则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量,则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度,则看传入的最小容量与数组最大长度对比,取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度),返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

接下来,就是删除,remove方法。由于该方法传入待删除元素的位置索引index,因此需要检查index
的范围是否符合要求。编写一个函数rangeCheck来检查下标。

	/**
     * 检查index范围
     * 超出范围则抛出异常
     * @param index 数组下标位置
     */
     void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("哎呀,超出范围了!");
    }

index没有超出范围,则接下来就是获取索引对应的元素,获取方式很简单,就是elementData[index]即可。考虑到其他方法也会需要通过这样方式来获取对应位置的元素,因此我们将这个操作抽取出来,成为一个函数elementData(),用于获取元素。

 	/**
     * 返回数组中指定位置的元素
     * @param index
     * @return
     */
    E elementData(int index){
        return (E) elementData[index];
    }

那么,目前remove方法前面两个操作我们已经完成

    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
       
    }

删除index元素,需要把该位置后面的所有元素都向前移动一个位置。因此接下来我们就需要将index后面的元素向前移动一个位置。

具体做法是,先计算出需要移动的元素个数numMoved,用数组中最后一个元素的下标减去index即可获得需要移动的元素个数:size-1-index

然后利用System.arraycopy()来移动元素,该方法的用法如下:

System.arrayCopy(Object srcArray,int srcPos,Object destArray ,int destPos,int length)
①Object srcArray 原数组(要拷贝的数组)
②int srcPos 要复制的原数组的起始位置(数组从0位置开始)
③ Object destArray 目标数组
④ int destPos 目标数组的起始位置
⑤int length 要复制的长度
从原数组srcArray 取元素,范围为下标srcPos到srcPos+length-1,取出共length个元素,存放到目标数组中,存放位置为下标destPos到destPos+length-1。

我们将原数组和目标数组都设为elementData,然后原数组的起始位置为index+1,目标数组的起始位置为index,要复制的长度设为元素个数numMoved。这样就能做到将数组index位置后面的元素向前移动一位。

不过这样做目标数组的最后一位元素依然是原来的数,因此我们需要将目标数组最后的元素置为null,并且由于是删除,所以元素个数size需要减一。至此,删除方法remove完成。

	/**
     * ArrayList的remove方法
     * @param index 要删除元素的位置
     * @return 返回被删除元素
     */
    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
        //3、计算需要移动的元素的个数
        int numMoved = size - 1 - index;
        //4、将index后面的数往前移动一位
        if (numMoved > 0){
            System.arraycopy(elementData,index + 1, elementData, index, numMoved);
        }
        //5、把最后的元素置为null
        elementData[--size] = null;
        //返回被删除元素
        return oldValue;
    }

增删操作已完成,接下来就是改操作,set()方法。这个方法就比较简单,具体的步骤如下:
①检查index范围
②获取index位置的元素
③将index位置的元素,替换为传入的元素
④返回原先index位置的元素

	/**
     * ArrayList的set
     * @param index 需要修改的位置
     * @param e 需要替换的元素
     */
    E set(int index, E e){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        E oldValue = elementData(index);

        //3、替换元素
        elementData[index] = e;

        //4、返回原先index位置的元素
        return oldValue;
    }

最后,就是查操作,get方法。该方法更为简单,只需要先检查index范围,再获取index位置的元素直接返回即可。

	/**
     * ArrayList的get方法
     * @param index
     * @return
     */
    E get(int index){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        return elementData(index);
    }

到这里,我们编写的简易版ArrayList的增删改查操作就全部完成了。点进JDK1.8中ArrayList源码可以看到,我们的上面的代码几乎与ArrayList源码一模一样。

最终这个简易版ArrayList所有代码如下:

public class MyArrayList<E> {

    private int size; //ArrayList中实际元素的数量的size
    private Object[] elementData; //ArrayList的对象数组

    private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
    private final static int MAX_ARRAY_SIZE = Integer.MAX_VALUE; //数组的最大长度,也就是整数的最大值
    private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList的对象数组的默认初始化
    private static final Object[] EMPTY_ELEMENTDATA = {}; //传入容量为0时的初始化

    /**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 传入指定初始容量的构造函数
     * @param initialCapacity
     */
    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("非法的容量: "+
                    initialCapacity);
        }
    }

    /**
     * ArrayList的add方法
     * 将元素放到数组有效长度的末尾
     * @param e 待插入的元素
     * @return
     */
    boolean add(E e){
        //1、自动扩容机制,传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕,将元素存入
        elementData[size++] = e;

        return true;
    }


    /**
     * 判断原数组是否为空数组
     * 是:则选默认容量和目前需要的最小容量二者中的最小值,然后接着往下判断
     * 否:则直接继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组,则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比,取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

    /**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度,才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容,否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

    /**
     * 扩容函数:如何进行扩容(扩多少)
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量,则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度,则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位,即相当于除2,最后加原长度,则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量,则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度,则看传入的最小容量与数组最大长度对比,取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度),返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

    /**
     * ArrayList的remove方法
     * @param index 要删除元素的位置
     * @return 返回被删除元素
     */
    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
        //3、计算需要移动的元素的个数
        int numMoved = size - 1 - index;
        //4、将index后面的数往前移动
        if (numMoved > 0){
            System.arraycopy(elementData,index + 1, elementData, index, numMoved);
        }
        //5、把最后的元素置为null
        elementData[--size] = null;
        //返回被删除元素
        return oldValue;
    }

    /**
     * 检查index范围
     * 超出范围则报错
     * @param index
     */
    void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("哎呀,超出范围了!");
    }

    /**
     * 返回数组中指定位置的元素
     * @param index
     * @return
     */
    E elementData(int index){
        return (E) elementData[index];
    }


    /**
     * ArrayList的set
     * @param index 需要修改的位置
     * @param e 需要替换的元素
     */
    E set(int index, E e){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        E oldValue = elementData(index);

        //3、替换元素
        elementData[index] = e;

        //4、返回原先index位置的元素
        return oldValue;
    }

    /**
     * ArrayList的get方法
     * @param index
     * @return
     */
    E get(int index){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        return elementData(index);
    }


    /**
     * 获取元素个数
     * @return
     */
    int size(){
        return size;
    }

}

我们测试一下,这个简易版ArrayList

 public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        //增
        myArrayList.add("hello");
        myArrayList.add("word");
        myArrayList.add("hello");
        myArrayList.add("java");
        //改
        myArrayList.set(1,"####");
        //删
        myArrayList.remove(2);
        //查
        for (int i = 0; i < myArrayList.size(); i++){
            System.out.println(myArrayList.get(i));
        }

    }

测试结果如下:

hello
####
java
分享到 :
相关推荐