走进源码——ArrayList阅读笔记
Arraylist
继承自AbstractList，实现了List，RandomAccess，Cloneable，和Serializable接口，具有List的特性，提供可随机访问，提供自身克隆以及序列化的一个容器类。
特点：线程不安全；数组实现
主要成员变量
- 来自自身的成员变量：
// 序列化ID
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 空的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认容量的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正存放对象的数组
transient Object[] elementData;
// 容器的大小
private int size;
- 来自父类和接口的成员变量：
// 操作计数
protected transient int modCount = 0;
这些变量都怎么被用到？接下来看方法
方法
方法的话，分几个模块来看吧
- 初始化
初始化的构造函数有三个
第一个，无参构造函数ArrayList()，函数直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
第二个，带int形参的构造函数ArrayList(int initialCapacity),函数首先判断initialCapacity是否为0，如果是0，则将EMPTY_ELEMENTDATA赋值给elementData，如果大于0，就将elementData初始化为一个容量为initialCapacity的对象数组
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);
}
}
第三个，带Collection形参的构造函数ArrayList(Collection<? extends E> c)，首先调用Collection的toArray()方法，返回的结果赋值给elementData,这里值得注意的是，有可能返回的结果不是Object[]（有可能是null），所以才会有if (elementData.getClass() != Object[].class)的判断,如果判断成立，调用Arrays.copyOf()来将collection中的数据复制到elementData中。其次，如果collection中没有数据，就将EMPTY_ELEMENTDATA赋值给elementData
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;
}
}
这就是全部的构造函数，有疑问，就是三个构造函数都存在赋值一个空数组给elementData，但是为什么无参的赋的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，剩余两个是EMPTY_ELEMENTDATA，带着疑问进入下面的方法
- 添加
添加元素这个功能涉及到好几个方法，一个一个来看，首先是最基本的Add方法，把一个元素添加到elementData中，要做这个之前，要扩容
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
扩容方法，在这里就看到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果EMPTY_ELEMENTDATA是由DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值而成，那么就将扩容的数量minCapacity和DEFAULT_CAPACITY进行比较，然后取其中的最大值，最大值再传参给ensureExplicitCapacity函数
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureExplicitCapacity(minCapacity)方法，在这个方法中先将操作数记录值modCount自增，然后根据minCapacity和elementData.length的大小来决定是否需要增加容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow(minCapacity)方法，这个就是重头戏
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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 = Arrays.copyOf(elementData, newCapacity);
}
容量增加为原来的1.5倍的实现
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)的判断是因为oldCapacity有可能为0，这样得到的newCapacity也会为0
if (newCapacity - MAX_ARRAY_SIZE > 0)的判断确保数组的容量不大于Integer的最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
最后再返回一个包含原来数据的新容量的数组
elementData = Arrays.copyOf(elementData, newCapacity);
到这里上文的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的选择问题也就明了清晰了
-
调用无参构造函数时创建容器时，当第一次往该容器添加对象时，执行到
ensureCapacityInternal,因为这个时候minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)形参列表中的minCapacity必定是1，所以初始化出来的elementData必定是长度为10的数组，这就是为什么网传默认的ArrayList的容量为10的由来 -
当调用剩下两个构造函数初始化时，即便初始化出来是容量为0的容器，在第一次往容器里添加对象时，只会让容量扩充到1
// oldCapacity为0，newCapacity为0，minCapacity为1，
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
个人猜测这个设计的由来是为了容器容量的缓慢增长，避免浪费太多的空间，所以以后编码遇到容器类需要存储比较少对象的时候，用带参数的构造函数有利于节省内存
好了，上面就是ArrayList的重头戏扩容，还有剩余的几个add方法也一并过了
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++;
}
add(int index, E element)方法，根据制定下标开始添加元素，首先会调用rangeCheckForAdd方法判断下标是否有错，然后再判断是否需要扩容，然后调用
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
将index之后的数据往后移一位，最后将element添加到elementData的index，同时size增加
add系列还有
public boolean addAll(Collection<? extends E> c) // 添加集合
public boolean addAll(int index, Collection<? extends E> c) // 往直接下标开始添加集合
具体实现就不再啰嗦了，大同小异，有兴趣可以自己翻阅，我们进入下一个模块
- 获取
ArrayList提供好几种获取容器内对象的方法
第一种，get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
简单易懂，就不叙述了
第二种，通过Iterator()返回私有内部类Itr对象(Itr实现了Iterator接口)，然后在迭代器对象基础上获取容器内的对象
各种迭代器的方法我就不在叙述了
第三种，通过listIterator()或者listIterator(int index)返回私有内部类ListItr对象(ListItr继承Itr并实现了ListIterator接口)，然后在迭代器对象基础上获取容器内的对象
ListIterator继承于Iterator，在普通的迭代的基础上增加了往前迭代的操作，因此使用ListIterator迭代ArrayList对象也提供了往前操作对象的方法
这里有一个点注意的是上文中提到的modcount,就拿ListItr中的previous()方法举例吧
我们先过一遍这个方法，游标减1后赋值给i，如果i的值小于0，报错；然后通过闭包获取到外部类的elementData，如果i大于elementData的长度，报错；然后将i赋值给游标，然后直接获取到elementData中的值
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
checkForComodification()，就是这个方法用到了modCount我们点进去看下
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
然后再看下代码中expectedModCount是什么东西
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
int expectedModCount = modCount;
....
}
可以看到expectedModCount就是modCount的一个副本，是在Itr类对象被创建的时候初始化的，也就是一经创建就不会改变。而modCount是在每次操作容器内的数据的时候会自增的，那么什么时候modCount != expectedModCount呢？没错，就是已经通过list对象获取到一个迭代器对象之后，又对list对象进行了数据对象的操作，为此我做了一个测试
意料之中的ConcurrentModificationException
这也是ArrayList线程不安全的一个体现，共享变量是没加锁的，在多线程环境下很容易被修改然后数据就乱套了
其他方法和正常的ListIterator差不多，这里也不再啰嗦了
- 其他模块
其他的大概就是set，remove,size,indexOf序列化的两个方法(readObjact(),writeObject())，在搞定了add()的扩容基础上，前四个也是很小case了，而后两个是私有方法，我们是无法直接使用，找了找资料说是调用ObjectOutInputStream序列化的时候会通过反射调用，这里还没了解过和测试过，也不自作高明了。
后言
看了源码才发现源码真的就像高中数理化那些基础一样，基础好了，弄很多东西都顺手拈来，也是看了源码才知道一个类有哪些地方需要注意，甚至是有哪些地方可以优化，而不是一个API工程师
