Java ArrayList
属性
/** * Default initial capacity. * * 如初始化时不指定，则默认容量为10 */private static final int DEFAULT_CAPACITY = 10;/** * Shared empty array instance used for empty instances. */private static final Object[] EMPTY_ELEMENTDATA = {};/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. * * 用来存储所有元素 */transient Object[] elementData; // non-private to simplify nested class access/** * The size of the ArrayList (the number of elements it contains). * * @serial * 以后 elementData 曾经有的元素的长度，新元素会放在 elementData[size] 下 */private int size;结构器
默认结构器
/** * Constructs an empty list with an initial capacity of ten. */public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}指定长度
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 新建长度为 initialCapacity 的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}传入汇合
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); // 如果传入的汇合长度不为 0 ，则把汇合中的元素 copy 到 elementData 中 if ((size = elementData.length) != 0) { // defend against c.toArray (incorrectly) not returning Object[] // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}扩容
最大长度
依据正文能够看到，有些虚拟机须要在数组中保留额定信息（保留的额定信息）须要占用肯定的空间，所以 ArrayList 的最大长度为 2^32 - 8
/** * The maximum size of array to allocate (unless necessary). * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;每次扩容时候，newCapacity 为 oldCapacity + (oldCapacity >> 1)，相当于旧容量的 1.5 倍
/** * Returns a capacity at least as large as the given minimum capacity. * Returns the current capacity increased by 50% if that suffices. * Will not return a capacity greater than MAX_ARRAY_SIZE unless * the given minimum capacity is greater than MAX_ARRAY_SIZE. * * @param minCapacity the desired minimum capacity * @throws OutOfMemoryError if minCapacity is less than zero */private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 依照扩容规定计算的新容量小于预期容量 if (newCapacity - minCapacity <= 0) { // 当应用默认结构器进行初始化时，在此处才进行底层数组的初始化 // 新的底层数组长度为默认容量（10）和冀望容量之间最大的值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } // 依照扩容规定计算出的容量是否超过默认最大容量？ // 不超过：则间接返回 // 超过：依据 hugeCapacity() 计算出新的长度 return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity);}当通过默认规定扩充为原来 1.5 后如果超过默认最大容量时，则通过比拟预期容量和默认最大容量来判断最大容量；
当预期容量比默认的 MAX_ARRAY_SIZE 大时，则返回 Integer.MAX_VALUE
否则返回默认的 MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity * @throws OutOfMemoryError if minCapacity is less than zero */private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));}private Object[] grow() { return grow(size + 1);}add()
add 办法一共有两个公开办法，一个是在尾部增加元素的 add(E e) 和在任意地位插入元素的 add(int index, E element)
尾部插入 add(E e)
该公开办法调用了 add(E e, Object[] elementData, int s)
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */public boolean add(E e) { modCount++; add(e, elementData, size); return true;}如果以后容量已满则进行扩容，否则间接把元素放到 s (= size) 的地位，数组元素长度 size + 1
/** * This helper method split out from add(E) to keep method * bytecode size under 35 (the -XX:MaxInlineSize default value), * which helps when add(E) is called in a C1-compiled loop. */private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1;}任意地位插入 add(int index, E element)
/** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */public void add(int index, E element) { // 查看要插入的地位是否越界 // 查看的范畴为 [0, size] rangeCheckForAdd(index); modCount++; final int s; Object[] elementData; // 数组曾经放满了，须要进行扩容 if ((s = size) == (elementData = this.elementData).length) elementData = grow(); // 把原来元素拷贝一份到新数组 System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; size = s + 1;}