ArrayList的数据结构

ArrayList 在 Java 集合框架中是非常重要的一个组成部分。为了深入理解 ArrayList 的工作机制，我们可以分析其源码。在这里，我们会简化某些部分以便更好地解释其核心功能和细节。

ArrayList 的数据结构

ArrayList 基于数组实现，可以动态扩容以适应不断增加的元素。以下是其主要的内部结构：

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, Serializable {
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // 存储元素的数组
    private int size; // 实际元素数量
    // 省略其他无关代码
}

ArrayList 的核心方法

• add(E e): 添加元素到 ArrayList 末尾。
• ensureCapacity(int minCapacity): 确保 ArrayList 有足够的容量来存储指定数量的元素。
• grow(int minCapacity): 扩容方法，当内部数组不足以容纳更多元素时被调用。

  源码解析（简化版）

  下面是 ArrayList 的几个关键方法的源码分析：

  public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable {
      // 默认初始容量大小
      private static final int DEFAULT_CAPACITY = 10;
      
      // 空数组（用于空实例）
      private static final Object[] EMPTY_ELEMENTDATA = {};
      // 存储ArrayList元素的数组缓冲区，将其标记为transient是因为它的内容在序列化过程中由writeObject和readObject方法管理
      transient Object[] elementData;
      // ArrayList中元素的数量
      private int 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);
          }
      }
      // 调整数组大小以确保至少能容纳最小容量参数指定的元素数量
      public void ensureCapacity(int minCapacity) {
          int minExpand = (elementData != EMPTY_ELEMENTDATA)
              // 任何大小
              ? 0
              // 较大的数组大小
              : DEFAULT_CAPACITY;
          
          if (minCapacity > minExpand) {
              ensureExplicitCapacity(minCapacity);
          }
      }
      // 添加方法，将给定元素e添加到此列表的末尾
      public boolean add(E e) {
          ensureCapacityInternal(size + 1);  // Increments modCount!!
          elementData[size++] = e;
          return true;
      }
      // 计算容量
      private void ensureCapacityInternal(int minCapacity) {
          if (elementData == EMPTY_ELEMENTDATA) {
              minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
          }
          ensureExplicitCapacity(minCapacity);
      }
      // 确保容量
      private void ensureExplicitCapacity(int minCapacity) {
          modCount++;
          // 溢出意识的代码
          if (minCapacity - elementData.length > 0) {
              grow(minCapacity);
          }
      }
      // 增长方法，增加存储容量
      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);
          }
          // 数组复制和扩容
          elementData = Arrays.copyOf(elementData, newCapacity);
      }
      private static int hugeCapacity(int minCapacity) {
          if (minCapacity < 0) // overflow
              throw new OutOfMemoryError();
          return (minCapacity > MAX_ARRAY_SIZE) ?
              Integer.MAX_VALUE :
              MAX_ARRAY_SIZE;
      }
      // 省略其他细节实现
  }
  

  代码演示

  以下是 ArrayList 的一个简单的使用示例：

  import java.util.ArrayList;
  public class Main {
      public static void main(String[] args) {
          ArrayList list = new ArrayList<>();
          // 添加元素
          list.add("Java");
          list.add("Python");
          list.add("C++");
          // 打印所有元素
          for (String language : list) {
              System.out.println(language);
          }
      }
  }
  

  细节分析

  在 ArrayList 的实现中，有几个要点需要注意：

  • 动态扩容: 当添加元素超出当前数组容量时，ArrayList 会进行数组扩容，通常是旧容量的1.5倍。
  • 空间和时间权衡: 扩容操作需要复制旧数组内容到新数组，这是一个时间成本较高的操作。动态扩容机制是一种空间换时间的策略。
  • modCount: 这是用于快速失败行为的计数器，记录结构性修改的次数。
  • 线程不安全: ArrayList 不是线程安全的，因此在多线程环境下共享时需要外部同步。
  • 最大容量限制: ArrayList 的最大容量受到 Integer.MAX_VALUE 的限制，当实际使用接近这个值时要特别小心，可能会导致内存溢出错误。

    通过这样深入的源码分析，我们可以更好地理解 ArrayList 的内部机制，这对于在实际编程中高效使用 ArrayList 是非常有帮助的。