【java基础】ArrayList源码解析

矫情吗；* 2023-09-24 22:59 44阅读 0赞

### 文章目录 ###

*  基本介绍
 *  构造器
 *   *  指定初始容量
     *  默认创建
     *  通过集合创建
 *  添加
 *   *  add扩容机制
     *  批量添加addAll
     *  添加指定位置add
     *  添加多个元素到指定位置addAll
 *  删除
 *   *  删除指定元素remove
     *  删除指定索引元素remove
     *  条件删除removeIf
     *  批量删除removeAll
 *  修改
 *   *  修改指定位置set
     *  替换所有满足要求元素replaceAll
 *  一些实用方法
 *  总结

# 基本介绍 #

ArrayList是使用数组存储元素的的集合，能够自动进行扩容。ArrayList的类图如下

![在这里插入图片描述][a4b1356fceec4ec58b8190b4fb090b4b.png]

该类拥有许多操作集合的方法，在这篇文章中将会debug几个常见的方法。

这里先将ArrayList的成员属性以及注释列出来

private static final long serialVersionUID = 8683452581122892189L;
    
        /**
         * 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的几个构造器如下

public ArrayList(int initialCapacity){
        
    	...
    }
    
    public ArrayList() {
        
    	...
    }
    
    public ArrayList(Collection<? extends E> c){
        
    	...
    }

## 指定初始容量 ##

在创建ArrayList的时候指定集合的大小

ArrayList<Integer> list = new ArrayList<>(20);

下面来debug一下这个流程。  
首先进行到构造方法，  
![在这里插入图片描述][efcf81d4a19348e0ba21e54200c715c0.png]

可以发现这个方法就是简单的判断了一下传入的容量是否大于0，如果大于0，那么初始化elementData，如果等于0，那么就将一个空数组赋值给elementData，否则就抛出异常

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

## 默认创建 ##

现在debug一下无参构造器

ArrayList<Integer> list = new ArrayList<>();

![在这里插入图片描述][c0f2f4e030a04a64b8a62344ec730a25.png]

可以看见这个构造器就是将DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA的引用传递给elementData，下面来看一下elementData

![在这里插入图片描述][36b9bafa1a2d4b52bcdeda38a6e38c34.png]

可以发现就是一个空数组，这个数组会在添加元素的时候初始化大小。构造器结束后发现并没有实际创建数组

![在这里插入图片描述][c52fa3cbfc9445239d588ff6143bd5f8.png]

## 通过集合创建 ##

开始debug参数为Collection的构造器

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4));

Arrays.asList会返回一个ArraysList，ArrayList就是Collection的子类，下面为Arrays。asList的源代码

![在这里插入图片描述][0abaa9b568834239a7a95e49765e78d3.png]

下面开始debug

![在这里插入图片描述][08a9520ae6454960ac0b334e4361b9af.png]

我们来分析一下这个代码

if ((size = a.length) != 0)

上面是将a数组的长度赋值给size，并且判断是否为0

if (c.getClass() == ArrayList.class) {
        
    		        elementData = a;
    		    } else {
        
    		        elementData = Arrays.copyOf(a, size, Object[].class);
    		    }

上面代码就判断传入的集合是否为ArrayList，如果是，那么就直接赋值，否则就创建一个和a一样大的数组.

// replace with empty array.
                elementData = EMPTY_ELEMENTDATA;

最后这个就是用来出来传入集合为空的。

# 添加 #

![在这里插入图片描述][943ba4fa207d4815a190103f6c26bed3.png]

可以发现主要有4个方法。add表示添加一个元素，addAll表示批量添加。默认是添加在数组最后一个元素后面的，也可以指定要添加的索引。对于添加到指定索引，这个应该叫修改。

## add扩容机制 ##

我们在上面的构造器中看见了如果没有指定初始容量，那么默认的初始大小就是0。我们来看看ArrayList的扩容机制是怎样的

public static void main(String[] args) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < 11; i++) {
        
                list.add(i);
            }
        }

上面代码会想集合中添加11个元素，先来看添加第一个元素的流程。首先进入add方法，最开始element为空，所以size也为0

![在这里插入图片描述][58f005ec1ed2454794c962b1b31d20f3.png]

然后进入ensureCapacityInternal方法

![在这里插入图片描述][27656a7124a7443681f3cc82e2c8583d.png]

然后进入calculateCapacity方法，这个方法用来计算最小容量的

![在这里插入图片描述][6dd7b69c690c4a95a1b01af79dfa4668.png]

由于我们是通过无参构造器创建的集合，所以elementData就会等于DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，然后返回一个最小容量Math.max(DEFAULT\_CAPACITY, minCapacity)，DEFAULT\_CAPACITY就是10，minCapacity等于1，所以就会返回10。然后进入ensureExplicitCapacity方法

![在这里插入图片描述][01683ddc222f45038ac2765848bbd12e.png]

这个方法就是用来判断集合所需的最小容量是否大于当前集合的容量，在这里，显然是大于的。然后进入grow方法

![在这里插入图片描述][3054da11f54e40c78b4ad0df7b14a50e.png]

这个方法简单来说就是将当前容量扩大为1.5倍，就是下面的语句

int newCapacity = oldCapacity + (oldCapacity >> 1);

然后判断扩大后的容量是否满足最小的容量需求

if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;

最后就是创建新数组，容量更大(一般情况都是1.5倍大小)。然后elementData 执行新数组

elementData = Arrays.copyOf(elementData, newCapacity);

然后一直返回到add方法

![在这里插入图片描述][4db7edd681744890bdac85eb19552a75.png]

此时elementData为容量10的空数组

![在这里插入图片描述][63a1cf4e900b4ac398f80a76e309e867.png]

然后进行数组赋值

![在这里插入图片描述][d97ed0dacdf84175a83a7992a44b9ab7.png]

这样add方法就结束了。现在，我们就可以做一个总结，add方法就是会将元素存储在最后一个元素的后面，但是存储之前会判断一下数组，也就是elementData是否还有足够大的容量。

所以，我们后面存储1-9都不会进行扩容

![在这里插入图片描述][cd6c1d54b2fd477396f4a92d2a208911.png]

当我们存储10的时候，又会将容量扩大为1.5倍(对于添加单个元素)，也就是15

![在这里插入图片描述][238ef66258d0417da0f8964501992471.png]

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

## 批量添加addAll ##

批量添加就是addAll，传入应该Collection，然后就会将传入的Collection添加到当前集合

![在这里插入图片描述][248d896d61f6442cb51a0a06b93a538e.png]

可以发现这个方法非常简单，就是先判断是否还有足够的容量，然后数组复制。对于

ensureCapacityInternal方法，上面说了对于单个元素基本就是扩容1.5倍了，因为扩容1.5倍后添加一个元素肯定没有问题了，但是对于批量添加的，扩容1.5倍不一定够，对于批量添加可能就是扩容为当前size+传入集合大小。

看下面例子

public static void main(String[] args) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < 11; i++) {
        
                list.add(i);
            }
            List<Integer> addList = new ArrayList<>();
            for (int i = 0; i < 100; i++) {
        
                addList.add(i);
            }
            list.addAll(addList);
        }

我们直接添加了100个元素，猜一下现在的list大小为多少？现在的大小为111

![在这里插入图片描述][e96714c966f14bcc85b21b045e1eeb99.png]

原因就是下面的语句

![在这里插入图片描述][5b57de194d5b49529a2a8e2528aafb7e.png]

## 添加指定位置add ##

使用add(int index, E element)，将指定元素插入到此列表中的指定位置。将当前位于该位置的元素(如果有的话)和所有后续元素向右移动(向它们的下标添加1)。

![在这里插入图片描述][45ec00e5b9cf42fc9132c7068449a52d.png]

我们来分析一下这个方法，首先就是检查索引是否越界

![在这里插入图片描述][a4dbe7d9378f4abda7f97d6f35e5f427.png]

然后就是移动数组元素，保存指定值

![在这里插入图片描述][22d71a56478c490a889c79bf0f183dcd.png]

## 添加多个元素到指定位置addAll ##

使用 addAll(int index, Collection<? extends E> c)，传入索引和集合

![在这里插入图片描述][f950de70880f4dfb9ee26b052aa60b40.png]

这个方法和上面基本一样都是数组复制，不细说了

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

# 删除 #

列表删除主要有以下几个方法，下面分别介绍

![在这里插入图片描述][cedc23dacac144c38035a3ba6655dda5.png]

## 删除指定元素remove ##

remove(Object o)，这个方法传入一个元素，从此列表中删除该元素的第一次出现。

![在这里插入图片描述][a737a43929c04b14b9ef643fac42bff9.png]

可以发现这个方法十分简单，就是对所有元素进行比较，如果相等就调用fastRemove这个方法，将要删除元素的索引传过去

![在这里插入图片描述][933ae60ad0854db9af8dc4c9ccad0d6b.png]

上面就是fastRemove，可以发现也是通过数组复制完成的。

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

## 删除指定索引元素remove ##

remove(int index)，传入要删除元素的索引

![在这里插入图片描述][130cbc94aad3412d9ad66949242c8cde.png]

上面就是该方法的源码，可以发现处理也很简单，就是先检查传入的index是否合法，然后保存要删除的值，然后数组移动，最后返回删除的值。

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

## 条件删除removeIf ##

removeIf(Predicate<? super E> filter) 这个方法就会根据传入的条件来进行删除，下面是该方法的源代码

@Override
        public boolean removeIf(Predicate<? super E> filter) {
        
            Objects.requireNonNull(filter);
            // figure out which elements are to be removed
            // any exception thrown from the filter predicate at this stage
            // will leave the collection unmodified
            int removeCount = 0;
            final BitSet removeSet = new BitSet(size);
            final int expectedModCount = modCount;
            final int size = this.size;
            for (int i=0; modCount == expectedModCount && i < size; i++) {
        
                @SuppressWarnings("unchecked")
                final E element = (E) elementData[i];
                if (filter.test(element)) {
        
                    removeSet.set(i);
                    removeCount++;
                }
            }
            if (modCount != expectedModCount) {
        
                throw new ConcurrentModificationException();
            }
    
            // shift surviving elements left over the spaces left by removed elements
            final boolean anyToRemove = removeCount > 0;
            if (anyToRemove) {
        
                final int newSize = size - removeCount;
                for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
        
                    i = removeSet.nextClearBit(i);
                    elementData[j] = elementData[i];
                }
                for (int k=newSize; k < size; k++) {
        
                    elementData[k] = null;  // Let gc do its work
                }
                this.size = newSize;
                if (modCount != expectedModCount) {
        
                    throw new ConcurrentModificationException();
                }
                modCount++;
            }
    
            return anyToRemove;
        }

对于上面的方法，其实思路很简单，第一步就是遍历所有元素，然后将要删除的元素索引放入一个Set。（BitSet后续文章会进行说明）

int removeCount = 0;
            final BitSet removeSet = new BitSet(size);
            final int expectedModCount = modCount;
            final int size = this.size;
            for (int i=0; modCount == expectedModCount && i < size; i++) {
        
                @SuppressWarnings("unchecked")
                final E element = (E) elementData[i];
                if (filter.test(element)) {
        
                    removeSet.set(i);
                    removeCount++;
                }
            }

然后再次遍历集合，用不需要删除的元素来填充删除元素

for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
        
                    i = removeSet.nextClearBit(i);
                    elementData[j] = elementData[i];
                }

最后再将集合中最后x(x表示删除元素的个数)个元素置为null

for (int k=newSize; k < size; k++) {
        
                    elementData[k] = null;  // Let gc do its work
                }
                this.size = newSize;

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

## 批量删除removeAll ##

removeAll(Collection<?> c)，这个方法会删除包含在传入集合中的所有元素。

![在这里插入图片描述][87aad9a1686742b1b5ebd1e2ae392293.png]

该方法会去调用batchRemove方法，下面就直接来看看这个方法

private boolean batchRemove(Collection<?> c, boolean complement) {
        
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try {
        
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
        
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {
        
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {
        
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }

这个方法我们来分解一下，首先是

for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];

可以发现，这个循环就理解为将数组不被删除的元素左移即可，被删除的元素将被覆盖

finally {
        
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {
        
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {
        
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }

上面代码的第一个判断没有用，直接忽略，下面一个判断 w != size，就是为了将集合中最后x(x表示删除元素的个数)个元素置为null。

# 修改 #

修改元素，我们可以使用set和replaceAll方法，下面来进行说明

## 修改指定位置set ##

使用set(int index, E element)，该方法内容如下

![在这里插入图片描述][c2f24365426a437e91465e223aea821d.png]

可以发现就是检查索引是否越界，然后就将指定索引设置为新值，最后返回旧值

## 替换所有满足要求元素replaceAll ##

replaceAll(UnaryOperator operator)，这个方法传入一个lambda表达式即可，会对所有满足条件的元素进行更新

![在这里插入图片描述][68e46f5e4a6844d8ba4a81f645e3df59.png]

该方法很简单，就是一个for循环，核心语句就是如下语句

elementData[i] = operator.apply((E) elementData[i]);

如果看不懂，那就是lambda学的不扎实，建议参考 [一篇文章彻底搞懂lambda表达式][lambda]

# 一些实用方法 #

上面以及介绍完了ArrayList的很多基本操作，现在给出一些ArrayList的一些实用方法及其说明

*  clear方法，该方法会将集合所有元素清空  
    ![在这里插入图片描述][40b3f47666a1470b809e2e40bdc4a2e0.png]
 *  indexOf(Object o) 返回元素第一次出现的索引![在这里插入图片描述][abe22a25c52144948a07cf002416fe9a.png]
 *  contains(Object o) 判断集合中是否包含指定元素![在这里插入图片描述][2ef5f8cf7e9e404e9b31c7b9143fd2d7.png]
 *  toArray(T\[\] a) 将集合转换为数组![在这里插入图片描述][a3b5935f89a14ff99228808378984174.png]
 *  trimToSize() ，调整集合容量为当前元素个数![在这里插入图片描述][2ee7264bf97045f897def577226bfd48.png]

# 总结 #

对于ArrayList，就理解为一个简单的数组即可，该数组会自动扩容(一般为1.5)。

在ArrayList中，其实还有一些方法没有进行说明，例如forEach，sort，clone，retainAll等等，对于这些方法，原理都比较简单，大家经过上面的学习，自行查看源码即可

ArrayList删除读和取，不擅长修改和删除，如果要频繁使用修改和删除请使用LinkedList。

[a4b1356fceec4ec58b8190b4fb090b4b.png]: https://img-blog.csdnimg.cn/a4b1356fceec4ec58b8190b4fb090b4b.png
[efcf81d4a19348e0ba21e54200c715c0.png]: https://img-blog.csdnimg.cn/efcf81d4a19348e0ba21e54200c715c0.png
[c0f2f4e030a04a64b8a62344ec730a25.png]: https://img-blog.csdnimg.cn/c0f2f4e030a04a64b8a62344ec730a25.png
[36b9bafa1a2d4b52bcdeda38a6e38c34.png]: https://img-blog.csdnimg.cn/36b9bafa1a2d4b52bcdeda38a6e38c34.png
[c52fa3cbfc9445239d588ff6143bd5f8.png]: https://img-blog.csdnimg.cn/c52fa3cbfc9445239d588ff6143bd5f8.png
[0abaa9b568834239a7a95e49765e78d3.png]: https://img-blog.csdnimg.cn/0abaa9b568834239a7a95e49765e78d3.png
[08a9520ae6454960ac0b334e4361b9af.png]: https://img-blog.csdnimg.cn/08a9520ae6454960ac0b334e4361b9af.png
[943ba4fa207d4815a190103f6c26bed3.png]: https://img-blog.csdnimg.cn/943ba4fa207d4815a190103f6c26bed3.png
[58f005ec1ed2454794c962b1b31d20f3.png]: https://img-blog.csdnimg.cn/58f005ec1ed2454794c962b1b31d20f3.png
[27656a7124a7443681f3cc82e2c8583d.png]: https://img-blog.csdnimg.cn/27656a7124a7443681f3cc82e2c8583d.png
[6dd7b69c690c4a95a1b01af79dfa4668.png]: https://img-blog.csdnimg.cn/6dd7b69c690c4a95a1b01af79dfa4668.png
[01683ddc222f45038ac2765848bbd12e.png]: https://img-blog.csdnimg.cn/01683ddc222f45038ac2765848bbd12e.png
[3054da11f54e40c78b4ad0df7b14a50e.png]: https://img-blog.csdnimg.cn/3054da11f54e40c78b4ad0df7b14a50e.png
[4db7edd681744890bdac85eb19552a75.png]: https://img-blog.csdnimg.cn/4db7edd681744890bdac85eb19552a75.png
[63a1cf4e900b4ac398f80a76e309e867.png]: https://img-blog.csdnimg.cn/63a1cf4e900b4ac398f80a76e309e867.png
[d97ed0dacdf84175a83a7992a44b9ab7.png]: https://img-blog.csdnimg.cn/d97ed0dacdf84175a83a7992a44b9ab7.png
[cd6c1d54b2fd477396f4a92d2a208911.png]: https://img-blog.csdnimg.cn/cd6c1d54b2fd477396f4a92d2a208911.png
[238ef66258d0417da0f8964501992471.png]: https://img-blog.csdnimg.cn/238ef66258d0417da0f8964501992471.png
[248d896d61f6442cb51a0a06b93a538e.png]: https://img-blog.csdnimg.cn/248d896d61f6442cb51a0a06b93a538e.png
[e96714c966f14bcc85b21b045e1eeb99.png]: https://img-blog.csdnimg.cn/e96714c966f14bcc85b21b045e1eeb99.png
[5b57de194d5b49529a2a8e2528aafb7e.png]: https://img-blog.csdnimg.cn/5b57de194d5b49529a2a8e2528aafb7e.png
[45ec00e5b9cf42fc9132c7068449a52d.png]: https://img-blog.csdnimg.cn/45ec00e5b9cf42fc9132c7068449a52d.png
[a4dbe7d9378f4abda7f97d6f35e5f427.png]: https://img-blog.csdnimg.cn/a4dbe7d9378f4abda7f97d6f35e5f427.png
[22d71a56478c490a889c79bf0f183dcd.png]: https://img-blog.csdnimg.cn/22d71a56478c490a889c79bf0f183dcd.png
[f950de70880f4dfb9ee26b052aa60b40.png]: https://img-blog.csdnimg.cn/f950de70880f4dfb9ee26b052aa60b40.png
[cedc23dacac144c38035a3ba6655dda5.png]: https://img-blog.csdnimg.cn/cedc23dacac144c38035a3ba6655dda5.png
[a737a43929c04b14b9ef643fac42bff9.png]: https://img-blog.csdnimg.cn/a737a43929c04b14b9ef643fac42bff9.png
[933ae60ad0854db9af8dc4c9ccad0d6b.png]: https://img-blog.csdnimg.cn/933ae60ad0854db9af8dc4c9ccad0d6b.png
[130cbc94aad3412d9ad66949242c8cde.png]: https://img-blog.csdnimg.cn/130cbc94aad3412d9ad66949242c8cde.png
[87aad9a1686742b1b5ebd1e2ae392293.png]: https://img-blog.csdnimg.cn/87aad9a1686742b1b5ebd1e2ae392293.png
[c2f24365426a437e91465e223aea821d.png]: https://img-blog.csdnimg.cn/c2f24365426a437e91465e223aea821d.png
[68e46f5e4a6844d8ba4a81f645e3df59.png]: https://img-blog.csdnimg.cn/68e46f5e4a6844d8ba4a81f645e3df59.png
[lambda]: https://blog.csdn.net/m0_51545690/article/details/129298954
[40b3f47666a1470b809e2e40bdc4a2e0.png]: https://img-blog.csdnimg.cn/40b3f47666a1470b809e2e40bdc4a2e0.png
[abe22a25c52144948a07cf002416fe9a.png]: https://img-blog.csdnimg.cn/abe22a25c52144948a07cf002416fe9a.png
[2ef5f8cf7e9e404e9b31c7b9143fd2d7.png]: https://img-blog.csdnimg.cn/2ef5f8cf7e9e404e9b31c7b9143fd2d7.png
[a3b5935f89a14ff99228808378984174.png]: https://img-blog.csdnimg.cn/a3b5935f89a14ff99228808378984174.png
[2ee7264bf97045f897def577226bfd48.png]: https://img-blog.csdnimg.cn/2ee7264bf97045f897def577226bfd48.png