ArrayList { }

文章说明：看源码分析 ArrayList 与LinkedList 的区别，注意到 ArrayList 类中的三个基本属性，对创建多个ArrayList 实例，指向 { }时是否会数据覆盖产生疑问，以下是简要分析。

1. ArrayList 中三个数组

private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

① EMPTY_ELEMENTDATA ，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 被 static final 修饰，属于类，且在类加载的初始化阶段赋值为{}

② elementData 没有被 static 修饰，每个实例变量都有各自的 elementData

关于序列化问题：Java transient 关键字

2. elementData

问题：elementData 和 EMPTY_ELEMENTDATA ，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 之间分别是什么关系？

2.1 elementData && EMPTY_ELEMENTDATA

ArrayList 中操作 EMPTY_ELEMENTDATA 的函数

① ArrayList(int initialCapacity) 使用指定 capacity 构造空 list

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {// 若指定 capacity = 0 则将 elementData 赋值为 EMPTY_ELEMENTDATAthis.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}
}

② ArrayList(Collection<? extends E> c) 根据指定 Collection 构造 list

public ArrayList(Collection<? extends E> c) {// 1. 将集合 c 转化为数组并赋值给 elementDataelementData = c.toArray();if ((size = elementData.length) != 0) {// 2. 入参集合不为空，判断转换后elementDta 是否为 Object[] 类型，否则调用 Arrays.copyOf(original, newLength, Class) 转化为 Object[] 类型// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 3. 入参集合为空，则将 elementData 赋值为 EMPTY_ELEMENTDATA// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}
}

③ trimToSize() 裁剪 ArrayList 实例对象的容量为当前 list 的容量

public void trimToSize() {modCount++;if (size < elementData.length) {// 若实例对象 size = 0 则 elementData = EMPTY_ELEMENTDATAelementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}
}

④ readObject(java.io.ObjectInputStream s) 从 stream 中复原数组

private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// 1. 使用 EMPTY_ELEMENTDATA 初始化 elementDataelementData = EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityensureCapacityInternal(size);// 创建 Object[] 类型数组，并赋值为 elementDataObject[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}
}

问题：为什么不直接操作 EMPTY_ELEMENTDATA 将其赋值给 a

EMPTY_ELEMENTDATA 被 static 修饰属于类，考虑创建多个ArrayList 实例时，多个实例共享 EMPTY_ELEMENTDATA ，直接操作类变量会导致数据覆盖

2.2 elementData && DEFAULTCAPACITY_EMPTY_ELEMENTDATA

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 同 EMPTY_ELEMENTDATA 都是 shared empty array instance

注释部分指出两者的区别在于，首次添加元素时应该扩容为多少

下文提到：使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是在调用无参构造时，由于未指定 initCapacity ，会作为标识，将 minCapactiy 赋值为默认大小 10

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

// shared empty array instance 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 中操作 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的函数

① ArrayList() 空参构造器

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

至此已经整理了ArrayList 中的三种构造器

// 1. 指定初始大小的构造函数
public ArrayList(int initialCapacity) {....this.elementData = EMPTY_ELEMENTDATA;
}
// 2. 传入Collection 集合的构造函数
public ArrayList(Collection<? extends E> c) {....this.elementData = EMPTY_ELEMENTDATA;
}
// 3. 无参构造函数
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

即只有在无参构造的时候，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA

② 检查容量 ensureCpacity(int minCpacity)

public void ensureCapacity(int minCapacity) {int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table? 0// larger than default for default empty table. It's already// supposed to be at default size.: DEFAULT_CAPACITY;if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}
}

在添加大量元素的时候会调用该函数，避免多次进行扩容操作

// package com.sun.corba.se.impl.orbutil
private void extend( int index )
{if (index >= list.size()) {list.ensureCapacity( index + 1 ) ;int max = list.size() ;while (max++ <= index)list.add( null ) ;}
}

③ ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {// 1. 若通过无参构造初始化，则设置 minCapacityif (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}

4. elementData 与 {} 问题

上面分析到：ArrayList 中的三个 Object 类型的数组 EMPTY_ELEMENTDATA，DEFAULTCAPACITY_EMPTY_ELEMENTDATA，elementData

三者的关系是：

① ArrayList 实例化对象操作 list 是通过 elementData 实现的

② 类加载时并没有对 elementData 初始化而是在构造函数中进行初始化

③ 调用有参构造 elementData = EMPTY_ELEMENTDATA

④ 调用无参构造 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA

⑤ EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是由 static final 修饰的，类加载时初始化，并且引用地址不可变

即每次初始化时对象的 elementData 指向的是 类加载时为 {}分配的内存地址

那么：创建多个 ArrayList 的时候，每个实例的 elementData 指向同一个 {}有没有数组覆盖问题呢？

首先分析添加元素的情况，以及添加元素是如何添加的

4.1 使用 Collection 填充数组

① 入参 Collection 填充数组，会根据 Collection 中有无元素分两步处理

public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} ...
}

② c.toArray() 将 collection 转化为 数组赋值给 elementData

elementData = c.toArray();
// ArrayList.java 
public Object[] toArray() {return Arrays.copyOf(elementData, size);
}

③ 当 collection 不为空时，判断是否需要进行类型转化，最终都会通过 toArray() 调用 Arrays.copyOf() 创建新数组 copy 接收复制后的数组

public static <T> T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());
}public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {@SuppressWarnings("unchecked")T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;
}

实际上，即使Arrays.copyOf(…) 没有返回新数组， elementData 指向的引用地址都不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 了，这一步说明了，传入 Collection 添加数组元素时，会通过 Arrays.copyOf(…) 生成新数组，而 elementData 会指向 新数组的地址，不会在DEFAULTCAPACITY_EMPTY_ELEMENTDATA 所引用的地址上进行操作

4.2 使用 add(E e) 添加数组元素

① 添加指定元素到 list 末尾

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

② 添加前先确定数组容量

private void ensureCapacityInternal(int minCapacity) {// 满足if 条件，使用无参构造初始化 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 入参 minCapacity = size + 1,未添加元素前 size = 0minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 使用无参构造，会执行if体，使得 minCapacity = DEFAULT_CAPACITY = 10ensureExplicitCapacity(minCapacity);
}

③ 判断是否需要扩容

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)// 若所需的最小容量大于当前数组容量时扩容grow(minCapacity);
}

④ 根据 minCapacity 扩容

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// newCapacity = 1.5 oldCpacityint newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)//newCapacity小于所需最小容量，则设置为 minCapacitynewCapacity = minCapacity;// 若扩容后 newCapacity > MAX_ARRAY_SIZE 则调用hugeCapacity(minCapacity) 仍然是根据 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);
}

⑤ 根据 minCapacity 处理 Integer.MAX_VALUE 和 MAX_ARRAY_SIZE 问题

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private static int hugeCapacity(int minCapacity) {// 所需最小容量 minCapacity < 0 说明溢出，抛出异常if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 若 minCapactiy > MAX_ARRAY_SIZE 则赋值为Integer.MAX_VALUEreturn (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

根据上述扩容的流程可以总结以下几点：

1. minCapacity >= newCapacity，在 MAX_ARRAY_SIZE 问题上，若 minCapacity < MAX_ARRAY_SIZE ，则即使扩容后 newCapacity > MAX_ARRAY_SIZE 也会缩减为 MAX_ARRAY_SIZE
2. newCapacity = 1.5 oldCapacity 每次扩容为 1.5 倍

private void grow(int minCapacity) {// overflow-conscious code....// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);
}

elementData 指向了 Arrays.copyOf(…) 的返回值，前面已经分析到该函数会返回新的数组

所以综上来说：elementData 与类加载时为 {}分配的内存空间只是在 ArrayList 实例在构造器中初始化 elementData 中有关联，而添加元素时，elementData 不再指向 {}所在的地址，而是指向 Arrays.copy(…) 返回的 copy 数组的内存地址

写在最后：为什么要使用两个 static 类型的数组呢？

暂时没想到怎么理解 =_=，继续探索