你好，面试官 | 我用Java List 狂怼面试官~-编程知识-白鹭情

原文链接，排版更舒适

本期是【你好，面试官】系列文章的第2期，持续更新中.....，

回复"我要进大厂"获取思维导图，目前还在更新中，从小白到大厂~

小龙有话说

本期会模拟面试 List 相关内容，

本期题目选自 ——2022届春招京东二面

面试现场

叮叮叮......

面试官：“你好，我是XX面试官，请问是小龙吗？”

小龙：“您好，面试官，我是小龙”

面试官：“好的，现在有空吗，我们开始面试吧”

小龙：“嗯嗯，准备好啦”

.......

other questions

.......

面试官：“我看你简历上有提到熟悉Java集合相关，还看过原始码对吧？”

小龙：“是的”

面试官：“好的，那你平时开发中经常用的集合有哪些呢？”

小龙：“嗯~，平时主要使用 Collection、Map 两个类别的集合，Collection 下用的比较多的是 List、Set 界面的相关实作类，Map 下用得比较多的是 HashMap、TreeMap、LinkedHashMap这些，”

面试官：“好的，我们一个一个来，你有提到 List ,那你能简单说说什么时候用 List 吗？”

小龙：“List 界面元素是有序的并且可重复，Set 界面元素是无序的只接收一次，具有去重性，因此我们可以结合二者的特点做出选择，然后 List 某些实作类比如 ArryList 由于底层实作是阵列，可以支持索引下标随机访问，因此可以结合它的这些特性去考虑”

面试官：“好的，那你能讲讲你经常使用的 List 下的实作类吗？”

小龙：“List 下比较常用的是 ArryList，LinkedList，

小龙：“ ArrayList 底层是阵列实作，由于可以支持下标访问，查询资料快，但是它非执行绪安全，并且在写入资料时，由于阵列复制需要时间，并且扩容需要实体化新阵列也要时间，因此写入资料慢，而且假如当插入元素后刚触发扩容机制，会导致浪费很多空间，”

小龙：”我们可以看看具体内部原始码实作，“

// 查询元素
public E get(int index) {
    rangeCheck(index);                  // 检查是否越界
    return elementData(index);
}
// 顺序添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);   // 扩容机制
    elementData[size++] = e;
    return true;
}
// 从阵列中间添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);            // 阵列下标越界检查
    ensureCapacityInternal(size + 1);   // 扩容机制
    System.arraycopy(elementData, index, elementData, index + 1, size - index); // 复制阵列
    elementData[index] = element;       // 替换元素
    size++;
}
// 从阵列中洗掉元素
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
}
?

小龙：”从原始码中可以得知，ArrayList在执行查询操作时：1、先判断下标是否越界，2、然后在直接通过下标从阵列中回传元素，“

小龙：”ArrayList在执行顺序添加操作时：1、通过扩容机制判断原阵列是否还有空间，若没有则重新实体化一个空间更大的新阵列，把旧阵列的资料拷贝到新阵列中，2、在新阵列的最后一位元素添加值，“

小龙：”ArrayList在执行中间插入操作时：1、先判断下标是否越界，2、扩容，3、若插入的下标为i，则通过复制阵列的方式将i后面的所有元素，往后移一位，4、新资料替换下标为 i 的旧元素，洗掉也是一样：只是阵列往前移了一位，最后一个元素设定为 null，等待 JVM垃圾回收，“

小龙：”从上面的原始码分析，我们可以看出 ArrayList 快在下标定位，慢在阵列复制，“

小龙：”不过，您可能会问，能否将每次扩容的长度设定大点，减少扩容的次数，从而提高效率？其实每次扩容的长度大小是很有讲究的，若扩容的长度太大，会造成大量的闲置空间；若扩容的长度太小，会造成频发的扩容(阵列复制)，效率更低“

小龙：“而 LinkedList 底层是基于链表，由于访问元素需要变量链表导致查询慢，写资料、洗掉资料便只需要修改指标的指向，因此速度快，同样它也是非执行绪安全的，”

