ArrayList 源码分析(jdk1.8)
类继承关系:
(*=>:接口实现)
java.lang.Object
–java.util.AbstractCollection =>Collection
–java.util.AbstractList =>List
–java.util.ArrayList =>List,Serializable(), Cloneable, RandomAccess
什么是ArrayList
ArrayList既然类名中包含array,那必然跟数组有关,ArrayList其底层是通过数组实现的,但是与数组不同的是,定义一个数组时必须要定义其长度,与定义好其容量就不会改变的数组相比,ArrayList是根据不断添加的元素,而自动扩容的动态数组(下面将详细介绍)。
源码分析:
1.类继承实现
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable,Serializable{
//方法....
}
在这里扩展了AbstractList类,实现了List接口,但是查看RandomAccess,Cloneable,Serializable这三个接口时,发现是空接口……..
其实这里的这三个接口只是起到标记作用,是接口的一种非典型用法的标记接口。
例如Collections.shuffle()就是通过instanceof 判断该集合是否实现了RandomAccess接口来执行不同的随机排序算法。
RandomAccess:这个接口用于表示集合是否支持快速访问,ArrayList是基于数组实现的,支持快速随机访问。而LinkedList中则没有实现这个接口,因为LinkedList是双向链表,虽然支持通过下标进行访问,但是代价却很大。
Cloneable:可以克隆。ArrayList中也重写了clone方法(浅克隆)
Serializable:可以序列化,这个用的比较多就不说了。
我个人不太理解的是为什么不使用Annotation,而去采用这种标记接口的方式,或许是这种设计方式比较早,还没有Annotation,现在难以修改,不知道理解的对不对,如果有了解的大神,还请留言指点一下,谢谢。
2.成员变量/
**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例
* 我们根据第一个元素被添加时知道多少个元素去填充把它与EMPTY_ELEMENTDATA
* 区分开来.
* (这个变量是jdk1.8新加的)
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存了添加到ArrayList中的元素的数组
* transient修饰不会被序列化
*/
transient Object[] elementData;
/**
* 数组当前长度
* 其实就是这个ArrayList的长度 ,调用size()方法的返回值
*/
private int size;
/**
* 数组最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
需要注意的变量:
elementData这个数组其实就是用来存储向ArrayList添加的元素的,在第一次初始化的时候给这个数组初始化长度为DEFAULT_CAPACITY(10),可以添加null值,当数组长度不足时会进行扩容为1.5倍,下面会详细介绍。
transient 修饰elementData表示将不会被序列化,但是ArrayList又是一个可序列化的类,因为elementData是个缓存数组,通常会预留一些容量,ArrayList在序列化时会调用writeObject(),反序列化时调用readObject()方法,这样保证只序列化实际存储的元素,而不是整个数组。
3.主要方法
构造方法
ArrayList一共提供了3种构造方法
1.
/**
* 这一种是我们最常用的构造方法
* 直接创建一个空数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.
/**
* 根据指定容量创建
*/
public ArrayList(int initialCapacity) {
//指定容量>0时,根据指定容量创建数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//当指定容量为0时,直接创建空数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
//其他情况 非法参数异常 带回参数
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
3.
/**
* 创建一个和传入集合一样的ArrayList
*/
public ArrayList(Collection<? extends E> c) {
//将传入集合转换为数组,赋给elementData(ArrayList中存储元素的数组)
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toarray可能(错误地)不返回对象[ ]
if (elementData.getClass() != Object[].class)
//copy数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 用空数组替换。
this.elementData = EMPTY_ELEMENTDATA;
}
}
获取元素
/**
*
*/
public E get(int index) {
//检查参数是否正确
rangeCheck(index);
//因为ArrayList是通过elementData这个数组存储元素
//所以直接根据下标获取该数组的元素即可
return elementData(index);
}
/**
* 检查是否越界
*/
private void rangeCheck(int index) {
if (index >= size)//如果index大于当前长度 异常索引越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加元素
/**
* 添加元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); //扩容方法 size+1为最小容量(添加一个元素 所以为1)
elementData[size++] = e;
return true;
}
/**
* 获取所需最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
//如果elementData为空数组时
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY(默认容量10)和最小容量中取最大的为最小容量
minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 是否扩容判断
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//修改次数++
//需要的最小容量比elementData长度大时,容量不足,则需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 扩容
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//新的容量为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果超过最大长度 则设置为最大长度 不管了
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//对数组进行复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
当我们使用ArrayList时,如果需要加入大量的元素时,将不断会进行扩容,进行数组copy,这样的效率很低,在jdk1.8中提供了ensureCapacity()方法,我们可以预先设置容量,来提高初始化效率。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
移除元素
/**
* 根据下标移除
*/
public E remove(int index) {
//检查是否越界
rangeCheck(index);
//修改次数+1
modCount++;
//获取要移除的元素
E oldValue = elementData(index);
//数组elementData中index位置之后的所有元素向前移一位
int numMoved = size - index - 1;
if (numMoved > 0)
//复制数组
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
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;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null;
}
4.Fail-Fast 机制
为什么要记录修改操作次数?
关于modcount是从AbstractList中继承来的,用来检查列表中的元素是否发生结构性变化,当一个线程正在迭代遍历,另一个线程修改了这个列表的结构。就会出现ConcurrentModificationException异常。这种情况下我们就需要Collections.synchronizedList加上线程锁控制,或者使用Concurrent并发包下的CopyOnWriteArrayList。
同理我们也不能在迭代过程中用集合方法去操作集合,如果需要进行操作,则需要使用迭代器中提供的方法进行修改。
---------------------
原文:https://blog.csdn.net/qq_23830637/article/details/78979628
上一篇: Docker端口映射实现网络访问
下一篇: php正则提取img所有属性值