写点什么

从面试角度分析 ArrayList 源码

用户头像
Java旅途
关注
发布于: 2020 年 12 月 15 日

注:本系列文章中用到的 jdk 版本均为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);    }}
复制代码


二、添加元素、动态扩容


ArrayList.add(E e)源码:


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)方法用来判断是否需要扩容,假如第一次添加元素,minCapacity10elementData容量为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提供两种删除元素的方法,可以通过索引元素进行删除。两种删除大同小异,删除元素后,将后面的元素一次向前移动。


ArrayList.remove(int index)源码:


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将其转变为线程安全的集合,不过一般不会使用,VectorCopyOnWriteArrayList是线程安全的,Vector性能一般,逐渐被CopyOnWriteArrayList取代了。


点关注、不迷路


如果觉得文章不错,欢迎关注、*点赞*、收藏,你们的支持是我创作的动力,感谢大家。


如果文章写的有问题,请不要吝惜文笔,欢迎留言指出,我会及时核查修改。


如果你还想看到更多别的东西,可以微信搜索「Java 旅途」进行关注。「Java 旅途」目前已经整理各种中间件的使用教程及各类 Java 相关的面试题。扫描下方二维码进行关注就可以得到这些资料。



发布于: 2020 年 12 月 15 日阅读数: 22
用户头像

Java旅途

关注

还未添加个人签名 2020.06.17 加入

公众号:Java旅途

评论

发布
暂无评论
从面试角度分析ArrayList源码