在java编程中，数据结构起着至关重要的作用，而ArrayList作为一种常用的动态数组，为我们在处理数据时提供了便利。其中，其独特的动态扩容机制更是为其赢得了广泛的应用。我们不管在工作还是面试中，都会遇到ArrayList，本文将深入探讨ArrayList的动态扩容机制，以便我们在工作或者面试中用到。
ArrayList简介
ArrayList是Java编程语言中的一个类，它实现了List接口，底层通过数组来存储元素。提供了对List 的添加（add）、删除（remove）、获取元素（get）等功能。其缺点是元素必须连续存储，所以增删慢，优点是查询快。ArrayList具有动态扩容的特性，这意味着它能够根据需要自动调整内部数组的大小，以适应不同数量的元素。
动态扩容详解
当我们向ArrayList 中添加元素(调用add()或者addAll())时,都调用了一个ensureCapacityInternal（）方法
我们来看源码：
add()
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
addAll()
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
从源码可以看到，这两个方法都调用了ensureCapacityInternal（）这个方法，参数是当前list的长度加上要插入的对象给个个数（单个对象的话为1，对象集合的话是集合的长度），既集合添加元素所需最小的长度
ensureCapacityInternal（）
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
ensureExplicitCapacity() 方法的入参是calculateCapacity（）（参数是存储实际元素的数组和集合添加元素所需最小的长度） 方法处理后的值。
calculateCapacity（）
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
当前方法返回的值是如果源集合是空的，则返回 默认容量（10）和元素集合添加元素所需最小的长度值比较，值大的一个，若不为空则返回minCapacity。
ensureExplicitCapacity()
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow
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 = Arrays.copyOf(elementData, newCapacity);
}
我们来详细解读下这段代码
- int oldCapacity = elementData.length;
获取当前数组的容量，也就是elementData数组的长度，即当前存储元素的数组长度。
- int newCapacity = oldCapacity + (oldCapacity >> 1);
计算新的容量。这里使用位运算右移1位（相当于除以2）的方式，将当前容量扩大1.5倍。
如果对 位运算符 >> 不太了解对的家人们可以看下我们上篇文章 深入解析Java中的位运算符：<<、>>和>>>
- if (newCapacity - minCapacity < 0)
检查计算得到的新容量是否满足最小容量要求。如果不满足，则将新容量设置为最小容量minCapacity。
- if (newCapacity - MAX_ARRAY_SIZE > 0)
检查新容量是否超过了最大数组容量限制。MAX_ARRAY_SIZE是ArrayList内部定义的一个常量，表示数组的最大容量。如果新容量超过这个限制，就调用hugeCapacity(minCapacity)方法来获得一个足够大的容量。
- elementData = Arrays.copyOf(elementData, newCapacity);
使用Arrays.copyOf()方法将原有的elementData数组复制到一个新数组中，新数组的容量为计算得到的新容量newCapacity。这实现了实际的数组扩容操作。
使用注意事项和优化
- 初始化大小
在创建ArrayList时，如果我们能够预测大致的数据量，初始化一个合适的初始大小可以减少扩容次数，从而提高性能。
- 避免频繁扩容
频繁的扩容会带来较大的性能开销，因此尽量避免在循环中多次添加元素，以免触发多次扩容操作。
总结
ArrayList作为一种常用的数据结构，在动态扩容机制的支持下，为我们的编程工作带来了很大的便利。深入理解其动态扩容的原理和应用场景，有助于我们更好地在工作中使用ArrayList，同时在面试中也能够展现出扎实的基础知识。
无论是处理不确定数据量的业务逻辑，还是在技术面试中回答ArrayList相关问题，对其动态扩容机制的理解都将让你更加从容应对各种挑战。
