从面试角度分析ArrayList源码
共 3650字,需浏览 8分钟
·
2021-02-09 02:25
java8
ArrayList
类图如下:ArrayList
的底层是由数组实现的,数组的特点是固定
大小,而ArrayList
实现了动态扩容
。ArrayList
部分变量如下,在下面的分析中会用到这些变量。/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空的对象数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 无参构造器创建的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放数据的数组的缓存变量
*/
transient Object[] elementData;
/**
* 元素数量
*/
private int size;
一 初始化ArrayList
ArrayList
一般会使用以下两个构造器1.1 无参构造器
ArrayList
的时候如果不指定大小,则会创建一个空数组。public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1.2 指定数组大小的构造器
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 boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add()
中elementData[size++] = e
很好理解,就是将元素插入第size
个位置,然后将size++
,我们重点来看看ensureCapacityInternal(size + 1)
方法;private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureCapacityInternal()
方法中判断缓存变量elementData
是否为空,也就是判断是否是第一次添加元素,如果是第一次添加元素,则设置初始化大小为默认容量10
,否则为传入的参数。这个方法的目的就是获取初始化数组容量。获取到初始化容量后调用ensureExplicitCapacity(minCapacity)
方法;private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
ensureExplicitCapacity(minCapacity)
方法用来判断是否需要扩容,假如第一次添加元素,minCapacity
为10
,elementData
容量为0
,那么就需要去扩容。调用grow(minCapacity)
方法。// 数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
grow(minCapacity)
方法对数组进行扩容,扩容大小为原数组的1.5
倍,如果计算出的扩容容量比需要的容量小,则扩容大小为需要的容量,如果扩容容量比数组最大容量大,则调用hugeCapacity(minCapacity)
方法,将数组扩容为整数的最大长度,然后将elemetData
数组指向新扩容的内存空间并将元素复制到新空间。1.5
倍就会非常消耗空间,因此建议初始化时预估一个容量大小。三 删除元素
ArrayList
提供两种删除元素的方法,可以通过索引
和元素
进行删除。两种删除大同小异,删除元素后,将后面的元素一次向前移动。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;
}
ArrayList
的大小,如果索引范围正确,则将索引位置的下一个元素赋值到索引位置,将ArrayList
的大小-1
,最后返回移除的元素。操作图如下,假如我要移除索引为1
的元素:四 总结
ArrayList
底层是数组实现的,可以进行动态扩容,扩容大小为原来的1.5倍,虽然可以通过动态扩容,但是数组非常大时会特别浪费空间,因此建议初始化时预估数组大小。ArrayList
允许插入重复值和空值。ArrayList
实现了RandomAccess
接口,支持快速随机访问,就是可以通过索引快速查到某个元素,因此遍历时使用for循环的方式效率更高。ArrayList
是线程不安全的,可以通过Collections.synchronizedList
将其转变为线程安全的集合,不过一般不会使用,Vector
和CopyOnWriteArrayList
是线程安全的,Vector
性能一般,逐渐被CopyOnWriteArrayList
取代了。有道无术,术可成;有术无道,止于术
欢迎大家关注Java之道公众号
好文章,我在看❤️