ArrayList 的使用及原理，面试必问的知识点

矫情吗；* 2021-08-27 11:14 385阅读 0赞

点击上方 [Java后端][Java]，选择 设为星标

优质文章，及时送达

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

为后面的面试做准备，今天复习一下 ArrayList ，这是必问的知识点 ![format_png][]

在开始之前给大家说一下，昨天发布了[《今天面试了吗》][Link 1]系列文章第一篇，看来大家分享喜欢此系列，会继续更新。大家可以标星（置顶）本公众号：Java后端，获取后续更新。

ArrayList属于Collection集合类大家族的一员，是分支List中的主力军之一。ArrayList使用非常广泛，无论是在数据库表中查询，还是网络信息爬取都需要使用，所以了解ArrayList的原理就十分重要了（本文中若无特地说明，ArrayList版本基于JDK 1.8）。

### **ArrayList的继承关系** ###

![format_png 1][]

### **如何定义一个ArrayList？** ###

ArrayList有三个**构造函数**：① 无参；②参数为整数；③参数为集合。

举个栗子：

//默认创建一个ArrayList集合
    ArrayList<String> a1 = new ArrayList<>();
    //创建一个初始长度为12的ArrayList集合
    ArrayList<String> a2 = new ArrayList<>(12);
    //将其他类型的集合转为ArrayList
    ArrayList<String> a3 = new ArrayList<>(new HashSet());

我们读ArrayList构造函数的源码之前，先看看ArrayList的**属性**的情况：

