ArrayList 扩容 讲解 小白易懂版本

易懂版本"/>

ArrayList 扩容 讲解 小白易懂版本

ArrayList 扩容 讲解 小白易懂版本

注意本文使用的是 java 11

首先我们假设有一个空数组，现在要开始添加第一个元素

public boolean add(E e) {//modCount： 这个就是记录修改的次数，比如我们增加或删除元素会对数组的结构造成修改，记录一下次数modCount++;add(e, elementData, size);return true;
}

private void add(E e, Object[] elementData, int s) {//s 就是 size，代表是当前数据的个数if (s == elementData.length) //第一个数据，肯定走这里elementData = grow();elementData[s] = e;//给数组赋值size = s + 1;//大小加1
}

我们看看elementData = grow();做了什么

private Object[] grow() {return grow(size + 1);//这里的size应该是 0 不是 1哈，因为grow()函数先执行的
}

private Object[] grow(int minCapacity) { // 这里的 minCapacity 就是 1（size+1）//然后我们看一下这个新容量应该是多少//newCapacity(minCapacity)return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}

怎么理解minCapacity呢？它就是期望的最小容量。什么叫期望的最小容量？

比如我们当前的 数组 size为2，当我们进行add时（假设我们不知道数组的具体容量），那么我们希望 数组的最小容量应该为 3（ size+1） ， 只有这样，我们在添加数据的时候才不会报错。所以 minCapacity=size+1。

只要理解了minCapacity，arraylist的扩容就没啥难的了。

private int newCapacity(int minCapacity) {// overflow-conscious code// 第一次添加数据// oldCapacity 和  newCapacity 都是 0；int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);// 此时  newCapacity 为 0，minCapacity 为 1if (newCapacity - minCapacity <= 0) {//当我们声明的对象采用默认的无参构造时就会走这一步if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);//先返回 10 和 minCapacity大的那一个if (minCapacity < 0) // overflow 问题直接抛出throw new OutOfMemoryError();return minCapacity;//后面讲这种情况}return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);
}

也就是说，采用默认的无参构造时，数组的初始容量并不是10 ，而是在第一次添加函数之后才变成10。

private Object[] grow(int minCapacity) { // 这里的 minCapacity 就是 1（size+1）//newCapacity(minCapacity)return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}

newCapacity(minCapacity)就是10 。

Arrays.copyOf的底层实现就是根据 我们传递的 newCapacity 声明一个新数组，然后把我们传递的数组的值全都给复制到这个新数组，然后返回这个数组。

那么，第一次进行扩容之后

elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这个条件就不成立了，因为我们的elementData相当于指向新生成的数组所在的空间了。

第一次插入就到这里结束

那么二我们开始第二次插入，省略部分代码

private void add(E e, Object[] elementData, int s) {//s 就是 size，代表是当前数据的个数,此时 s为1if (s == elementData.length) //第二个数据，elementData.length 为 10；不用扩容elementData = grow();elementData[s] = e;//直接给数组赋值size = s + 1;//大小加1
}

ok我们发现第一次扩容之后，要经过好几次add之后才会再次出现再次扩容，当我们的数组大小够用的时候就直接赋值。

我们来到 s = 10 的时候。因为第一次扩容后 数组大小为10 ，当我们插入第11个元素的时候，就会再次出发扩容。

private void add(E e, Object[] elementData, int s) {//s 就是 size，代表是当前数据的个数,此时 s为10if (s == elementData.length) //当前的数据已经把数组占满了，我们即将要插入的这个数据没地方放了elementData = grow();//扩个容elementData[s] = e;//直接给数组赋值size = s + 1;//大小加1
}

private Object[] grow() {return grow(size + 1);//这里的size ： 10 
}
private int newCapacity(int minCapacity) {// overflow-conscious code// minCapacity 为 11// oldCapacity 为 10；// newCapacity 为 15int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity <= 0) {//这个条件不成立了if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // overflow 问题直接抛出throw new OutOfMemoryError();return minCapacity;}//开始走这一步 只要我们的 新容量小于最大容量 就返回我们的新容量// 但是如果我们的新容量超出了数组所能接受的最大容量//就返回 hugeCapacity(minCapacity);return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//如果我们当前期望的容量比数组能接受的最大容量大，那么就返回 Integer.MAX_VALUE// 否则就返回 MAX_ARRAY_SIZE ；此时数组已经达到最大的容量了。//因为我们本来是应该扩大1.5倍的，但是不支持了，但是我们期望的大小是不需要这么大的//那么MAX_ARRAY_SIZE 就刚好合适return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}

if (newCapacity - minCapacity <= 0) {//这个条件不成立了//当我们声明的对象采用默认的无参构造时就会走这一步if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // overflow 问题直接抛出throw new OutOfMemoryError();return minCapacity;
}

上面是无参构造一个arraylist集合的扩容，我们发现 return minCapacity;这个代码好像没用到。emm

那么我们看一下另外一种情况

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

指定初始值的扩容

我们先来看指定的初始值为0这种情况

this.elementData = EMPTY_ELEMENTDATA;

我们还是来看第一次添加元素，

private void add(E e, Object[] elementData, int s) {//s 就是 size，代表是当前数据的个数if (s == elementData.length) //第一个数据，肯定走这里elementData = grow();elementData[s] = e;//给数组赋值size = s + 1;//大小加1
}
private Object[] grow() {return grow(size + 1);//这里的size ： 0
}
private Object[] grow(int minCapacity) { // 这里的 minCapacity 就是 1（size+1）//newCapacity(minCapacity)return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {// minCapacity 为 1// oldCapacity  newCapacity 都是 0int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);// 此时  newCapacity 为 0，minCapacity 为 1if (newCapacity - minCapacity <= 0) {//条件成立//当我们指定了默认的初始值为0  this.elementData = EMPTY_ELEMENTDATA;//这个判断就不成立了if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // overflow 问题直接抛出throw new OutOfMemoryError();//就走到了这里，返回了个 1 !return minCapacity;}...
}

此时 elementData.length变成了 1！

private void add(E e, Object[] elementData, int s) {//s 就是 size，代表是当前数据的个数if (s == elementData.length) //第一个数据，肯定走这里elementData = grow();
}

当我们第二次添加元素的时候依旧会触发扩容

private int newCapacity(int minCapacity) {// miminnCapacity 为 2// oldCapacity  1  newCapacity 还是 1int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity <= 0) {//条件成立了//就走到了这里，返回了个 2 !return minCapacity;}...
}
那么再添加元素（就不看代码了）
oldCapacity = 2   newCapacity = 2+2/2 = 3
minCapacity = 3  返回的还是 minCapacity
再来一次
oldCapacity = 3    newCapacity = 3+3/2 = 4
minCapacity = 4  返回的还是 minCapacity
再来
oldCapacity = 4    newCapacity = 4 + 4/2 = 6
minCapacity = 5 开始变了！
开始变成 6 了！     
return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);    
那么再添加元素就跟上面无参的情况一样了，根据情况判断是否扩容

至于初始容量不为 0 的 数组。就应该是先一个一个插入，然后不够了再扩容了！（就不再跟代码吗）