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

用户头像
小傅哥
关注
发布于: 2020 年 08 月 28 日
面经手册 · 第7篇《ArrayList也这么多知识?一个指定位置插入就把谢飞机面晕了!》

作者:小傅哥

博客: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.copyOfObject[]集合中在赋值给属性elementData



**注意:c.toArray might (incorrectly) not return Object[] (see 6260652)**



see 6260652 是JDK bug库的编号,有点像商品sku,bug地址:https://bugs.java.com/bugdatabase/viewbug.do?bugid=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

4. 10,扩容时:1010 + 1010 >> 1 = 1010 + 0101 = 10 + 5 = 15

2. 7,扩容时:0111 + 0111 >> 1 = 0111 + 0011 = 7 + 3 = 10

  1. 当扩容完以后,就需要进行把数组中的数据拷贝到新数组中,这个过程会用到 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/ 大家可以参考学习。



六、系列文章





发布于: 2020 年 08 月 28 日 阅读数: 471
用户头像

小傅哥

关注

公众号:bugstack虫洞栈 2019.04.03 加入

作者小傅哥多年从事一线互联网Java开发的学习历程技术汇总,旨在为大家提供一个清晰详细的学习教程,侧重点更倾向编写Java核心内容。如果能为您提供帮助,请给予支持(关注、点赞、分享)!

评论

发布
暂无评论
面经手册 · 第7篇《ArrayList也这么多知识?一个指定位置插入就把谢飞机面晕了!》