jdk1.8集合框架源码解析（四）ArrayList源码解析

阳光穿透心脏的1/2处 2022-03-31 15:54 297阅读 0赞

ArrayList是我们日常开发中最常用的集合类甚至没有之一，了解其底层源码非常重要，以下源码基于

jdk1.8.0\_144版本

## 一、ArrayList的数据结构 ##

集合框架数据结构是其灵魂，理解数据结构才能更好理解ArrayList的实现思路。

ArrayList的数据结构如下：

![20190104092303561.png][]

ArrayList其底层是一个动态数组，存储的元素是所有对象即Object,下面看ArrayList是如何实现动态数组的。

## 二、ArrayList的继承体系 ##

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

ArrayList实现了List接口、RandomAccess（可随机访问）、Cloneable（可拷贝）、Serializable（可序列化）。

继承了AbstractList

### 2.1 实现RandomAccess接口的作用： ###

RandomAccess是List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

将操作随机访问列表的最佳算法（如 ArrayList）应用到连续访问列表（如 LinkedList）时，可产生二次项的行为。如果将某个算法应用到连续访问列表，那么在应用可能提供较差性能的算法前，鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof，如果需要保证可接受的性能，还可以更改其行为。

现在已经认识到，随机和连续访问之间的区别通常是模糊的。例如，如果列表很大时，某些 List 实现提供渐进的线性访问时间，但实际上是固定的访问时间。这样的 List 实现通常应该实现此接口。实际经验证明，如果是下列情况，则 List 实现应该实现此接口，即对于典型的类实例而言，此循环：

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

的运行速度要快于以下循环：

for (Iterator i=list.iterator(); i.hasNext(); ){
        i.next();
    
     }

### 2.2 实现Cloneable接口的作用： ###

此类实现了 `Cloneable`接口，以指示 `Object.clone()` 方法可以合法地对该类实例进行按字段复制。

如果在没有实现 `Cloneable`接口的实例上调用 Object 的 clone 方法，则会导致抛出 `CloneNotSupportedException` 异常。

按照惯例，实现此接口的类应该使用公共方法重写 Object.clone（它是受保护的）。请参阅 `Object.clone()`，以获得有关重写此方法的详细信息。

注意，此接口*不* 包含 clone 方法。因此，因为某个对象实现了此接口就克隆它是不可能的。即使 clone 方法是反射性调用的，也无法保证它将获得成功。

### 2.3实现Serializable接口的作用： ###

类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。可序列化类的所有子类型本身都是可序列化的。序列化接口没有方法或字段，仅用于标识可序列化的语义。

## 三、ArrayList的field ##

/**
         *
         * 为保证 serialVersionUID 值跨不同 java 编译器实现的一致性，序列化
         * 类必须声明一个明确的 serialVersionUID 值。
         * 还强烈建议使用 private 修饰符显示声明 serialVersionUID（如果可能），
         * 原因是这种声明仅应用于直接声明
         * 类 -- serialVersionUID 字段作为继承成员没有用处
         *
         */
        private static final long serialVersionUID = 8683452581122892189L;
    
        /**
         * 默认初始容量
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * 空的实例.
         */
        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 = {};
    
        // 元素数组
        transient Object[] elementData; // non-private to simplify nested class access
    
        //元素的个数
        private int size;
        
        //分配数组的最大值
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

elementData，类型为Object\[\]的数组，用于存放实际元素，并且被标记为transient，也就意味着在序列化的时候，此字段是不会被序列化的

protected transient int modCount = 0;

modCount 是从其父类继承来的，已*从结构上修改* 此列表的次数。

## 四、ArrayList的构造函数 ##

//构造一个空的list其size为DEFAULT_CAPACITY 10
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        //构造一个空的list根据指定的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);
            }
        }
    
        //传入一个Collection初始化ArrayList
        public ArrayList(Collection<? extends E> c) {
            //把给定的集合转成Object[]数组
            elementData = c.toArray();
            //elementData的length不为空
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)//判断集合存的元素不是Object
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                //elementData的length为空，直接将ArrayList的数组替换为空数组
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

