ArrayList扩容机制源码分析

拼搏现实的明天。 2023-06-23 13:26 13阅读 0赞

## 1、先看一下ArrayList的构造方法 ##

**1-1：空参构造方法:**

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

可以看到默认的空参构造方法是**赋值了一个空数组**

**1-2：传入默认大小/容量，构造方法**

private static final Object[] EMPTY_ELEMENTDATA = { };
    
    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);
        }
    }

*  当你传入的容量大于等于0，就会给你new出相对应大小的数组。不然就会抛出非法参数的异常
 *  因为扩容是需要浪费时间的性能的。所以如果你开始就知道容量大小，应当直接选择这种构造方法

**1-2：传入一个Collection的集合，构造方法**

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集合

## 2、看一下ArrayList是如何进入扩容的 ##

**看一下add()方法**

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

可以看到首先就是调用了这个 ensureCapacityInternal，因为你添加一个元素，可能会出现数组越界，那这个方法就是预防这个问题的。

**我们再看一下这个 ensureCapacityInternal**

private void ensureCapacityInternal(int minCapacity) { 
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

**这个里面先调用了calculateCapacity，后调用 ensureExplicitCapacity，我们依次来看**

private static final int DEFAULT_CAPACITY = 10;
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

*  这个方法就是判断，目前这个集合/数组是否为空，因为我们看到使用空参构造出来的集合/数据是空的。如果是空的话。就取默认大小和当前大小的最大值。
 *  可以看到默认容量大小是 10

**上面看了calculateCapacity，我们再来看下 ensureExplicitCapacity**

private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
        if (minCapacity - elementData.length > 0){ 
        	grow(minCapacity);
        }        
    }

这个 **minCapacity** 就是我们现在需要的容量大小，如果它大于当前的数组大小。那么就触发了 **grow()** 方法，也就是扩容方法。

## 3、现在我们可以来具体看一下这个 grow() 扩容方法了 ##

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    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);
    }

**简单解释一下 >> 右位移，你也可以直接记住是扩大了50%**  
     **这里直接把oldCapacity当作 999**  
    1、把 999 转化成二进制 1111100111  
    2、从右边去掉一位变成 111110011 就是最后的结果，转成十进制是 499  
    3、你可以理解成 >> 后面接几，就移除几位

*  通过上面的解释我们知道了新的容量大小是之前的1.5倍。
 *  如果当前所需容量大小，还是大于新的容量大小。 就直接让当前容量大小作为扩容后的大小
 *  如果新的容量要是大于默认最大值，就需要调用一下hugeCapacity方法，取Integer和当前容量的最大值

private static int hugeCapacity(int minCapacity) { 
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

## 4、总结 ##

*  当我们向集合里面添加一个元素的时候，就会去判断当前集合大小是否满足。
 *  因为使用无参构造方法创建的ArrayList，默认是空数组。所以需要先判断数组是否为空，如果为空的话，就取当前长度和默认长度的最大值，默认长度是10。
 *  然后判断当前所需空间是否大于数组的空间，如果不大于就不需要进行扩容了。如果大于则需要进去扩容。
 *  新的长度大小，是在旧的基础上加上旧长度的0.5倍。使用向右位移一位计算出来的。
 *  如果新计算的长度还是小于当前需要的长度，就直接让新的长度等于当前所需长度。
 *  最后得出的新长度要和最大的数组长度对比。如果大于最大长度。就需要让新长度和最大长度比较，大于最大长度，就让新长度等于Integer的最大值，否则就让新长度等于数组最大长度。
 *  最后一步，得出了新的长度，调用Arrays.copyOf，生成新的数组。

**感兴趣的可以关注我的个人订阅号：**  
![在这里插入图片描述][20200113140735681.jpg]

[20200113140735681.jpg]: https://img-blog.csdnimg.cn/20200113140735681.jpg