基于JDK1.8源码讲解ArrayList扩容机制

现在有两组ArrayList,分别是list1和list2

        List list1 = new ArrayList();
        list1.add(1);
        list1.add(14);
        List list2 = new ArrayList(list1);

先说list1的情况,我们点进ArrayList查看ArrayList构造器(无参),如下会构造一个默认容量为10的ArrayList[],即Object[],此时的size为0 (如果我们分析list2的话,如果我们传进来的数组不是空数组,则他的容量大小以及size为传进来数组的长度;如果是空数组,则初始化一个空数组(EMPTY_ELEMENTDATA),这句话好像是废话.... )

    
   public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    
    private static final Object[] EMPTY_ELEMENTDATA = {};

    
   public ArrayList(Collection 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;
        }
    }

我们重点看不传数组的现象

    
    private static final int DEFAULT_CAPACITY = 10;

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    private int size;

当我们去执行list.add的时候

    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

elementData[size++]=e;这一行代码好理解,添加元素进数组, 我们重点看ensureCapacityInternal(size+1);这一行扩容代码.我们点进去查看

为了方便展示,我们在代码行里进行注释

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }//如果我们使用的是无参构造器产生的ArrayList
         //则DEFAULT_CAPACITY为10(之前代码定义过),minCapacity的大小为size+1,则取最大的容量capacity,以免数组容量不够

        ensureExplicitCapacity(minCapacity);//调用下一个函数
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        //如果我们上述取得的minCapacity大于数组原有长度,调用下一个函数
            grow(minCapacity);
    }

这里我们特别注意MAX_ARRAY_SIZE的大小为Integer最大值-8,他对数组长度溢出的约束有着大作用. 特别的,我们要知道:两个数字其中一个数字越界之后,A-B<0和ASystem.out.println(Integer.MAX_VALUE + 1 - MAX_ARRAY_SIZE < 0);//false System.out.println(Integer.MAX_VALUE + 1 < MAX_ARRAY_SIZE);//true System.out.println(MAX_ARRAY_SIZE - (Integer.MAX_VALUE + 1) < 0);//true System.out.println(MAX_ARRAY_SIZE < Integer.MAX_VALUE + 1);//false System.out.println(Integer.MAX_VALUE + 1 - (Integer.MAX_VALUE + 2) < 0);//true System.out.println(Integer.MAX_VALUE + 1 < Integer.MAX_VALUE + 2);//true 接下来,我们看grow(minCapacity)方法

    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //原有数组长度增加3/2,>>即二进制右移1位,相当于原数字大小除以2        
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //newCapacity和minCapacity,谁大取谁,不用管数字溢出的事,即使最大的数为负数 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

        //如果我们取得的最大的数比MAX_ARRAY_SIZE 还大,(通常不会有这种情况)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //查看是否数组长度溢出的方法,这个方法有一个判断溢出的方法,溢出就抛出OutOfMemoryError
            newCapacity = hugeCapacity(minCapacity);


        // minCapacity is usually close to size, so this is a win:
        //溢出的话,在hugeCapacity()方法中就抛出异常了,到不了此方法,不溢出的话就copyOf(数组)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            //如果minCapacity为负数,则抛出内存超出错误
            throw new OutOfMemoryError();

        //返回最大的数组长度,到此结束
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

到此结束