JDK1.8中ArrayList是如何扩容的

JDK1.8中ArrayList是如何扩容的

ArrayList简介：

ArrayList实现了List接口它是一个可调整大小的数组可以用来存放各种形式的数据。并提供了包括CRUD在内的多种方法可以对数据进行操作但是它不是线程安全的，外ArrayList按照插入的顺序来存放数据。

在讲扩容机制之前，我们需要了解一下ArrayList中最主要的几个变量：

private static final int DEFAULT_CAPACITY = 10;//数组默认初始容量

private static final Object[] EMPTY_ELEMENTDATA = {};//定义一个空的数组实例以供其他需要用到空数组的地方调用

private static final Objehttp://ct[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定义一个空数组，跟前面的区别就是这个空数组是用来判断ArrayList第一添加数据的时候要扩容多少。默认的构造器情况下返回这个空数组

transient Object[] elementData;//数据存的地方它的容量就是这个数组的长度，同时只要是使用默认构造器（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加数据的时候容量扩容为DEFAULT_CAPACITY = 10

private int size;//当前数组的长度

本题的所有的讲解都是基于JDK8

这道题考察了ArrayList的构造器和对扩容机制的了解，本篇博客基于此出发讲解ArrayList的扩容机制

想要做出这道题必须了解ArrayList的构造函数，ArrayList的构造函数总共有三个：

ArrayList()构造一个空的数组。JDK7中构造一个初始容量为10的空列表但是JDK8中只是构造一个空的数组

ArrayList(Collection extends E> c)构造一个包含指定 collection 的元素的数组，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

ArrayList(int initialCapacity)构造一个具有指定初始容量的空数组。

我们重点来看这两个ArrayList(int initialCapacity)，ArrayList()构造函数

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

初始化一个空数组，这是JDK8不同于之前版本的地方

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);

}

}

对于形参initialCapacity判断，如果大于0那么就声明一个和形参一样大小的数组。了解到这里似乎这道题的正确答案也出来了即选择A，并没有发生扩容

但是作为一名合格的程序员要有探索精神，题目提到了扩容，既然ArrayList底层是一个数组，那么就肯定会满，什么时候发生扩容呢？

//1.add方法为添加元素在数组末尾

public boolean add(E e) {

//确保数组容量 size指向数组的末尾

ensureCapacityInternal(size + 1);

//在完成添加之前要确保数组长度足够

elementData[size++] = e;

return true;

}

//3.elementData为ArrayList底层维护的数组，minCapacity为此时数组的大小

private static int calculateCapacity(Object[] elementData, int minCapacity) {

//如果数组为初始化的值，就初始化数组容量为10(空参的构造方法下首次添加)

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

return minCapacity;

}

//2.minCapacity表示此时数组的大小

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

//4.minCapacity表示此时数组的大小

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

//如果此时数组容量的大小不够就扩容

if (minCapacity - elemenhttp://tData.length > 0)

grow(minCapacity);

}

源码读到这里，我们明白了，当我们每次向ArrayList添加元素的时候，都会首先确保数组容量够放下元素如果不够就会 grow(minCapacity)调用扩容函数，那么秉承着探索的精神，原本大小的数组扩容之后变成多大了呢？还得继续看源码

//扩容源码

private void grow(int minCapacity) {

//获取当前数组的长度

int oldCapacity = elementData.length;

//>>右移相当于整除2，新容量相当于就旧容量的1.5倍

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);

}

源码大致读完后，我们明白了ArrayList的自动扩容机制，每次新添加元素的时候都会判断是否能够容下，如果不够就会发生扩容，扩容的大小为原大小的1.5倍数，明白这些以后让我们看看下面这段程序扩容了几次呢？？容量是多少呢？

ArrayList arrayList = new ArrayList(20);

for(int i=1;i<=50;i++) {

arrayList.add(i);

}

前20次添加不会发生扩容，当21元素添加时数组容量从20扩容到30，当添加31元素时数组容量从30扩容到45，当添加46元素时数组容量从45扩容到67

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。