##  五、ArrayList函数分析 ##

### 5.1 trimToSize ###

public void trimToSize() {
            modCount++;//修改次数加1
            if (size < elementData.length) {
                //如果底层数组的length为空则置为EMPTY_ELEMENTDATA
                //否则使用Arrays的方法对复制元素
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

### 5.2 add方法 ###

add方法有两个

<table>  add函数  
 <tbody> 
  <tr> 
   <td style="width:283px;">函数</td> 
   <td style="width:566px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:283px;">&nbsp;public boolean add(E e)</td> 
   <td style="width:566px;"> <p>将指定的元素添加到此列表的尾部</p> </td> 
  </tr> 
  <tr> 
   <td style="width:283px;">public void add(int index, E element)</td> 
   <td style="width:566px;"> <p>在列表的指定位置插入指定元素（可选操作）。将当前处于该位置的元素（如果有的话）和所有后续元素向右移动（在其索引中加 1）。</p> </td> 
  </tr> 
 </tbody> 
</table>

public boolean add(E e) {
            //确保函数的大小
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

add调用了函数ensureCapacityInternal(int size)  此函数可以理解为确保ArrayList底层数组elementData有合适的大小

private void ensureCapacityInternal(int minCapacity) {
              //判断是否为空数组
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //取DEFAULT_CAPACITY 10和minCapacity中的大值
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }

而ensureCapacityInternal调用了ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {
            //修改次数++
            modCount++;
    
            // overflow-conscious code
            //数组放不下
            if (minCapacity - elementData.length > 0)
                //数组扩增容量
                grow(minCapacity);
        }

ArrayList动态增大主要是依赖于grow方法

private void grow(int minCapacity) {
            // overflow-conscious code
            //旧容量
            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);
            // minCapacity is usually close to size, so this is a win:
            //扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

add函数的调用过程：

![20190104170836167.png][]

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

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;
            //元素数量加1
            size++;
        }

### 5.3 addAll方法 ###

addAll方法也有两个

<table>  addAll  
 <tbody> 
  <tr> 
   <td style="width:391px;">方法</td> 
   <td style="width:458px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:391px;">&nbsp; public boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td style="width:458px;"> <p>按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部</p> </td> 
  </tr> 
  <tr> 
   <td style="width:391px;">public boolean addAll(int index, Collection&lt;? extends E&gt; c)</td> 
   <td style="width:458px;"> <p>从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。向右移动当前位于该位置的元素（如果有）以及所有后续元素（增加其索引）。新元素将按照指定 collection 的迭代器所返回的元素顺序出现在列表中。</p> </td> 
  </tr> 
 </tbody> 
</table>

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;
            //先把原数组从index开始把所有元素位置往后移空出a所需的位置
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                                 numMoved);
            //空的位置上放上a的所有元素
            System.arraycopy(a, 0, elementData, index, numNew);
            //重新计算元素的个数
            size += numNew;
            return numNew != 0;
        }

所有的关键就在System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)这个方法

从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 `src` 引用的源数组到 `dest` 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 `length` 参数。源数组中位置在 `srcPos` 到 `srcPos+length-1` 之间的组件被分别复制到目标数组中的 `destPos` 到 `destPos+length-1` 位置。

如果参数 `src` 和 `dest` 引用相同的数组对象，则复制的执行过程就好像首先将 `srcPos` 到 `srcPos+length-1` 位置的组件复制到一个带有 `length` 组件的临时数组，然后再将此临时数组的内容复制到目标数组的 `destPos` 到 `destPos+length-1` 位置一样。

如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6YXVfaXRkb2c_size_16_color_FFFFFF_t_70][]

addAll方法就好理解多了

public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

### 5.4 get函数 ###

