Java-ArrayList深度解析

124 阅读 0 评论 82 点赞

我是靠谱客的博主感动菠萝，最近开发中收集的这篇文章主要介绍Java-ArrayList深度解析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Java集合框架----ArrayList

之前我们学过数组了，已经知道数组有个缺点，数组一旦被创建，不能自行扩容。现在介绍ArrayList集合容器，它是对数组进行了封装，使其可以动态扩容和缩小长度，并且ArrayList还可以存储任意类型的数据。因此ArrayList底层实现的数据结构就是数组。

一、ArrayList集合容器中实现的接口和继承的类

1）先继承AbstractList父类，自己本身也实现List接口。继承和重写父类和接口中的方法。
2）实现RandomAccess接口：这是有关效率的问题了，实现这个接口说明可以随机进行存取。
3）实现Serializable接口：实现这个接口，说明ArrayList类可以序列化。
4）实现Cloneable接口：实现和这个接口，可以使用Object.clone()方法了。

二、ArrayList集合容器中的属性：

1）序列化版本号：
private static final long serialVersionUID = 8683452581122892189L;
2）private static final int DEFAULT_CAPACITY = 10；
默认的初始容量。
3）private static final Object[] EMPTY_ELEMENTDATA = {};
如果自定义长度为0，则使用它来初始化ArrayList,或者用于空数组替换。
4）private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
如果没有自定义容量，则使用它来初始化ArrayList，或者用于空数组的对比。
transient Object[] elementDate;
这是ArrayList底层用到的数组，前面关键字transient关键字说明这个变量已经实现序列化的类中，不允许再序列化。
5）private int size;
这个变量是用来记录实际的ArrayList大小。
6）private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
可分配的最大容量。（但是在Java8的源码中已经没有这个属性了）。

三、ArrayList的构造方法：

1）无参构造函数：

public ArrayList(){
    /**
    *   无参构造函数，设置元素数组为空
    */
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2）int数据类型的参数：
参数为数组的初始化长度，首先需要判断initialCapacity和0的关系。
如果initialCapacity的值大于0，则创建一个长度为initialCapacity的对象数组。
如果initialCapacity的值等于0，则将EMPTY_ELEMENTDATA赋给elementData。
如果initialCapacity的值小于0，则抛出异常，非法容量。

public ArrayList(int initialCapacity){
    if(initialCapacity > 0){
        //当初始化容量大于0，则新建一个Object的数组；
        this.elementData = new Object[initialCapacity];
    }else if(initialCapacity == 0){
        //当初始容量为0的时候，则初始化为空对象数组
        this.elementData = EMPTY_ELEMENTDATA;
    }else{
        //如果初始化容量小于0，这个时候就需要抛出异常了
        throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
    }
}

Collection<? extends E>类型的参数：
第一步：将参数中的集合转换成数组，赋值给elementData。
第二步：判断参数集合是否为空，通过比较size和第一步中的集合比较。
第三步：如果参数集合为空，则设置元素数组为空，即将EMPTY_ELEMENTDATA的值赋给elementData。
第四步：如果参数集合不为空，接下来判断是否能够成功转换成Object数组，如果转换成Object类型的数组，则将数组进行复制。

public ArrayList(Collection <? extends E> c){
    //转换成数组
    elementData = c.toArray();
    //判断参数容器的长度：
    if((size = elementData.length) != 0){
        //判断是否能够成功转换成Object数组，如果不可以就复制数组
        if(elementData.getClass() != Object[].class){
            elementData = Arrays.copyOf(elementData,size,Object[].class);
        }
    }else{
        //说明参数容器中的实际长度为0，则将空对象数组赋值给elementData
        elementData = EMPTY_ELEMENTDATA;
    }
}

四、ArrayList的常用方法：

1）add(E e)：
在添加的方法中，主要需要完成以下三个步骤：
步骤1：判断容器中容量，如果容量不足，则需要动态扩容。
步骤2：将元素添加到容器中的指定位置。
步骤3：将元素中的实际元素个数加1，也就是size++;

/**
* ArrayList的增加方法的源码：
*/
public boolean add(E e){
    ensureCapacityInternal(size+1);
    elementData[size++] = e;
    return true;
}

在上面的代码中，如果ArrayList容器的容量不足的时候，则需要进行动态扩容，下面介绍ArrayList的扩容机制：
ArrayList的扩容机制是在ArrayList容器的add(E e)方法的时候会启用，扩容机制也是为了确保ArrayList容器可以将要添加的元素成功添加上去。一次扩容需要经历以下步骤：

1）在方法中首先调用了ensureCapacityInternal(size+1)的方法，用来确定添加元素成功需要的最小集合容量minCapacity，size+1是为了当元素添加成功之后，则将容器中的实际容量加1。

2）调用ensureExplicitCapacity(minCapacity)方法来确保集合容器为了将元素添加成功，是否需要扩容，将计数器加1，然后判断minCapacity和当前数组的长度大小，当minCapacity的值比当前数组的长度大时，则说明需要扩容。

3）当容器需要扩容的时候，则调用grow(minCapacity)方法，minCapacity表示确保元素添加成功的最小容量，在扩容的时候，首先对原数组的长度增加1.5倍，然后对扩容后的容量和minCapacity比较，如果比新容量比minCapacity的小，则将minCapacity的值设置为容量，否则设置为新容量。再将原数组拷贝到新容器中。

/**
* ensureCapacityInternal(size + 1)方法，用来确定是否需要扩容。
*/
private void ensureCapacityInternal(int minCapacity){
    //括号中的参数calculateCapacity是用来计算容量的
    ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
}

/**
*   计算容量的方法calculateCapacity(elementData,minCapacity)方法
*/
private static int calculateCapacity(Object[] elementData,int minCapacity){
    //如果elementData的数组为空数组：
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        //返回默认空数组的长度和传入参数两个中较大的值
        return Math.max(DEFAULT_CAPACITY,minCapacity);
    }
    //否则直接返回minCapacity；
    return minCapacity;
}

