Java List常见面试题

Java集合面试之List篇

你好，面试官 | 我用Java List 狂怼面试官~ (qq.com)

本文涉及ArrayList 与 LinkedList 区别、ArrayList 扩容机制、CopyOnWriteArrayList 特点、场景、思想

• ArrayList : 基于数组实现的非线程安全的集合。实现 RandomAccess 接口，支持随机访问，查询元素快，插入，删除中间元素慢。
• LinkedList : 基于链表实现的非线程安全的集合。查询元素慢，插入，删除中间元素快，一般情况占用空间大（维护双指针）。
• Vector : 基于数组实现的线程安全的集合。线程同步（方法被synchronized修饰），性能比 ArrayList 差。
• CopyOnWriteArrayList : 基于数组实现的线程安全的写时复制集合。线程安全（ReentrantLock加锁），性能比Vector高，适合读多写少的场景，最终一致性。

ArrayList 和 LinkedList 的区别是什么？

（1）数据结构：ArrayList是动态数组，而 LinkedList 是双向链表。

（2）随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。

（3）增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响其他数据下标。

（4）内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

（5）线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

讲讲ArrayList的扩容机制

ArrayList 添加元素时使用 ensureCapacityInternal()方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容

新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右。

扩容操作需要调用Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数，最好会利用 modCount 记录结构修改次数。

ArrayList 和 LinkedList 都是非线程安全的，需要考虑并发问题时怎么办？

第一个办法，使用Vector，Vector 和 ArrayList 差不多，不过它对数据操作的方法都加了synchronized，因此它是线程安全的，不过由于加了 synchronized，线程同步，导致 Vector 性能很差。

第二个办法，使用Collections.synchronizedList(list)方法或者使用 CopyOnWriteArrayList 集合。

ArrayList 和 Vector 的区别是什么？

（1）线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。

（2）性能：ArrayList 在性能方面要优于 Vector。

（3）扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

介绍一下CopyOnWriteArrayList

CopyOnWriteArrayList，它是一个写时复制的容器。何为写时复制呢？

当我们往一个容器添加元素的时候，不是直接往当前容器添加，而是先将当前容器进行 copy一份，复制出一个新的容器，然后对新容器里面操作元素，最后将原容器的引用指向新的容器。

它实现了List接口，内部持有 ReentrantLock 对象，底层使用 volatile transient 声明得数组，能更好的处理锁竞争问题，在并发高时，比 Vector 性能更佳，读写分离，写时复制，先用 ReetrantLock 对象加锁，然后会复制一份原数组进行写操作，写完了再将新数组值赋予原数组。适合读多写少场景

CopyOnWriteArrayList的缺点你说说

正因为它写时复制的特性，因此每次写都要复制一个数组，很耗费内存的，数据量大时，对内存压力较大，可能会引起频繁 GC。

还有就是大量写操作性能极差，所以只适合读多写少的

并且无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而 CopyOnWriteArrayList 由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

CopyOnWriteArrayList为什么无法保证实时性

因为 COW（CopyOnWrite）写时复制，CopyOnWriteArrayList 读取时不加锁，只是写入、删除、修改时加锁，由于所有的写操作都是在新数组进行的，这个时候如果有线程并发的写，则通过锁来控制，如果有线程并发的读，则分几种情况

1. 如果写操作未完成，那么直接读取原数组的数据；
2. 如果写操作完成，但是引用还未指向新数组，那么也是读取原数组数据；
3. 如果写操作完成，并且引用已经指向了新的数组，那么直接从新数组中读取数据。

因此，对 CopyOnWriteArrayList 进行增删改操作，与此同时有其他线程来访问 CopyOnWriteArrayList 中的元素，因为增删改操作未完成，所以读取元素的线程看不到新数据。可能会读到脏数据。