先上图
类继承关系图
ArrayList 是我们经常使用的java util. 首先我们来看看他的继承关系图，ArrayList 继承自AbstractList,实现了List,Serializable,Cloneable,RandomAccess接口。
- List:底层基于数组实现容量大小动态变化，允许 null 的存在。
- Serializable: 序列化，序列化是将对象状态转换为可保持或传输的格式的过程
- Cloneable:可复制
- RandomAccess:快速访问
成员变量：
//序列化ID
private static final long serialVersionUID = 8683452581122892189L;
//数组默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//区分上一个，添加第一个元素时，知道要扩容
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
//数组容量大小 没有使用volatile 修饰，非线程安全
private int size;
构造函数：
- 无参数初始化
- 指定容量初始化
- 指定初始数据初始化
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
增：
public boolean add(E e) {
//确保数组空间大小足够，不够就扩容，size维护当前数组大小，会修改modCount表示版本号
ensureCapacityInternal(size + 1); // Increments modCount!!
//直接赋值，在多线程情况下，不能保证线程安全
elementData[size++] = e;
return true;
}
add会链式调用
ensureCapacityInternal———>calculateCapacity-————>ensureExplicitCapacity—>grow
业务也比较简单
拆成多个函数的好处：
- 增强代码的复用性
- 方便测试
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//看是否是容量为10的那个
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);
}
grow函数为扩容函数
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
扩容实现和工程意识：
- 扩容规则为1.5倍扩容
- 最大扩容空间为Integer.MAX_VALUE,超过，JVM也不会再为这个数组分配内存空间 了
- 源码在扩容的时候注意到了检验容量的合法值，也就是上下界，及时抛出异常
- 扩容完毕且无异常的情况下，再elementData[size++] = e;没有任何锁，所以线程不安全
- Arrays.copyOf(elementData, newCapacity)传回的数组是新的数组对象，先建立一个newCapacity的新数组，然后把老数组的数据拷贝过去。
（见注释）
public E remove(int index) {
//先做一个检查，检查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;
}
这里注意一个点：
就是判断了删除指定元素对null做了if-else判断，因为添加元素的时候是没有对null进行校验的，所以数组中有null值
其实到现在我们可以发现源码逻辑很简单清晰，但是我们看源码就会感觉他调过来调过去的，其实会发现他调用的那些函数都是职责高度单一的任务，这样就可以实现代码的重用，极大的减少冗余代码。同时，在实现一个业务时，代码量会极大减少，同时代码结构也会更加清晰。如果出现问题，可以一个函数一个函数的去test，这样就不用一行一行的去test了，也减轻了debug的难度。
get：根据index获取元素，底层是数组，所以可以随机访问
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
其他的函数方法就不一一讲了，实现方式大同小异。
ArrayList 内部还写了四个内部类
内部类仍然是一个独立的类，在编译之后内部类会被编译成独立的.class文件，但是前面冠以外部类的类名和$符号 。
- Itr
- ListItr
- SubList
- ArrayListSpliterator 这是一个静态内部类
前两个是迭代器，实现了java.util.Iterator
迭代器重要参数
int cursor; // 下一个元素的位置
int lastRet = -1; //上一个元素的位置 ，开始的时候为-1
int expectedModCount = modCount; //在一次迭代中，记录此时数组的版本号
hasNext
判断还有没有后继元素，就是看cursor有没有到数组末尾
public boolean hasNext() {
return cursor != size;
}
next
取下一个元素的时候，首先检查数组版本号，那么为啥要检查这个东西呢？因为这是java的快速失败机制，就是避免并发的情况，如果有一个其他的进程修改了这个数组，那么数组的版本号就会发生改变，这样及时发现错误，不会继续执行当前进程。
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];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
remove
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();
}
}
- 删除掉lastRet位置的元素后，lastRet赋值为-1，这样就避免了多次重复调用remove函数删除，只有当next()函数被执行后，lastRet才会赋合法值，也就是说next()函数是remove()函数的前置条件
- 调用this.remove之后，数组版本号发生了变化，expectedModCount = modCount;需要重新赋值
ListItr 继承了Itr，实现大致上也差不多。
SubList
可以看到的是，并没有申请新的空间去存储那些元素，而是共享存储空间，只是对index下标号做了一些处理，在增删改这些方法上都是对ArrayList实例的数据做操作
private final AbstractListparent; private final int parentOffset; private final int offset; int size; SubList(AbstractList parent, int offset, int fromIndex, int toIndex) { this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } public E set(int index, E e) { rangeCheck(index); checkForComodification(); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; }
ArrayListSpliterator ，实现了Spliterator接口
Spliterator为jdk1.8新增接口，也是一个迭代器实现，Spliterator是一个可分割的迭代器，用来分割和迭代给定源的元素，这里的源可以是collection，array和io等。
进行迭代器拆分，每次拆分后的迭代器接近上一次的二分之一。
这是官方对于大数据量数组多线程遍历加工的一种趋势性指引。
推荐博客：jdk8中Spliterator的作用
那么为啥要写这四个内部类呢？为啥需要内部类？-----总结自知乎回答
- 间接实现多继承。内部类可以独立地继承一个抽象类或者实现一个接口，解决继承 + 实现时碰到的方法同名问题和累赘实现问题（实现一个接口，就要重写所有方法）
- 封装性。满足黑箱调用（摒弃白箱调用，可符合接口隔离/单一指责原则）来保护(fields与methods的)封装性，别人无法通过new 对象的方式来访问
- 匿名内部类实现回调（把实现对象作为实参直接传给调用者，从而实现回调）
文章内容来自对网络资料，书本的归纳整理和自己的实践，如果有理解错误或者不足的地方，还请不吝赐教。
