腾讯一面对 ArrayList 集合的面试问题,带你通过源码分析回答这些问题

网友投稿 608 2022-05-30

我是陈皮,一个在互联网 Coding 的 ITer,微信搜索「陈皮的JavaLib」第一时间阅读最新文章,回复【资料】,即可获得我精心整理的技术资料,电子书籍,一线大厂面试资料和优秀简历模板。

1 前言

腾讯一面对 ArrayList 集合的面试问题,带你通过源码分析回答这些问题

ArrayList 是开发中使用最频繁的集合框架中的数据结构之一了,而且也是面试中必问考题。所以很有必要掌握,熟练使用。所以,我们将从源码分析底层原理实现和面试中常用考点分析。

2 ArrayList 简介

ArrayList 是 Java 集合框架中的成员之一,底层是基于数组实现,并且集合容量可动态变化的。它继承自 AbstractList 抽象类,实现了 List 接口。同时还实现了 RandomAccess,Cloneable 和 Serializable 三个标记接口,说明 ArrayList 是支持快速随机访问,可克隆复制的,可序列化的。

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { }

3 ArrayList 源码分析

3.1 变量

ArrayList 底层是基于数组实现,并且集合容量可动态变化。类中定义了一个 Object 类型的数组存储元素,因为是 Object 类型的数组,所以也只能存储引用数据类型,如果存储基本数据类型(例如 int ,double等),底层会自动将基本数据类型进行类的包装。

ArrayList 中还定义了一个记录数组元素个数的变量,以及一个代表默认初始化容量的静态变量

/** * ArrayList 中存储元素的数组,数组的长度即集合的容量 * 不用 private 关键字修饰是为了内部类方便访问此数组 * transient 关键字修饰代表此数组不作为序列化的一部分 */ transient Object[] elementData; /** * 记录 ArrayList 集合中实际存储的元素个数 */ private int size; /** * 默认初始化容量 */ private static final int DEFAULT_CAPACITY = 10;

ArrayList 中定义了两个静态空数组对象,主要用来当集合初始化,并且没有添加任何元素时,作为一个空数组对象赋值给 elementData 数组对象,代表一个空 list。那为啥要定义2个空数组对象呢?后面会细讲。

/** * 一个共享的静态空数组对象,用于空 list 集合中 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 一个共享的静态空数组对象,用于默认大小初始化的空 list 集合中 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 的父类 AbstractList 中定义了 modCount 变量,它记录了集合被操作修改的次数,在使用迭代器 Iterator 中会被使用到,因为在使用迭代器遍历集合元素的过程中集合结构不允许被修改(例如添加元素,删除元素),通过比较 modCount 的值能防止在迭代的过程中集合被修改。

protected transient int modCount = 0;

3.2 构造函数

ArrayList 有三个构造函数,一个无参构造函数,一个指定集合容量大小的有参构造函数,以及一个使用指定 Collection 集合来构造集合的构造函数。

无参构造函数,即初始化一个容量为10的空 list 集合,虽说是初始化容量为10的集合,但是实际此时没创建一个容量为10的数组,而只是将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组对象赋值给 elementData 变量,只有在第一次添加元素时才创建一个容量的为10的数组。

/** * 构造一个容量为10的空 list */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

指定初始化容量的有参构造函数,当初始化容量大于0时,直接创建指定容量大小的数组,如果初始化容量为0,则将 EMPTY_ELEMENTDATA 空数组对象赋值给 elementData 变量。

/** * 构造一个指定初始化容量大小的空 list */ 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); } }

使用指定 Collection 集合来构造 ArrayList 对象,如果 Collection 不为空,则将其元素拷贝赋值到 elementData 中,如果 Collection 为空,则还是创建一个空的 list,相当于 new ArrayList(0)。

/** * 构造一个 list,它包含了指定 Collection 集合元素,这些元素的顺序是通过集合迭代器返回元素的顺序决定的 */ public ArrayList(Collection 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; } }

3.3 常用方法

public boolean add(E e)

在 list 尾部添加一个元素,首先会将记录对集合操作的次数加1,然后再判断集合容量是否足够,不够则进行扩容。