/**
*   确保容量可用的方法：ensureExplicitCapacity(minCapacity)
*/
private void ensureExplicitCapacity(int minCapacity){
    //结构性修改+1；
    modCount++;
    //如果minCapacity的值大于了当前数组的长度，则说明数组存放满了，需要扩容。
    if(minCapacity - elementData.length > 0){
        grow(minCapacity);
    }
}

/**
* 数组扩容：grow(int minCapacity)；
*/
private void grow(int minCapacity){
    //获取原有数组的容量大小：
    int oldCapacity = elementData.length;
    //计算新容量，新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断如果新容量小于参数指定容量，则新容量修改为参数容量minCapacity;
    if(newCapacity - minCapacity < 0){
        newCapacity = minCapacity;
    }
    //判断如果新容量大于了最大容量(Integer.MAX_VALUE-8),则执行新的内容。
    if(newCapacity - MAX_ARRAY_SIZE > 0){
        newCapacity = hugeCapacity(minCapacity);
    }
    //拷贝扩容：
    elementData = Arrays.copyOf(elementData,newCapacity);
}

2）set(int index,E element):设置指定索引处的元素值。
在对象调用set方法的时候，会做以下三个步骤：
步骤1：校验输入参数下标是否合法。
步骤2：将数组中该下标值原有的元素值取出。
步骤3：将参数新的元素设置到该位置，然后将原有的元素值作为返回值返回。

/**
*   set(int index,E element)方法源码
*/
pubic E set(int index,E element){
    //校验输入的参数是否合法：
    rangeCheck(index);
    //获取到该下标位置的原有元素值
    E oldValue = elementData(index);
    //将该小标位置上设置上新元素
    elementData[index] = element;
    //将该下标位置的原有元素值返回
    return oldValue;
}

/**
*   校验输入参数是否合法的方法
*/
private void rangeCheck(int index){
    if(index >= size){
        //抛出异常：
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

3)indexOf(Object obj):找出该容器中第一次出现obj的索引
indexOf方法是从容器的开头开始查找与传入元素是否相等，如果相等，则返回第一次出现该元素的索引值，否则返回-1.
注意：通过源码可以知道，在查找是否有相同元素的,因为ArrayList集合中可以存放null值，所以要区分传入的参数是否为null，否则在比较的时候会出现空指向的异常

/**
*   indexOf查找和传入参数相同的下标值
*/
public int indexOf(Object obj){
    if (obj == null) {
        //遍历容器，找到为null元素的下标
        for (int i = 0;i < size;i++) {
            //如果找到元素为null的值，则返回下标值
            if (elementData[i] == null) {
                return i;
            }
        }
    } else {
        //遍历容器
        for (int i = 0;i < size;i++) {
            //如果找到了和传入参数的值相等的下标，则返回下标
            if (obj.equals(elementData[i])) {
                return i;
            }
        }
    }
    //没有找到则返回-1
    return -1;
}

3)get(int index):找出指定下标的元素值

步骤1：检查输入的参数是否合法
步骤2：如果参数合法，则将集合容器中的元素值返回

/**
*  get(int index)：找出指定下标元素值的方法源码
*/
public E get(int index){
    //校验下标值是否合法
    rangeCheck(index);
    //如果下标参数合法，则返回该下标的元素值
    return elementData(index);
}

4)remove(int index):根据下标值删除该位置的元素：

步骤1：将下标位置处往后的所有元素往前面（左边）移动一位。
步骤2：取出index下标位置的原有元素值。
步骤3：计算需要移动的元素个数。
步骤4：将最后一个位置的元素赋值为null,有助于gc
步骤5：将该index位置的原有元素返回。

/**
*  remove(int index):删除指定下标的元素值，并返回原有元素值的源码
*/
public E remove(int index){
    //检测传入参数下标值是否合法：
    rangeCheck(index);
    //记录实际操作的测试
    modCount++;
    //获取到原有元素值：
    E oldValue = elementData(index);
    //计算需要移动的元素个数：
    int numMoved = size - index - 1;
    //判断移动元素的个数是否大于0
    if(numMoved > 0){
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    //将最后一个下标元素赋值为null
    elementData[--size] = null;
    //返回原有元素：
    return oldValue;
}

总结:ArrayList的优缺点

优点:
1、ArrayList底层为数组，并且ArrayList是实现了RandomAccess接口，可以实现随机访问模式，因此查询和修改效率高。
2、可以自动扩容，每次扩容为原来容量的1.5倍
缺点：
1、ArrayList的删除和插入效率较慢.
2、根据查看源码得知，其中的方法indexOf(int index),因为需要遍历整个元素，因此效率不高。
3、线程是不安全的。