深入探索ArrayList源码解析

向右看齐 2022-12-27 02:22 209阅读 0赞

> ArrayList集合是平时开发最常用的集合之一，它是一种线性结构，其底层是用数组实现的，相当于一个动态数组。下面来一起看看ArrayList的一些常用方法是如何实现的。

### 文章目录 ###

*   *  ArrayList继承关系
     *   *  继承实现的接口和类
         *  类图
     *  源码解析
     *   *  ArrayList属性
         *  构造方法
         *  trimToSize()方法
         *  size()方法
         *  isEmpty()方法
         *  indexOf(Object o)方法
         *  lastIndexOf(Object o)方法
         *  get(int index)方法
         *  set(int index, E element)方法
         *  add(E e)方法
         *  add(int index, E element)方法
         *  remove(int index)方法
         *  remove(Object o)方法
         *  clear()方法
     *  总结

--------------------

## ArrayList继承关系 ##

### 继承实现的接口和类 ###

*  ArrayList继承于AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable这些接口。
 *  ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
 *  ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
 *  ArrayList 实现了Cloneable接口，可以调用Object.clone方法返回该对象的浅拷贝
 *  ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

**ArrayList类源码**

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

### 类图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]

## 源码解析 ##

### ArrayList属性 ###

ArrayList底层其实是一个数组实现的，是一个默认长度为10的数组，当存放元素到达数组长度时，ArrayList会对数组进行扩容操作，即扩大数组的容量，扩容后的数组是原数组的1.5倍容量。

但删除元素后不会自动减少数组容量，如果需要减少，可以手动调用trimToSize()方法

**注意：ArrayList线程不安全，如果是多线程，可以选择Vector。**

//序列号
    private static final long serialVersionUID = 8683452581122892189L;
    
    //定义初始化集合(数组)的长度
    private static final int DEFAULT_CAPACITY = 10;
    
    //定义一个空数组，当ArrayList元素为空时，返回该数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    //定义一个空数组，ArrayList默认的返回
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    //存放元素的数组，不能被序列化，transient修饰的内容不能被序列化
    transient Object[] elementData; // non-private to simplify nested class access
    
    //数组中存储数据的数量
    private int size;

### 构造方法 ###

ArrayList源码中有三个构造方法，分别为带int类型参数构造方法、无参构造方法、Collection<? extends E>类型参数构造方法。

**int类型参数构造方法**

传入的参数initialCapacity为初始化数组的容量。

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);
        }
    }

如果传入的参数initialCapacity大于0，则创建一个初始容量为initialCapacity大小的空数组。

如果传入的参数等于0，将上述定义的EMPTY\_ELEMENTDATA空数组赋值给elementData。

当传入的参数非法(小于0)，则抛出异常。

**无参构造方法**

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

无参构造方法，将上述定义的DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA空数组赋值给elementData。

无参构造方法，初始化数组长度为0，通过第一次调用add方法后，对数组长度进行扩容至10。

**Collection<? extends E>类型参数构造方法**

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 判断c.toArray()返回的数组是否为Object类型数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 把空数组EMPTY_ELEMENTDATA赋值给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

通过上述的继承关系图，可以知道Collection是一个集合。

*  将参数转换为数组，赋值给elementData
 *  判断数组的长度是否为0
 *  如果不等于0，如果c.toArray()返回的数组不是Object类型数组，则通过Arrays.copyOf()函数转换为Object类型数组，并重新赋值给elementData。
 *  如果等于0，则把上述定义的EMPTY\_ELEMENTDATA空数组赋值给elementData。

### trimToSize()方法 ###

上面提到过ArrayList集合删除元素不会自动减小数组的容量，但是我们可以通过调用trimToSize()方法来减小数组的容量。

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

trimToSize方法先对当前数组长度和当前数组存放的元素数量进行比较。

如果元素数量小于当前数组长度，则通过Arrays.copyOf()函数对数组elementData的容量进行调整，减小数组的容量。

### size()方法 ###

定义属性时，定义了一个size属性，用于保存数据的数量，所以这里size方法返回的为集合中的元素个数。

public int size() {
    	return size;
    }

### isEmpty()方法 ###

isEmpty()方法用于判断集合中元素数量是否等于0，即判断集合是否为空。为空返回true，否则返回false。

public boolean isEmpty() {
      	return size == 0;
    }

### indexOf(Object o)方法 ###

indexOf()方法查找元素 o 在集合中的位置索引，返回第一次查找到的位置索引。如果没有查找到则返回-1。

public int indexOf(Object o) {
    	// 判断参数o是否为空
       	if (o == null) {
       		//为空，则遍历数组，判断数组中是否有元素为空，有则返回该元素下标
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
        	//如果不为空，则遍历数组，使用equals判断是否和o相等，相等则返回相等元素的下标
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        // 如果没有找到，则返回-1
        return -1;
    }

先判断查找的元素o是否为空，如果为空，遍历数组，判断数组中是否存在空元素，存在则返回数组中第一个空元素的下标。

如果查找元素o不为空，遍历数组，使用equals关键字比较数组中元素是否和元素o相等，返回第一个相等元素的下标。

如果没有找到，则返回-1。

### lastIndexOf(Object o)方法 ###

lastIndexOf()方法和indexOf()方法一样，都是查找元素o是否存在集合中。

区别在与lastIndexOf()方法，返回最后一次查找到的位置索引。indexOf()方法返回第一次查找到的位置索引。

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;
    }

