彻底搞懂ArrayList
对ArrayList字段，内部类，常用方法和问题进行讲解。文章很长，值得收藏
Java版本:1.8字段
- private static final long serialVersionUID = 8683452581122892189L;
序列化的版本号
- private static final int DEFAULT_CAPACITY = 10;
ArrayList默认存储空间为10
- private static final Object[] EMPTY_ELEMENTDATA = {};
空的对象数组
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
同样是空的数组对象，和EMPTY_ELEMENTDATA区别在于，无参构造函数的空数组会用DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值，有参构造函数的空数组会用EMPTY_ELEMENTDATA赋值。
- transient Object[] elementData;
存储数据的数组，该字段表明ArrayList底层数据结构是数组。transient表明该字段无需序列化
- private int size;
ArrayList存储数据的数量，int类型默认为0。
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
最大容量。减去8是因为数组中保留了一些头信息。避免内存溢出
构造器
ArrayList有三个构造函数
- 无参构造函数
这里用的是elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}- 指定容器大小的构造函数
这里如果initialCapacity等于0，则elementData = EMPTY_ELEMENTDATA
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);
}
}- 通过指定元素集合的构造函数
需要注意两点:
1.toArray方法是Collection函数，子类根据自己数据结构返回一个对象数组。
2.如果size是0，那么elementData 还是会等于 EMPTY_ELEMENTDATA，如果不是0，且elementData.getClass!=Object[].class，那么会重新拷贝一份数据到新的数组中，并且elementData会指向新的数组。
这里提出第一个问题，为什么不通过c.size来判断长度而是直接使用c.toArray()呢？(答案在文章末尾)
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);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}内部类
Itr
提供了遍历和删除的方法。该内部类支持遍历删除，且告诉我们为什么迭代器移除元素，必须要调用next方法(这是第二个问题，重点在于cursor和lastRet字段赋值代码上)。
private class Itr implements Iterator<E> {
//cursor代表要下一个要返回元素的索引
//int类型，所以默认初始化为0
int cursor;
//最后返回元素的索引，如果没有返回过则为-1
int lastRet = -1;
//修改次数
int expectedModCount = modCount;
//构造器
Itr() {
//判断是否还有下元素
public boolean hasNext() {
return cursor != size;
}
//返回下一个元素
@SuppressWarnings("unchecked")
public E next() {
//检查修改次数是否异常
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
//cursor迁移
cursor = i + 1;
//返回元素
//此时i为当前最后一个返回的元素，赋给lastRet
return (E) elementData[lastRet = i];
}
//移除当前最后一个遍历出的元素
public void remove() {
//如果lastRet小于0，表明还没有元素被遍历出
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//移除元素
ArrayList.this.remove(lastRet);
//cursor前移
cursor = lastRet;
//将lastRet设置为-1，表明没有最后一个遍历的原色
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//JDK8中增加forEachRemaining用于遍历
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}ListItr
在Itr的基础上增加了一些特性，Itr遍历是从头开始，且不可逆。ListItr可以指定下标位置进行遍历。并且支持previous，set和add方法。其中set方法的下标是最后一个遍历元素的位置lastRet。而add方法则是在cursor(下一个遍历元素的位置)位置增加元素。源码就不贴了，理解Itr就不难理解ListItr。
SubList
该类最重要的作用就是切割ArrayList，然后返回一个List集合的其中一部分视图，这里有第三个问题，ArrayList的subList会得到部分视图，那么对于SubList的操作会影响到ArrayList吗。这个类平时自己使用的比较少。理解中使用场景可能是，这里分析一下源码的字段，内部的方法就不看了
private final AbstractList<E> parent;
//父类偏移量
private final int parentOffset;
//偏移量
private final int offset;
//数量
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
//fromIndex表明从何处开始切割视图
this.parentOffset = fromIndex;
//因为内部也存在subList方法，所以存储记录offset + fromIndex 表明索引位置
//如果构造参数offset为0，那么this.parentOffset实际上等效于offset
this.offset = offset + fromIndex;
//toIndex - fromIndex为数量
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}ArrayListSpliterator
ArrayListSpliterator实现了Spliterator，Spliterator是JDK8出现的，其含义是可分割迭代器，大大增强并行处理的能力。个人理解重点在于trySplit方法。getFence方法可以认为是获取List的最大边界。然后使用二分对List进行切割。
public ArrayListSpliterator<E> trySplit() {
//
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}需要注意的是，并行处理能力的前提是先进行切割，切割完的数据，可使用多线程去处理，而不是并行的切割处理。
核心方法
ArrayList的核心方法(主要以public为主)从前往后依次来看
- trimToSize
如果容器元素数量size小于数组长度，则将其调整为size大小的长度，该方法可以预防浪费空间。
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}- ensureCapacity
增加ArrayList实例的容量。该方法链中grow方法是核心，第四个问题的答案也在grow中，多线程的情况下，增加元素数据为什么导致集合中出现null值
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//该方法是扩容的前置方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return 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;
//正常情况下新的容器大小为 旧大小的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//下面两个判断是针对特殊情况对newCapacity赋值
if (newCapacity - minCapacity < 0)
newCapacity = 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);
}- size
返回元素数量
- isEmpty 判断集合是否为空
- contains 判断集合是否包含某个元素。通过遍历方式判断。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}- lastIndexOf 元素最后出现的位置，倒叙遍历集合
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}- clone 通过Arrays.copyOf返回一个新的集合
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}- toArray 一个返回Object数组，一个返回指定类似的数组 public Object[] toArray() { return Arrays.copyOf(elementData, size); } public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
- get
获取指定位置的集合元素，rangeCheck是判断数组是否越界
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}- set
覆盖指定位置的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}- add 增加元素，其中ensureCapacityInternal方法在上面ensureCapacity聊过，扩容逻辑在该方法链中 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
- remove 该方法提供通过索引删除和通过元素删除
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}- ** clear** 清空元素 public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
- iterato和listIteratorr 获取迭代器，也就是前面我们说的内部类Itr和ListItr
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public Iterator<E> iterator() {
return new Itr();
}- subList 获取SubList对象 public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); }
- spliterator
切割对象，提高并行能力
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}问题答案
第一个问题:通过元素集合Collection<? extends E> c构造ArrayList，为什么先调用c.toArray()，然后再判断size大小呢，而不是先调用c.size判断大小后，再调用c.toArray()？
答案:我们并未对c做任何同步操作，多线程的情况下，如果线程A调用c.size()得到结果是1，还未来得及调用c.toArray()方法时，线程将c的元素移除掉，那么ArrayList就会出现size为1的，elementData.length=0的情况，所以优先使用c.toArray。
第二个问题:为什么ArrayList通过迭代器支持遍历删除，此外为什么迭代器移除元素，必须要调用next方法？
答案:不通过迭代器删除元素时，由于数据会进行前移，可能(不是一定，要考虑元素的位置)会造成数组越界和数据遗漏(i+1的元素前移到i的位置，那么原来i+1的元素就会被遗漏掉)，通过迭代器remove删除元素后，cursor = lastRet(cursor前移，保证正确的遍历)。至于为什么移除元素必须调用next方法是因为迭代器remove的元素必须要遍历过，如果没有遍历过那么lastRet=-1，迭代器会抛出异常，而且删除后lastRet重新等于-1，所以每次删除都需要调用next方法。
第三个问题:ArrayList的subList会得到部分视图，那么对于SubList的操作会影响到ArrayList吗?
答案:会影响到，在SubList源码中我们可以发现，其内部的操作函数实际上都是对ArrayList的elementData的操作。
第四个问题:多线程的情况下，增加元素数据为什么出现null值
因为grow并非线程安全的操作，elementData会重新指向新的数组，如果size发生自增，那么会跨过一个索引下标赋值。