基于jdk1.8版本
一、本节目录：
- ArrayList的继承体系
- Arraylist的重要的属性
- ArrayList的构造函数
- ArrayList的扩容
- ArrayList的核心方法
- ArrayList的fast fail机制延伸至fast safe
二、继承体系图
image.png
三、重要属性：
- modCount
这个参数我们单独讲，与后面讲到的fast fail有关联，同时也与一个著名的以后ConcurrentModificationException有关。 - 默认初始容量值：
private static final int DEFAULT_CAPACITY = 10;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //最大容量值2^31-9
这两个变量值我们需要区分开，一个是ArrayList的容量capacity，一个是ArrayList盛装的元素的数量
- 盛装元素的容器：
transient Object[] elementData; // transient 表名当前对象不参与序列化
上面所说的size即便是elementData的size
- 初始化容器：
// 如果使用 0 作为初始化容量的时候，ArrayList就会使用这个对象来初始化
private static final Object[] EMPTY_ELEMENTDATA = {};
// 如果使用默认的构造函数的话，就会使用这个对象初始化
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
四、构造函数：
- 默认构造
// 直接使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA来初始化
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 使用指定大小容量的构造
// 当initialCapacity 为0的时候，则会使用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);
}
}
- 使用指定的集合来初始化
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 {
this.elementData = EMPTY_ELEMENTDATA;
}
}
五、扩容机制：
5.1 如果自己来写这个扩容的思路
我们先自己分析一下思路（本来想画一个流程图的，但是后来发现不好命名，所以这个只好自己描述一下），首先只有在往容器里面添加数据的时候才会有扩容这一说，首先由于我们初始化的方法不同，所以在初次添加元素的时候需要做特别的处理，然后判断是否超过最大容量，判断在现有的size+1的基础上是否需要扩容，然后扩容，拷贝数组添加元素。
5.2 ArrayList的思路
private void ensureCapacityInternal(int minCapacity) {
/** 如果使用默认的构造参数的话，则选择minCapacity和DEFAULT_CAPACITY中较大的一个来作为最小的初始容量，
大家可能奇怪，既然判断了初始化这一说，为何还会有传入的minCapacity
和DEFAULT_CAPACITY比较这一说，是因为ensureCapacityInternal也会被addAll调用
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 下面这个完全是基于 **溢出来考虑的**
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
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倍
- x>>y 和 x<<y:
- 首先大原则：左乘右除
- 改写： x>>y x/(2^y)
- 举例：怎样算28最快，2<<3即：2(2*3)
- 原理：具体的原理需要去掰扯位移运算，这个大家自行百度
六、核心方法：
- 添加： 从源码看ArrayList是可以添加null的同时是可以添加重复元素的
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
- 判断空和容量，都是基于size这个成员属性来进行判断的
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
- indexOf：是返回首个和指定元素相等的索引
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;
}
- remove：大家知道数组的一大优势是查询索引快，但是缺点就是对于元素的删减操作效率比较低，所以与之互补的一个数据结构为链表，在java中对应的则是LinkedList
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; // clear to let GC do its work
return oldValue;
}
图示如下：
image.png
还有很多方法，这里不再一一介绍，因为其他的方法比较常规，所以直接看api文档即可，下面重点来介绍一下一个异常和fast fail的故事。
七：fast fail 与ConcurrentModificationException
先看异常：ConcurrentModificationException
modCount：list每进行一次cud操作，modCount就会+1，而在进行遍历的时候则会把这个值复制给expectedModCount ，在遍历的过程中一但这两个值不相等则说明了在遍历的过程中，有另外的线程对list做了修改（添加、删除、修改）这样出现数据不一致的情况是不允许的，所以抛出ConcurrentModificationException
那如果我不使用Iterator遍历是不是就不会出现这个情况呢，是的如果我们使用for循环就不会出现这个事情，但是也有一点小技巧需要注意，如果我们在for循环中遍历的同时删除数据，arraylist的size就会发生改变
for(int i = 0 ; i<list.size();i++) // 不会出现问题
int size = list.size();
for(int i = 0 ; i<size ;i++) // 这种则会报空指针异常
// 这个是ArrayList的一个内部类，用来快速的遍历list的
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;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
现在我们基本上了解了ConcurrentModificationException，下面聊聊fast fail机制：其实ConcurrentModificationException是fast fail的一种响应，当Collection在遍历的过程中发现了修改就可能产生fast-fail，fast fail 机制并不保证在不同步代码的情况下一定会抛出异常，只是进最大努力抛出。注意这个机制对大多数的Collection都是有效的
- 出现的场景：
- 在单线程中：遍历的过程中进行修改（使用Iterator遍历）
- 多线程中：一个线程修改另外一个线程的遍历的 Collection
解决的方法：
- 对对象加锁
- 使用java.util.concurrent包中的类来代替ArrayList和Hashmap来达到
fast safe 和fast fail则是相对应的，可能这个地方我并没有介绍的太清楚，这个点在面试的过程中可能会被问到，做一了解即可，详细的介绍可以看一下这一篇博文https://www.cnblogs.com/shamo89/p/6685216.html
网友评论