本期是【 你好,面试官】系列文章的第 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
底层是数组实现,由于可以支持下标访问,查询数据快。但是它非线程安全,并且在写入数据时,由于数组复制需要时间,并且扩容需要实例化新数组也要时间,因此写入数据慢,而且假如当插入元素后 刚触发扩容机制,会导致浪费很多空间。”
小龙:”我们可以看看具体内部源码实现。”
小龙:”从源码中可以得知, 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;
面试官:”那意思就是 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】持续追更~
Original: https://www.cnblogs.com/xlcoding/p/15814791.html
Author: 小龙coding
Title: 你好,面试官 | 我用Java List 狂怼面试官~
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/573440/
转载文章受原作者版权保护。转载请注明原作者出处!