/** * 在 list 尾部添加一个元素 */ public boolean add(E e) { // 修改操作次数,并且是否进行扩容操作 ensureCapacityInternal(size + 1); // 将新元素添加在数组尾部 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 如果是采用默认初始化容量10构造的 list,则取默认初始化容量10和当前需要添加元素的下标+1的最大值来初始化 list // 这里就说明了为什么要定义2个空数组对象,因为通过判断空 list 是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA, // 如果是,则使用默认的初始化容量10来进行扩容 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { // 修改次数加1 modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) // 扩容 grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 扩容到原来容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 最大容量为 Integer.MAX_VALUE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 拷贝数组 elementData = Arrays.copyOf(elementData, newCapacity); }

public void add(int index, E element)

在 list 指定下标位置添加一个元素,首先会检查下标是否在范围内,将记录对集合操作的次数加1,然后再判断集合容量是否足够,不够则进行扩容。

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // 将下标位置后面的所有元素往后拷贝移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

public E set(int index, E element)

修改 list 指定下标位置的元素,首先会检查下标是否在范围内,然后替换指定下标的元素,返回旧的元素。

/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

public boolean addAll(Collection c)

将指定 Collection 的所有元素添加到 list 的尾部中去,还是先检查是否需要扩容,最后再将 Collection 集合拷贝到 list 尾部。

public boolean addAll(Collection c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }

public int size()

返回集合中元素的个数

public int size() { return size; }

public boolean isEmpty()

判断集合是否为空,即集合是否有元素

/** * Returns true if this list contains no elements. * * @return true if this list contains no elements */ public boolean isEmpty() { return size == 0; }

public boolean contains(Object o)

判断集合是否包含某元素,主要通过 equals 方法比较是否存在某元素。

public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }

public E get(int index)

返回指定下标位置的元素,访问速度快。

public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }

public Iterator iterator()

获取 list 的迭代器,用于遍历集合中的元素。

public Iterator iterator() { return new Itr(); }

4 常见面试题分析

4.1 ArrayList 是线程安全的吗?

我们通过分析 ArrayList 源码可知,对它的任何操作都是没有加锁的,所以在多线程场景下,它是线程不安全的。如果在非多线程使用场景下,我们还是使用很频繁,因为主要用来存储数据,查询比较多,增删操作比较少。

如果增删操作比较多的话,可以使用 LinkedList,LinkedList 增删操作速度比较快。(下期我们介绍 LinkedList )。

如果需要线程安全的话,可以推荐使用 Vector 集合,分析 Vector 源码会发现好多方法加了 synchronized 关键字修饰,即同一时间只允许一个线程进行操作,所以效率比较低,但是 Vector 是线程安全的。不过JDK集合中的工具类 Collections 提供一个方法 synchronizedList 可以将线程不安全的 ArrayList 集合变成线程安全的集合对象,所以 Vector 慢慢地也很少人使用了。

