ArrayList是如何扩容的?

面试中经常问到的问题之一就是List的扩容机制了，他是怎么做到扩容的，大家都能答出来底层是数组，复制一个数组来扩容，但是再具体一点来说，大家就不知道该怎么说了，如果不看源码说这么多确实就差不多了，但是看了源码你会说的更多，更详细，更具体

1)List扩容实现步骤

总的来说就是分两步：

1、扩容: 把原来的数组复制到另一个内存空间更大的数组中
2、添加元素: 把新元素添加到扩容以后的数组中

2)源码分析

• 在分析源码之前,先看一下它定义的一些属性

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

分析之前我们先看一下ArrayList的两个构造方法

ArrayList() 默认初始化容量为10
ArrayList(int initialCapacity) 给定初始容量

 /**
     * Constructs an empty list with the specified initial capacity.
     * 构造具有指定初始容量的空列表
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
    *  构造初始容量为10的空列表。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

扩容的方法就是add()

/**
     * Appends the specified element to the end of this list.
     * 将指定的元素追加到此列表的末尾
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

add方法实现

/**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

其实add方法就两步，第一步：增加长度，第二步：添加元素到数组
在这里可以看出, 对数组容量进行增长grow(), 如果在添加的时候远数组是空的，就直接给一个10的长度，否则的话就加一

private Object[] grow() {
        return grow(size + 1);
    }

/**
     * 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
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

/**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     * 返回至少与给定的最小容量相同大的容量, 返回当前容量增加了50%，如果这就足够了。
     * 将不会返回大于MAX_ARRAY_SIZE的容量，除非给定的最小容量大于MAX_ARRAY_SIZE。
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

通过这个地方是真正的增加长度，当需要的长度大于原来数组长度的时候就需要扩容了，相反的则不需要扩容
这个地方注意这一句

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

之前的所有都是确定新数组的长度，确定之后就是把老数组copy到新数组中，这样数组的扩容就结束了

数组的sort()排序方法, reversed()的效果为倒序
list.sort(Comparator.comparing(model::getDate).reversed());