关于后端:面经手册-第7篇ArrayList也这么多知识一个指定位置插入就把谢飞机面晕了

30次阅读

共计 9465 个字符，预计需要花费 24 分钟才能阅读完成。


作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！????

一、前言

数据结构是写好代码的根底！

说到数据结构根本包含；数组、链表、队列、红黑树等，但当你看到这些数据结构以及想到本人平时的开发，仿佛并没有用到过。那么为什么还要学习数据结构？

其实这些知识点你并不是没有用到的，而是 Java 中的 API 曾经将各个数据结构封装成对应的工具类，例如 ArrayList、LinkedList、HashMap 等，就像在后面的章节中，小傅哥写了 5 篇文章将近 2 万字来剖析 HashMap，从而学习它的外围设计逻辑。

可能有人感觉这类常识就像 八股文，学习只是为了应酬面试。如果你真的把这些用于撑持其整个语言的根基当八股文学习，那么硬背下来不会有多少播种。文科学习更在乎逻辑，重在是了解基本原理，有了原理根底就复用这样的技术使用到理论的业务开发。

那么，你什么时候会用到这样的技术呢？就是，当你思考体量、夯实服务、推敲性能时，就会逐步的深刻到数据结构以及外围的基本原理当中，那里的每一分深刻，都会让整个服务性能成指数的晋升。

二、面试题

谢飞机，据说你最近在家很努力学习 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 是父类，它能够是其余任意类型。
  • 子类实现和父类同名的办法，仅仅返回值不统一时，默认调用的是子类的实现办法。

造成这个后果的起因，如下；

  1. Arrays.asList 应用的是：Arrays.copyOf(this.a, size,(Class<? extends T[]>) a.getClass());
  2. 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！类关系图如下；

从以上的类图关系能够看到；

  1. 这两个 List 压根不同一个货色，而且 Arrasys 下的 List 是一个公有类，只能通过 asList 应用，不能独自创立。
  2. 另外还有这个 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 个长度的空间，如果超过这个长度则须要进行扩容，那么它是怎么扩容的呢？

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

图中介绍了当 List 联合可用空间长度有余时则须要扩容，这次要包含如下步骤；

  1. 判断长度短缺；ensureCapacityInternal(size + 1);
  2. 当判断长度有余时，则通过扩充函数，进行扩容；grow(int minCapacity)

  3. 扩容的长度计算；int newCapacity = oldCapacity + (oldCapacity >> 1);，旧容量 + 旧容量右移 1 位，这相当于扩容了原来容量的(int)3/2。

    1. 10，扩容时：1010 + 1010 >> 1 = 1010 + 0101 = 10 + 5 = 15
    2. 7，扩容时：0111 + 0111 >> 1 = 0111 + 0011 = 7 + 3 = 10
  4. 当扩容完当前，就须要进行把数组中的数据拷贝到新数组中，这个过程会用到 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 元素迁徙

指定地位插入的外围步骤包含；

  1. 判断 size，是否能够插入。
  2. 判断插入后是否须要扩容；ensureCapacityInternal(size + 1);。
  3. 数据元素迁徙，把从待插入地位后的元素，程序往后迁徙。
  4. 给数组的指定地位赋值，也就是把待插入元素插入进来。

局部源码：

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. 删除

有了指定地位插入元素的教训，了解删除的过长就比拟容易了，如下图；

这里咱们联合着代码：

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;
}

删除的过程次要包含；

  1. 校验是否越界；rangeCheck(index);
  2. 计算删除元素的挪动长度 numMoved，并通过System.arraycopy 本人把元素复制给本人。
  3. 把结尾元素清空，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)，你怎么解决？

想解决这个问题，就须要晓得元素增加到汇合中后晓得它的地位，而这个地位呢，其实能够通过哈希值与汇合长度与运算，得出存放数据的下标，如下图；

  • 如图就是计算出每一个元素应该寄存的地位，这样就能够 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/ 大家能够参考学习。

六、系列文章

  • HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习
  • 简历写成这样，谁要你呀!
  • 工作 5 年的学习路线资源汇总
  • 讲道理，只有你是一个爱折腾的程序员，毕业找工作真的不须要再花钱培训！
  • 高级开发必须要懂设计模式，并能重构代码

正文完
后端
发表至： 后端
2020-08-28
 0
关于后端:015-Linux-标准输入输出重定向管道和后台启动进程命令
关于后端:最近爆火的AI修图工具不想试试吗
关于后端:EE450-套接字编程
关于后端:ChatGPT万字长文理解透彻分布式事务