本期是【你好，面试官】系列文章的第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
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
