Java进阶（List）——面试时List常见问题解读 & 结合源码分析

青旅半醒 2024-02-20 10:31 52阅读 0赞

![在这里插入图片描述][d2b4b953f1e9405aab3ef62c9834e72c.png]

## 前言 ##

List、Set、HashMap作为Java中常用的集合，需要深入认识其原理和特性。

本篇博客介绍常见的关于Java中List集合的面试问题，结合源码分析题目背后的知识点。

关于的Set的博客文章如下：

*  [Java进阶（Set）——面试时Set常见问题解读 & 结合源码分析][Java_Set_Set_ _]

关于HaseMap的博客文章如下：

*  [Java进阶（HashMap）——面试时HashMap常见问题解读 & 结合源码分析][Java_HashMap_HashMap_ _]
 *  [Java进阶（ConcurrentHashMap）——面试时ConcurrentHashMap常见问题解读 & 结合源码分析 & 多线程CAS比较并交换 初识][Java_ConcurrentHashMap_ConcurrentHashMap_ _ _ _ _CAS_]

其他相关的List的文章合集如下：

*  [手动实现ArrayList & 源码的初步理解分析 & 数组插入数据和删除数据的问题][ArrayList _ _ _]
 *  [Java学数据结构（1）——抽象数据类型ADT & 表List、栈Stack和队列Qeue][Java_1_ADT _ _List_Stack_Qeue]

#### 目录 ####

*  前言
 *  引出
 *  ArrayList 如何扩容的？/ArrayList的大小是如何自动增加的？
 *   *  1.add添加第一个元素
     *  2.添加第11个元素时
 *  如何复制某个ArrayList到另一个Arraylist中去？
 *   *  厘清概念：深浅拷贝
     *  复制的方法
 *  在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？
 *   *  效率确实低
     *  源码arraycopy方法
 *  现在我有一个很大的数组需要拷贝，原数组大小是 5k，请问如何快速拷贝？
 *  如何获得一个线程安全的ArrayList集合？
 *   *  Collections.synchronizedList
     *  源码分析
 *  LinkedList 和 ArrayList 该如何选择？
 *   *  选择原则
     *  LinkedList源码node节点
 *  Vector 集合
 *  总结

## 引出 ##

--------------------

1.ArrayList如何扩容，1.5倍；  
2.ArrayList如何拷贝，深拷贝，浅拷贝；  
3.ArrayList的增加或者删除效率低，arraycopy方法；  
4.指定长度创建ArrayList对象，避免频繁扩容；  
5.线程安全的ArrayList集合：Collections.synchronizedList；  
6.LinkedList 和 ArrayList 该如何选择：ArrayList增删效率低，查询效率高；LinkedList 查询效率低，增删效率高  
7.Vector 集合和 ArrayList 区别：Vector扩容机制为原始的2倍，线程安全；

## ArrayList 如何扩容的？/ArrayList的大小是如何自动增加的？ ##

ArrayList初始化的时候，若没有给定长度，则默认调用无参构造

![在这里插入图片描述][b14dd114e1804fb188eb3ca00d9fd1f5.png]

此处elelmentData为ArrayList底层数组，**后面DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 为常量数组初值为空，即长度为0**

![在这里插入图片描述][6fd5b87906bc4a5b8a53953492c41061.png]

### 1.add添加第一个元素 ###

**当执行add方法添加第一个元素时，执行下面的代码**

![在这里插入图片描述][c9322b60838f470386919b5f6032d624.png]

此处涉及到两条代码：

*  ensureCapacityInternal方法内会调用calculateCapacity方法，**此处才是赋予数组长度为10**

> ensureCapacityInternal 方法

![在这里插入图片描述][3e2cab2115c04f1a98ae3a975978e48d.png]

> calculateCapacity方法

![在这里插入图片描述][d1d88d21fd1b443eb6d5f243f59b4e86.png]

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        //如果数组是空的
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
               //返回数组的容量，DEFAULT_CAPACITY=10
               return Math.max(DEFAULT_CAPACITY, minCapacity);
           }
           return minCapacity;
       }

此时集合可以添加默认的10个元素

### 2.添加第11个元素时 ###