public E get(int index) {
            //角标越界检查
            rangeCheck(index);
    
            return elementData(index);
        }
    
       @SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }

直接将底层数组的index索引元素返回

### 5.5 set函数 ###

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

直接法修改对应角标的元素

### 5.6 remove函数 ###

<table>  remove函数  
 <tbody> 
  <tr> 
   <td style="width:373px;">函数</td> 
   <td style="width:476px;">作用</td> 
  </tr> 
  <tr> 
   <td style="width:373px;">&nbsp; public E remove(int index)</td> 
   <td style="width:476px;"> <p>移除此列表中指定位置上的元素。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:373px;">&nbsp;public boolean remove(Object o)</td> 
   <td style="width:476px;"> <p>移除此列表中首次出现的指定元素</p> </td> 
  </tr> 
  <tr> 
   <td style="width:373px;">protected void removeRange(int fromIndex, int toIndex)</td> 
   <td style="width:476px;"> <p>移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素</p> </td> 
  </tr> 
 </tbody> 
</table>

public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                //从index位置把后面元素迁移，
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //置空最后一个元素，让gc回收
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

当我们明白了System.arraycopy()函数的用处上述代码非常易懂

public boolean remove(Object o) {
            //如果移除的元素为空
            if (o == null) {
                // //遍历找到要移除的第一个元素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;
        }

上述移除操作都调用fastRemove函数

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
        }

fastRemove函数与remove（int index）原理是一样的

protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
    
            // clear to let GC do its work
            int newSize = size - (toIndex-fromIndex);
            for (int i = newSize; i < size; i++) {
                elementData[i] = null;
            }
            size = newSize;
        }

removeRange把toIndex元素后面元素迁移至fromIndex,size-(toIndex-fromIndex)后面元素全部置空

### 5.7 retainAll 函数 ###

public boolean retainAll(Collection<?> c) {
            //集合不为空
            Objects.requireNonNull(c);
            return batchRemove(c, true);
        }

retainAll仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。换句话说，移除此 collection 中未包含在指定 collection 中的所有元素

retainAll函数主要功能依赖于batchRemove()函数

