你好,面试官 | 我用Java List 狂怼面试官~

你好,面试官 | 我用Java List 狂怼面试官~

原文链接,排版更舒适

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

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

小龙有话说

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

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

面试现场

叮叮叮......

面试官:“你好,我是XX面试官,请问是小龙吗?”

小龙:“您好,面试官,我是小龙”

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

小龙:“嗯嗯,准备好啦”

.......

other questions

.......

面试官:“我看你简历上有提到熟悉Java集合相关,还看过源码对吧?”

小龙:“是的”

面试官:“好的,那你平时开发中经常用的集合有哪些呢?”

小龙:“嗯~,平时主要使用 Collection、Map 两个类别的集合。Collection 下 用的比较多的是 List、Set 接口的相关实现类,Map 下用得比较多的是 HashMapTreeMapLinkedHashMap这些。”

面试官:“好的,我们一个一个来。你有提到 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高,适合读多写少的场景,最终一致性。

微信搜【 小龙coding】持续追更~