面试官：要不今天来讲讲Java的List吧，你对List了解多少？

矫情吗；* 2024-04-08 12:08 49阅读 0赞

**面试官**：**要不今天来讲讲Java的List吧，你对List了解多少？**

**候选者**：List在Java里边是一个接口，常见的实现类有ArrayList和LinkedList，在开发中用得最多的是ArrayList

**候选者**：ArrayList的底层数据结构是数组，LinkedList底层数据结构是链表。

![66b0ba4b5152439fa1930bdb713cad3d.png][]

**面试官**：**那Java本身就有数组了，为什么要用ArrayList呢？**

**候选者**：原生的数组会有一个特点：你在使用的时候必须要为它创建大小，而ArrayList不用。

**候选者**：在日常开发的时候，往往我们是不知道数组的大小的

**候选者**：如果数组的大小指定多了，内存浪费；如果数组大小指定少了，装不下。

**候选者**：假设我们给定数组的大小是10，要往这个数组里边填充元素，我们只能添加10个元素。

**候选者**：而ArrayList不一样，ArrayList我们在使用的时候可以往里边添加20个，30个，甚至更多的元素

**候选者**：因为ArrayList是实现了动态扩容的

![00738e56eccc4995b39640f898130296.png][]

**候选者**：大概的意思就是：

**候选者**：当我们new ArrayList()的时候，默认会有一个空的Object数组，大小为0。

**候选者**：当我们第一次add添加数据的时候，会给这个数组初始化一个大小，这个大小默认值为10

**候选者**：使用ArrayList在每一次add的时候，它都会先去计算这个数组够不够空间

**候选者**：如果空间是够的，那直接追加上去就好了。如果不够，那就得扩容

**面试官**：**那怎么扩容？一次扩多少？**

**候选者**：在源码里边，有个grow方法，每一次扩原来的1.5倍。比如说，初始化的值是10嘛。

**候选者**：现在我第11个元素要进来了，发现这个数组的空间不够了，所以会扩到15

**候选者**：空间扩完容之后，会调用arraycopy来对数组进行拷贝

![2c4520278d7e4cd7909645e0d1f43bcd.png][]

**面试官**：哦，可以的。

**面试官**：**那为什么你在前面提到，在日常开发中用得最多的是ArrayList呢？**

**候选者**：是由底层的数据结构来决定的，在日常开发中，遍历的需求比增删要多，即便是增删也是往往在List的尾部添加就OK了。

**候选者**：像在尾部添加元素，ArrayList的时间复杂度也就O(1)

**候选者**：另外的是，ArrayList的增删底层调用的copyOf()被优化过

**候选者**：现代CPU对内存可以块操作，ArrayList的增删一点儿也不会比LinkedList慢

![619762bdfed445a89292d4b813a19084.png][]

**面试官**：**Vector你了解吗？**

**候选者**：嗯，Vector是底层结构是数组，一般现在我们已经很少用了。

**候选者**：相对于ArrayList，它是线程安全的，在扩容的时候它是直接扩容两倍的

**候选者**：比如现在有10个元素，要扩容的时候，就会将数组的大小增长到20

![79aa58a93af74e948cf171541343644c.png][]

**面试官**：**嗯，那如果我们不用Vector，线程安全的List还有什么？**

**候选者**：首先，我们也可以用Collections来将ArrayList来包装一下，变成线程安全。

**候选者**：但这肯定不是你想听的，对吧。在java.util.concurrent包下还有一个类，叫做CopyOnWriteArrayList

**候选者**：要讲CopyOnWriteArrayList之前，我还是想说说copy-on-write这个意思，下面我会简称为cow。

**候选者**：比如说在Linux中，我们知道所有的进程都是init进程fork出来的

**候选者**：除了进程号之外，fork出来的进程，默认跟父进程一模一样的。

**候选者**：当使用了cow机制；子进程在被fork之后exec之前，两个进程用的是相同的内存空间的

**候选者**：这意味着子进程的代码段、数据段、堆栈都是指向父进程的物理空间

**候选者**：当父子进程中有更改的行为发生时，再为子进程分配相应物理空间。

**候选者**：这样做的好处就是，等到真正发生修改的时候，才去分配资源，可以减少分配或者复制大量资源时带来的瞬间延时。

**候选者**：简单来说，就可以理解为我们的懒加载，或者说单例模式的懒汉式。等真正用到的时候再分配

![fa047d7a06ae47cabdca982b1b18a5ad.png][]

**面试官**：嗯

**候选者**：在文件系统中，其实也有cow的机制。

**候选者**：文件系统的cow就是在修改数据的时候，不会直接在原来的数据位置上进行操作，而是重新找个位置修改。

**候选者**：比如说：要修改数据块A的内容，先把A读出来，写到B块里面去。

**候选者**：如果这时候断电了，原来A的内容还在。这样做的好处就是可以保证数据的完整性，瞬间挂掉了容易恢复。

**候选者**：再回头来看CopyOnWriteArrayList吧，CopyOnWriteArrayList是一个线程安全的List，底层是通过复制数组的方式来实现的。

**候选者**：我来说说它 的add()方法的实现吧

**面试官**：好

**候选者**：在add()方法其实他会加lock锁，然后会复制出一个新的数组，往新的数组里边add真正的元素，最后把array的指向改变为新的数组

**候选者**：get()方法又或是size()方法只是获取array所指向的数组的元素或者大小。读不加锁，写加锁

**候选者**：可以发现的是，CopyOnWriteArrayList跟文件系统的COW机制是很像的

![4d2a002abb2f4d64b3708ef831139295.png][]

**面试官**：**那你能说说CopyOnWriteArrayList有什么缺点吗？**

**候选者**：很显然，CopyOnWriteArrayList是很耗费内存的，每次set()/add()都会复制一个数组出来

**候选者**：另外就是CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性。

**候选者**：假设两个线程，线程A去读取CopyOnWriteArrayList的数据，还没读完

**候选者**：现在线程B把这个List给清空了，线程A此时还是可以把剩余的数据给读出来。

![45681951c32343808487a6c4126cbe02.png][]

**面试官**：嗯，还可以。

[66b0ba4b5152439fa1930bdb713cad3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c2d119d287f54b4eab604a20a13729c9.png
[00738e56eccc4995b39640f898130296.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/81d28bf81fb4418ba4147fbae429a03f.png
[2c4520278d7e4cd7909645e0d1f43bcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/17326a274f534358970fd715395e2ce4.png
[619762bdfed445a89292d4b813a19084.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/38a738ac0ae24d33a6fb1a7dc83c606c.png
[79aa58a93af74e948cf171541343644c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/f04aa37c05394cbea0644fa4a44a92ef.png
[fa047d7a06ae47cabdca982b1b18a5ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8234a3fa0c304547be235862063aaf25.png
[4d2a002abb2f4d64b3708ef831139295.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/03a8b9c9aab64d21ab8d04eb123db9fb.png
[45681951c32343808487a6c4126cbe02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2a35e957db404b389811c012cceb7cec.png