面试官：”好的，刚才我听你提过 ArrayList 的扩容，你能讲讲它的扩容机制吗？“

独白：”wc，这是往死里薅啊....“

小龙：”刚才我们也看过原始码啦，可见 ArrayList 扩容：添加元素时使用 ensureCapacityInternal()方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容“

小龙：”新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2，其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右，（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍-0.5）“

小龙：”扩容操作需要呼叫Arrays.copyOf() 把原阵列整个复制到新阵列中，这个操作代价很高，因此最好在创建 ArrayList 物件时就指定大概的容量大小，减少扩容操作的次数，最好会利用 modCount 记录结构修改次数，“

面试官：”好小伙，基础不错，再问一下，你之前也有说这些都是非执行绪安全的，那当遇到需要考虑并发问题时，你怎么办呢？“

独白：”好家伙，我就知道你又要这样问，得好我早就把八股给你准备好了，“

小龙：”谈到执行绪安全，想必肯定都知道 Vector，Vector 和 ArrayList 差不多，不过它对资料操作的方法都加了synchronized，因此它是执行绪安全的，不过由于加了 synchronized，执行绪同步，导致 Vector 性能很差，“

面试官：”那有什么解决办法吗？“

小龙：”可以使用Collections.synchronizedList(list)方法或者使用 CopyOnWriteArrayList 集合“

面试官：”噢？还知道CopyOnWriteArrayList，不错！那你能简单介绍一下这个集合吗？ “

独白：”晕，这不是自己给自己挖坑吗....，“

小龙：”CopyOnWriteArrayList，它是一个写时复制的容器，何为写时复制呢？顾名思义~“

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

小龙：”它实作了List界面，内部持有 ReentrantLock 物件，底层使用 volatile transient 宣告得阵列，能更好的处理锁竞争问题，在并发高时，比 Vector 性能更佳，读写分离，写时复制，先用 ReetrantLock 物件加锁，然后会复制一份原阵列进行写操作，写完了再将新阵列值赋予原阵列，适合读多写少场景“

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;//写时复制
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

面试官：”那意思就是 CopyOnWriteArrayList 就特别好吗？“

小龙：”双刃剑嘛，有利肯定有弊，正因为它写时复制的特性，因此每次写都要复制一个阵列，很耗费存储器的，资料量大时，对存储器压力较大，可能会引起频繁 GC，

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

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

面试官：”你说无法保证实时性？何以见得呢？“

小龙：”因为 COW（CopyOnWrite）写时复制，CopyOnWriteArrayList 读取时不加锁，只是写入、洗掉、修改时加锁，由于所有的写操作都是在新阵列进行的，这个时候如果有执行绪并发的写，则通过锁来控制，如果有执行绪并发的读，则分几种情况，“

小龙：”1、如果写操作未完成，那么直接读取原阵列的资料；2、如果写操作完成，但是参考还未指向新阵列，那么也是读取原阵列资料；3、如果写操作完成，并且参考已经指向了新的阵列，那么直接从新阵列中读取资料，“

小龙：”因此，对 CopyOnWriteArrayList 进行增删改操作，与此同时有其他执行绪来访问 CopyOnWriteArrayList 中的元素，因为增删改操作未完成，所以读取元素的执行绪看不到新资料，可能会读到脏资料，“

面试官：”此刻，我想为你竖起大拇指！！“

知识总结

本期我们通过面试模拟简单介绍了集合，重点剖析了 List 相关集合，

面试重点

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

ArrayList : 基于阵列实作的非执行绪安全的集合，实作 RandomAccess 界面，支持随机访问，查询元素快，插入，洗掉中间元素慢，
LinkedList : 基于链表实作的非执行绪安全的集合，查询元素慢，插入，洗掉中间元素快，一般情况占用空间大（维护双指标），
Vector : 基于阵列实作的执行绪安全的集合，执行绪同步（方法被synchronized修饰），性能比 ArrayList 差，
CopyOnWriteArrayList : 基于阵列实作的执行绪安全的写时复制集合，执行绪安全（ReentrantLock加锁），性能比Vector高，适合读多写少的场景，最终一致性，