上述代码可以看出，lastIndexOf()方法是从数组的最后一个元素开始往前查找的，查找到之后即返回该元素的下标，所以返回的为数组中最后一次出现该元素的位置索引。

相反indexOf()方法，是从数组的第一个元素开始往后查找的，所以返回的为数组中第一次出现该元素的位置索引。

**lastIndexOf()和indexOf()方法，查找的时间复杂度都为O(n)。**

### get(int index)方法 ###

get()方法，返回集合中指定位置的元素。

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

get()方法，首先会使用**rangeCheck()** 方法判断一下传递的索引是否越界，如果传递的索引值，大于数组的长度，则会抛出异常。

**rangeCheck()方法源码如下：**

private void rangeCheck(int index) {
      	if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

如果传递的索引值没有问题，则返回该索引值在数组中对应的元素。

### set(int index, E element)方法 ###

set()方法修改下标为index位置的元素为element，返回修改之前的元素值。

public E set(int index, E element) {
    	//判断index索引是否越界
       	rangeCheck(index);
    	
    	//保存index索引位置的值
        E oldValue = elementData(index);
        //修改index索引位置的值
        elementData[index] = element;
        //返回修改之前的值 	
        return oldValue;
    }

set()方法和get方法一样，会先调用**rangeCheck()** 方法判断一下传递的索引是否越界。

把index索引位置的值先保存，之后把index索引位置的值改为element，最后返回index索引位置修改之前的元素值。

### add(E e)方法 ###

add()方法添加一个元素在集合的末尾。

public boolean add(E e) {
    	//判断是否需要对数组进行扩容
       	ensureCapacityInternal(size + 1);
       	//将元素e添加在数组的末尾  
        elementData[size++] = e;
        //添加成功返回true
        return true;
    }

先回调用ensureCapacityInternal()方法判断是否需要对数组进行扩容，因为需要添加一个元素，所以这里参数为size+1。之后将元素添加在数组末尾，size数组内容数量++。

**添加元素在数组最后，元素不用移动，所以时间复杂度为O(n)。**

**ensureCapacityInternal()方法源码如下：**

private void ensureCapacityInternal(int minCapacity) {
    	//判断数组是否为空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//取最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    	//判断数组是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }

如果集合为空，数组容量取初始容量和minCapacity之间的最大值。

ensureExplicitCapacity()方法判断是否需要对数组进行扩容

private void ensureExplicitCapacity(int minCapacity) {
      	modCount++;
    
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

如果传递的参数减去数组的长度大于0，则需要扩容，grow()方法对数组进行扩容，扩容后的数组长度为原数组的1.5倍。

private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //扩容原来的1.5倍
        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);
    }

### add(int index, E element)方法 ###

add(int index, E element)方法，添加元素到index位置。

public void add(int index, E element) {
      	rangeCheckForAdd(index);
    
    	//是否需要对数组进行扩容
        ensureCapacityInternal(size + 1);
        //插入位置后的元素，依次往后移动一个位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //插入元素
        elementData[index] = element;
        size++;
    }

在判断是否需要对数组进行扩容操作后，使用了**System.arraycopy()** 方法对插入位置后的元素依次往后移动一个位置，之后在index位置插入元素。

**System.arraycopy()** 方法作用为：**从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。**

### remove(int index)方法 ###

remove(int index)方法删除指定索引位置的元素，返回删除的元素值。

public E remove(int index) {
    	//判断索引是否合法
      	rangeCheck(index);
    
        modCount++;
        //保存删除的元素值
        E oldValue = elementData(index);
    
    	//数组元素数量-1
        int numMoved = size - index - 1;
        //如果删除后集合中元素数量 > 0
        if (numMoved > 0)
        	//把索引位置后的元素依次往前移动一个位置
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将数组最后一个元素置为空，元素数量-1
        elementData[--size] = null; // clear to let GC do its work
    
    	//返回删除的元素值
        return oldValue;
    }

调用rangeCheck()方法，判断位置索引是否合法。

如果删除后集合中元素数量大于0，则把索引位置后的元素依次往前移动一个位置。

将数组最后一个元素置为空，元素数量减一，返回删除的元素值。

### remove(Object o)方法 ###

remove(Object o)方法删除指定元素，如果指定元素出现多次，则只删除第一次出现的元素。删除成功返回true。

public boolean remove(Object o) {
    	//判断删除的元素是否为空
      	if (o == null) {
      		//如果为空，找到数组中第一个元素为空的下标
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                	//删除下标为index的元素
                    fastRemove(index);
                    return true;
                }
        } else {
        	//如果不为空，找到数组中第一个和元素o相等的元素下标
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

remove(Object o)方法逻辑和indexof()方法很像。fastRemove(index)方法，删除下标为index的元素，源码如下。

private void fastRemove(int index) {
      	modCount++;
        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
    }

### clear()方法 ###

clear()方法，清空集合中所有元素。

public void clear() {
       	modCount++;
    
        // 遍历，把集合中所有元素置为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
    
        size = 0;
    }

--------------------

## 总结 ##

*  ArrayList底层是数组实现的，会进行动态扩容，是一种线性结构。
 *  根据下标查找和访问元素时效率会很高。
 *  add()方法添加元素，是在数组的最后进行添加元素，所以效率也很高。
 *  在中间插入和删除元素时需要移动元素，所以效率比较低。
 *  线程不安全。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]: /images/20221120/f7908ab6b8c74ce9b904f5b3c1459edc.png