写给Java程序员的Scala入门教程
596
2022-05-30
我是陈皮,一个在互联网 Coding 的 ITer,微信搜索「陈皮的JavaLib」第一时间阅读最新文章,回复【资料】,即可获得我精心整理的技术资料,电子书籍,一线大厂面试资料和优秀简历模板。
1 前言
ArrayList 是开发中使用最频繁的集合框架中的数据结构之一了,而且也是面试中必问考题。所以很有必要掌握,熟练使用。所以,我们将从源码分析底层原理实现和面试中常用考点分析。
2 ArrayList 简介
ArrayList 是 Java 集合框架中的成员之一,底层是基于数组实现,并且集合容量可动态变化的。它继承自 AbstractList 抽象类,实现了 List 接口。同时还实现了 RandomAccess,Cloneable 和 Serializable 三个标记接口,说明 ArrayList 是支持快速随机访问,可克隆复制的,可序列化的。
public class ArrayList
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 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; } }
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 extends E> c)
将指定 Collection 的所有元素添加到 list 的尾部中去,还是先检查是否需要扩容,最后再将 Collection 集合拷贝到 list 尾部。
public boolean addAll(Collection extends E> 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
获取 list 的迭代器,用于遍历集合中的元素。
public Iterator
4 常见面试题分析
4.1 ArrayList 是线程安全的吗?
我们通过分析 ArrayList 源码可知,对它的任何操作都是没有加锁的,所以在多线程场景下,它是线程不安全的。如果在非多线程使用场景下,我们还是使用很频繁,因为主要用来存储数据,查询比较多,增删操作比较少。
如果增删操作比较多的话,可以使用 LinkedList,LinkedList 增删操作速度比较快。(下期我们介绍 LinkedList )。
如果需要线程安全的话,可以推荐使用 Vector 集合,分析 Vector 源码会发现好多方法加了 synchronized 关键字修饰,即同一时间只允许一个线程进行操作,所以效率比较低,但是 Vector 是线程安全的。不过JDK集合中的工具类 Collections 提供一个方法 synchronizedList 可以将线程不安全的 ArrayList 集合变成线程安全的集合对象,所以 Vector 慢慢地也很少人使用了。
public static void main(String[] args) { 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 extends E> 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
查看 内部类 Itr ,定义了三个变量,cursor 变量指示下一个需要返回元素的下标;lastRet 变量指示当前需要返回元素的下标,-1代表不返回;expectedModCount 变量在 new Itr () 时被赋值 ArrayList 集合中 modCount 变量此时的值。
在获取下一个元素的方法 next() 中,会先 checkForComodification() 方法,它的作用是检查当前 expectedModCount 的值是否等于 ArrayList 对象目前 modCount 的值,如果不相等会报错,这也就是为什么在使用迭代器的过程中,不允许对 ArrayList 对象的做增删操作。
private class Itr implements Iterator
4.8 Arrays.asList 创建 ArrayList 的使用问题
Arrays.asList() 方法生成的 ArrayList 类对象,在调用 add,remove等方法时会报错。
public static void main(String[] args) { List
通过源码分析,Arrays.asList() 生成的 ArrayList 对象不是我们本文所讲的 java.util.ArrayList,Arrays 中的内部类 ArrayList 继承了 AbstractList 类,但是它没有重写 AbstractList 类的 add 和 remove 等法,所以直接调用这些方法时会调用它父类 AbstractList 的同名方法,而 AbstractList 类中这些方法是没有具体的实现操作的,而是简单地抛出了异常。
public class Arrays { public static
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小时内删除侵权内容。