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. 有参构造size赋值为0的初始数组
*/
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;
数据存储在elementData
流程
构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_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);
}
}
第一次调用add方法
我们以无参构造初始化list为例，有参构造类似
public boolean add(E e) {
//第一次进来size==0
//ensureCapacityInternal 校验是否需要扩容并完成扩容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//minCapacity == size + 1 =1
private void ensureCapacityInternal(int minCapacity) {
//calculateCapacity 计算出需要的容量信息
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//minCapacity=1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA具体看上面的构造函数 无参构造满足
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY = 10, minCapacity=1 所以返回10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//有参构造直接返回1
return minCapacity;
}
// minCapacity 有参=1 无参=10
private void ensureExplicitCapacity(int minCapacity) {
//记录操作次数 一种并发乐观锁策略，后续delete中会在此用到
modCount++;
// overflow-conscious code
//两种情况满足，一种无参构造的minCapacity=10 elementData.length=0,或者有参构造传入new ArrayList(0) 此时minCapacity=1 elementData.length=0触发扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// minCapacity 有参=1 无参=10
private void grow(int minCapacity) {
// overflow-conscious code
//无参或者new ArrayList(0) elementData.length=0
int oldCapacity = elementData.length;
//oldCapacity>>1等价于oldCapacity/2 => newCapacity = 1.5oldCapacity；无参或者new ArrayList(0) elementData.length=0 =>newCapacity=0
int newCapacity = oldCapacity + (oldCapacity >> 1);
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数组长度为10，
elementData = Arrays.copyOf(elementData, newCapacity);
}
接下来 9次都不满足
if (minCapacity - elementData.length > 0)
grow(minCapacity);
不会触发扩容，只是把modCount++; 操作次数累加，并把新值插入到数组中
第11次调用add方法
public boolean add(E e) {
//size=10
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//minCapacity == size + 1 =11
private void ensureCapacityInternal(int minCapacity) {
//calculateCapacity 计算出需要的容量信息
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//minCapacity=11
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA具体看上面的构造函数 无参构造满足
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY = 10, minCapacity=1 所以返回10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//有参构造或者已经扩容过的list直接返回11
return minCapacity;
}
// minCapacity = 11
private void ensureExplicitCapacity(int minCapacity) {
//记录操作次数
modCount++;
// overflow-conscious code
//两种情况满足，11 - 10 > 0 满足条件触发扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// minCapacity=11
private void grow(int minCapacity) {
// overflow-conscious code
// elementData.length=10
int oldCapacity = elementData.length;
//oldCapacity>>1等价于oldCapacity/2 => newCapacity = 1.5oldCapacity => newCapacity=15
int newCapacity = oldCapacity + (oldCapacity >> 1);
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数组长度为15，
elementData = Arrays.copyOf(elementData, newCapacity);
}
get(int index)
public E get(int index) {
// 检查下标是否合法
rangeCheck(index);
// 通过下标获取数组对应的元素
return elementData(index);
}
//检查索引是否越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set(int index, E element)
public E set(int index, E element) {
rangeCheck(index); // 检查下标
// 获取下标原来的值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 获取要移动的元素的个数 {1,2,3,4,5,6,7,8,9} // 3 size=9 index=3
// {1,2,3,5,6,7,8,9,null}
int numMoved = size - index - 1; // 5
if (numMoved > 0)
// 源数组 开始下标 目标数组 开始下标 长度
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
// 删除的节点对应的信息
return oldValue;
}
并发修改异常处理
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.get(0);
Iterator<String> iterator = list.iterator();
if(iterator.hasNext()){
list.remove(0);
iterator.next();
}
}
//ArrayList.iterator返回一个Itr实例 关键在于checkForComodification()方法，在iterator的next()和remove()中有调用
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
//在初始化是指定了expectedModCount = modCount
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 = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@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() {
//由于expectedModCount在掉一个呢next()之前list执行了remove或者add方法 此时modCount+1，但是expectedModCount还是原来的modCount 此时就会报ConcurrentModificationException
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
解决方法
在iterator中做迭代的时候，使用iterator自带的remove方法，或者使用索引来维护循环for(int i=0; i<list.size; i++)
注意: for(item : list) 底层使用的是iterator，在循环里面进行add或remove可能抛出ConcurrentModificationException