ArraysList扩容的源码

Sub-item

type

status

date

slug

summary

category

icon

password

Parent item

日期

Sep 19, 2023 03:01 AM

首先ArrayList是我们List接口的一个实现类，是线性非安全的。优点是访问数据快，复杂度为O(1),缺点是对数据进行删除和添加的话不方便，时间复杂度在最好的情况下为O(1)，最坏的情况下为O(n)。

第一个参数是编号，第二个参数是10，是ArrayList在加入元素时会进行，扩容的长度。

然后是两个默认的空数组。

第一个ArraysList的存储数组第二个是ArrayList的大小（它包含的元素数）

一共三个构造方法，第三个暂不讨论，第一个和第二个

两个构造方法，分别是带参数的构造方法和不带参数的构造方法。我们可以看到，如果我们在构造ArrayList的时候，如果一开始就带了参数，那么如果参数大于0的情况下，我们会为它创建长度为参数大小的数组，否则我们按照默认的空数组进行创建。

来到add方法，首先我们将size进行一个加一，因为我们我们是新加入了一个元素，然后调用我们的ensureCapacityInternal方法判断我们现在的存储空间是否是够用的，然后我们进行一个赋值操作。

在这里我们可以看到我们将现在的size和我们的初始默认参数进行了一个比较，并且取了他们当中的最大值。（即当我们加入1个元素时，此时的minCapacity为1，而Default参数为10）所以此时我们的minCapacity已经变成了10，然后我们进入到ensureExplicitCapacity方法中进行判断。

我们可以轻松地看出我们的if是成立的，因为minCapacity是10，而此时的elementData的长度是0.所以我们可以继续向下进入到，grow方法中进行扩容。

在这个方法中我们可以看到我们的ArrayList是怎样进行扩容的了，首先我们将长度定义为之前的长度加上之前的长度右移一位位之后得到的树（并不是完全意义上的1.5倍，但是近似）。然后我们判断当前扩容之后的长度是否够用，否则我们就以传入的长度（我的理解此时数据的多少）作为数组长度，因为这是我们一开始取了max之后的长度。

例如在addAll() 方法中我们可以看出。

此时的size是加上了我们要加入的所有元素的长度的。所以我们在前面得到的size+1则是我们此时数据的真实长度，所以我们如果使用此方法，我们的扩容就可能跟不上我们的1.5倍扩容机制，所以我们才有了不够的情况下使用真实长度作为数组长度的情况。而最后的实现才用的是Arrays.copyOf方法，此方法区别于下面的System.arraycopy的方式，此方法是在原数组的基础上进行长度的改变，如一开始我们的数组nums是1,2,3 如果我们使用了Arrays.copyOf（nums,5）此时数组则变为了1,2,3,0,0

ArrayList中还有在index添加元素的add方法，此时我们主要利用的是System.arraycopy的方式进行实现，此方法主要是在两个数组上进行实现，方法的参数分别是源数组，开始复制的下标，目标数组，开始的下标，要复制的长度最后的结果是存在目标数组当中的

类似的实现方式还有remove操作

fighting-bug