ArrayList 基本介绍
ArrayList
实现了List
接口。它可以存储包括null
的任何类型的对象,允许重复元素。ArrayList
在内部使用一个数组来存储元素,当元素数量超过数组容量时,ArrayList
会自动重新分配更大的内部数组,并且将现有元素复制到新数组中。ArrayList
基本等同于Vector
,但是ArrayList
是线程不安全的(执行效率高),在多线程情况下不建议使用ArrayList
。
ArrayList 源码阅读及操作机制
首先ArrayList
中用来存储元素的数组是 Object 类型的数组 elementData,ArrayList
的容量就是这个数组的大小。
transient Object[] elementData;
通过 debug 下面这段代码来观察ArrayList
的扩容机制。
public class TestArrayList() {
public static void main(String[] args) {
ArrayList list = new ArrayList();
// ArrayList list = new ArrayList(4);
for (int i = 1; i <= 10; i++) {
list.add(i);
}
for (int i = 11; i <= 15; i++) {
list.add(i);
}
}
}
构造方法
当使用无参构造器创建ArrayList
对象时,会创建一个默认容量为10的空数组。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 用于默认大小的空实例的共享空数组。将其与 EMPTY_ELEMENTDATA 区分开,
// 以便在添加第一个元素时知道需要扩容多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
使用指定大小的构造器创建ArrayList
对象时,则初始 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);
}
}
add(E e)
add(E e)
方法将指定元素添加到列表末尾,该方法先调用ensureCapacityInternal()
方法确保容量至少是所需的最小容量(即当前大小加一),然后再赋值。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
由于ArrayList
允许的元素类型是 Object,所以添加基本类型的数据时,会先将其转换为对应的包装类型。
ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
calculateCapacity()
该方法计算需要的容量,如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
(使用无参构造器时即符合该条件),则返回DEFAULT_CAPACITY
(10),否则返回 minCapacity(size + 1)。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private static final int DEFAULT_CAPACITY = 10;
ensureExplicitCapacity(int minCapacity)
modCount 记录列表被结构性修改的次数(结构性修改是指添加或删除一个或多个元素,或显式调整后备数组的大小,仅仅设置元素的值不是结构性修改)。如果需要的容量大于 elementData 的长度,则调用grow()
方法进行扩容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow()
该方法增加容量以确保列表至少能够容纳最小容量参数minCapacity
指定的元素数量。计算得到新容量应为旧容量的 1.5 倍。如果计算得到的新容量小于需要的最小容量,则新容量应为需要的最小容量(使用无参构造器第一次添加元素时即为这种情况,第一次扩容为 10)。如果请求的数组大小超过了虚拟机的限制,可能会导致 OutOfMemoryError。最后通过数组复制copyOf.copyOf()
来进行真正的扩容。
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 = copyOf.copyOf(elementData, newCapacity);
}
总结
当使用无参构造器创建ArrayList
对象时,elementData 初始容量为 0,第一次添加元素时 elementData 扩容为 10,以后再需要扩容,按 1.5 倍来扩容。若使用有参构造器创建ArrayList
对象,elementData 初始容量为指定大小,如果需要扩容,则扩容为 1.5 倍。
值得注意的是,由于每次调整容量都需要将所有元素复制到新数组中,所以在元素数量较多时,频繁地调整容量可能会导致性能下降。为了避免频繁地调整容量,可以使用ArrayList
的指定大小的构造方法或在添加大量元素之前使用ensureCapacity()
方法预先指定较大的容量,以减少容量调整的次数。文章来源:https://www.toymoban.com/news/detail-480258.html
另外,当从ArrayList
中删除元素时,并不会立即缩小内部数组的容量。如果希望减少内存占用,可以使用trimToSize()
方法来调整ArrayList
的容量,使其与元素数量匹配。这样可以释放未使用的内存空间。文章来源地址https://www.toymoban.com/news/detail-480258.html
到了这里,关于ArrayList 底层结构和源码分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!