欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ArrayList源码分析及扩容机制

程序员文章站 2022-07-11 12:15:10
...

ArrayList的主要成员变量:

//数组默认初始容量
private static final int DEFAULT_CAPACITY = 10;

//定义一个空的数组实例以供其他需要用到空数组的地方调用 
private static final Object[] EMPTY_ELEMENTDATA = {};
 
/*
定义一个空数组,跟前面的区别就是这个空数组是用来判断ArrayList第一添加数据的时候要扩容多少。
默认的构造器情况下返回这个空数组 
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
/*
数据存的地方它的容量就是这个数组的长度,同时只要是使用默认构造器:
(DEFAULTCAPACITY_EMPTY_ELEMENTDATA )第一次添加数据的时候容量扩容为DEFAULT_CAPACITY = 10 
*/
transient Object[] elementData;
 
private int size;//当前数组的长度

部分源码分析:

	//***
	private static final long serialVersionUID = 8683452581122892189L;
 	//默认容量
    private static final int DEFAULT_CAPACITY = 10;
 
    /**
     * 一个空数组
     * - 当用户指定该 ArrayList 容量为 0 时,返回该空数组
     * - ArrayList(int initialCapacity)
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
 
    /**
     * 一个空数组实例
     * - 当用户没有指定 ArrayList 的容量时(即调用无参构造函数),返回的是该数组==>刚创建一个 ArrayList 时,其内数据量为 0。
     * - 当用户第一次添加元素时,该数组将会扩容,变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组
     * ===>通过  ensureCapacityInternal() 实现
     * 它与 EMPTY_ELEMENTDATA 的区别就是:该数组是默认返回的,而后者是在用户指定容量为 0 时返回
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    /**
     * ArrayList基于数组实现,用该数组保存数据, ArrayList 的容量就是该数组的长度
     * - 该值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入 ArrayList 中时,数组将扩容值 DEFAULT_CAPACITY(10)
     */
    transient Object[] elementData; // non-private to simplify nested class access
 
    /**
     * ArrayList实际存储的数据数量
     */
    private int size;
    
    /**
     * 创建一个初试容量的、空的ArrayList
     * - 可能报错: java.lang.OutOfMemoryError: Requested array size exceeds VM limit
     * @param  initialCapacity  初始容量
     * @throws IllegalArgumentException 当初试容量值非法(小于0)时抛出
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	// 数组缓冲区为 EMPTY_ELEMENTDATA,注意与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }

    /**
     * 无参构造函数:
     * - 创建一个 空的 ArrayList,此时其内数组缓冲区 elementData = {}, 长度为 0
     * - 当元素第一次被加入时,扩容至默认容量 10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

扩容机制:

    /**
     * 添加新值到 list 末尾
     * @param e 添加的值
     * @return <tt>true</tt>
     */
    public boolean add(E e) {
    	// 确定ArrayList的容量大小---严谨
    	// 注意:size + 1,保证资源空间不被浪费,按当前情况,保证要存多少个元素,就只分配多少空间资源
        ensureCapacityInternal(size + 1);  // 这里是size是指已经有几个元素,如果是初次add,size为0
        // 添加 e 到 ArrayList 中,然后 size 自增 1
        elementData[size++] = e;
        return true;
    }
	/**
     * 指定 ArrayList 的容量
     * @param   minCapacity   指定的最小容量
     */
    public void ensureCapacity(int minCapacity) {
    	// 最小扩充容量,默认是 10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        
        // 若用户指定的最小容量 > 最小扩充容量,则以用户指定的为准,否则还是 10
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);	
        }
    }
    
    /**
     * 私有方法:明确 ArrarList 的容量,提供给本类使用的方法
     * - 用于内部优化,保证空间资源不被浪费:尤其在 add() 方法添加时起效
     * @param minCapacity    指定的最小容量
     */
    private void ensureCapacityInternal(int minCapacity) {
        //第一次添加,调用add()时,elementData == {}
    	// 若 elementData == {},则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值
    	//假设第一次添加,调用add(),minCapacity为0,默认容量为10,则取DEFAULT_CAPACITY默认容量的值,即为10
    	// 注:ensureCapacity() 是提供给用户使用的方法,在 ArrayList 的实现中并没有使用
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);	
    }
    
    /**
     * 私有方法:明确 ArrayList 的容量
     * - 用于内部优化,保证空间资源不被浪费:尤其在 add() 方法添加时起效
     * @param minCapacity    指定的最小容量
     */
    private void ensureExplicitCapacity(int minCapacity) {
    	// 将“修改统计数”+1,该变量主要是用来实现fail-fast机制的 
        modCount++;
 
        // 防止溢出代码:确保指定的最小容量 > 数组缓冲区当前的长度
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    /**
     * 私有方法:扩容,以确保 ArrayList 至少能存储 minCapacity 个元素
     * - 扩容计算:newCapacity = oldCapacity + (oldCapacity >> 1);	
     * @param minCapacity    指定的最小容量
     */
    private void grow(int minCapacity) {
    	// 防止溢出代码
        int oldCapacity = elementData.length;
        // 运算符 >> 是带符号右移. 如 oldCapacity = 10,则 newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
        int newCapacity = oldCapacity + (oldCapacity >> 1);	
        if (newCapacity - minCapacity < 0)					// 若 newCapacity 依旧小于 minCapacity
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)			// 若 newCapacity 大于最大存储容量,则进行大容量分配
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

相关标签: Java