浅谈ArrayList扩容机制

我就是我 2023-03-04 13:25 25阅读 0赞

# 一、构造函数 #

ArrayList目前一共三种构造函数，无参数构造函数，指定初始化数组长度的构造函数和指定collection元素的列表的构造函数

// 默认构造的数组容量是10
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_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);
            }
        }
        // 指定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;
            }
        }

# 二、add()方法 #

ensureCapacityInternal(size + 1);方法是用来确定扩容大小。  
然后再赋值即可。

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

首先，点开 *ensureCapacityInternal(int minCapacity)* 方法看看。这里的**minCapacity 就是需要实际大小（当前数组需要的最小长度）**。接着调用 *calculateCapacity(Object\[\] elementData, int minCapacity)*。

private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    		// 比较当前数组所需的最小长度 和 数组已有的长度
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    	private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            	// DEFAULT_CAPACITY = 10 常量值
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
            }

**calculateCapacity()** 方法的返回值也是当前ArrayList数组**所需要的最小长度**，（初始化返回的是10）。因为，**第一次**给ArrayList添加数据的时候，会判断**elementData**是否是初始化给定的空数组**DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA**。  
若是，则接着比较常量值10和数组所需的最小长度（1）比较，返回其中最大值。——**这也就是为什么初始化返回是10的原因。**

接下来在*ensureExplicitCapacity()方法里比较当前数组所需的最小长度 和 数组已有的长度。如果存不下，则进行grow(minCapacity)* 扩容

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

**int newCapacity = oldCapacity + (oldCapacity >> 1);**  
将原有的数组长度进行扩容，位移运算。一共扩容1.5倍。  
第一个if判断，如果通过计算得到数组新长度newCapacity比我们需要最小的长度minCapacity还小。则直接将最小长度赋值给newCapacity。  
第二个if判断，如果扩大后的新长度比MAX\_ARRAY\_SIZE常量（Integer.MAX\_VALUE - 8)还大，通过hugeCapacity(),给新数组长度赋值成Integer.MAX\_VALUE。  
最后通过，  
**Arrays.copyOf(elementData, newCapacity);**  
进行数组扩容。

#### 小结 ####

·1.ArrayList初始容量为10,每次扩容是1.5倍 （偶数则是1.5倍，奇数则为1.5倍左右）  
2.ArrayList 无参构造函数创建时候。只是声明了一个空数组，只有第一次添加数据之后，才开始第一次扩容(默认10)