目录 显示

image.png|500
List 接口的可调整大小数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现 List 接口之外，此类还提供一些方法来操作内部用于存储列表的数组的大小。（此类大致等同于 Vector，只是它是不同步的)

size、isEmpty、get、set、iterator 和 listIterator 操作以恒定时间运行。 添加操作以线性时间运行，即添加N个元素需要 O(n)时间。所有其他操作都以线性时间运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。

每个 ArrayList 实例都有容量。容量是用于存储列表中元素的数组的大小。它至少与列表大小一样大。当元素添加到 ArrayList 中时，其容量会自动增长。除了添加元素具有恒定的摊销时间成本这一事实之外，没有指定增长策略的细节。
应用程序可以在使用ensureCapacity 操作添加大量元素之前增加 ArrayList 实例的容量。这可能会减少增量重新分配的数量。

请注意，此实现不是同步的。 如果多个线程同时访问ArrayList实例，并且至少有一个线程在结构上修改了列表， 则必须在外部同步该列表。（结构修改是添加或删除一个或多个元素，或显式调整后备数组大小的任何操作; 仅设置元素的值不是结构修改。这通常是通过在自然封装列表的某个对象上进行同步来实现的。如果不存在此类对象，则应使用该 Collections.synchronizedList 方法“包装”列表。这最好在创建时完成，以防止意外的不同步访问列表：

List list = Collections.synchronizedList(new ArrayList(...));

该类的 iterator 和 listIterator 方法返回的迭代器是快速失败fail-fast的：如果在创建迭代器后的任何时间对列表进行结构修改，除了通过迭代器自身的 remove 或 add 方法外，迭代器将抛出 ConcurrentModificationException 。因此，面对并发修改，迭代器会快速、干净利落地失败，而不是冒着在未来某个不确定时间出现任意、非确定行为的风险。

请注意，无法保证迭代器的快失效行为，因为一般来说，在非同步并发修改的情况下，不可能做出任何硬性保证。快失效迭代器会尽力抛出 ConcurrentModificationException 。因此，如果程序的正确性依赖于这种异常，那将是错误的：迭代器的快失效行为只能用于检测错误。

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

ArrayList 的1.5倍扩容

为什么按大约1.5倍扩容
扩容因子的大小选择，需要考虑如下情况：

  • 扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制。
  • 扩容容量不能太大，需要充分利用空间，避免浪费过多空间。
  • 为了能充分使用之前分配的内存空间，最好把增长因子设为 1<k<2. k=1.5时，就能充分利用前面已经释放的空间。如果k >= 2，新容量刚刚好永远大于过去所有废弃的数组容量。

并且充分利用移位操作（右移一位），减少浮点数或者运算时间和运算次数。

//在添加原元素时会触发容量检测👇👇👇
public boolean add(E e) {  
    ensureCapacityInternal(size + 1);  // Increments modCount!!  
    elementData[size++] = e;  
    return true;  
}
//传入size+1 保证容量👇👇👇
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;  
    //向下位移并取证（除2取整）
    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);  
}

ArrayList如何实现序列化安全

在序列化方法writeObject()方法中可以看到，先用默认写方法，然后将size写出，最后遍历写出elementData，因为该变量是transient修饰的，所有进行手动写出，这样它也会被序列化了。那是不是多此一举呢？

protected transient int modCount = 0;
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // 写出元素计数和任何隐藏的内容
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // 将大小写出为容量，以实现与 clone()的行为兼容性
    s.writeInt(size);

    // 按正确的顺序写出所有元素。
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

当然不是，其中有一个关键的modCount, 该变量是记录list修改的次数的，当写入完之后如果发现修改次数和开始序列化前不一致就会抛出异常，序列化失败。这样就保证了序列化过程中是未经修改的数据,保证了序列化安全。

ArrayList特性

  • 底层是数组
  • 查询、更新快
  • 增删慢
  • 可以存储重复元素
  • 保证有序性
  • 线程不安全
  • 当数据量增加时需要扩容