JAVA中ArrayList源码分析
本文将会从5个方面来介绍ArrayList的源码。其中涉及到了ArrayList是如何实现数据的存贮,ArrayList为什么可以随着元素的添加而增加容量以及它的容量是如何扩充的与元素个数有什么关系,是如何判断并发修改异常。
A:ArrayList类的属性:
/**
* 集合的默认容量为10;当我们创建一个集合时,如下
* ArrayList<String> list=new ArrayList<String>();
* list.add("aaaa");
* 此时添加元素时集合会扩充容量达到默认值10
* 在E项的基本方法中我会讲解add方法便可知道为什么集合的容量会
* 是10了。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 集合为空的状态。当我们创建一个集合时,如下
* ArrayList<String> list=new ArrayList<String>();
* 此时集合的状态便是同下面一样。至于为什么会在B项构造方法中讲解
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 集合容器的本质,集合之所以可以存放各种元素,是因为它把元素都存在* 了这个对象数组中
* 在C项中我们会讲解,为什么集合可以变长,他是如何增加自身容量的
*/
private transient Object[] elementData;
/**
* 集合中元素个数,要与集合的容量区分开。比如集合容量是10,但里面
* 只存
* 放了一个元素,则size为1
*/
private int size;
/**
* 集合的最大容量,至于为什么是整型最大值-8还没搞明白
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 这不是ArrayList类中的成员变量,是它的父类AbstractList的成员* 变量,用来记录
* 操作集合的次数。但是,只有在集合结构发生变化时modCount才会增长。
* 也就是说对集合做增加,删除操作会使这个变量值增加
* 他是判断ConcurrentModificationException并发修改异常的依据
* 在D项中我会介绍到
*/
protected transient int modCount = 0;
B:ArrayList的构造方法:
ArrayList有三种构造方法一个无参的,两个有参的。其本质都是对对象数组的操作。
/**
* ArrayList集合的无参构造方法。当我们创建集合时不指定参数将 * 调用此方法,如下
* ArrayList list=new ArrayList();
* 期内部this.elementData = EMPTY_ELEMENTDATA;
* 等于Object[] elementData={};
* 因为如A项中所说EMPTY_ELEMENTDATA是一个空数组,
* 所以elementData在赋值之后也是一个空数组
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 创建集合时,指定集合的大小
* 其内部this.elementData = new Object[initialCapacity];
* 等于Object[] elementData=new Object[initialCapacity];
* 本质就是数组的初始化操作
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 用指定集合初始化ArrayList集合
* 内部的本质依旧是操作对象数组数组
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //将c这个集合变为Objc类型数组
size = elementData.length; //数组长度
//如果上面没有复制成功就按下面的方法进行复制
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(lementData, size, Object[].class);
}
C:ArrayList的容量控制:
/**
* 进行集合容量的判断,设置集合增量的值
* 内部ensureExplicitCapacity(minCapacity);
* 判断增量是否过大而导致内存溢出
*/
private void ensureCapacityInternal(int minCapacity) {
//如果集合为空,则集合的增量为默认值与要求值得最大值
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 判断增量是否过大
* 如果增量没有超出范围
* 则调用grow(minCapacity);
* 增加集合容量
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 进行集合容量的扩充,每次扩充旧容量的1.5倍。
* 如果扩充之后人不满足需要,则按着需求增加
*/
private void grow(int minCapacity) {
//集合容量
int oldCapacity = elementData.length;
//集合新的容量=1.5倍的旧容
//右移一位表示除以2
int newCapacity = oldCapacity + (oldCapacity >> 1); //如果新容量还没有满足要求
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量比最大容量还要大
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//规定集合容量为新的容量
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 设置集合容量为最大容量,即整型的最大值
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果你需求的集合容量大于集合最大容量就让集合的 //容量为整数最大值,否则为整数最大值-8
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
D:ArrayList的迭代器:
/**
* 创建迭代器
* ArrayList<String> list=new ArrayList<String>();
* list.listIterator();
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* 调用迭代器的构造方法,cursor为迭代器里面的索引初始指向0* 这个位置
*/
ListItr(int index) {
super();
cursor = index;
}
/**
* 增加操作
* expectedModCount = modCount;保证了集合的操作只由迭代器完成
* 如果中间插入了其他修改集合变化的操作modCount与expectedModCount 将会不一致
* 从而利用checkForComodification();该方法检测出来,抛出并发修改* 异常
*/
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/**
* 检查是否有并发修改异常
*/
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
E:ArrayList的基本方法:
/**
* 向集合中添加元素
* 其本质就是向对象数组中添加一个元素
* 当我们向一个刚创建出来的集合中添加元素
* ensureCapacityInternal(size + 1);
* 会判断集合的容量并增加集合的容量,如在上面所述的C项中,
* 如果集合为空会默认先增加10的容量,
* 所以向一个空的集合中插入 数据,集合会增加10的默认容量
*
* 由上面的D项所述可知,当集合发生了结构性变化时modCount会增加。
* modCount隐藏在了ensureCapacityInternal(size + 1);这个方法内* 部
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
/**
* 移出指定位置的元素
* 本质还是操纵数组
* modCount++;集合发生了结构性变化
* 当元素被移出时结合的容量不会发生变化
*/
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;
return oldValue;
}