ArrayList扩容机制及不可变性详解（附源码分析）

た入场券 2022-03-15 01:22 243阅读 0赞

## 前言 ##

我们都知道ArrayList是不可变的，但是为什么是不可变的呢？

网上能搜索到ArrayList扩容机制是扩容为原本的1.5倍，那是怎么去实现的呢？

package org.lyz;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class WINGZINGDemo {
    	public static void main(String[] args) {
    		List<String> strList = new ArrayList<>();
    		strList.add("AA");
    		strList.add("BB");
    		strList.add("CC");
    		strList.add("DD");	
    	}
    }

扩容机制肯定是从add方法进行分析，查看ArrayList对add方法的实现。

/**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

数组长度小于最小长度的时候，调用grow()方法；

继续查看gorw(int minCapacity)方法

/**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        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 oldCapacity = elementData.length;

然后源数组长度的1.5倍，赋值给newCapacity；

这里运用到了位运算符，>> 1 代表向右移动一位(二进制)。等价于整除2，但是位运算符的效率高于整除。加上本身长度就是1.5倍。

后面就是进行判断有没有超过范围或者是最小长度之类的。

然后又是熟悉的Arrays.copyOf(T\[\] original, int newLength)，不过其底层实现还是调用了arraycopy方法。

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

所以ArrayList扩容的时候还是依旧新建一个数组然后进行复制，旧数组就等待GC进行回收。

其他add的重载也都有类似的代码进行实现，这里就不冗余展示了。

## 其他关于集合的文章 ##

[for-each循环对集合进行remove操作为什么会报错][for-each_remove]

[去除集合中重复的元素的3个方法(set newlist 递归)][3_set newlist]

[ArrayList和LinkedList的区别、扩容机制以及底层实现][ArrayList_LinkedList]

[for-each_remove]: https://blog.csdn.net/WINGZINGLIU/article/details/87971536
[3_set newlist]: https://blog.csdn.net/WINGZINGLIU/article/details/87258073
[ArrayList_LinkedList]: https://blog.csdn.net/WINGZINGLIU/article/details/83715578