ArrayList源码解析
2017-01-12 本文已影响121人
Skymiles
ArrayList简介
ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
ArrayList源码分析 (JDK 1.6)
首先我们先分析一个List接口的实现类之一，也是最常用的ArrayList的源码。
ArrayList底层使用一个数组完成数据的添加，查询，删除，修改。这个数组就是下面提到的elementData。
这里分析的代码是基于jdk1.6的（加入了比较详细的注释）。限于篇幅有几个小方法没有列出,80%的代码都列出了。
// MyArryList=ArrayList
public class MyArrayList<T> extends AbstractList<T> implements List<T>, RandomAccess, Cloneable, Serializable {
private static final long serialVersionUID = -6268233918174116440L;
// ArrayList基于该数组实现，用该数组保存数据
private transient Object[] elementData;
// ArrayList中实际数据的数量
private int size;
// ArrayList带容量大小的构造函数
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
elementData = new Object[initialCapacity];
}
// ArrayList无参构造函数。默认容量是10。
public MyArrayList() {
this(10);
}
// 创建一个包含collection的ArrayList
public MyArrayList(Collection<? extends T> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray方法可能不会返回一个Object[]结果，需要做一层判断。这个一个Java的bug，可以在http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652查看
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
@Override
public void trimToSize() {
modCount++;
int oldSize = elementData.length;
if (size < oldSize)
// 真实的size小于数组的大小
elementData = Arrays.copyOf(elementData, size);
}
@Override
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
//新的容量=“(原始容量x3)/2 + 1”
int newCapacity = oldCapacity * 3 / 2 + 1;
//如果还不够，则直接将minCapacity设置为当前容量
if (minCapacity > newCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// 直接添加元素e
@Override
public boolean add(T e) {
// 确定ArrayList的容量大小
ensureCapacity(size + 1); // Increments modCount!!
// 添加e到ArrayList中
elementData[size++] = e;
return true;
}
// 将element添加到ArrayList的指定位置
@Override
public void add(int index, T element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
// System.arraycopy最终实现是native方法
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 从index位置开始，将集合c全部添加到ArrayList
public boolean addAll(int index, Collection<? extends T> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
// 删除ArrayList指定位置index的元素
@Override
public T remove(int index) {
rangeCheck(index);
modCount++;
T oldVal = (T) elementData[index];
int numMoved = size - index - 1;
// 删除ArrayList中最后一个元素,是不会执行这个if的
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldVal;
}
// 删除ArrayList的指定元素
@Override
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
remove(index); //JDK 1.6版本实际上用了fastRemove(int index). 这个和remove(int index)区别就是没有了rangeCheck步骤
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
remove(index); //JDK 1.6版本实际上用了fastRemove(int index). 这个和remove(int index)区别就是没有了rangeCheck步骤
return true;
}
}
return false;
}
@Override
public void clear() {
modCount++;
for (int i = 0; i < elementData.length; i++)
elementData[i] = null;
size = 0;
}
@Override
public T get(int index) {
rangeCheck(index);
return (T) elementData[index];
}
@Override
public T set(int index, T element) {
rangeCheck(index);
T oldData = (T) elementData[index];
elementData[index] = element;
return oldData;
}
@Override
protected Object clone() throws CloneNotSupportedException {
try {
MyArrayList<T> cloned = (MyArrayList<T>) super.clone();
cloned.elementData = Arrays.copyOf(elementData, size);
cloned.modCount = 0;
return cloned;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
@Override
public int size() {
return size;
}
// ArrayList是否包含Object(o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回ArrayList是否为空
public boolean isEmpty() {
return size == 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;
}
// 返回ArrayList的Object数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// 返回ArrayList元素组成的数组
public <T> T[] toArray(T[] a) {
// 若数组a的大小 < ArrayList的元素个数；
// 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 若数组a的大小 >= ArrayList的元素个数；
// 则将ArrayList的全部元素都拷贝到数组a中。
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 迭代器实现
public Iterator<T> iterator() {
return new Itr();
}
private class Itr implements Iterator<T> {
int cursor; // index of next element to return 下一个将要返回的元素的下表
int lastRet = -1; // index of last element returned; -1 if no such 上一个返回的元素的下表, -1表示没有
int expectedModCount = modCount; // fast-fail机制
// 是否还有元素
@Override
public boolean hasNext() {
// 由于cursor是将要返回元素的索引，也就是下一个元素的索引，和size比较是否相等，也就是判断是否已经next到最后一个元素
return cursor != size();
}
// 下一个元素
@Override
public T next() {
checkForComodification();
// i=下一个元素索引
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = MyArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
lastRet = i;
return (T) elementData[lastRet];
}
// 将迭代器返回的元素删除
@Override
public void remove() {
if (lastRet == -1)
throw new IllegalStateException();
checkForComodification();
try {
MyArrayList.this.remove(lastRet);
cursor = lastRet; // 重置为-1,不能连续两次调用remove()
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}
ArrayList注意点
-
当数据量很大的时候, ArrayList内部操作元素的时候会移动位置，很耗性能
-
ArrayList虽然可以自动扩展长度，但是数据量一大，扩展的也多，会造成很多空间的浪费
-
ArrayList允许加入null元素
-
ArrayList支持3种遍历方式
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
(02) 第二种，随机访问，通过索引值去遍历。由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
value = (Integer)list.get(i);
}
(03) 第三种，for循环遍历。如下：
Integer value = null;
for (Integer i:list) {
value = i;
}
遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！！！
