ArrayList源码解析

旧城等待， 2021-09-22 13:36 454阅读 0赞

ArrayList是基于List 接口，大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。下面我们来分析ArrayList的源代码，ArrayList继承体系结构如下：

public class ArrayList<E> extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList类继承AbstractList类并实现了List、Cloneable和Serializable接口，因而ArrayList具有克隆和序列化的功能。

### 属性 ###

//默认初始容量

private static final int DEFAULT\_CAPACITY = 10;

//用于空实例的共享空数组实例

private static final Object\[\] EMPTY\_ELEMENTDATA = \{\};

//用于默认大小的空实例的共享空数组实例。与EMPTY\_ELEMENTDATA数组的区别在于当第一个元素被加入进来的时候,它知道扩大多少

private static final Object\[\] DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA = \{\};

//elementData数组用来存储ArrayList中的元素

transient Object\[\] elementData;

//ArrayList中存储的元素的个数

private int size;

### 构造函数 ###

ArrayList提供了三种方式的构造器：

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

源码的注释是构造一个初始容量为 10 的空列表。即当我们不提供参数而new一个对象时，底层的数组就是直接用长度为10的空实例数组DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA进行实例化。难点就是DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA的长度我们还不知道，关于如何使用DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA构造了一个初始容量为10的空列表在下面的add(E e)函数源码的介绍中就会知道答案了。

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中情况进行了处理。当参数小于0时抛异常；当参数等于0时；用空实例数组对象EMPTY\_ELEMENTDATA来初始化底层数组elementData。

public ArrayList(Collection<? extends E> c) {  
        elementData = c.toArray();  
        size = elementData.length;  
        // c.toArray might (incorrectly) not return Object[] (see 6260652)  
        if (elementData.getClass() != Object[].class)  
            elementData = Arrays.copyOf(elementData, size, Object[].class);  
    }

将容器Collection转化为数组赋给数组elementData，还对Collection转化是否转化为了Object\[\]进行了检查判断。如果Collection为空，则就将空的实例数组对象EMPTY\_ELEMENTDATA赋给了elementData。

## 常用方法 ##

### 修改 ###

// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。  
    public E set(int index, E element) {  
        RangeCheck(index);  
      
        E oldValue = (E) elementData[index];  
        elementData[index] = element;  
        return oldValue;  
    }

### 添加 ###

// 将指定的元素添加到此列表的尾部。  
    public boolean add(E e) {  
        ensureCapacityInternal(size + 1);   
        elementData[size++] = e;  
        return true;  
    } 
    
    // 将指定的元素插入此列表中的指定位置。  
    // 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。  
    public void add(int index, E element) {  
        //位置有效性检查
        rangeCheckForAdd(index);
        //添加修改次数以及判断是否需要扩张数组长度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //完成数组自身从index开始的所有元素拷贝到index+1开始且长度为size-index的位置上。
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    } 
    
    // 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。  
    public boolean addAll(Collection<? extends E> c) {  
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacityInternal(size + numNew);  // Increments modCount 
        //将a中的所有元素拷贝到数组elementData最后一个元素的后面 
        System.arraycopy(a, 0, elementData, size, numNew);  
        size += numNew;  
        return numNew != 0;  
    } 
    
    // 从指定的位置开始，将指定collection中的所有元素插入到此列表中。  
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);  
        Object[] a = c.toArray();  
        int numNew = a.length;  
        ensureCapacityInternal(size + numNew);  // Increments modCount  
    
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        System.arraycopy(a, 0, elementData, size, numNew);  
        size += numNew;  
        return numNew != 0;  
    }

### 读取 ###

public E get(int index) {
            rangeCheck(index);//有效性检查
            return elementData(index);
        }

### 删除 ###

ArrayList提供了根据下标或者指定对象两种删除方法，如下：

// 删除此列表中指定位置上的元素。
    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;
        }
    // 移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。
    public boolean remove(Object o) {
    // 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。
            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;
        }

从源码中可以看到，无论指定对象o是否为null，都是在ArrayList中找到与此第一个相等的元素的位置，然后调用fastRemove(index)来进行移除；如果没有找到指定对象o的位置，则返回false，表示没有移除成功。

需要注意的是从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向前移动一个位置。remove（int index）从代码就可以看到，而 remove(Object o)则是调用了fastRemove(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
    }

可以看到，我们需要左移的功能是在这里实现的

### 清除 ###

//直接将数组中的所有元素设置为null即可，这样便于垃圾回收
    public void clear() {
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

### 扩容 ###

扩容需要要重点说明的一个，在添加方法中涉及到ensureCapacityInternal（）方法，源码如下：

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
    }

如果elementData==DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，则就用默认容量10来进行开辟空间。这里的源码就解释了DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA数组和EMPTY\_ELEMENTDATA数组的区别之所在。也说明了当我们用无参构造函数来实例化一个对象时，确实是构造的一个长度为10的数组对象。

接下来再看下ensureExplicitCapacity（）方法

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

接着看grow（）方法

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            /*
            下面两个if的作用为处理两种情况：
            1）第一种情况为：如果newCapacity扩展的过小。则应该至少扩张到所需的空间大小minCapacity
            2）第二种情况为：newCapacity扩张的过大，如果过大，则用Integer.MAX_VALUE来代替。
             */
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            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);
        }

从源码中可以看到，此函数的功能就是一个数组的扩容。一般情况下是扩展到原来数组长度的1.5倍。

但是，由于扩张1.5倍可能和我们的需要不一致，即可能太小，也可能太大。因此，就有了源码中的两个if条件的处理。即如果扩张1.5倍太小，则就用我们需要的空间大小minCapacity来进行扩容。如果扩张1.5倍太大或者是我们所需的空间大小minCapacity太大，则进行Integer.MAX\_VALUE来进行扩容。

参考：

[http://zhangshixi.iteye.com/blog/674856][http_zhangshixi.iteye.com_blog_674856]

[https://blog.csdn.net/u010412719/article/details/51108357][https_blog.csdn.net_u010412719_article_details_51108357]

[https://blog.csdn.net/ns\_code/article/details/35568011][https_blog.csdn.net_ns_code_article_details_35568011]

[http_zhangshixi.iteye.com_blog_674856]: http://zhangshixi.iteye.com/blog/674856
[https_blog.csdn.net_u010412719_article_details_51108357]: https://blog.csdn.net/u010412719/article/details/51108357
[https_blog.csdn.net_ns_code_article_details_35568011]: https://blog.csdn.net/ns_code/article/details/35568011