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 读取时不加锁,只是写入、删除、修改时加锁,由于所有的写操作都是在新数组进行的,这个时候如果有线程并发的写,则通过锁来控制,如果有线程并发的读,则分几种情况
- 如果写操作未完成,那么直接读取原数组的数据;
- 如果写操作完成,但是引用还未指向新数组,那么也是读取原数组数据;
- 如果写操作完成,并且引用已经指向了新的数组,那么直接从新数组中读取数据。
因此,对 CopyOnWriteArrayList 进行增删改操作,与此同时有其他线程来访问 CopyOnWriteArrayList 中的元素,因为增删改操作未完成,所以读取元素的线程看不到新数据。可能会读到脏数据。