写点什么

《我们一起学集合》-ArrayList

用户头像
蚊子
关注
发布于: 2021 年 01 月 28 日
《我们一起学集合》-ArrayList

微信关注【面试情报局】我们一起干翻面试官。

1.前言


今天我们要研究的集合是 ArrayList,在我们学习 ArrayList 之前,我们先看看面试官是如何利用 ArrayList 的相关知识点来吊打我们得。


  1. ArrayList 的底层结构是什么?

  2. ArrayList 的初始化容量是多少?

  3. ArrayList 的容量会变吗?是怎么变化滴?

  4. ArrayList 是线程安全的吗?

  5. ArrayList 和 LinkedList 有什么区别?


看了这些面试题,是不是内心觉得:

言归正传,下面我们就通过 ArrayList 源码学习来解决解决上述问题。

2.概述


ArrayList 是基于数组,支持自动扩容的一种数据结构。相比数组来说,因为他支持自动扩容,并且内部实现了很多操作数组的方法,所以成为我们日常开发中最常用的集合类。其内部结构如下:


3.类图

  • AbstractList 抽象类,提供了 List 接口的相关实现和迭代逻辑的实现,不过对 ArrayList 意义不大,因为 ArrayList 大量重写了 AbstractList 的实现

  • List 接口,定义了数组的增删改查迭代遍历等相关操作。

  • Cloneable 接口,支持 ArrayList 克隆

  • Serializabel 接口,支持 ArrayList 序列化与反序列化

  • RandomAccess 接口,支持 ArrayList 快速访问

4.属性


先让我们看看 ArrayList 的源码:

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    // 默认初始容量。    private static final int DEFAULT_CAPACITY = 10;        // 用于空实例的共享空数组(创建空实例时使用)    private static final Object[] EMPTY_ELEMENTDATA = {};        // 用于默认大小的空实例的共享空数组实例。    // 我们将其与EMPTY_ELEMENTDATA区分开来,以便知道添加第一个元素时要膨胀多少。    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储数组列表元素的数组缓冲区。arrayList的容量就是这个数组缓冲区的长度。 // 任何空的ArrayList 将被扩展到10当(第一次添加元素时) // 注意是通过transient修饰 transient Object[] elementData; // non-private to simplify nested class access
// 数组列表的大小(它包含的元素数量) private int size; /* 要分配的数组的最大大小 * 尝试分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制*/ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 该属性是通过继承 AbstractList 得来,列表修改的次数(版本号) protected transient int modCount = 0;}
复制代码

通过源码我们可以知道到:


  • DEFAULT_CAPACITY 表示 ArrayList 的初始容量(采用无参构造时第一次添加元素扩容的容量,后面会介绍),默认是10

  • elementData 表示 ArrayList 实际储存数据的数组,是一个Object[]

  • size 表示该 ArrayList 的大小(就是elementData包含的元素个数)。

  • MAX_ARRAY_SIZE 表示 ArrayList 能分配的最大容量 Integer.MAX_VALUE - 8

  • modCount 表示该 ArrayList 修改的次数,在迭代时可以判断 ArrayList 是否被修改。


看到这里,我们就可以很轻松回答上面的 1 和 2 两个问题。


  1. ArrayList 的底层结构是什么?

  2. ArrayList 的初始化容量是多少?


ArrayList 底层实现就是一个数组,其初始容量是10


5.常用方法

5-1.构造函数


首先还是让我们看看源码,因为源码最有说服力。

// 使用指定的初始容量构造一个空列表。public ArrayList(int initialCapacity) {    if (initialCapacity > 0) {        this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {        this.elementData = EMPTY_ELEMENTDATA; // 如果为0使用默认空数组    } else {        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);    }}
/*Constructs an empty list with an initial capacity of ten.* 构造一个初始容量为10的空列表。(在第一次扩容时容量才为10,现在还是null)*/public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
// 构造一个包含指定集合的元素的列表,按照集合的迭代器返回它们的顺序。public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); // 将集合转变为数组 // 赋值 size 并判非 0 if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) 这是一个bug在java9已经被解决 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}
复制代码

通过查看源码我们可以发现:


  • ArrayList 有三个构造函数:指定初始化大小构造,无参构造,指定初始化数据构造

  • ArrayList 的无参构造,其实默认是空数组,我们上面说的初始化容量默认为10,是当我们用无参构造函数后,第一次向 ArrayList 添加元素时扩容的默认大小。

5-2.增加


ArrayList 添加元素的方法有四个:一个是在末尾添加,一个是指定索引添加,另两个是在末尾添加集合和在指导索引位置添加集合

