文章目录

1.ArrayList 类图2.相关简述3.初始化以及扩容机制4.相关接口说明RandomAccess 接口Cloneable 接口Clone相关的浅拷贝、深拷贝问题 Serializable 接口Iterable 接口 5.迭代器 和 Fail-Fast机制安全失败(fail-safe) 6.序列化与反序列化7.多线程的替代方案VectorCollections.synchronizedListCopyOnWriteArrayList 参考资料

1.ArrayList 类图

实现了Collection接口实现了List接口，是List实现类之一实现了Iterable，可以for-each迭代实现了RandomAccess接口，可以随机访问实现了Cloneable，可以克隆实现了Serializable，可以序列化

2.相关简述

ArrayList 实现了List接口，是List的一个具体实现类，底层结构是可变数组，在使用无参构造方法初始化ArrayList时，默认容量为10，扩容倍数为1.5。ArrayList实现了RandomAccess、Serializable、Cloneable、Iterable接口，表明其支持随机访问、序列化与反序列化、克隆以及通过迭代器访问集合。

与LinkedList相比，因为ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问，也就是能够下标进行快速访问，也表明底层是数组，因此ArrayList的查询效率比LinkedList高。但是涉及到元素的添加和删除，LinkedList的效率是比ArrayList高的。

使用空构造方法创建ArrayList并不会创建数组，等真正add的时候会真正的创建数组。

此外，Arraylist和LinkedList都是线程不安全的。如果想使用线程的List，可以参考Vector以及CopyOnWriteArrayList。

3.初始化以及扩容机制

使用ArrayList arrayList = new ArrayList<>(); 只是创建一个空数组。

使用add方法时，会进入到ensureCapacityInternal，此时最小容量为当前的size + 1 :

private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

如果当前数组为空，则最小容量为10，否则为minCapacity。

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

newCapacity是旧数组的Capacity的1.5倍。

如果newCapacity - minCapacity < 0，说明原本是空数组，则newCapacity等于默认容量为10。

如果newCapacity大于数组的最大容量MAX_ARRAY_SIZE的话，那么newCapacity就等于MAX_ARRAY_SIZE。

确定好newCapacity之后，使用Arrays.copyOf进行复制，并将旧数组的引用指向新数组：

elementData = Arrays.copyOf(elementData, newCapacity);

4.相关接口说明

RandomAccess 接口

随机访问接口，可以看下源码发现居然没有一行代码：

RandomAccess接口这类没有一行代码的接口也叫做标记接口，意思是表明实现该接口的类支持随机访问，那什么叫随机访问呢？简单来说就是可以靠下标index快速访问，换言之也表明该类的底层数据结构是数组。

与之相对的LinkedList并没有实现RandomAccess接口，表明他不支持下标访问，也表明其底层数据结构不是数组：

那我们应该怎么利用RandomAccess接口呢？可以看下下面这个例子：

import java.util.*; public class RandomAccessTest { public static void traverse(List list){ if (list instanceof RandomAccess){ System.out.println("实现了RandomAccess接口，不使用迭代器"); for (int i = 0;i < list.size();i++){ System.out.println(list.get(i)); } }else{ System.out.println("没实现RandomAccess接口，使用迭代器"); Iterator it = list.iterator(); while(it.hasNext()){ System.out.println(it.next()); } } } public static void main(String[] args) { List<String> arrayList = new ArrayList<>(); arrayList.add("a"); arrayList.add("b"); traverse(arrayList); List<String> linkedList = new LinkedList<>(); linkedList.add("c"); linkedList.add("d"); traverse(linkedList); } }

可以用instanceof判断该类有没有实现RandomAccess接口。

如果实现了RandomAccess接口，则可以使用for循环的形式遍历得到该集合。

如果没有实现RandomAccess接口，则使用迭代器模式。

此外可以做个实验，实验是ArrayList和LinkedList都使用for循环下标、迭代器迭代计算时间，我这里就只放结果了：

Cloneable 接口

无论是Arraylist还是LinkedList都实现了Cloneable接口，表明能够克隆。该方法也是一个标记型接口。

在此之前，可以想一下在Object中也有Clone方法，直接使用Clone方法进行克隆不行吗？

