Java基础之ArrayList的扩容机制

Java基础之ArrayList的扩容机制

我们知道java中的ArrayList对象底层是基于数组实现的，而数组是有长度限制的，那基于数组实现的ArrayList是否有长度限制呢？我们通过ArrayList的构造方法来剖析

ArrayList提供了3种构造方法以便我们来获取：

ArrayList(int initialCapacity) 第一种需要赋值长度进行new

ArrayList() 第二种无参构造，不需要赋值数组初始长度

ArrayList(Collection extends E> c) 第三种入参一个继承了Collection对象转化为ArrayList

//需要赋值ArrayList一个int类型长度值

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

}

}

//无参构造

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

//入参继承了Collection对象转化为ArrayList

public ArrayList(Collection extends E&Tlvnagt; c) {

elementData = c.toArray();

if ((size = elementData.length) != 0) {

// c.toArray might (incorrectly) not return Object[] (see 6260652)

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

} else {

// replace with empty array.

this.elementData = EMPTY_ELEMENTDATA;

}

}

接下来我们从ArrayList的赋值初始长度的构造方法和无参构造方法进行跟踪，来得到我们的答案；

1.ArrayList(int initialCapacity)

/**

* Shared empty array instance used for empty instances.

*/

private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {

//initialCapacity大于0的情况下，就去new一个Object类型、长度为initialCapacity的数组

if (initialCapacity > 0) {

this.elementData = new Object[initialCapacity];

} else if (initialCapacity == 0) {

//initialCapacity等于0的情况下，则生成已经创造好的Object[]；

this.elementData = EMPTY_ELEMENTDATA;

} else {

//initialCapacity小于0的情况下，直接抛异常

throw new IllegalArgumentException("Illegal Capacity: "+

initialCapacity);

}

}

通过上述源码分析，在赋值初始长度的构造方法中，如果initialCapacity符合大于0的情况下的话，在new ArrayList的时候是会创造一个长度为initialCapacity的对象数组，而小于0的情况下则返回已经创造好的Object[] EMPTY_ELEMENTDATA；

2.ArrayList(）

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {

//当你没有赋值初始长度时，同样是去赋值已经创造好的空数组，没有长度值

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

当ArrayList生成后，我们接着来看他的add()添加方法,找到ArrayList实现的ahttp://dd方法：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public boolean add(E e) {

//1、add的第一步先去调用ensureCapacityInternal方法传入size+1

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

//3、传入一开始我们new的数组和add后的数组长度

private static int calculateCapacity(Object[] elementData, int minCapacity) {

//如果elementData等于空数组，则对比DEFAULT_CAPACITY和minCapacity大小，返回大的值，DEFAULT_CAPACITY默认为10

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

//否则返回minCapacity

return minCapacity;

}

//2、在ensureCapacityInternal方法内部又去调用calculateCapacity(elementData, minCapacity)方法，传入add数据后的list的size长度

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

//4、拿到minCapacity的值后，对modCount++，比对添加后的list的长度和现在的list的长度来判断是否需要进行扩容；

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// 如果添加list的长度大于list现在的长度，则说明list的长度已经不够了，需要走grow(minCapacity)方法进行扩容

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

经过上面的分析，我们发现在add时，ArrayList会先去判断你是不是一个空数组，如果是的话则会给你赋值数组的,长度值，默认为10，到这一步我们就知道了，不管是哪种构造方法都会在add时，都会进行判断给空数组进行赋值长度，也就是说对于ArrayList来讲，他是需要数组的长度的，同时他还会对比数组原来长度和add后的长度来判断是否需要进行扩容。

接下来我们看grow(minCapacity)扩容方法：

private void grow(int minCapacity) {

// 拿到数组原来的长度

int oldCapacity = elementData.length;

//进行1.5倍计算

int newCapacity = oldCapacity + (oldCapacity >> 1);

//如果1.5倍的值小于add后的长度值，则把add后的长度值设置成新数组的长度

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

//如果1.5倍的值大于array的最大长度则调用hugeCapacity(minCapacity)方法

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// 调用Arrays.copyOf方法传入旧数组对象和新数组的长度，进行扩容

elementData = Arrays.copyOf(elementData, newCapacity);

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

//如果add后的长度大于array的最大长度那就返回Integer的最大长度，否则返回array的最大长度，丢弃1.5倍的值，选择array的最大长度来进行扩容

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

到此，我们对于源码的分析就结束了。

结论：

1.new的时候可以给ArrayList设置数组的长度值，也可以不设置，不设置的情况下，在第一次add时会默认赋值长度为10

2.每一次add时都会去对比add后的长度值和数组原有长度值，判断是否需要走grow(int minCapacity)扩容方法

3.默认ArrayList是以1.5的长度进行扩容，会先去创造一个新的长度的数组，再将原来数组赋值过去，完成扩容操作

4.还会去对比1.5的长度和array的最大长度进行选择用array的最大长度还是选择Integer的最大长度

5.工作时，如果我们能知道ArrayList将要存储多少数据时，最好是new的时候赋值一个初始值，因为去数组扩容肯定是要浪费时间和cpu资源的

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。