可能有人觉得这类知识就像「八股文」，学习只是为了应付面试。如果你真的把这些用于支撑其整个语言的根基当八股文学习，那么硬背下来不会有多少收获。理科学习更在乎逻辑，重在是理解基本原理，有了原理基础就复用这样的技术运用到实际的业务开发。

那么，你什么时候会用到这样的技术呢？就是，当你考虑体量、夯实服务、琢磨性能时，就会逐渐的深入到数据结构以及核心的基本原理当中，那里的每一分深入，都会让整个服务性能成指数的提升。

二、面试题

「谢飞机」，听说你最近在家很努力学习HashMap？那考你个ArrayList知识点🦀

你看下面这段代码输出结果是什么？

public static void main(String[] args) {
    List<String> list = new ArrayList<String>(10);
    list.add(2, "1");
    System.out.println(list.get(0));
}

嗯？不知道！👀眼睛看题，看我脸干啥？好好好，告诉你吧，这样会报错！至于为什么，回家看看书吧。

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 0
 at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:665)
 at java.util.ArrayList.add(ArrayList.java:477)
 at org.itstack.interview.test.ApiTest.main(ApiTest.java:13)
Process finished with exit code 1

🤭谢飞机是懵了，咱们一点点分析ArrayList

三、数据结构

Array + List = 数组 + 列表 = ArrayList = 数组列表

ArrayList的数据结构是基于数组实现的，只不过这个数组不像我们普通定义的数组，它可以在ArrayList的管理下插入数据时按需动态扩容、数据拷贝等操作。

接下来，我们就逐步分析ArrayList的源码，也同时解答谢飞机的疑问。

四、源码分析

1. 初始化

