ArrayList底层原理剖析
ArrayList实现原理和对应优缺点
ArrayList底层是基于数组来实现的。由于Java数组是定长数组，一旦声明了数组，数组长度就是固定的，存储元素的个数就是固定的。没办法改变。
=> 所以ArrayList自动扩容的实现方式只能是重新声明一个长度更大的数组，并且把旧数组的元素拷贝到新数组中
=> 所以说频繁的往ArrayList存放元素，就会涉及到数组扩容和元素拷贝，这个过程相对来说性能并不是很好
到这里就引申出ArrayList的一个缺点：就是频繁往ArrayList中塞入数据可能会导致性能下降
还有一点就是往ArrayList指定位置插入或者删除元素，由于底层就是基于数组来实现，所以往数组指定位置插入元素，该位置后面的元素就要往后移动。删除元素，该位置开始后面的元素就要往前移动，频繁插入或删除元素，性能会有所下降。这也是ArrayList的一个缺点
说完缺点再说优点，数组是支持随机读的，也就是查询到数组中任意位置的元素。这个过程是基于内存地址来快速定位到元素的，查询性能很高，所以说ArrayList是支持随机读的，可以快速读取到集合中的任意一个元素
ArrayList的应用场景
基于ArrayList的优缺点，不难发现ArrayList更多的是适合读大于写的场景。也就是往ArrayList存放一批数据，后面就不会往ArrayList中频繁的插入或者删除元素，更多的是查询ArrayList的元素。
ArrayList的元素是有顺序的，如果业务需要按照一定顺序去存放元素到集合当中，并且后面不会频繁的去插入新元素而是更多的去读取元素，那么ArrayList是非常合适的选择
ArrayList的核心API
代码语言：java复制public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>(50);
// 存放元素
list.add("张三");
list.add("李四");
list.add("王五");
// 随机读
System.out.println(list.get(1));
// 移除指定位置的元素
list.remove(1);
// 获取元素个数
System.out.println(list.size());
// 修改指定位置的元素值
list.set(0, "赵六");
// 指定索引位置添加元素
list.add(1, "小明");
// 遍历ArrayList
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}ArrayList源码分析
ArrayList构造方法的源码分析
=> 使用无参的构造方法创建对象，则是让ArrayList底层引用一个空的数组，长度为0。容量大小默认是10；
=> 使用有参的构造方法创建对象，则是校验入参合法性，如果大于0则是创建一个指定长度的，元素类型为Object类型 的数组
=> 对ArrayList玩的比较熟的，基本上都会使用有参构造方法来创建ArrayList。如果存储的元素个数比较多，使用无参 构造方法创建ArrayList，默认容量只有10，所以会直接执行好几次数组扩容和元素拷贝，性能不是很高
代码语言：java复制public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 初始化容量，默认是10
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 这个是ArrayList底层引用的数组。元素类型是Object类型的一个数组
transient Object[] elementData; // non-private to simplify nested class access
// 存放的元素个数，默认是0
private int size;
// 有参构造方法，给ArrayList指定容量
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);
}
}
// 无参构造方法，没有指定容量，默认的容量大小为DEFAULT_CAPACITY，也就是10
public ArrayList() {
// 使用无参构造方法，给elementData赋予一个空数组，没有元素
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}ArrayList的add()方法的源码分析
add()是直接在ArrayList中添加一个元素。调用add方法添加元素的时候，则是先判断容量是否充足， ensureCapacityInternal这个后面讲。在容量充足的前提下，添加元素实际上就是往底层维护的数组当中去添加一个元素，添加完再让数组元素个数+1
代码语言：java复制 public boolean add(E e) {
// 这个是判断容量是否充足的方法，涉及到数组扩容和元素拷贝，是ArrayList的核心方法
ensureCapacityInternal(size + 1);
// 直接给数组添加元素，并给元素个数+1
elementData[size++] = e;
return true;
}ArrayList的get()方法的源码分析
这个方法是根据索引获取元素，由于ArrayLIs底层是一个Object数组，根据索引来获取数组中的元素，其实就是基于内存地址直接定位到元素的位置，性能很高，也是ArrayList的一个优势
代码语言：java复制 public E get(int index) {
// 校验索引是否越界，有则抛出一个数组索引越界异常
rangeCheck(index);
// 直接根据索引到数组中获取元素，性能很高
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}ArrayList的add(int,E)方法的源码分析
指定索引位置去插入一个元素。核心就是System.arraycopy(elementData, index, elementData, index + 1, size - index)。就是从指定插入元素位置开始的所有元素，全部往后挪动一个位置，然后再把原来的元素改为要插入的元素值
代码语言：java复制public void add(int index, E element) {
// 校验索引是否越界
rangeCheckForAdd(index);
// 判断容量是否是否充足，是否需要扩容
ensureCapacityInternal(size + 1);
// 把数组中索引位置为index开始，拷贝到原数组中以index+1未开始的位置，拷贝size-index元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 数组元素往后挪动一位后，让index位置的元素改为传入的元素值
elementData[index] = element;
size++;
}ArrayList的remove(int)方法的源码分析
这个方法和上面的方法差不多，核心就是 System.arraycopy(elementData, index+1, elementData, index,numMoved)。就是把要删除元素的索引位置开始，全部往前面挪动一位。最后再把最后一个元素改为null
代码语言：java复制 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);
// 元素往前移动后，最后一个元素改为NULL
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}ArrayList的set(int,E)方法的源码解析
修改指定索引位置的元素值。因为ArrayList底层就是Object数组，所以直接基于内存地址去修改的，所以执行这个方法的性能也是很高的。
代码语言：java复制 public E set(int index, E element) {
// 校验索引是否越界
rangeCheck(index);
// 获取旧元素的值
E oldValue = elementData(index);
// 改为新元素的值
elementData[index] = element;
return oldValue;
}ArrayList的扩容方法源码解析
=> 判断ArrayList引用是否为空数组，如果是则赋予初始化容量为10
=> 如果引用不是空数组，就判断目前元素个数是否超过了数组长度
=> 如果超过数组长度，就重新设置数组容量，大小是旧数组容量的1.5倍
=> 执行Arrays.copyof()创建一个新容量的数组，并且把旧数组的元素拷贝到新数组当中
代码语言：java复制// minCapacity是添加新元素之前的数组元素个数+1
private void ensureCapacityInternal(int minCapacity) {
// 判断elemenetData是否为{}
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 如果是，就直接赋予DEFAULT_CAPACITY,也就是之前说的默认初始化容量10
// 使用无参构造方法创建对象，第一次调用add方法就会执行到这里，给数组默认为10的长度
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 扩容的核心逻辑
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断最小容量是否大于目前数组长度，如果是，才需要扩容
if (minCapacity - elementData.length > 0)
// 扩容的核心逻辑
grow(minCapacity);
}
private void grow(int minCapacity) {
// 获取旧数组长度
int oldCapacity = elementData.length;
// 旧数组长度右移一位，想当于除以2，再加上旧数组长度，等于新数组长度
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);
}
发布评论