// 将指定的元素添加到列表的末尾。public boolean add(E e) {    // 确保容量足够    ensureCapacityInternal(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}
// 在列表指定的位置插入指定的元素。// 将当前位于该位置的元素(如果有的话)和随后的元素向右移动(下标加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++; // 大小加 1}
private void ensureCapacityInternal(int minCapacity) { // 判断是不是通过无参构造创建的 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 这才是第一次添加元素是默认扩容到10 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity);}
// 预扩容private void ensureExplicitCapacity(int minCapacity) { modCount++; // 修改版本号 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity);}
// 增加容量,以确保至少可以保存由最小容量(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; if (newCapacity - MAX_ARRAY_SIZE > 0) // 分配jvm的最大容量,防溢出 newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: // 扩容 elementData = Arrays.copyOf(elementData, newCapacity);}
// 分配最大容量private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}
// 将指定集合中的所有元素追加到此列表的末尾。按照指定集合的迭代器返回它们的顺序。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 boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); // 检查索引是否合法 Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) // 腾出空位 System.arraycopy(elementData, index, elementData, index + numNew,numMoved); // 将a拷贝到elementData System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;}
复制代码


通过源码我们知道 ArrayList 添加元素大致流程如下:

通过源码我们需要注意:


  • 扩容是原容量+原容量大小一半,也就是说是按照1.5倍扩容:oldCapacity + (oldCapacity >> 1),但最后的容量并不一定是按照这个规则计算得到的大小,因为他还有两个if判断。

  • ArrayList 中数组最大只能分配Integer.MAX_VALUE,在大就会导致OutOfMemoryError

  • ArrayList 扩容时有许多溢出判断操作,这非常值得借鉴。

  • ArrayList 扩容底层调用的是System.arraycopy(Object src,int srcPos,Object dest, int destPos,int length)方法,每个参数对应为(原始数组,起始位置,目标数组,起始位置,拷贝大小)


看到这里我们可以回答第 3 个问题:


ArrayList 的容量会变吗?是怎么变化滴?


数组容量会改变,改变的规则是按照原数组1.5倍进行扩容,但最终容量不一定是通过该规则计算得到的值,因为后面有两个if判断:1.是否满足期望容量;2.是否超出 jvm 分配的最大容量

5-3.删除


ArrayList 删除元素的方法有四个:删除指定索引位置的元素,删除指定元素,删除指定集合元素和通过过滤器删除。

// 删除列表中指定位置的元素。将所有后续元素向左移动(从它们的下标减去1)。public E remove(int index) {    // 确保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;}
// 从列表中删除指定元素的第一个匹配项,如果它存在的话并返回 true。public boolean remove(Object o) { if (o == null) { // 空值单独删除,因为add时也没有对null进行效验 for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); // 移除元素 return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { // 通过equals比较,如果是自定义对象元素,一定要重写它 fastRemove(index); return true; } } return false;}
// 跳过边界检查的移除方法(因为已经被验证边界合法)private void fastRemove(int index) { modCount++; 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}
// 从此列表中删除指定集合中包含的所有元素。// 如果此列表包含空元素,而指定的集合不允许空元素则会抛出NullPointerExceptionpublic boolean removeAll(Collection<?> c) { // 判断是否为null Objects.requireNonNull(c); return batchRemove(c, false);}
// 通过不同complement来操作列表private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) // complement决定操作行为 if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r,elementData, w,size - r); w += size - r; } if (w != size) { // 将删除的元素赋null // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified;}
@Overridepublic boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed 找出要删除的元素 // any exception thrown from the filter predicate at this stage // will leave the collection unmodified int removeCount = 0; final BitSet removeSet = new BitSet(size); // 记录要删除元素的集合 final int expectedModCount = modCount; // 记录版本号 final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { @SuppressWarnings("unchecked") final E element = (E) elementData[i]; if (filter.test(element)) { // 记录要删除的元素index removeSet.set(i); removeCount++; } } if (modCount != expectedModCount) { // 如果版本号不一致,抛出异常 throw new ConcurrentModificationException(); }
// shift surviving elements left over the spaces left by removed elements final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; // 遍历并剔除要删除的元素 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove;}
复制代码

通过源码我们可以知道:


  • ArrayList 删除元素是通过System.arraycopy移动数组覆盖元素来实现的

  • ArrayList 添加元素时没有校验 null 值,所以删除 null 值时是特殊处理的

  • ArrayList 通过对象删除时判断相等是通过equals判断,所以我们在储存自定义对象是要注意对equals进行重写


通过源码我们可以看出在使用 ArrayList 时我们要尽量避免大量的随机删除,因为删除元素会导致元素拷贝(尤其是大元素),这是非常消耗性能的一件事;就算我们通过removeAll()来删除也不是特别好,因为它也要通过c.contains()去查找元素,不同的集合有不同的实现方式所以查找的性能也不同。

5-4.修改


ArrayList 的修改比较简单,是通过指定索引修改。

// 将列表中指定位置的元素替换为指定的元素。public E set(int index, E element) {    rangeCheck(index);    E oldValue = elementData(index);    elementData[index] = element;    // 返回被替换的元素    return oldValue;}
复制代码

现在我们在看看第 4 问


ArrayList 是线程安全的吗?


通过源码的阅读,我们可以很轻松的回答这个问题。他是不安全的,因为他既没有在属性elementDatavalidate,也没有在方法上加synchronized。而且在 ArrayList 的类注释上明确指出他是线程不安全的,要使用线程安全的话可以使用Collections.synchronizedList,或者Vector


/* <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access an <tt>ArrayList</tt> instance concurrently, * and at least one of the threads modifies the list structurally, it * <i>must</i> be synchronized externally.  (A structural modification is * any operation that adds or deletes one or more elements, or explicitly * resizes the backing array; merely setting the value of an element is not * a structural modification.)  This is typically accomplished by * synchronizing on some object that naturally encapsulates the list. *************************************************************************** * 注意,这个实现是不同步。如果多个线程同时访问ArrayList实例,且至少有一个线程在结构上修改列表, * 它必须外部同步。(一个结构修改:添加或删除一个或多个元素的任何操作,或者是明确的改变数组大小, * 仅仅设置元素的值不是结构修改) 这通常是通过在自然封装列表的对象上同步来实现的。  * If no such object exists, the list should be "wrapped" using the * {@link Collections#synchronizedList Collections.synchronizedList} * method.  This is best done at creation time, to prevent accidental * unsynchronized access to the list:<pre> *   List list = Collections.synchronizedList(new ArrayList(...));</pre> *************************************************************************** * 如果不存在这样的对象,列表应该使用方法“包装”(Collections.synchronizedList)。 * 这最好在创建时进行,以防止意外对列表的非同步访问*/
复制代码

至于第 5 个问题,我们将在学习 LinkedList 时在来对比讲解。

6.总结


通过上面的学习,我们已经较为深刻的理解了 ArrayList 的底层实现,当然如果要非常深刻的理解 ArrayList 肯定需要自己亲自调试 ArrayList 的源码;作为面试和平常工作,了解到这里也差不多了。


ArrayList 本质就是一个可以自动扩容的数组包装类,他通过无参构造函数初始化并第一次添加元素的扩容大小默认是 10,往后每次自动扩容的大小是原数组容量的 1.5 倍oldCapacity + (oldCapacity >> 1),在使用 ArrayList 时尽量确定初始化容量的大小,这样可以避免频繁扩容;也要尽量避免随机插入和删除操作,这样会引起元素移动,消耗资源(尤其是对移动大元素来说)。


最后我们在看看 ArrayList 的一些方法,没有必要全记住因为我也记不住,只要有个大概印象就好了,在我们要用的时候再去查找。


  • trimToSize() 调整列表容量为列表的当前大小

  • ensureCapacity(int minCapacity) 确保列表容量

  • size() 获取列表元素个数

  • contains(Object o) 判断是否包含某个对象

  • indexOf(Obejct o) 从前往后查找指定对象

  • lastIndexOf(Obejct o) 从后往前查找指定对象

  • clone() 克隆列表

  • toArray() 转换为数组

  • toArray(T[] a) 转换为指定类型数组

  • get(int index) 获取指定索引元素

  • set(int index,E element) 指定索引位置修改

  • add(E o) 向列表末尾添加元素

  • add(int index,E elemet) 指定位置插入元素

  • remove(int index) 移除指定索引

  • remove(Object o) 移除指定元素

  • clear() 情况列表

  • addAll(Collection<? extends E> c) 在列表末尾添加集合

  • addAll(int index,Collection<? extends E> c) 在列表指定索引添加集合

  • removeAll(Collection<? > c) 移除包含集合内的所有元素

  • retainAll(Collection<? > c) 移除集合内没有的元素

  • iterator() 返回一个迭代器

  • subList(int fromIndex,int toIndex) 截取子数组

  • forEach(Consumer<? super E> action) 增强 for 循环

  • removeIf(Predicate<? super E> filter) 删除元素

  • replaceAll(UnayOperator<E> operator) 替换指定元素

  • sort(Comparator<? super E>) 排序

  • isEmpty() 是否为空


微信关注【面试情报局】我们一起干翻面试官。


发布于: 2021 年 01 月 28 日阅读数: 35
用户头像

蚊子

关注

只有做自己喜欢的事情,才能元气满满 2020.10.24 加入

公众号:面试情报局 个人碎碎念,面试心得记录 喜欢可乐鸡翅,啤酒炸鸡 喜欢小仙女,是个lsp

评论

发布
暂无评论
《我们一起学集合》-ArrayList