List<String> list = new ArrayList<String>(10);
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
 /**
  * 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);
     }
 }

通常情况空构造函数初始化ArrayList更常用，这种方式数组的长度会在第一次插入数据时候进行设置。
当我们已经知道要填充多少个元素到ArrayList中，比如500个、1000个，那么为了提供性能，减少ArrayList中的拷贝操作，这个时候会直接初始化一个预先设定好的长度。
另外，EMPTY_ELEMENTDATA 是一个定义好的空对象；private static final Object[] EMPTY_ELEMENTDATA = {}

1.1 方式01；普通方式

ArrayList<String> list = new ArrayList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

这个方式很简单也是我们最常用的方式。

1.2 方式02；内部类方式

ArrayList<String> list = new ArrayList<String>() \\{
    add("aaa");
    add("bbb");
    add("ccc");
\\};

这种方式也是比较常用的，而且省去了多余的代码量。

1.3 方式03；Arrays.asList

ArrayList<String> list = new ArrayList<String>(Arrays.asList("aaa", "bbb", "ccc"));

以上是通过Arrays.asList传递给ArrayList构造函数的方式进行初始化，这里有几个知识点；

1.3.1 ArrayList构造函数

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

通过构造函数可以看到，只要实现Collection类的都可以作为入参。
在通过转为数组以及拷贝Arrays.copyOf到Object[]集合中在赋值给属性elementData。

「注意：c.toArray might (incorrectly) not return Object[] (see 6260652)」

see 6260652 是JDK bug库的编号，有点像商品sku，bug地址:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652

那这是个什么bug呢，我们来测试下面这段代码；

@Test
public void t(){
    List<Integer> list1 = Arrays.asList(1, 2, 3);
    System.out.println("通过数组转换：" + (list1.toArray().getClass() == Object[].class));
    ArrayList<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    System.out.println("通过集合转换：" + (list2.toArray().getClass() == Object[].class));
}

测试结果：

通过数组转换：false
通过集合转换：true
Process finished with exit code 0

public Object[] toArray() 返回的类型不一定就是 Object[]，其类型取决于其返回的实际类型，毕竟 Object 是父类，它可以是其他任意类型。
子类实现和父类同名的方法，仅仅返回值不一致时，默认调用的是子类的实现方法。

造成这个结果的原因，如下；

Arrays.asList 使用的是：Arrays.copyOf(this.a, size,(Class<? extends T[]>) a.getClass());
ArrayList 构造函数使用的是：Arrays.copyOf(elementData, size, Object[].class);

1.3.2 Arrays.asList

「你知道吗？」

Arrays.asList 构建的集合，不能赋值给 ArrayList
Arrays.asList 构建的集合，不能再添加元素
Arrays.asList 构建的集合，不能再删除元素

那这到底为什么呢，因为Arrays.asList构建出来的List与new ArrayList得到的List，压根就不是一个List！类关系图如下；

小傅哥 bugstack.cn & List类关系图

从以上的类图关系可以看到；

这两个List压根不同一个东西，而且Arrasys下的List是一个私有类，只能通过asList使用，不能单独创建。
另外还有这个ArrayList不能添加和删除，主要是因为它的实现方式，可以参考Arrays类中，这部分源码；private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable

此外，Arrays是一个工具包，里面还有一些非常好用的方法，例如；二分查找Arrays.binarySearch、排序Arrays.sort等

1.4 方式04；Collections.ncopies

Collections.nCopies 是集合方法中用于生成多少份某个指定元素的方法，接下来就用它来初始化ArrayList，如下；

ArrayList<Integer> list = new ArrayList<Integer>(Collections.nCopies(10, 0));

这会初始化一个由10个0组成的集合。

2. 插入

ArrayList对元素的插入，其实就是对数组的操作，只不过需要特定时候扩容。

2.1 普通插入

List<String> list = new ArrayList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

当我们依次插入添加元素时，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;
}

这是插入元素时候的源码，size++自增，把对应元素添加进去。

2.2 插入时扩容

在前面初始化部分讲到，ArrayList默认初始化时会申请10个长度的空间，如果超过这个长度则需要进行扩容，那么它是怎么扩容的呢？

从根本上分析来说，数组是定长的，如果超过原来定长长度，扩容则需要申请新的数组长度，并把原数组元素拷贝到新数组中，如下图；

小傅哥 bugstack.cn & 数组扩容

图中介绍了当List结合可用空间长度不足时则需要扩容，这主要包括如下步骤；

判断长度充足；ensureCapacityInternal(size + 1);
当判断长度不足时，则通过扩大函数，进行扩容；grow(int minCapacity)
扩容的长度计算；int newCapacity = oldCapacity + (oldCapacity >> 1);，旧容量 + 旧容量右移1位，这相当于扩容了原来容量的(int)3/2。4. 10，扩容时：1010 + 1010 >> 1 = 1010 + 0101 = 10 + 5 = 15 2. 7，扩容时：0111 + 0111 >> 1 = 0111 + 0011 = 7 + 3 = 10
当扩容完以后，就需要进行把数组中的数据拷贝到新数组中，这个过程会用到Arrays.copyOf(elementData, newCapacity);，但他的底层用到的是；System.arraycopy

「System.arraycopy；」

@Test
public void test_arraycopy() {
    int[] oldArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int[] newArr = new int[oldArr.length + (oldArr.length >> 1)];
    System.arraycopy(oldArr, 0, newArr, 0, oldArr.length);
    newArr[11] = 11;
    newArr[12] = 12;
    newArr[13] = 13;
    newArr[14] = 14;
    System.out.println("数组元素：" + JSON.toJSONString(newArr));
    System.out.println("数组长度：" + newArr.length);
    /**
     * 测试结果
     * 
     * 数组元素：[1,2,3,4,5,6,7,8,9,10,0,11,12,13,14]
     * 数组长度：15
     */
}

拷贝数组的过程并不复杂，主要是对System.arraycopy的操作。
上面就是把数组oldArr拷贝到newArr，同时新数组的长度，采用和ArrayList一样的计算逻辑；oldArr.length + (oldArr.length >> 1)

2.3 指定位置插入

list.add(2, "1");

