深入理解ArrayList的动态扩容机制及应用

朱雀 2023-10-15 12:14 149阅读 0赞

在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。

![\_20230828230112.png][20230828230112.png]

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)方法来获得一个足够大的容量。

![\_20230828230251.png][20230828230251.png]

![\_20230828230304.png][20230828230304.png]

*  elementData = Arrays.copyOf(elementData, newCapacity);

使用Arrays.copyOf()方法将原有的elementData数组复制到一个新数组中，新数组的容量为计算得到的新容量newCapacity。这实现了实际的数组扩容操作。

#### 使用注意事项和优化 ####

*  初始化大小

在创建ArrayList时，如果我们能够预测大致的数据量，初始化一个合适的初始大小可以减少扩容次数，从而提高性能。

*  避免频繁扩容

频繁的扩容会带来较大的性能开销，因此尽量避免在循环中多次添加元素，以免触发多次扩容操作。

#### 总结 ####

ArrayList作为一种常用的数据结构，在动态扩容机制的支持下，为我们的编程工作带来了很大的便利。深入理解其动态扩容的原理和应用场景，有助于我们更好地在工作中使用ArrayList，同时在面试中也能够展现出扎实的基础知识。

无论是处理不确定数据量的业务逻辑，还是在技术面试中回答ArrayList相关问题，对其动态扩容机制的理解都将让你更加从容应对各种挑战。

[20230828230112.png]: https://img-blog.csdnimg.cn/img_convert/f3d10ebfdeec5ed513e46d5b68ac8be4.png
[20230828230251.png]: https://img-blog.csdnimg.cn/img_convert/561358b35fe598e09622de34b5e71bd3.png
[20230828230304.png]: https://img-blog.csdnimg.cn/img_convert/9e9a709145e55d376214cf18da6fd0d2.png