原文链接http://zhhll.icu/2021/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/ArrayList%E8%AF%A6%E8%A7%A3/
ArrayList详解
List中使用最多的就是ArrayList，基本上大家在实例化一个List的时候都是
List list = new ArrayList();
所以在这里了解一下ArrayList的实现过程(以java8为例)
主要特点
- 有序存储元素
- 允许元素重复，允许存储null值
- 支持动态扩容
- 非线程安全
继承关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList
继承了AbstractList类，实现了List接口、RandomAccess接口、Cloneable接口和Serializable接口，所以ArrayList是支持随机访问、克隆和序列化的
源码分析
关键变量
/**
* 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 默认的空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认无参构造器使用的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList底层用来存储数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList实际的长度
*/
private int size;
/**
* 可分配的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造函数
/**
* 自定义初始化容量，根据传入的初始化容量来确定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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 通过集合来进行初始化，使用了Arrays.copyOf来将集合中的数据copy到数组中
*/
public ArrayList(Collection<? extends E> 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;
}
}
add方法
public boolean add(E e) {
// 在添加元素之前先确认一下容量是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// minCapacity为当前所需要的最小容量
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);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 当原数组为空数组时，newCapacity为0，是小于minCapacity 10 的
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);
}
remove方法
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); // index所对应的元素被删除，后续所有的元素向前移动一位
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
其他的方法都是中规中矩的操作数组
如:
// get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 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;
}
迭代器
在使用foreach循环遍历的时候实际上是使用的迭代器，对于ArrayList而言，使用普通的for循环会比使用foreach效率更高
接下来看一下ArrayList的迭代器
public Iterator<E> iterator() {
return new Itr();
}
Itr是ArrayList的内部类，实现了Iterator接口
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
// 当Itr被实例化的时候，记录一下迭代器被实例化时ArrayList的修改次数(在用ArrayList进行add/remove操作时modCount每次都加一)
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
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];
}
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();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
// 检查是否被修改了
checkForComodification();
}
// 检查是否被修改了
final void checkForComodification() {
// 当修改次数与Itr被实例化时的修改次数不一致时，说明在进行迭代操作的时候其他线程进行了ArrrayList的add/remove操作，此时抛出ConcurrentModificationException，即为fast-fail快速失败机制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
使用说明
- 由于ArrayList的默认初始值为10，扩容为1.5倍，如果集合中所需要存储的元素数量多的话，需要进行多次扩容，重新申请内存并进行赋值，比较耗时，所以如果在进行实例化时指定初始容量，可以减少扩容次数，提升性能
由于本身的博客百度没有收录，博客地址http://zhhll.icu
网友评论