关于java:ArrayList源码浅析

简介：ArrayList作为咱们开发中最罕用的汇合，作为极高频次应用的类，咱们无妨浏览源码一谈到底。

ArrayList 作为咱们开发中最罕用的汇合，作为极高频次应用的类，咱们无妨浏览源码一谈到底。

ArrayList 继承关系如下

AaaryList 次要实现了 List 接口，同时标记为能够序列化 Serializable、可复制 CloneAble、反对随机拜访 RandomAccess。

几个重要的成员变量

 /**
  * 默认容量
  */
 private static final int DEFAULT_CAPACITY = 10;

 /**
  * 用于空实例的共享空数组实例。*/
 private static final Object[] EMPTY_ELEMENTDATA = {};

 /**
  * 用于默认大小的空实例的共享空数组实例。咱们将其与空元素数据辨别开来，以理解增加第一个元素时要收缩多少。*/
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

 /**
  * 存储 ArrayList 元素的数组缓冲区。ArrayList 的容量是此数组缓冲区的长度。*/
 transient Object[] elementData; // non-private to simplify nested class access

 /**
  * ArrayList 的大小（它蕴含的元素数）。*/
 private int size;

数据结构

ArrayList 底层就是一个数组，数组会随着数据的增长而扩容，数组的扩容就是建设一个新的容量大的数组，而后把旧数组下面的数据复制进新数组。对于扩容，前面会具体解说。

因为是数组，所以反对随机拜访，且有序。

罕用办法

ArrayList()无参构造方法
    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

初始化数组为一个空数组。与空元素数据辨别开来，以理解增加第一个元素时要收缩多少。

add(E e) 增加元素
将指定的元素追加到此列表的开端

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

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

当增加元素，会先查看是否超出容量，如果超出，则须要扩容。

当第一次增加元素时，size 为默认值 0，会计算出一个最小容量 minCapacity，如果是无参结构创立的，则会取默认的容量 10，

Math.max(DEFAULT_CAPACITY, minCapacity)，这里传入的 minCapacity 为 0，所以获取更大的 10。

如果计算出的最小容量大于原容量 minCapacity – elementData.length > 0，则会进行扩容。

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

扩容算法是，扩为老容量的 1.5 倍，如果扩容后的容量依然小于须要的最小容量 minCapacity，则新的容量就取最小容量。

如果扩容后的大小超过最大容量，则会进行上面的操作

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

计算出扩容后的容量后，进行扩容，也就是，新建一个数组初始化为新容量，而后复制旧元素到新数组。elementData = Arrays.copyOf(elementData, newCapacity);

 public static <T> T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());
 }

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

为什么不能在 forEach 外面批改列表

ArrayList 在新增、删除元素都会执行 modCount++

modCount 定义在 ArrayList 的父类 AbstractList。

/**
   * 此列表在结构上被批改的次数。构造批改是指那些扭转列表大小的批改，或者以某种形式烦扰列表，使得正在进行的迭代可能产生不正确的后果。迭代器和列表迭代器办法返回的迭代器和列表迭代器实现应用此字段。如果此字段的值意外更改，迭代器（或列表迭代器）将抛出 ConcurrentModificationException 以响应下一个、删除、上一个、设置或增加操作。这提供了疾速生效行为，而不是在迭代过程中面对并发批改时的非确定性行为。子类应用此字段是可选的。如果子类心愿提供 fail fast 迭代器（和列表迭代器），那么它只需在 add（int，E）和 remove（int）办法（以及它重写的任何其余办法，这些办法会导致列表的构造批改）中减少该字段。对 add（int，E）或 remove（int）的单个调用只能向该字段增加一个，否则迭代器（和列表迭代器）将抛出虚伪的 ConcurrentModificationException。如果实现不心愿提供故障疾速迭代器，则能够疏忽此字段。*/
  protected transient int modCount = 0;

而后咱们来看下 forEach 的实现。

 @Override
 public void forEach(Consumer<? super E> action) {Objects.requireNonNull(action);
     final int expectedModCount = modCount;
     @SuppressWarnings("unchecked")
     final E[] elementData = (E[]) this.elementData;
     final int size = this.size;
     for (int i=0; modCount == expectedModCount && i < size; i++) {action.accept(elementData[i]);
     }
     if (modCount != expectedModCount) {throw new ConcurrentModificationException();
     }
 }

在遍历前，会暂存 modCount 值，每次循环都判断下 modCount 是否有更改，若更改了，外面跳出循环，随后抛出异样。

原文链接
本文为阿里云原创内容，未经容许不得转载。

关于java:ArrayList源码浅析

前言

介绍