当添加第11个元素时，ensureExplicitCapacity方法中，minCapacity为11，而原数组长度为10，所以if结构进入**grow方法-扩容核心方法**

> ensureExplicitCapacity方法

![在这里插入图片描述][9f70d9f31b9843a980e01b88c06ad8dc.png]

> grow方法-扩容核心方法

![在这里插入图片描述][47a18c3ae54c40c8b69f36c16dfa2875.png]

private void grow(int minCapacity) {
        
           // overflow-conscious code
            //把旧的长度赋值给oldCapacity
           int oldCapacity = elementData.length;
            //新的长度就=旧的长度*1.5
           int newCapacity = oldCapacity + (oldCapacity >> 1);
           if (newCapacity - minCapacity < 0)
               newCapacity = minCapacity;
           if (newCapacity - MAX_ARRAY_SIZE > 0)
               newCapacity = hugeCapacity(minCapacity);
           // minCapacity is usually close to size, so this is a win:
            //按照新的长度复制出一个新的数组
           elementData = Arrays.copyOf(elementData, newCapacity);
       }

*  oldCapacity赋值为原数组长度，为10 ，**newCapacity赋值为原长度1.5倍，即15**
 *  **调用复制数组方法，将之前的数组复制到新的数组中，并将需要添加的元素加到数组最后一位，完成扩容！**

## 如何复制某个ArrayList到另一个Arraylist中去？ ##

**重写clone方法，ArrayList克隆**

![在这里插入图片描述][0f8b8b18f88f4ceea96fb1df6043e71d.png]

### 厘清概念：深浅拷贝 ###

[Java进阶（4）——结合类加载JVM的过程理解创建对象的几种方式：new，反射Class，克隆clone（拷贝），序列化反序列化][Java_4_JVM_new_Class_clone]

![在这里插入图片描述][f7614e0d2d214f398bb939d6b52c62f8.png]

浅拷贝：虽然返回一个元素一样的ArrayList，复制的是元素的引用，即其中一个改变了元素，另一个也会跟着改变

**两个集合中间存储了同一份元素的引用**

例如：

深拷贝：重写clone方法，利用迭代器iterator或遍历集合，重新创建引用对象，逐个添加

例如：

![在这里插入图片描述][8c2df0fb091b4a07b00ccbab853c9402.png]

### 复制的方法 ###

![在这里插入图片描述][2bc108135f49416d864e81864be94932.png]

> list.clone()

![在这里插入图片描述][16953681d4d14d76981bd777f05e70be.png]

> clone.addALl(list);

![在这里插入图片描述][77e41804d59f48e0b957eb0d77dba148.png]

> Collections.copy(clone,list);

![在这里插入图片描述][2d3e88df3daf4e6f9fb16febb0d723a4.png]

## 在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？ ##

### 效率确实低 ###

效率是很低的，因为ArrayList无论是增加或者删除某个对象，我们都要通过对数组中的元素进行移位来实现。

*  增加元素时，我们要把要增加位置及以后的所有元素都**往后移一位**，先腾出一个空间，然后再进行添加。
 *  删除某个元素时，我们也要把删除位置以后的元素全部元素**往前挪一位**，通过覆盖的方式来删除。

而这种移位就需要不断的**arraycopy**，是很耗时间的，所以效率自然也很低。

### 源码arraycopy方法 ###

> 增加元素时

![在这里插入图片描述][0410b9f1239b4cb583e83e63f82d8335.png]

> 删除元素时

![在这里插入图片描述][6bf2b2cfe21d4d4b84463d2af4d70e4f.png]

## 现在我有一个很大的数组需要拷贝，原数组大小是 5k，请问如何快速拷贝？ ##

指定长度创建ArrayList对象，避免频繁扩容

## 如何获得一个线程安全的ArrayList集合？ ##

### Collections.synchronizedList ###

List<Object> datas = Collections.synchronizedList(new ArrayList<>());

### 源码分析 ###

![在这里插入图片描述][bd1e21dbf7ba4b17bef7125f67f1b5bf.png]

从源码可以看到集合操作都加了synchronized 关键字，保证了在同一时刻，数组和链表只会被一个线程所修改。

## LinkedList 和 ArrayList 该如何选择？ ##

