[Java知识库]阅读ArrayList源码

0-?背景

????????阅读了JAVA中ArrayList的源码，觉得挺有意思的部分，分享给大家。

????????JDK版本：1.8.0

1-?扩容的实现方法

????????ArrayList扩容的核心方法为：grow方法，该方法具有两个重载方法：

（1）?有参方法

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

（2）无参方法

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

? ? ? ?当调用无参方法时，会默认的再次调用有参方法，所以扩容实质上是基于有参方法实现的

2- grow方法的功能解读

（1）首先定义变量：

当前需要的长度为：minCapacity;? ?

当前的真实长度为：oldCapacity = elementData.length;

那么，

差值为：int differValue = minCapacity - oldCapacity;

（2）为了减少扩容次数，则每次多扩容一点，可以选择扩原来长度的1.5倍，或者差值，那么为了尽可能减少扩容次数，则需要取它们的最大值，也就是源码中的newLength方法功能：

扩容之后的长度为：

int newCapacity = oldCapacity + Max.max(differValue, oldCapacity*0.5);

当然，位运算更快，故写为：

int newCapacity = oldCapacity + Max.max(differValue, oldCapacity>>1);

????????值得一提的是，之前的版本（JDK1.7）为：

int newCapacity = oldCapacity + oldCapacity>>1;

（3）如果原长度为小于等于0，或者原数组元素为空，或者则返回一个object[]，长度为默认长度和所需长度的最大值（应该是为了应对直接调用grow方法）。

3- grow和newLength源码的完整源码

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

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

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // assert oldLength >= 0
        // assert minGrowth > 0

        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) {
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }

ps：ArrayList其它方法都比较简单，认真的看一看源码就懂了。有时间的话，再为大家详细解读一下。?