ArrayList内部原理解析

俞其荣 · 简书 · · 2018-02-04 16:34

正文

请到「今天看啥」查看全文

add()

    public boolean add(E e) {
        // 确保数组的容量，保证可以添加该元素
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将该元素放入数组中
        elementData[size++] = e;
        return true;
    }

发现在 add() 方法中，代码很简短。可以看出之前的预操作都放入了 ensureCapacityInternal 方法中，这个方法会去确保该元素在数组中有位置可以放入。

那么我们来看看这个方法：

    private void ensureCapacityInternal(int minCapacity) {
        // 如果数组是空的，那么会初始化该数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // DEFAULT_CAPACITY 为 10 ，所以调用无参默认 ArrayList 构造方法初始化的话，默认的数组容量为 10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }

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

        // 确保数组的容量，如果不够的话，调用 grow 方法扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

看了半天，扩容是在 grow 方法中完成的，所以我们接着跟进。

    private void grow(int minCapacity) {
        // 当前数组的容量
        int oldCapacity = elementData.length;
        // 新数组扩容为原来容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新数组扩容容量还是比最少需要的容量还要小的话，就设置扩充容量为最小需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断新数组容量是否已经超出最大数组范围，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        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);
    }

扩容方法其实就是新创建一个数组，然后将旧数组的元素都复制到新数组里面。