ArrayList扩容机制

简介: ArrayList扩容机制

先来看Add方法

再来看看ensureCapacityInternal()方法,可以看到add()方法首先调用了ensureCapacityInternal(size+1)
当要add进第一个元素时,minCapacity为1,在Math.max()方法比较后,minCapacity为10
ensureExplicitCapacity()方法
我们来仔细分析一下
1当我们要add进第一个元素到ArrayList时,elementData.length为0(因为还是一个空的list,里面还没有数据,所以没有进行扩容,默认扩容10),因为执行了ensureCapacityInternal()方法,所以minCapacity此时为10。此时,minCapacity - elemetData.length > 0(minCapacity=10,elemetData.length=0)成立,所以会进入==grow(minCapacity)==方法。
2当add第2个元素时,minCapacity为2,此时elementData.length(容量)在添加第一个元素后扩容成10了。此时,minCapacity - elementData.length > 0不成立,所以不会进入(执行)==grow(minCapacity)==方法。
3添加第3、4…到第10个元素时,依然不会执行==grow()==方法,数组容量都为10。知道添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进行grow方法进行扩容
4grow方法

privatevoidgrow(intminCapacity){

// oldCapacity为旧容量,newCapacity为新容量

intoldCapacity=elementData.length;//(0,10,15)

//将oldCapacity右移一位,其效果相当于oldCapacity/2;

// 我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍

intnewCapacity=oldCapacity+(oldCapacity>>1);

// 然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么久把最小需要容量当作数组的新容量

if(newCapacity-minCapacity<0)

newCapacity=minCapacity;

//判断新容量是否大于集合的最大容量(一般大不了)

if(newCapacity-MAX_ARRAY_SIZE>0)

newCapacity=hugeCapacity(minCapacity);

// 给elementData从新赋值(10,15)

elementData=Arrays.copyOf(elementData,newCapacity);

}

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍!
“>>”(移位运算符):>>1 右移一位相当于除2,右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
通过例子探究一下grow()方法
当add第一个元素时,oldCapacity为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity不比MAX_ARRAY_SIZE大,则不会进入hugeCapacity方法。数组容量为10,add方法中return true,size增为1。
当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中rerurn,true,size增为11。
以此类推…这里补充一点比较重要,但是容易被忽视掉的知识点:
java中的length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了length这个属性。
java中的length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法。
java中的size() 方法是针对泛型集合说的,如果想看这个泛型有多少元素,就调用此方法类查看!



相关文章
|
6天前
|
存储 Java
HashMap扩容机制详解
HashMap扩容机制详解
|
6天前
|
存储 Java
ArrayList的初始化容量与扩容机制解析
ArrayList的初始化容量与扩容机制解析
|
6月前
|
存储 Java
ArrayList自动扩容(详细篇)
ArrayList自动扩容(详细篇)
113 1
|
8月前
|
Java
ArrayList扩容机制的相关面试题
ArrayList扩容机制的相关面试题
44 1
|
6天前
HashMap和ArrayList初始大小和扩容后的大小
HashMap和ArrayList初始大小和扩容后的大小
|
6天前
|
Java 大数据
ArrayList扩容机制
ArrayList扩容机制
HashMap的扩容机制
HashMap的扩容机制
|
7月前
|
存储 Java 索引
ArrayList 的扩容机制
ArrayList 的扩容机制
|
7月前
ArrayList扩容机制~
ArrayList扩容机制~