/**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;

可以看到，ArrayList是非线程安全的容器，底层实现是Object\[\]，数据会添加到ArrayList的**elementData**数组中，而且默认容量DEFAULT\_CAPACITY为10。但其实**从jdk7之后，ArrayList的默认容量就是0了**，而DEFAULT\_CAPACITY在**扩容**的过程中才会用到。

接下来我们来看看定义ArrayList的**三种**构造函数。

#### ArrayList有参构造函数——入参类型为整型 ####

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

#### 可以看到，如果传入正整数，则elementData数组容量初始化为initialCapacity；如果传入0，则elementData数组赋值为一个空数组。可能有读者发现了ArrayList类中有两个属性定义为空数组。 ####

#### **为什么ArrayList会定义两个空数组？** ####

其实注释已经给出了官方解释（下有拙译）：

/**
         * Shared empty array instance used for empty instances.
         此共享空数组实例用于空实例
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /*
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         此共享空数组用于默认大小的空实例。我们将此与EMPTY_ELEMENTDATA区分开，以了解填充第一个元素时需要多少（空间）
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

简单说，EMPTY\_ELEMENTDATA与DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA**在功能上有不同的含义**，前者单纯用于赋值为空数组，后者是给elementData数组初始化的。

#### ArrayList有参构造函数——入参类型为集合类 ####

####     ####

public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

#### 可以看到，只要是实现了Collection的集合类，都会调用toArray()将集合类中的数组赋给elementData。而且toArray()返回的数组类型不是Object\[\]类型时…等等，**toArray()返回的数组类型为什么会不是Object\[\]类型**？举个栗子： ####

public class Test<E> extends ArrayList {
        @Override
        public Integer[] toArray() {
            return new Integer[]{0, 23};
        }
    
        public static void main(String[] args){
            Object[] elementData = new Test<Integer>().toArray();
            System.out.println(elementData.getClass());
            System.out.println(Object[].class);
            System.out.println(elementData.getClass() == Object[].class);
        }
    }

运行结果为：

class [Ljava.lang.Integer;
    class [Ljava.lang.Object;
    false

好，我们接着说当toArray()返回的数组类型不是Object\[\]类型时，会调用Arrays.copyOf()将原数组拷贝到新数组中去，而且类型还定义为Object类：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

#### ArrayList无参构造函数 ####

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

在这里，我们可以看到**JDK 1.8之后的ArrayList的默认容量为0**。

如果ArrayList的容量为0，还可以添加数据吗？

当然可以，通过扩容机制变可以扩充ArrayList的容量：

public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }

在这里我们可以看到，如果elementData数组依然为

DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA（即初始状态），则通过**ensureExplicitCapacity()方法将ArrayList的容量扩充为10**（DEFAULT\_CAPACITY）。

为什么无参构造函数中对ArrayList容量的初始化改变了呢？

虽然JDK 1.8中的ArrayList默认容量为0，但在JDK1.6的无参构造函数的ArrayList默认容量为10：

public ArrayList() {
      this(10);
    }

**个人认为**，JDK 1.8中延迟初始化ArrayList的实际容量，应该是考虑如果一开始就初始化为10，那么大小为10的数组中存的全部是null，这种数组多了也会占用大量的空间。所以这也是**为了节省不必要浪费的空间**，体现了懒加载的思想。

### **怎么使用ArrayList？** ###

既然我们已经知道了怎么去定义一个ArrayList，接下来就是要使用ArrayList了，而ArrayList提供的方法中常见的有：add、addAll、set、get、remove、size、isEmpty等。

因为ArrayList的一些方法会涉及到数据位置的变换，为了更直观地感受这些变化，在这里我们来举个栗子：

疫情以来，想必很多朋友已经很想念那些美食了。咱们在这里报一下菜单吧：

ArrayList<String> list = new ArrayList<>();
    list.add("双皮奶");
    list.add("云吞面");
    list.add("煲仔饭");
    list.add("叉烧包");
    list.add("艇仔粥");
    list.add("糯米鸡");

也就是说，elementData数组中有这些数据：

![format_png 2][]

如果想在菜单中加入“小笼包”，让我们看看这个操作在源码中是怎样的过程：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

首先，会先通过ensureCapacityInternal(size+1)检查elementData数组的容量是否充足，然后再将数据放入数组中，我们来看看ArrayList是怎么进行容量检查。

**ensureCapacityInternal()**

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

在这个方法中，确定elementData数组是不是空数组，如果是的话，将形参minCapacity赋值为10（DEFAULT\_CAPACITY)，然后进入ensureExplicitCapacity()方法。

**ensureExplicitCapacity()**

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

此方法中的modCount变量是从AbstractList继承下来的，用于记录对ArrayList对象操作的次数：

protected transient int modCount = 0;

可以看到当形参minCapacity的数值比当前的elementData数组的长度大，则要调用**grow()方法进行扩容**操作。

**grow()**

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            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);
        }

可以看到，扩容规则为“**数组当前的容量+（数组当前的容量/2）**”，即扩容后的数组容量为之前数组容量的1.5倍。当然，如果超过了最大值，在hugeCapacity()方法中会对其进行处理。

**hugeCapacity()**

private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0)
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

如果形参minCapacity大于MAX\_ARRAY\_SIZE，则赋值为Integer.MAX\_VALUE，实际上MAX\_ARRAY\_SIZE与Integer.MAX\_VALUE相差**8**。

回到我们的例子中，elementData数组的容量为10，而数组中的数据只有6个，所以"小笼包"的加入并不会引起扩容，此时elementData数组中的数据如下：

![format_png 3][]

与add()类似的方法还有：

**add(0, “炸鲜奶”)**

此方法将数组中的元素各自往后移动一位之后，再将“炸牛奶”放到第一个位置上：

![format_png 4][]

**addAll(1, list…“金钱肚”,“蒸凤爪”,“鲜虾饺”)**

将"金钱肚",“蒸凤爪”,"鲜虾饺"放到"炸牛奶"之后，那么数组第二个位置后的元素都需要往后移动三位，而且明显看到数组的容量已经不够了，按规则数组会扩容到16。

![format_png 5][]

如果需要在既定位置安插数据，则需要通过rangeCheckForAdd()方法判断数组是否越界。

**rangeCheckForAdd()**

private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

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

在add()方法过程中，如果要在数组中（除了数组末尾）安插一个数据，需要将安插位置之后的数据往后移动一位。但如果需要替换数组某个位置的数据，则**需要找到对应位置，并替换元素**即可。

public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

在set()方法执行过程中，需要进行rangeCheck()数组范围检查之后，再将**原数据取出用于返回，并在该数组位置替换新数据**，如将"炸鲜奶"替换为"普洱茶"：

![format_png 6][]

ArrayList中的get()方法获取数据的方式也很简单，只需先判断传入的数组下标是否越界，并**通过下标查找**，转换类型即可。

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

其中的elementData()方法的实现如下：

E elementData(int index) {
      return (E) elementData[index];
    }

### remove(int index)和remove(Object o) ###

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

**通过下标选择删除的元素的remove(int index)方法中**，在删除元素之前，需要先对下标进行范围检查rangeCheck()，然后再计算出需要移动的元素个数，通过arraycopy()即数组复制的方式，将既定位置之后的元素都向前移动一位，最后再设置elementData\[size-1\]为null，使**GC**回收对其起作用。

接下来我们来看后者：

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

**通过值对象删除元素的remove(Object o)方法中**，程序将null单独进行处理，因为null是一种状态，不属于任何类型的值。在选中了既定值对象对应的下标值之后，删除操作将会在fastRemove()方法中进行，而fastRemove()方法中的操作过程就跟remove(int index)类似，在此就不赘述了。

举个栗子，如果将"云吞面"删除了，那么菜单会变成：

![format_png 7][]

### 其他方法 ###

上文对ArrayList的增删改查方法进行了介绍，接下来简单介绍一下ArrayList的其他方法：

*  **size()**：用于获取集合的长度，可通过定义在ArrayList中的私有变量size得到。
 *  **isEmpty()**：用于确定ArrayList是否为空，可通过定义在ArrayList中的私有变量size得到。
 *  **contains(Object o)**：用于确定ArrayList是否包含某个元素，先通过遍历底层数组elementData，再通过equals或==判断。
 *  **clear()**：将ArrayList里的数据清空，通过遍历底层数组elementData，将数组里的值都设置为null。

### **结语** ###

本文主要对ArrayList原理进行介绍，着重介绍了ArrayList的增加、扩容机制、获取元素、修改元素、删除时元素移动的方式。

如果本文对你的学习有帮助，请给一个赞吧，这会是我最大的动力~

**参考资料：**

Java集合 ArrayList原理及使用

https://www.cnblogs.com/LiaHon/p/11089988.html

ArrayList的初始容量现在为0，不再是10了

https://www.jianshu.com/p/6d07246b11af

博文征集：如果有原创博文，欢迎投稿到公众号：Java后端，投稿请联系邮箱：webresource666@163.com

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

\-END-

如果看到这里，说明你喜欢这篇文章，请**转发****、点赞**。同时标星（置顶）本公众号可以第一时间接受到博文推送。

**推****荐****阅****读**

***1. ***[今天，我去面试了][Link 2]

***2. ***[JVM 深入解析（12000 字总结）][JVM _12000]

***3.*** [新版任你发，我用 Java 8][Java 8]

***4. ***[写出高质量 SQL 的 30 条建议][SQL _ 30]

![format_png 8][]

[Java]: https://blog.csdn.net/qq_37217713/article/details/101445094
[format_png]: /images/20210730/b26a624402c947078af577c10b7fb0eb.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e53a9f979dabf9f42435d6ab47cc02b3e94c0c5d310f8c269159d42dc3ea4fb460add8573&idx=1&mid=2247492650&scene=21&sn=1f1fcba0db35b3803f7af4cffa90015a#wechat_redirect
[format_png 1]: /images/20210730/bfbbd45763d14ae6b6abc85fb6fadf16.png
[format_png 2]: /images/20210730/11682bf122f54f6caa263be93c2520b0.png
[format_png 3]: /images/20210730/db5ee64400a840b8b7188193b220e996.png
[format_png 4]: /images/20210730/2a0515f4945342f281ba6812c61e6e04.png
[format_png 5]: /images/20210730/afe53b179bb34cc684f01c2ebc8d6238.png
[format_png 6]: /images/20210730/f626b7171b834dd79a0c28d609489f16.png
[format_png 7]: /images/20210730/95899aa0bf774a0ab3fac36faad4b34c.png
[Link 2]: https://blog.csdn.net/qq_37217713/article/details/105236691
[JVM _12000]: https://blog.csdn.net/qq_37217713/article/details/105236690
[Java 8]: https://blog.csdn.net/qq_37217713/article/details/105213193
[SQL _ 30]: https://blog.csdn.net/qq_37217713/article/details/105190544
[format_png 8]: /images/20210730/4cc63bdd1cb04030b5bb24d3dcb3ae3b.png