黑马程序员技术交流社区

标题: 【成都校区】ArrayList扩容详解 [打印本页]

---

作者: 小刀葛小伦    时间: 2019-9-5 16:28
标题: 【成都校区】ArrayList扩容详解


基于JDK1.8版本
ArrayList：底层数据结构是数组实现的，因此它的查询很快，增删却很慢，并且它是线程不安全的。
查看ArrayList源码，会发现ArrayList实现了List, RandomAccess, Cloneable, Seria
lizable四个接口。
实现List接口支持了它的大部分功能
实现RandomAccess接口支持它可以快速随机访问元素（通过下标快速访问）。
实现Cloneable接口支持它可以被克隆。
实现Serializable接口支持它可以序列化，可以通过序列化传输。

[Java] 纯文本查看 复制代码

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

三种创建方式：

[Java] 纯文本查看 复制代码

1、public ArrayList()

2、public ArrayList(int initialCapacity)

3、public ArrayList(Collection<? extends E> c)

第一种方式：

[Java] 纯文本查看 复制代码

private static final int DEFAULT_CAPACITY = 10;//默认空间大小为10

transient Object[] elementData;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**

 * Constructs an empty list with an initial capacity of ten.

 */

public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

无参数构建时，创建的ArrayList对象会默认空间大小为10，而且上面代码块种的element和DataDEFAULTCAPACITY_EMPTY_ELEMENTDATA都是空数组
第二种方式：

[Java] 纯文本查看 复制代码

/**

 * Constructs an empty list with the specified initial capacity.

 */

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

     }

}

当initialCapacity大于0时，创建一个大小为initialCapacity的数组

当initialCapacity等于0时，创建一个空数组

当initialCapacity小于0时，则抛出异常

第三种方式：

[Java] 纯文本查看 复制代码

/**

 * Constructs a list containing the elements of the specified

 * collection, in the order they are returned by the collection's

 * iterator.

*/

public ArrayList(Collection<? extends E> 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，创建的对象的空间大小和导入的集合的大小一致

add()方法

[Java] 纯文本查看 复制代码

/**

 * Appends the specified element to the end of this list.

 */

public boolean add(E e) {

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

        elementData[size++] = e;

        return true;

    }

ensureCapacityInternal()方法

[Java] 纯文本查看 复制代码

private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

 

//minCapacity=size+1;

//如果minCapacity大于当前集合的容量，如果大于就进行扩容

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

         grow(minCapacity);

}

//minCapacity=size+1;

//当elementData是空数组时，就返回初始大小10和minCapacity中较大的一个

//否则直接返回minCapacity

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

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

         return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

}

grow()方法（扩容核心代码）

[Java] 纯文本查看 复制代码

private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length;

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

        if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)

            newCapacity = hugeCapacity(minCapacity);

        // minCapacity is usually close to size, so this is a win:

        elementData = Arrays.copyOf(elementData, newCapacity);

}

//创建oldCapacity等于elementData数组的长度（原来的大小）

//创建newCapacity等于1.5倍的oldCapacity（左移一位相当于除于2）作为扩容后的大小

//当扩容后的大小仍小于minCapacity就使新的容量等于minCapacity

//当newCapacity大于MAX_ARRAY_SIZE（等于Integer的最大值减8），就使新的容量等于Integer的最大值

//elementData获取新的值

 

private static int hugeCapacity(int minCapacity) {

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?

            Integer.MAX_VALUE :

            MAX_ARRAY_SIZE;

}

总的来说，每次扩容都是原来容量的1.5倍，直到Integer的最大值，由于是指数扩容，所以扩容到Integer的最大值需要不了多少次。

扩容实例（利用反射获取ArrayList中数组的长度）：

[Java] 纯文本查看 复制代码

package Arr;

 

import java.lang.reflect.Field;

import java.util.ArrayList;

 

public class test {

        public static void main(String[] args) throws Exception {

                test t = new test();

                ArrayList<Integer> list = new ArrayList<>();

                for (int i = 0; i < 10; i++) {

                        list.add(i);

                }

                System.out.println("10个元素  "+t.getlength(list));

                list.add(10);

                System.out.println("11个元素-进行扩容"+t.getlength(list));

                for(int i=0;i<5;i++) {

                        list.add(i);

                }

                System.out.println("16个元素-进行扩容 "+t.getlength(list));

        }

    //获取list中数组的长度，及list的最大容量

        public int getlength(ArrayList list) throws Exception {

                Class<? extends ArrayList> li = list.getClass();

                Field filter = li.getDeclaredField("elementData");

                filter.setAccessible(true);

                Object[] o = (Object[]) filter.get(list);

                return o.length;

        }

}

/*输出结果：

 *

 *  10个元素  10

 *  11个元素-进行扩容15

 *  16个元素-进行扩容 22

 */

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2