可以看到，在该类没有实现Cloneable接口时，会抛出CloneNotSupportedException异常：

因此Clone类需实现Cloneable接口,既然说到了Clone，那就引申一下跟Clone相关的内容。

Clone相关的浅拷贝、深拷贝问题

在默认情况下，实现Cloneable接口并重写Clone方法，指的是浅拷贝。

浅拷贝：基本数据类型复制一份，但是引用类型没有复制，拷贝对象中的引用类型指针是指向原对象的指针，如果修改浅拷贝复制出来的对象，那么原对象也会受到变化。

深拷贝：全面复制，彼此修改不影响。

相关博客：https://blog.csdn.net/jeffleo/article/details/76737560

Serializable 接口

具体见ArrayList 序列化与反序列化

Iterable 接口

具体见ArrayList currentModifyException

5.迭代器 和 Fail-Fast机制

在Java.util包下的集合都是快速失败的，用于快速判断当前集合是不是在并发情况下修改（有一个比较经典的例子就是单线程中集合迭代器进行遍历时用list.remove修改），主要涉及到的变量就是modCount，modCount描述的是数组结构变化的次数，结构变化意思是数组添加元素、删除元素或者数组大小发生变化时，该值就会+1。

如果用迭代器迭代或者序列化时，都会比较modCount 跟 expectModcount进行比较。

在迭代器遍历集合时，如果操作不当，就会抛出著名的ConcurrentModificationException。

public static void main(String[] args) { ArrayList arrayList = new ArrayList(); for (int i = 0; i < 10; i++) { arrayList.add(i); } remove(arrayList); System.out.println(arrayList); } public static void remove(ArrayList<Integer> list) { Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()) { Integer number = iterator.next(); if (number % 2 == 0) { // 抛出ConcurrentModificationException异常 list.remove(number); } } }

首先先看一下iterator的next方法:

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]; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

!! 在iterator.next的时候会去判断当前modCount 跟 expectedModeCount是否相等，Iterator刚创建时，会将当前的list的modCount赋值给expectModCount，每次next的时候都会去判断checkForComodification，使用list.remove的时候，modCount会+1，下一次next的时候就会出现modCount != expectedModCount的情况，抛出异常。

正确的使用方法应该是:

it.remove(); public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // 移除之后将modCount 重新赋值给 expectedModCount expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }

安全失败(fail-safe)

在JUC包下的集合都是属于安全失败的，也就是在遍历的时候不是在原本的集合上遍历的，而是先复制一份集合，在集合的副本中进行遍历（CopyOnWriteArrayList）。

6.序列化与反序列化

虽然ArrayList实现了Serializeable接口，但是他的elementData却用transient修饰，transient表示序列化时不序列化改项：

但是他的序列化方法中把size，以及实际中存储的数据都持久化，从而节省时间和空间。

/** * 将ArrayLisy实例的状态保存到一个流里面 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // 按照顺序写入所有的元素 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }

7.多线程的替代方案

Vector

多线程可以使用Vector，因为Vector是线程同步的，但是每次执行都要加锁，开销比较大，而且Vector扩容是Arraylist的2倍。

但是Vector一定是线程安全的吗？ 答案是否定的。

比如这个方法，size和remove都是线程安全的，但是deleteLast不是线程安全的，因为deleteLast不是整体原子性，会出现ArrayIndexBoundOfException。

Collections.synchronizedList

返回的是Collections工具里的一个静态内部类，里面的方法都是用synchronized修饰的。

CopyOnWriteArrayList

CopyOnWriteArrayList是基于写时复制，做到读写不冲突的一个线程安全的ArrayList。 首先写的时候会使用ReentranLock来加锁，加锁的目的是为了复制一份变量的副本来写数据，避免产生多个变量副本。

那么在读的时候就很简单了，直接读取，不用加锁。

但是CopyOnWriteArrayList如果数组元素特别多的情况下，那么复制的时候内存大小就会变为两倍，这个是要注意的一个问题。

参考资料

https://mp.weixin.qq.com/s/3PNWmtS-bEZgZjd9wyMiDA https://mp.weixin.qq.com/s/WoGclm7SsbURGigI3Mwr3w