private boolean batchRemove(Collection<?> c, boolean complement) {
            final Object[] elementData = this.elementData;
            // 使用读写两个指针同时遍历数组
        
            // 读指针每次自增1，写指针放入元素的时候才加1
        
            // 这样不需要额外的空间，只需要在原有的数组上操作就可以了
            int r = 0, w = 0;
            boolean modified = false;
            try {
                //遍历当前集合所有元素，当集合c包含关系和complement相等时，就把元素值赋给索引w
                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.
              
                //如果 c.contains() 抛出异常
                if (r != size) {
                    //复制剩余的元素
                    System.arraycopy(elementData, r,elementData, w,size - r);
                    //w为当前集合A的length
                    w += size - r;
                }
                //把w后面的元素置空
                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;
        }

## 六、内部类Itr源码分析 ##

Itr是AbstractList.Itr的优化版本 ,

** 为什么会报ConcurrentModificationException异常?**  
1. Iterator 是工作在一个独立的线程中，并且拥有一个 mutex 锁。  
2. Iterator 被创建之后会建立一个指向原来对象的单链索引表，当原来的对象数量发生变化时，  
 这个索引表的内容不会同步改变，所以当索引指针往后移动的时候就找不到要迭代的对象，  
 3. 所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。  
 4. 所以 Iterator 在工作的时候是不允许被迭代的对象被改变的。  
 但你可以使用 Iterator 本身的方法 remove() 来删除对象，  
  5. Iterator.remove() 方法会在删除当前迭代对象的同时维护索引的一致性。

### 6.1 Itr的继承体系 ###

private class Itr implements Iterator<E> {    
      }

### 6.2 Itr的字段 ###

int cursor;       // 下个元素返回的索引
        //上一个元素返回的索引，如果没有返回-1
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;//此列表修改的次数

### 6.3 Itr函数分析 ###

hasNext()

public boolean hasNext() {
        return cursor != size;
     }

checkForComodification()

//检查modCount是否等于expectedModCount
     //在 迭代时list集合的元素数量发生变化时会造成这两个值不相等      
     final void checkForComodification() {
         if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
    }

next()

@SuppressWarnings("unchecked")
            public E next() {
                //检查是否存在并发修改
                checkForComodification();
                //当前元素的索引
                int i = cursor;
                //角标是否越界越界
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                //第二次检查,list集合中数量是否发生变化
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                //下一个元素的索引
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }

remove

public void remove() {
                //没有上一个元素，代表此迭代器状态异常，正常情况 要想删除元素，
                 //必须先迭代，只要迭代上个元素必然不小于0
                if (lastRet < 0)
                    throw new IllegalStateException();
                //并发修改异常的检查
                checkForComodification();
    
                try {
                    //内部类访问外部类的方法 （外部类.this.变量）
                    ArrayList.this.remove(lastRet);
                    //指针前移
                    cursor = lastRet;
                    //上个元素索引置为-1，表示无上个元素
                    lastRet = -1;
                    //修改次数置为相同
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

forEachRemaining

@Override
            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
                Objects.requireNonNull(consumer);
                //元素数量，内部类访问外部类的属性 （外部类.this.变量）
                final int size = ArrayList.this.size;
                //当前元素的索引
                int i = cursor;
                //如果越界直接返回
                if (i >= size) {
                    return;
                }
                //ArrayList底层的数组，内部类访问外部类的属性 （外部类.this.变量）
                final Object[] elementData = ArrayList.this.elementData;
                //并发修改检查
                if (i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                //遍历元素，并且每次对其进行并发修改判断
                while (i != size && modCount == expectedModCount) {
                    consumer.accept((E) elementData[i++]);
                }
                // update once at end of iteration to reduce heap write traffic
                //把迭代器指针还原
                cursor = i;
                lastRet = i - 1;
                //并发修改检查
                checkForComodification();
            }

## 七、内部类ListItr源码分析 ##

### 7.1 ListItr的继承关系 ###

private class ListItr extends Itr implements ListIterator<E>

### 7.2 ListItr的函数 ###

下面函数比较简单

ListItr(int index) {
                super();
                cursor = index;
            }
    
            public boolean hasPrevious() {
                return cursor != 0;
            }
    
            public int nextIndex() {
                return cursor;
            }
    
            public int previousIndex() {
                return cursor - 1;
            }

previous（）

@SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                //指针前移
                cursor = i;
                //返回上个元素
                return (E) elementData[lastRet = i];
            }

set(E e)

public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try {
                    //用指定元素替换lastRet索引位置的元素
                    ArrayList.this.set(lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

说明

只有在最后一次调用 next 或 previous 后既没有调用 ListIterator.remove 也没有调用 ListIterator.add 时才可以进行该调用

add(E e)

public void add(E e) {
                checkForComodification();
    
                try {
                    int i = cursor;
                    //在当前位置添加元素
                    ArrayList.this.add(i, e);
                    //指针右移
                    cursor = i + 1;
                    //上个元素的指针置空
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

## 总结 ##

（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；

（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；

（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；

（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；

（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；

（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；

（7）ArrayList支持求并集，调用addAll(Collection c)方法即可；

（8）ArrayList支持求交集，调用retainAll(Collection c)方法即可；

（7）ArrayList支持求单向差集，调用removeAll(Collection c)方法即可；

[20190104092303561.png]: /images/20220331/21605fc87d5e44a38530e7fe351e0c47.png
[20190104170836167.png]: /images/20220331/ead43a2c538940cc93342621e489102a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6YXVfaXRkb2c_size_16_color_FFFFFF_t_70]: /images/20220331/297fd7153aaf4f1b81cd9e4732dc442d.png