### 选择原则 ###

*  ArrayList 底层为数组，在增加和删除元素时会频繁的调用arraycopy，所以查询效率高，增删效率低
 *  LinkedList 底层为链表，故查询效率低，但增删效率高。

### LinkedList源码node节点 ###

![在这里插入图片描述][613c3270c6644a6daae639a8dae38ce1.png]

*  item 为当前元素
 *  next指向下一个元素，若为最后一个则为null
 *  prev指向上一个元素，若为第一个则为null

![在这里插入图片描述][6750358b194a4273b86721749f4f12ff.png]

## Vector 集合 ##

1.  vector 和 ArrayList 基本一样
2.  区别在于 vector扩容机制为原始的2倍，ArrayList为之前的1.5倍
3.  vector 是线程安全的，ArrayList是非线程安全的

![在这里插入图片描述][ec681fd4965e4e05bae873c065a732f3.png]

--------------------

## 总结 ##

[d2b4b953f1e9405aab3ef62c9834e72c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0315071e5ab847759edde99f2c1d82e6.png
[Java_Set_Set_ _]: https://blog.csdn.net/Pireley/article/details/134116768
[Java_HashMap_HashMap_ _]: https://blog.csdn.net/Pireley/article/details/134120418
[Java_ConcurrentHashMap_ConcurrentHashMap_ _ _ _ _CAS_]: https://blog.csdn.net/Pireley/article/details/134122251
[ArrayList _ _ _]: https://blog.csdn.net/Pireley/article/details/132326323
[Java_1_ADT _ _List_Stack_Qeue]: https://blog.csdn.net/Pireley/article/details/132482983
[b14dd114e1804fb188eb3ca00d9fd1f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/b5f0c9ae93a44d0e87664dbe3a4633ef.png
[6fd5b87906bc4a5b8a53953492c41061.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/6f55a44b946644b3b65e0c9eb0edb18e.png
[c9322b60838f470386919b5f6032d624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/70f8910902ab4361aa1bae70143c28c9.png
[3e2cab2115c04f1a98ae3a975978e48d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/71a593bd66da406a957dc3eabac0149f.png
[d1d88d21fd1b443eb6d5f243f59b4e86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/65e5c9e4cbfa41eabb6702b0abf7b0e1.png
[9f70d9f31b9843a980e01b88c06ad8dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/1ccc9d4bc7e547409e9e8e8115f346d0.png
[47a18c3ae54c40c8b69f36c16dfa2875.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4c7071354505436389bce1a44fea1cc7.png
[0f8b8b18f88f4ceea96fb1df6043e71d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/076eaf1d963c46f28940055585af73e0.png
[Java_4_JVM_new_Class_clone]: https://blog.csdn.net/Pireley/article/details/132355758
[f7614e0d2d214f398bb939d6b52c62f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cf355f1c9bd74b6a965e41f71dd5efce.png
[8c2df0fb091b4a07b00ccbab853c9402.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0891aa8d958c4d86bfd2809f47d1ce66.png
[2bc108135f49416d864e81864be94932.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/3731a597e82d4443a40d979b10e5c76b.png
[16953681d4d14d76981bd777f05e70be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/eb77d80792ec448db8b5fc5410c85a50.png
[77e41804d59f48e0b957eb0d77dba148.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/8051620252594f72a76137ce8075e0be.png
[2d3e88df3daf4e6f9fb16febb0d723a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/262823dd76a9449ca1177e2788556e0d.png
[0410b9f1239b4cb583e83e63f82d8335.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/422c61538c084538ba489aeff9d12a86.png
[6bf2b2cfe21d4d4b84463d2af4d70e4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c2f77a9366964bbfa4a28cbe5c5bda96.png
[bd1e21dbf7ba4b17bef7125f67f1b5bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9048a23ee2bc4ce7a14eee532e414a9f.png
[613c3270c6644a6daae639a8dae38ce1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/eea5bac6dc0e40128dd993f1b220cf2e.png
[6750358b194a4273b86721749f4f12ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0484a79854094fd2bd156fdbb55a369f.png
[ec681fd4965e4e05bae873c065a732f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/bb05d88f0ed74ac7a8e5b8a891b26a09.png