一看就明白的ArrayList源码分析

痛定思痛。 2022-12-03 13:00 178阅读 0赞

`ArrayList`是我们平时开发中最常用的集合之一，本文通过源码来解析一下`ArrayList`的底层实现原理。

##### ArrayList都有哪些特点 #####

*  ArrayList底层是通过定长数组实现的
 *  ArrayList存放的数据是有序且可重复的，且允许存入空值
 *  ArrayList是非线程安全的，在多线程环境下可能会出现`ConcurrentModificationException`
 *  由于ArrayList是基于定长数组实现的，所以可以保证在复杂度为`O(1)`的情况下完成查找数据；但是ArrayList的新增元素和删除元素比较慢
 *  ArrayList默认大小是0，在第一次存放数据时触发扩容，第一次扩容大小为10，之后为原有容量的1.5倍
 *  ArrayList是支持泛型的
 *  不推荐使用迭代器遍历

##### ArrayList的构造函数 #####

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
        // 默认大小为10
        private static final int DEFAULT_CAPACITY = 10;
    
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
        
    	// 上面提到的定长数组
        transient Object[] elementData; // non-private to simplify nested class access
    
        private int size;
    
        // 有参构造函数
        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);
            }
        }
    
        // 无参构造函数，初始化一个空数组
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        //...
    }

`ArrayList`的构造函数很好理解，目的都是为了初始化定长数组：`elementData`。构造函数分为两种：

*  `无参构造函数`，也是我们使用场景最多的一种，会初始化一个空数组，然后在第一次有数据插入的时候进行扩容，第一次扩容大小为10。
 *  `有参构造函数`，如果在已知数据大小的时候推荐使用有参构造函数，可以通过`initialCapacity`参数将`elementData`初始化为`initialCapacity`大小的数组，可以避免扩容，减少资源浪费。

##### 扩容机制 #####

通过阅读源码，我们可以看到，ArrayList的扩容机制是：`扩容为原数组大小的1.5倍`。接下来我们来看一下源码的实现。

/** 计算最小容量 */
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    /** 扩容的入口方法 */
    private void ensureCapacityInternal(int minCapacity) { 
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /** 扩容的核心方法 */
    private void grow(int minCapacity) { 
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 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);
    }
    
    private static int hugeCapacity(int minCapacity) { 
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

##### 查找数据 #####

查找数据的源码很简单，就是根据索引位置去数组里取数据，源码如下。

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

##### 插入数据 #####

对于数组(线性表)的插入方式分为两种，第一种是尾插法，第二种是在指定位置插入。我们来看一下ArrayList是如何实现这两种方法的。

*  尾插法

public boolean add(E e) { 
    	// 先判断是否需要扩容
    	ensureCapacityInternal(size + 1);  // Increments modCount!!
    	// 然后将待插入的元素放在线性表的尾部
    	elementData[size++] = e;
    	return true;
    }

其实尾插法实现起来很简单，第一步：检查数组是否有足够的空间插入新数据；第二步：在数组的尾部插入新数据。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center]

*  指定位置插入

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

这种插入方法相比尾插法稍微复杂一点，第一步：判断是否有足够的空间插入新数据；第二步：将指定位置后的所有数据后移；第三步：在指定位置插入元素。这种插入方法操作的时间复杂度为`O(N)`，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二种插入方法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center 1]

##### 删除数据 #####

不同于插入操作，ArrayList没有无参删除方法。所以其只能删除指定位置的元素或删除指定元素，这样就无法避免移动元素（除非从元素序列的尾部删除）。

*  删除指定位置元素

public E remove(int index) { 
        rangeCheck(index);
    
        modCount++;
        // 返回已删除的元素
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
        	// 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个元素置空，并将 size 值减1 
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

*  删除指定元素

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;
                }
        }
        // 如果数组里没有这个数据，返回false
        return false;
    }
    
    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
    }

*  遍历时删除

对于遍历时删除数据的操作应该尽量避免，如果需要在遍历的过程中删除数据，正确的做法使用迭代器提供的删除方法，而不是直接删除。至于为什么，我们可以在源码中寻找到答案：

private class Itr implements Iterator<E> { 
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
    
        Itr() { }
    
        public boolean hasNext() { 
            return cursor != size;
        }
    
        @SuppressWarnings("unchecked")
        public E next() { 
        	// 这里是重点，并发删除检查
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
    
        public void remove() { 
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
    
    	// 省略中间代码
    
        final void checkForComodification() { 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

##### 遍历数据 #####

ArrayList实现了 `RandomAccess` 接口（该接口是个标志性接口），表明它具有随机访问的能力。ArrayList 底层基于数组实现，所以它可在常数阶的时间内完成随机访问，效率很高。对 ArrayList 进行遍历时，推荐下面这种方式：

for (int i = 0; i < list.size(); i++) { 
        list.get(i);
    }

至于为什么不推荐foreach是因为foreach最终会变成迭代器遍历。

##### 缩容机制 #####

考虑一种情况，我们通常会往ArrayList中添加大量元素，然后移除大量元素，此时底层的数组就会有很多空闲空间浪费掉，因为ArrayList没有自动缩容机制，这些空间又不能自动释放掉，但是ArrayList提供了一个方法来解决这个问题：

/** 将数组容量缩小至元素数量 */
    public void trimToSize() { 
        modCount++;
        if (size < elementData.length) { 
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

##### 总结 #####

以上内容通过对ArrayList的构造方法、扩容机制、遍历、添加和删除元素等常用API结合源码做了解读，看起来也不难。ArrayList是最常用的集合之一，也是高频面试题，通过本文可以对ArrayList有一个更全面、深刻的理解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3e2d253c42a04d0a8cb981a28a23156f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdjaGVuZ21pbmcx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/98b52a35f35b43488b5d996eb876b692.png