到这，终于可以说说谢飞机的面试题，这段代码输出结果是什么，如下；

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 0
 at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:665)
 at java.util.ArrayList.add(ArrayList.java:477)
 at org.itstack.interview.test.ApiTest.main(ApiTest.java:14)

「其实」，一段报错提示，为什么呢？我们翻开下源码学习下。

2.3.1 容量验证

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ...
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

指定位置插入首先要判断rangeCheckForAdd，size的长度。
通过上面的元素插入我们知道，每插入一个元素，size自增一次size++。
所以即使我们申请了10个容量长度的ArrayList，但是指定位置插入会依赖于size进行判断，所以会抛出IndexOutOfBoundsException异常。

2.3.2 元素迁移

小傅哥 bugstack.cn & 插入元素迁移

指定位置插入的核心步骤包括；

判断size，是否可以插入。
判断插入后是否需要扩容；ensureCapacityInternal(size + 1);。
数据元素迁移，把从待插入位置后的元素，顺序往后迁移。
给数组的指定位置赋值，也就是把待插入元素插入进来。

「部分源码：」

public void add(int index, E element) {
 ...
 // 判断是否需要扩容以及扩容操作
 ensureCapacityInternal(size + 1);
    // 数据拷贝迁移，把待插入位置空出来
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 数据插入操作                  
    elementData[index] = element;
    size++;
}

这部分源码的主要核心是在，System.arraycopy，上面我们已经演示过相应的操作方式。
这里只是设定了指定位置的迁移，可以把上面的案例代码复制下来做测试验证。

「实践：」

List<String> list = new ArrayList<String>(Collections.nCopies(9, "a"));
System.out.println("初始化：" + list);
list.add(2, "b");
System.out.println("插入后：" + list);

「测试结果：」

初始化：[a, a, a, a, a, a, a, a, a]
插入后：[a, a, 1, a, a, a, a, a, a, a]
Process finished with exit code 0

指定位置已经插入元素1，后面的数据向后迁移完成。

3. 删除

有了指定位置插入元素的经验，理解删除的过长就比较容易了，如下图；小傅哥 bugstack.cn & 删除元素

这里我们结合着代码：

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

删除的过程主要包括；

校验是否越界；rangeCheck(index);
计算删除元素的移动长度numMoved，并通过System.arraycopy自己把元素复制给自己。
把结尾元素清空，null。

「这里我们做个例子：」

@Test
public void test_copy_remove() {
    int[] oldArr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int index = 2;
    int numMoved = 10 - index - 1;
    System.arraycopy(oldArr, index + 1, oldArr, index, numMoved);
    System.out.println("数组元素：" + JSON.toJSONString(oldArr));
}

设定一个拥有10个元素的数组，同样按照ArrayList的规则进行移动元素。
注意，为了方便观察结果，这里没有把结尾元素设置为null。

「测试结果：」

数组元素：[1,2,4,5,6,7,8,9,10,10]
Process finished with exit code 0

可以看到指定位置 index = 2，元素已经被删掉。
同时数组已经移动用元素4占据了原来元素3的位置，同时结尾的10还等待删除。这就是为什么ArrayList中有这么一句代码；elementData[--size] = null

4. 扩展

如果给你一组元素；a、b、c、d、e、f、g，需要你放到ArrayList中，但是要求获取一个元素的时间复杂度都是O(1)，你怎么处理？

想解决这个问题，就需要知道元素添加到集合中后知道它的位置，而这个位置呢，其实可以通过哈希值与集合长度与运算，得出存放数据的下标，如下图；

小傅哥 bugstack.cn & 下标计算

如图就是计算出每一个元素应该存放的位置，这样就可以O(1)复杂度获取元素。

4.1 代码操作(添加元素)

