List集合基础增强底层源码分析

作者：Stanley 罗昊

集合分为三个系列，分别为：List、set、map

List系列

特点：元素有序可重复

有序指的是元素的添加顺序，也就是说，元素被第一个存进去的时候，它就在第一位，这就是list集合的元素添加顺序；

通常情况下我们所说的有序有两个概念，第一个是添加顺序，第二个是大小顺序（实际上就是元素值的大小）

List下面重点关注两个实现类分别是：

ArrayList LinkedList

ArrayList

ArrayList底层实现是数组，既然是数组，那它就必然有数组的特点：查找快，增删慢；

这里简单解释一下：

首先我们建立一个数组，一旦建立一个数组，那么程序就会在内存中开辟一个连续的内存存储空间，并且它是有下标的，从0开始，一旦定义长度就无法发生改变。

现在，假设我们往数组里面存值，当然是你定义什么类型，你就存什么类型的值进去，如果现在想获取，我们直接通过下标就可以进行获取了，但是我删除元素的时候，是怎么删除的呢？

数组删除过程

假设我定义一个数组如下图：

List集合基础增强底层源码分析-LMLPHP

红框内，代表我存的值，黑线上方则是他们值对应的下标

假设我现在想删除c这个元素，这个时候d就会向前移动e也会移到d的位置f也会移到e的位置上，结果后面会空出来的那个就被删掉了，结果就成了👇下面这张图B-1：

List集合基础增强底层源码分析-LMLPHP

这个就是数组的删除过程。

数组添加过程

刚讲了删除过程，现在我们就来看看数组的添加过程：

添加元素首先会给即将进来的这个元素分配一个空间在如图B-1f后面，如果你想添加到如图B-1下标为1的空间里，那么它就会开始依次向后移，b占领d的位置d占领e的位置f占领后面新开辟空间的位置上。

这就是它的增加与删除过程，所以它增删慢，查询快；

那既然我刚讲了，数组一旦定义，长度不能发生改变，那么在咱们List集合底层是数组实现的，你List集合定义的时候你给过长度吗？很显然并没有给长度，那就可以无限添加元素，你填100个也行，你添10k也无所谓，既然数组长度不变，你说它底层怎么搞的呢？接下来我们就定义一个数组并且查看它的底层代码。

List集合底层源码详解

我用的是IDEA，按两下Shift键输入ArrayList回车即可查看源码，首先刚进来我们看到的是版本号：

private static final long serialVersionUID = 8683452581122892189L;//版本号

/**
 * Default initial capacity.（默认初始容量，也就说，当我们定义一个List集合没有给他指定长度的时候，默认长度就是10）
 */
private static final int DEFAULT_CAPACITY = 10;
那如果我添加11元素的时候怎么办？

答：扩容，下面我会详讲扩容

刚开始建这个集合的时候，默认长度是10

/**
 * 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);//新数组的长度 = oldCapacity + (oldCapacity>> 1)其中 >>符号是右移符，也就是/2的意思，算出来的结果是1.5，所以它扩容的时候是1.5倍1.5倍的扩的
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)（按住 Ctrl键 点进去 MAX_ARRAY_SIZE 就可以查看数组的最大容量，下面我有详讲）

        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
上面这个源码，就是数组初始化与扩容的方法，也就是说ArrayList里面它数组初始化是在你添加第一个元素的时候，当它扩完容后接下来就是数组的拷贝

你在创建List集合的时候，你也可以给它传一个初始容量，如何操作请继续向下阅读。

在ArrayList集合底层源码里有一个有参构造跟无参构造，它们分别在什么时候使用呢？

首先先看一下有参构造：

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

什么时候用有参构造：当你向集合中添加元素数量比较多的时候，你最好给它指定初始容量，因为这样就可以减少很多次的扩容和元素拷贝。
原理：如果你10000个元素，你让它10个以上扩一次容，扩完容后你再让它连续扩容必然会造成元素拷贝，元素拷贝它的性能就高不了，这样如此反复的话必然会拉低它的性能，如果你元素过多的话，你给它指定初始容量，这样我就能减少了很多次扩容和元素拷贝，从而提升性能（在一定程度上提升性能），
当元素比较少的时候，你就可以默认不指定初始容量
ArrayList容量有上限吗？
元素是有上限的，它的容量是Integer的最大值，在源码里面可以清楚的看到它的设定：

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;（写的很清楚，它的大小不能超过Integer的最大值（21亿））

我们可以看到它减了一个8，因为到后期就已经不需要扩容了，最后几个元素它是一个一个添加的，添加一个扩一个容，添加一个扩一个容。

值得一提的是，当它的容量超过10亿后，性能就有所衰减，这个实验是有人做过的，也被证实了，10亿之前它的性能都表现良好。

今日感悟：

很多人辞职的时候都会被老板挽留，误认以为自己是公司里不可取代的人，可实际上，没有人的工作是不可取代的。

老板在你辞职的时候挽留你，不过是说明：你是在可以取代你的那群人中，价格最便宜的。

---恢复内容结束---

Stanley的博客