ArrayList 源码分析
ArrayList 认识
ArrayList是最常见以及每个Java开发者最熟悉的集合类了
| 关注点 | 结论 |
|---|---|
| ArrayList是否允许空 | 允许 |
| ArrayList是否允许重复数据 | 允许 |
| ArrayList是否有序 | 有序 |
| ArrayList是否线程安全 | 非线程安全 |
两个全局变量
- elementData ：ArrayList 是基于数组的实现，底层是一个数组elementData
- size：ArrayList 里面元素的个数，当 执行add() 方法时 size 会自增，执行 remove() 方法时，会自减，
所以add了一个null进入ArrayList，size也会加1
ArrayList 构造方法
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
//假如 c.toArray() 返回的不是Object[]
if (elementData.getClass() != Object[].class)
//通过 Arrays.copyOf() 转化为 Object[]
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
第一个构造方法 首先将elementData 数组初始化，数组开始默认长度为 DEFAULT_CAPACITY = 10
第二个构造方法接受一个int类型的参数 ，能够自定义elementData 数组的长度
第三个构造方法一个Collection 类型的参数
ArrayList添加元素
1 public boolean add(E e) {
2 ensureCapacityInternal(size + 1); // Increments modCount!!
3 elementData[size++] = e;
4 return true;
5 }
暂不考虑第二行 ensureCapacityInternal 方法，它只是扩容用的
底层实际上在调用add方法的时候只是给elementData的某个位置添加了一个数据而已
elementData中存储的应该是堆内存中元素的引用，而不是实际的元素
ArrayList 扩容
private void ensureCapacityInternal(int minCapacity) {
// 如果 elementData 是空的集合
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改次数自增
modCount++;
如果下一个元素的 size 大于数组的长度 那么就要进行扩容了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//获取数组的长度
int oldCapacity = elementData.length;
//将数组的长度扩大 比如默认的数组长度是10 扩大后 长度就是 15 了
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩大后的长度 依然小于 下一个元素的 size 比如：刚开始时是一个空数组，
//数组的长度为0，经过上一行代码扩大后 还是0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//假如扩大后的长度 大于 限定的数组最大长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
//最大容量可以是 Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//最后调用到的是Arrays的copyOf方法，将元素组里面的内容复制到新的数组里面去
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList 删除元素
ArrayList支持两种删除方式：
- 按照下标删除
public E remove(int index) {
//检查 index 是否合法
rangeCheck(index);
//修改次数自增
modCount++;
E oldValue = elementData(index);
//需要移动元素的个数
int numMoved = size - index - 1;
if (numMoved > 0)
//将index 后面 的所有元素 都向前移动一位
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//将元素最后一个元素置为null
elementData[--size] = null; // clear to let GC do its work
//返回删除的元素
return oldValue;
}
- 按照元素删除，这会删除ArrayList中与指定要删除的元素匹配的第一个元素
public boolean remove(Object o) {
//判断要删除的元素是否为null
if (o == null) {
for (int index = 0; index < size; index++)
//假如元素 == null
if (elementData[index] == null) {
// 删除元素 算法 跟 remove(int index) 差不多
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
ArrayList 插入元素
- 按指定索引插入
public void add(int index, E element) {
//检查 index 的 值是否合法
rangeCheckForAdd(index);
//修改次数自增
//是否需要扩容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
//index 后面的元素都要向后移动一个位置
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//在index位置上添加源
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 默认的索引插入
public boolean add(E e) {
//修改次数自增
//是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//往数组中添加元素
elementData[size++] = e;
return true;
}
ArrayList的优缺点
从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下：
-
ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快
-
ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已
不过ArrayList的缺点也十分明显：
-
删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
-
插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能
ArrayList和Vector的区别
ArrayList是线程非安全的，这很明显，因为ArrayList中所有的方法都不是同步的，在并发下一定会出现线程安全问题。那么我们想要使用ArrayList并且让它线程安全怎么办？一个方法是用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List，比如
List<String> synchronizedList = Collections.synchronizedList(list);
另一个方法就是Vector，它是ArrayList的线程安全版本，其实现90%和ArrayList都完全一样
为什么ArrayList的elementData是用transient修饰的
看一下ArrayList中的数组，是这么定义的：
private transient Object[] elementData;
看一下ArrayList的定义：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
看到ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么？因为序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素
