黑马程序员技术交流社区

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

作者: 小刀葛小伦    时间: 2019-9-5 16:28
标题: 【成都校区】ArrayList扩容详解
本帖最后由 小刀葛小伦 于 2019-9-5 16:28 编辑

基于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