List<String> list = new ArrayList<String>(Collections.<String>nCopies(8, "0"));
list.set("a".hashCode() & 8 - 1, "a");
list.set("b".hashCode() & 8 - 1, "b");
list.set("c".hashCode() & 8 - 1, "c");
list.set("d".hashCode() & 8 - 1, "d");
list.set("e".hashCode() & 8 - 1, "e");
list.set("f".hashCode() & 8 - 1, "f");
list.set("g".hashCode() & 8 - 1, "g");

以上是初始化ArrayList，并存放相应的元素。存放时候计算出每个元素的下标值。

4.2 代码操作(获取元素)

System.out.println("元素集合:" + list);
System.out.println("获取元素f [\"f\".hashCode() & 8 - 1)] Idx：" + ("f".hashCode() & (8 - 1)) + " 元素：" + list.get("f".hashCode() & 8 - 1));
System.out.println("获取元素e [\"e\".hashCode() & 8 - 1)] Idx：" + ("e".hashCode() & (8 - 1)) + " 元素：" + list.get("e".hashCode() & 8 - 1));
System.out.println("获取元素d [\"d\".hashCode() & 8 - 1)] Idx：" + ("d".hashCode() & (8 - 1)) + " 元素：" + list.get("d".hashCode() & 8 - 1));

4.3 测试结果

元素集合:[0, a, b, c, d, e, f, g]
获取元素f ["f".hashCode() & 8 - 1)] Idx：6 元素：f
获取元素e ["e".hashCode() & 8 - 1)] Idx：5 元素：e
获取元素d ["d".hashCode() & 8 - 1)] Idx：4 元素：d
Process finished with exit code 0

通过测试结果可以看到，下标位置0是初始元素，元素是按照指定的下标进行插入的。
那么现在获取元素的时间复杂度就是O(1)，是不有点像HashMap中的桶结构。

五、总结

就像我们开头说的一样，数据结构是你写出代码的基础，更是写出高级代码的核心。只有了解好数据结构，才能更透彻的理解程序设计。并不是所有的逻辑都是for循环
面试题只是引导你学习的点，但不能为了面试题而忽略更重要的核心知识学习，背一两道题是不可能抗住深度问的。因为任何一个考点，都不只是一种问法，往往可以从很多方面进行提问和考查。就像你看完整篇文章，是否理解了没有说到的知识，当你固定位置插入数据时会进行数据迁移，那么在拥有大量数据的ArrayList中是不适合这么做的，非常影响性能。
在本章的内容编写的时候也参考到一些优秀的资料，尤其发现这份外文文档；https://beginnersbook.com/ 大家可以参考学习。

面经手册 · 第7篇《ArrayList也这么多知识？一个指定位置插入就把谢飞机面晕了！》

目录

一、前言

二、面试题

三、数据结构

四、源码分析

1. 初始化

1.1 方式01；普通方式

1.2 方式02；内部类方式

1.3 方式03；Arrays.asList

1.3.1 ArrayList构造函数

1.3.2 Arrays.asList

1.4 方式04；Collections.ncopies

2. 插入

2.1 普通插入

2.2 插入时扩容

2.3 指定位置插入

2.3.1 容量验证

2.3.2 元素迁移

3. 删除

4. 扩展

4.1 代码操作(添加元素)

4.2 代码操作(获取元素)

4.3 测试结果

五、总结

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

面经手册 · 第7篇《ArrayList也这么多知识？一个指定位置插入就把谢飞机面晕了！》

目录

一、前言

二、面试题

三、数据结构

四、源码分析

1. 初始化

1.1 方式01；普通方式

1.2 方式02；内部类方式

1.3 方式03；Arrays.asList

1.3.1 ArrayList构造函数

1.3.2 Arrays.asList

1.4 方式04；Collections.ncopies

2. 插入

2.1 普通插入

2.2 插入时扩容

2.3 指定位置插入

2.3.1 容量验证

2.3.2 元素迁移

3. 删除

4. 扩展

4.1 代码操作(添加元素)

4.2 代码操作(获取元素)

4.3 测试结果

五、总结

热门文章

最新文章

相关电子书