Java 源码 - ArrayList 集合类

介绍

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. This class is roughly equivalent to Vector, except that it is unsynchronized.

示例

public class Test {
  public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add("fei");
    list.add("gege");
    list.forEach(System.out::print);
  }
}

结构

源码

成员变量

/**
 * The array buffer into which the elements of the ArrayList are stored.
 */
transient Object[] elementData;

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for default sized empty instances.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The size of the ArrayList (the number of elements it contains).
 */
private int size;

/**
 * The maximum size of array to allocate.
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

成员方法

添加1

/**
 * Appends the specified element to the end of this list.
 */
public boolean add(E e) {
  ensureCapacityInternal(size + 1);
  elementData[size++] = e;
  return true;
}

添加2

/**
 * Inserts the specified element at the specified position in this list. 
 */
public void add(int index, E element) {
  rangeCheckForAdd(index);
  ensureCapacityInternal(size + 1);
  System.arraycopy(elementData, index, elementData, index + 1,
           size - index);
  elementData[index] = element;
  size++;
}

扩容1

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 */
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

扩容2

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

扩容3

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

扩容4

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

扩容5

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

面试

1、为何Java中ArrayList最大容量是Integer.MAX_VALUE-8？
有些虚拟机在数组中保留了一些头信息，避免内存溢出！
2、如何实现 ArrayList 的线程安全？
1、使用 Vector 集合类。
2、使用 Collections.synchronizedList 包装一下 List。
3、使用 CopyOnWriteArrayList 集合类。