深圳企业官网网站建设哪家好,做牙科设计的网站,安卓程序下载安装,东莞网页设计制作ArrayList 扩容 讲解 小白易懂版本
注意本文使用的是 java 11
首先我们假设有一个空数组#xff0c;现在要开始添加第一个元素
public boolean add(E e) {//modCount#xff1a; 这个就是记录修改的次数#xff0c;比如我们增加或删除元素会对数组的结构造成修改#xf…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 就是 1size1//然后我们看一下这个新容量应该是多少//newCapacity(minCapacity)return elementData Arrays.copyOf(elementData,newCapacity(minCapacity));
}怎么理解minCapacity呢它就是期望的最小容量。什么叫期望的最小容量
比如我们当前的 数组 size为2当我们进行add时假设我们不知道数组的具体容量那么我们希望 数组的最小容量应该为 3 size1 只有这样我们在添加数据的时候才不会报错。所以 minCapacitysize1。
只要理解了minCapacityarraylist的扩容就没啥难的了。
private int newCapacity(int minCapacity) {// overflow-conscious code// 第一次添加数据// oldCapacity 和 newCapacity 都是 0int oldCapacity elementData.length;int newCapacity oldCapacity (oldCapacity 1);// 此时 newCapacity 为 0minCapacity 为 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 就是 1size1//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 就是 1size1//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 为 0minCapacity 为 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 22/2 3
minCapacity 3 返回的还是 minCapacity
再来一次
oldCapacity 3 newCapacity 33/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 的 数组。就应该是先一个一个插入然后不够了再扩容了就不再跟代码吗
