1. 构造方法
ArrayList 有三个构造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*/
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
*/
private int size;
/**
* 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) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 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();
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 把数据都存储到 transient Object[] elementData 数组中，transient 是保证对象不被序列化（一般用于不可暴露的敏感信息或者无序序列化的对象）。
1.1 无参构造 ArrayList()
this.elementData 被赋值为空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
1.2 ArrayList(int initialCapacity)
初始化一个 initialCapacity 长度的数组赋值给 elementData
1.3 ArrayList(Collection<? extends E> c)
将入参数集合转成数组赋值给 elementData
2. 添加元素
/**
* 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;
}
/**
* 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;
}
modCount 是用来记录数组 elementData 变化的次数。
当调用 add(E e) 方法添加元素时，内部又调用了重载的私有方法 add(E e, Object[] elementData, int s)。
这里要明确两个东西：
一个是 size，每添加一个元素就 +1，每删除一个元素就 -1，它代表的是集合实际的元素个数；
另一个是 elementData.length，它是数组的真是长度，也就是数组当前的最大容量 capacity。
add(E e, Object[] elementData, int s) 通过 size 和 capacity的比较，判断是否需要扩容，也就是当实际元素个数和集合容量相等的时候，就需要扩容了（比如，集合的容量是10，添加第 10 个元素时，就需要先扩容，扩容后在添加元素），扩容用到的方法是 grow()。
/**
* 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);
}
可以看到扩容最终用到的是 Arrays.copyOf(arr, newLength) 方法，它的作用是 新建一个 newLength 长度的数组，然后把原来的数组 arr 中的元素复制到新数组。如果 arr.length > newLength，arr 中多余的数据就放弃；如果 arr.length < newLength，新数组中的其他位置就空着。
扩容的关键在于 newCapacity(minCapacity) 方法
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
oldCapacity >> 1，将 oldCapacity 右移一位，达到整除 2 的效果（10 二进制位 1010，右移一位变成 0101，对应十进制 5；9(1001) >>1,结果是 4(0100)）。这个地方妙啊，要我来肯定是用 2 整除，肯定没这个高效。
这里做了判断，if (newCapacity - minCapacity <= 0) 对应一下几种情况：
- minCapacity 为负数，抛出异常
- elementData 为空数组，那么 newCapacity 就是 DEFAULT_CAPACITY(默认值是10) 和 minCapacity 中最大的，空数组的size +1 = 1，所以空数组第一次扩容是直接扩到 10。
- 初始化的集合 capacity 较小，例如 1 和 2，此时 return minCapacity;
没能在上个判断中 return 的又分为两种情况
- 比较正常的数组，newCapacity <= MAX_ARRAY_SIZE，直接返回 newCapacity
- 超大集合，需要另一个方法 hugeCapacity(minCapacity)，这么大的数据，一般应该不会用集合了吧。。。。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
Integer.MAX_VALUE 个元素数量，就是 ArrayList 的极限了
3 移除元素
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
其中 found: 是个标志用于配合 break 跳出到指定位置，格式为 "字符"+":" 使用时字符可以自己定义，如：out：，in:
found 中的代码就是遍历数组，寻找要移除的对象，找不到则直接返回 false，找到了就跳出循环，执行 fastRemove。
最终删除过程，是利用本地方法 System.arraycopy(src, srcPos, dest, destPos, length) 实现
/**
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
*/
@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
这个方法，用途就是将 src 数组的第 srcPos 个元素开始，length 个元素，覆盖 dest 数组中的第 destPos 之后的元素。
此处实际上就是将需要删除的元素之后的所有元素向前移动一位（要保证数组元素的连续），要删除的元素就被后面的覆盖了，然后再把最后一个元素赋值为 null。
用 add(int index, E element) 添加元素时也类似，先把 index 位置及之后的元素向后移动一位，然后再把 index 位置的元素赋值为 element。
4 结论
4.1 扩容机制
- ArrayList 内部用数组 Object[] elementData 来存放数据。
- ArrayList三个构造方法：
2.1. 无参构造产生的 ArrayList 对象内部是个 length 为 0 的空数组。
2.2. ArrayList(int initialCapacity) 构造方法会生成一个，长度为 initialCapacity 的数组，initialCapacity 为负数则会报错
2.3. ArrayList(Collection<? extends E> c) 构造方法会利用 c.toArray()，将集合 c 转变成 ArrayList 对象内部的数组，长度自然为 c.size() - ArrayList 内部有一个重要参数 size，它代表的是 ArrayList 中的实际元素个数，添加元素的时候 size 自增 1，删除数据是自减 1；另外 elementData.length,代表的是Capacity，也就是 ArrayList 当前的最大容量，size <= elementData.length。
- 触发扩容：
4.1. elementData.length 为 0 时，添加第一个元素就会触发扩容，此时会将 elementData 扩容成一个长度为 DEFAULT_CAPACITY = 10 的数组，并将第一个元素赋值给 elementData[1]
4.2. elementData.length 不为 0 时，当添加第 elementData.length 个元素时，会触发扩容 - 使用 grow 方法扩容
5.1 常规情况下，通过 newCapacity = oldCapacity + (oldCapacity >> 1) 的方式扩容，即每次增加原来容量的 1/2，即扩容到原来的 1.5 倍。（如：10>15>22....）
5.2 elementData.length 为 0，直接扩容到 10
5.3 如果 Integer.MAX_VALUE > newCapacity > MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8, 扩容结果是扩容为长度为 Integer.MAX_VALUE 的数组，并且不会再扩容，如果真的添加到这个数组的最后一位，仍会触发扩容机制，导致 newCapacity = oldCapacity + (oldCapacity >> 1) 为负数，最终报错 OutOfMemoryError。
5.4 oldCapacity + (oldCapacity >> 1) 的理论值大于 Integer.MAX_VALUE 时，实际的结果是负数（因为超出了Integer的范围），此时会直接报 OutOfMemoryError。
4.2 适用场景
查：ArrayList 底层结构是数组，所以遍历方便。
增、删：add(e) 添加元素时，最末尾添加；add(index，e) 添加元素时，index 之后的元素全部后移一位，remove 删除元素时，该元素的之后的元素全部前移一位。运算量较大，并不适合。
4.3 线程安全
添加、删除元素都 涉及 size 加减的问题，并没有原子性的保障，多线程操作时 size 会混乱。
扩容涉及 size 和 elementData.length 的比较和判断，多个线程操作也会导致误判。
CopyOnWriteArryList 可以并发读，写时复制，可以解决线程安全问题。
网友评论