public static void main(String[] args) { ArrayList arrayList = new ArrayList<>(); arrayList.add("Java"); arrayList.add("C++"); // 封装成线程安全的集合 List list = Collections.synchronizedList(arrayList); }

4.2 ArrayList 优缺点

优点:查询速度快,因为底层是基于数组实现,数组在内存中是一块联系的内容空间,所以根据地址和索引的方式可以快速随机访问集合中的元素。

缺点:增删慢,每次添加和删除元素,都有可能涉及到数组长度的改变和元素的拷贝移动,特别是数组元素很多时比较耗时。线程不安全。

4.3 ArrayList 底层是数组实现的,那为什么不直接使用数组?

ArrayList 底层虽然是通过数组实现的,但是它内部对数组进行了封装,能支持自动动态扩容,而直接使用数组的话,如果想要实现动态扩容效果,需要开发人员自己去处理扩容机制,容易出错。而且 ArrayList 内部封装了许多方法(例如在指定位置添加元素,删除指定下标的元素,遍历集合等)方便开发人员操作集合,减少开发成本。

4.4 JDK 1.7 前后有什么变化?

在 JDK 1.7之前,ArrayList 初始化的时候,会直接调⽤ this(10) 达到真正初始化创建数组,而在 JDK 1.7以及之后只是将静态空数组赋值给 elementData,并没有真正初始化容量10,等到第一次添加元素时容量才变化为10。

再者,之前容量扩容的时候,是扩容到原来容量的1.5倍+1,而且之后是采用位操作扩容1.5倍,扩容速度更快。

// 1.7之前 int newCapacity = (oldCapacity * 3)/2 + 1; // 1.7之后 int newCapacity = oldCapacity + (oldCapacity >> 1);

4.5 初始化 ArrayList 后,直接调用 set方法会怎么样?

通过源码分析,通过构造方法初始化 ArrayList 之后(new ArrayList(Collection c) 除外),不管是默认的初始化还是指定容量大小的初始化,它们底层的 size 值都是为0,但是调用 set(int index, E element) 方法,它首先会检查下标是否大于等于 size 值,如果是会报错。 所以初始化后的 ArrayList 对象,不能马上直接调用 set 方法,会报错。

// 初始化后,此时 size 的值还是为0 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); } } public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

4.6 ArrayList 增删为什么会慢?

通过源码分析,对 ArrayList 集合的添加元素和删除元素,会涉及到数组的扩容和数据拷贝,如果数组元素个数巨大的话,会减低速度。但是如果是在尾部插入删除的话,如果在不超出数组原有长度的话,就不会涉及数组的扩容和数据拷贝,所以这时执行速度还是很快的。

所以我们要结合实际场景选择合适的数据结构,业务场景到底是增删多,还是查询多,增删多我们可以选择 LinkedList ,如果是查询多可以选择 ArrayList 。

4.7 使用迭代器 Iterator 过程中,可以增删元素吗?

通过源码分析,在获取集合的迭代器方法中,实际是返回了 Iterator 接口的实现类 Itr。而且 Itr 是 ArrayList 类中的一个内部类。

public Iterator iterator() { return new Itr(); }

查看 内部类 Itr ,定义了三个变量,cursor 变量指示下一个需要返回元素的下标;lastRet 变量指示当前需要返回元素的下标,-1代表不返回;expectedModCount 变量在 new Itr () 时被赋值 ArrayList 集合中 modCount 变量此时的值。

在获取下一个元素的方法 next() 中,会先 checkForComodification() 方法,它的作用是检查当前 expectedModCount 的值是否等于 ArrayList 对象目前 modCount 的值,如果不相等会报错,这也就是为什么在使用迭代器的过程中,不允许对 ArrayList 对象的做增删操作。

private class Itr implements Iterator { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

4.8 Arrays.asList 创建 ArrayList 的使用问题

Arrays.asList() 方法生成的 ArrayList 类对象,在调用 add,remove等方法时会报错。

public static void main(String[] args) { List list = Arrays.asList("Java", "C++", "Python"); list.add("C#"); // 这行会报错 }

通过源码分析,Arrays.asList() 生成的 ArrayList 对象不是我们本文所讲的 java.util.ArrayList,Arrays 中的内部类 ArrayList 继承了 AbstractList 类,但是它没有重写 AbstractList 类的 add 和 remove 等法,所以直接调用这些方法时会调用它父类 AbstractList 的同名方法,而 AbstractList 类中这些方法是没有具体的实现操作的,而是简单地抛出了异常。

public class Arrays { public static List asList(T... a) { return new ArrayList<>(a); } /** * @serial include */ private static class ArrayList extends AbstractList implements RandomAccess, java.io.Serializable { private static final long serialVersionUID = -2764017481108945198L; private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); } // 省略一些代码 } // 省略一些代码 }

AbstractList 类中方法的定义如下:

public void add(int index, E element) { throw new UnsupportedOperationException(); } /** * {@inheritDoc} * *

This implementation always throws an * {@code UnsupportedOperationException}. * * @throws UnsupportedOperationException {@inheritDoc} * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { throw new UnsupportedOperationException(); }

4.9 ArrayList 可以存储null值吗?元素可以重复吗?

ArrayList 底层是数组实现的,并且在添加元素的时候。没有对元素进行值校验,而是直接赋值到数组中,所以 ArrayList 是可以存储 null 值,并且存储的元素是可以重复的。

/** * 在 list 尾部添加一个元素 */ public boolean add(E e) { // 修改操作次数,并且是否进行扩容操作 ensureCapacityInternal(size + 1); // 将新元素添加在数组尾部 elementData[size++] = e; return true; }

4.10 如何边遍历 ArrayList 元素,边删除指定元素?

可能有人会使用下面的方式来实现边遍历 ArrayList 元素,边删除指定元素:

你会发现执行报错了,ConcurrentModificationException 并发修改异常,前面我们提到使用迭代器 Iterator 遍历集合时,不能对集合进行增删操作(会导致 modCount 值变化),而增强 for 循环底层也是使用迭代器实现的,所以会报错。应该使用 Iterator 类的 remove 方法。

5 总结

关于 ArrayList 集合类的相关知识先介绍到这,也建议大家自己翻阅下源码,然后写几个demo调试下,这样才能更加深对它的了解。大家也可以在下方评论你遇到过的 ArrayList 面试题,我来给你解答或者一起探讨。

下期我会继续讲解和 ArrayList 比较相似的集合类 LinkedList,欢迎大家关注,,,下期文章及时学习!

Java 数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:AB153x API----GPIO枚举
下一篇:计算机网络之数据链路层
相关文章