ArrayList 是 Java 集合框架中最常用的类之一，它基于动态数组实现，提供了对元素的随机访问功能，并且支持自动扩容。ArrayList 实现了 List 接口，是一个有序的集合，允许元素重复。

1. ArrayList 的基本特性

• 底层结构：ArrayList 使用一个动态数组来存储元素，初始容量为 10。
• 容量扩展：当添加的元素数量超过当前容量时，ArrayList 会进行扩容，通常是原容量的 1.5 倍。
• 线程不安全：ArrayList 不是线程安全的，如果在多线程环境中需要使用，建议使用 Collections.synchronizedList() 或者使用 CopyOnWriteArrayList。

2. 构造函数

ArrayList 提供了三种主要的构造函数：

• 默认构造函数：创建一个初始容量为 10 的空列表。

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

• 指定初始容量的构造函数：可以指定列表的初始容量。

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

• 集合构造函数：根据传入的集合创建列表。

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

3. 添加元素 (add() 方法)

ArrayList 的 add() 方法用于向列表末尾添加元素，核心逻辑如下：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e;
    return true;
}

• ensureCapacityInternal()：确保内部数组有足够的容量来存放新元素。

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

• ensureExplicitCapacity()：当内部数组容量不足时，进行扩容。

  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      if (minCapacity - elementData.length > 0)
          grow(minCapacity); // 扩容方法
  }
  

4. 获取元素 (get() 方法)

ArrayList 的 get() 方法用于通过索引获取元素，时间复杂度为 O(1)：

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

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

• rangeCheck()：检查索引是否越界，如果越界则抛出 IndexOutOfBoundsException。

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

5. 删除元素 (remove() 方法)

ArrayList 的 remove() 方法有两种重载方式，一种是通过索引删除元素，另一种是通过对象删除元素。

• 通过索引删除元素：

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

  • System.arraycopy()：用于将删除位置后的元素整体前移，保持数组的连续性。

• 通过对象删除元素：

  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;
  }
  
  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; // 清除最后一个元素，便于垃圾回收
  }
  

6. 扩容机制分析

ArrayList 的扩容机制是其性能的关键点。默认情况下，ArrayList 的初始容量为 10，当容量不足时，会自动扩容。扩容的方式是创建一个更大的数组并将原有元素复制到新数组中。默认情况下，新容量是原容量的 1.5 倍，即 oldCapacity + (oldCapacity >> 1)。这种扩容策略在性能和内存利用之间取得了平衡。

扩容的具体过程

1. 检测容量是否足够：在向 ArrayList 添加元素时，首先会调用 ensureCapacityInternal() 方法来确保内部数组有足够的容量。

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

   如果当前数组为空（使用默认构造函数创建），会将最小容量设置为默认容量（10）。

2. 扩容逻辑：如果当前容量不足以容纳新元素，则调用 grow() 方法进行扩容。

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

   modCount 是用于记录 ArrayList 结构修改次数的变量，用于迭代器的快速失败机制。

3. 计算新容量：在 grow() 方法中，新容量为原容量的 1.5 倍。

   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   

   • 计算新容量：newCapacity = oldCapacity + (oldCapacity >> 1)，即原容量加上其一半。
   • 确保新容量足够：如果新容量小于所需的最小容量，则将新容量设置为最小容量。
   • 最大容量检查：如果新容量超过了 MAX_ARRAY_SIZE（通常为 Integer.MAX_VALUE - 8），则调用 hugeCapacity() 方法，防止内存溢出。

4. 复制原数组到新数组：最后通过 Arrays.copyOf() 方法将原数组中的元素复制到新数组中。

   elementData = Arrays.copyOf(elementData, newCapacity);
   

扩容的优缺点

• 优点：

  • 减少扩容次数：每次扩容都会将容量增加到原来的 1.5 倍，这样可以有效减少扩容的次数，从而降低扩容带来的性能开销。
  • 动态调整容量：ArrayList 的容量可以根据实际需要动态调整，适合元素数量变化频繁的场景。

• 缺点：

  • 内存浪费：每次扩容都会将容量增大 1.5 倍，这可能导致内存浪费，尤其是在元素数量变化较大而最终保留元素较少的情况下。
  • 扩容成本高：扩容时需要创建一个新的数组并将原数组中的元素复制到新数组，这在元素数量较大时会产生明显的性能开销。

如何优化扩容性能

1. 指定初始容量：如果能够预估 ArrayList 的最终大小，建议在创建 ArrayList 时指定初始容量，以减少扩容次数。

   List<String> list = new ArrayList<>(1000); // 指定初始容量为 1000
   

2. 使用 ensureCapacity() 方法：在批量添加元素之前，可以使用 ensureCapacity() 方法一次性将容量增加到合适的大小，减少扩容带来的性能影响。

   ArrayList<String> list = new ArrayList<>();
   list.ensureCapacity(500); // 提前确保容量为 500
   

扩容机制小结

ArrayList 的扩容机制是通过增加容量到原来的 1.5 倍来实现的，这种策略在内存和性能之间取得了一定的平衡。尽管扩容的过程会带来一定的开销，但通过合理地设置初始容量和使用 ensureCapacity() 方法，可以有效减少扩容次数，优化性能。在处理大量数据时，理解扩容机制对于优化内存和提升程序性能至关重要。

• 扩容的优点：减少了频繁扩容的开销。
• 扩容的缺点：可能会浪费部分内存，尤其是当实际数据量远小于扩容后的容量时。

7. 总结

ArrayList 是 Java 集合框架中常用的动态数组实现，适合读取频繁、插入和删除操作较少的场景。通过对源码的分析，我们可以看到 ArrayList 的实现注重效率和内存使用之间的平衡。扩容机制、元素的插入和删除等操作都经过精心设计，以在大部分情况下提供较好的性能表现。

在多线程环境中使用 ArrayList 时需要特别注意其线程不安全的特性，通常可以使用 Collections.synchronizedList() 方法将其转换为线程安全的版本，或者使用 CopyOnWriteArrayList 来替代。