微信关注【面试情报局】我们一起干翻面试官。
1.前言
今天我们要研究的集合是 ArrayList，在我们学习 ArrayList 之前，我们先看看面试官是如何利用 ArrayList 的相关知识点来吊打我们得。
ArrayList 的底层结构是什么？
ArrayList 的初始化容量是多少？
ArrayList 的容量会变吗?是怎么变化滴？
ArrayList 是线程安全的吗？
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 两个问题。
ArrayList 的底层结构是什么？
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; }}
复制代码
通过查看源码我们可以发现：
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 是线程安全的吗？
通过源码的阅读，我们可以很轻松的回答这个问题。他是不安全的，因为他既没有在属性elementData加validate，也没有在方法上加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() 是否为空
微信关注【面试情报局】我们一起干翻面试官。
评论