面试针对复习——Java容器集合经典面试题集

灰太狼 2022-10-05 09:45 266阅读 0赞

## 概述类面试题 ##

#### 1. 请说一下Java容器集合的分类，各自的继承结构 ####

`Java`集合分为两大类：`Collection` 和 `Map`

`Collection`集合

![6ea4001d1f51654cf18bf02b4b4d93d2.png][]

`Map`集合

![daeabc665df1d2f5da1b99d557574393.png][]

#### 2. 请谈一谈Java集合中的fail-fast和fail-safe机制 ####

###### fail-fast ######

`fail-fast`也就是 “快速失败”，它是`Java`集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。假设存在两个线程（线程1、线程2），线程1通过`Iterator`在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 `ConcurrentModificationException` 异常，从而产生了`fail-fast`机制

**`ArrayList`产生`fail-fast`的原理：**

首先`ArrayList`自身会维护一个`modCount`变量，每当进行增删元素等操作时，`modCount`变量都会进行自增。当使用迭代器遍历`ArrayList`时，迭代器会新维护一个初始值等于`modCount`的`expectedModCount`变量，每次获取下一个元素的时候都会去检查`expectModCount`和`modCount`是否相等。在上面举的例子中，由于B线程增删元素会导致`modCount`自增，当A线程遍历元素时就会发现两个变量不等，从而抛出`ConcurrentModificationException`异常

**`fail-fast`解决办法**

*  方案一：在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，这样就可以解决（不推荐，因为增删造成的同步锁可能会阻塞遍历操作）
 *  方案二：使用CopyOnWriteArrayList来替换ArrayList( 推荐使用）

###### fail-safe ######

`fail-safe`机制更像是一种对`fail-fast`机制的补充，它被广泛地实现在各种并发容器集合中。回头看上面的例子，如果线程A遍历的不是一个`ArrayList`，而是一个`CopyOnWriteArrayList`，则符合`fail-safe`机制，线程B可以同时对该集合的元素进行增删操作，线程A不会抛出任何异常

`CopyOnWriteArrayList`产生`fail-safe`的原理：

当使用迭代器遍历集合时，会基于原数组拷贝出一个新的数组（`CopyOnWriteArrayList`的底层是数组），后续的遍历行为在新数组上进行。因此线程B同时进行增删操作不会影响到线程A的遍历行为

#### 3. 如何一边遍历一边删除Collection中的元素？ ####

ArrayList<Integer> list = new ArrayList<>();
    // 使用迭代器
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        
        System.out.println(iterator.next());
        iterator.remove();
    }

## List类面试题 ##

#### 1. 谈谈ArrayList和LinkedList的区别 ####

`ArrayList`的底层是数组，`LinkedList`的底层是双向链表

数组拥有O(1)的查询效率，可以通过下标直接定位元素；链表在查询元素的时候只能通过遍历的方式查询，效率比数组低

数组增删元素的效率比较低，通常要伴随拷贝数组的操作；链表增删元素的效率很高，只需要调整对应位置的指针即可

比如说我们常常用`ArrayList`代替数组，因为封装了许多易用的api，而且它内部实现了自动扩容机制，由于它内部维护了一个当前容量的指针size，直接往`ArrayList`中添加元素的时间复杂度是O(1)的，使用非常方便

`LinkedList`常常被用作Queue队列的实现类，由于底层是双向链表，能够轻松地提供先入先出的操作

#### 2. 谈谈ArrayList和Vector的区别 ####

两者的底层实现相似，关键的不同在于`Vector`的对外提供操作的方法都是用`synchronized`修饰的，也就是说`Vector`在并发环境下是线程安全的，而`ArrayList`在并发环境下可能会出现线程安全问题。

由于Vector的方法都是同步方法，执行起来会在同步上消耗一定的性能，所以在单线程环境下，`Vector`的性能是不如`ArrayList`

除了线程安全这点本质区别外，还有一个实现上的小细节区别：`ArrayList`每次扩容的大小为原来的1.5倍；`Vector`可以指定扩容的大小，默认是原来大小的两倍

#### 3. 为什么ArrayList的elementData数组要加上transient修饰 ####

由于`ArrayList`有自动扩容机制，所以`ArrayList`的`elementData`数组大小往往比现有的元素数量大，如果不加`transient`直接序列化的话会把数组中空余的位置也序列化了，浪费不少的空间

ArrayList中重写了序列化和反序列化对应的`writeObject`和`readObject`方法，在遍历数组元素时，以size作为结束标志，只序列化ArrayList中已经存在的元素

## Map类面试题 ##

#### 1. 请介绍一下HashMap的实现原理 ####

*  在`JDK7`底层是数组+ 链表实现的，`JDK8`底层是数据+链表+红黑树实现的
 *  在进行`put`操作时，会调用hash方法对key进行计算，并与`HashMap`长度进行与运算，得出其在数组的下标索引
 *  这时候存在两种情况：
    
     *  此位置无元素，直接填充
     *  此位置有元素，这时候就会出现哈希冲突，此位置的多个元素都是链表形式存储，依次跟链表上的这些元素进行对比，如果hash值一样且equal方法返回true则说明是替换操作，将原来的元素替换，否则则是添加操作
 *  最后就是扩容操作，如果HashMap的size超过阀值，就会进行扩容操作，在`JDK8`中，如果同一索引的元素个数超过8且数组的长度超过64，则将该索引的元素转换成红黑树存储

#### 2. HashMap是怎样确定key存放在数组的哪个位置的？ ####

首先计算key的hash值，计算过程是：先得到key的hashCode（int类型，4字节），然后把hashCode的高16位与低16位进行异或，得到key的hash值。

接下来用key的hash值与数组长度减一的值进行按位与操作，得到key在数组中对应的下标

**追问：为什么计算key的hash时要把hashCode的高16位与低16位进行异或？（变式：为什么不直接用key的hashCode）**

计算key在数组中的下标时，是通过hash值与数组长度减一的值进行按位与操作的。由于数组的长度通常不会超过2^16，所以hash值的高16位通常参与不了这个按位与操作

为了让hashCode的高16位能够参与到按位与操作中，所以把hashCode的高16位与低16位进行异或操作，使得高16位的影响能够均匀稀释到低16位中，使得计算key位置的操作能够充分散列均匀

#### 3. 为什么要把链表转为红黑树，阈值为什么是8？ ####

在极端情况下，比如说key的`hashCode()`返回的值不合理，或者多个密钥共享一个`hashCode`，很有可能会在同一个数组位置产生严重的哈希冲突。这种情况下，如果我们仍然使用使用链表把多个冲突的元素串起来，这些元素的查询效率就会从O(1)下降为O(N)。为了能够在这种极端情况下仍保证较为高效的查询效率，`HashMap`选择把链表转换为红黑树，红黑树是一种常用的平衡二叉搜索树，添加，删除，查找元素等操作的时间复杂度均为`O(logN)`

至于阈值为什么是8，这是HashMap的作者根据概率论的知识得到的。当key的哈希码分布均匀时，数组同一个位置上的元素数量是成泊松分布的，同一个位置上出现8个元素的概率已经接近千分之一了，这侧面说明如果链表的长度达到了8，key的hashCode()肯定是出了大问题，这个时候需要红黑树来保证性能，所以选择8作为阈值

**追问：为什么红黑树转换回链表的阈值不是7而是6呢？**

如果是7的话，那么链表和红黑树之间的切换范围值就太小了。如果我的链表长度不停地在7和8之间切换，那岂不是得来回变换形态？所以选择6是一种折中的考虑

#### 4. 请说一下HashMap的扩容原理 ####

1.  首先得到新的容量值和新的扩容阈值，默认都是原来大小的两倍。
2.  然后根据新容量创建新的数组
3.  最后把元素从旧数组中迁移到新数组中

在`JDK1.7`中，迁移数据的时候所有元素都重新计算了hash，并根据新的hash重新计算数组中的位置。

在`JDK1.8`中，这个过程进行了优化：如果当前节点是单独节点（后面没有接着链表），则根据该节点的hash值与新容量减一的值按位与得到新的地址

如果当前节点后面带有链表，则根据每个节点的hash值与旧数组容量进行按位与的结果进行划分

*  如果得到的值为0，这些元素会被分配回原来的位置
 *  如果得到的结果不为0，则分配到新位置，新位置的下标为当前位置下标加上旧数组容量

还有一种情况是当前节点是树节点，那么会调用一个专门的拆分方法进行拆分

**追问：为什么HashMap不支持动态缩容？**

如果要支持动态缩容，可能就要把缩容安排在remove方法里，这样可能会导致remove方法的时间复杂度从O(1)上升为O(N)

#### 5. 为什么HashMap中适合用Integer、String这样的基础类型作为key？ ####

因为这些基础类内部已经重写了hashCode和equals方法，遵守了HashMap内部的规范。

**追问：如果要用我们自己实现的类作为key，要注意什么？**

一定要重写hashCode()和equals()方法，而且要遵从以下规则：

equals()是我们判断两个对象是否相同的依据，如果我们重写了equals方法，用自己的逻辑去判断两个对象是否相同，那么一定要保证：两个equals()返回true的对象，一定要返回相同的hashCode。这样，在HashMap的put方法中才能正确判断key是否相同

**追问：两个对象hashCode相同，equals一定返回true吗？**

答案肯定是否的，这和你的设计密切相关：如果在你的编程思路中这两个对象是不同的，那么就算恰巧两个对象的hashCode相同，equals也应该返回false

#### 6. 为什么HashMap数组的长度是2的幂次方？ ####

因为这样能够提高根据key计算所在数组位置的效率

HashMap根据key计算数组位置的算法是：用`key`的`hash`值与（数组长度 - 1）的值进行按位与操作

因为hashMap 的数组长度都是2的n次幂 ，那么对于这个数再减去1，转换成二进制的话，就肯定是**最高位为0，其他位全是1** 的数

eg:

第一个key：        hashcode值：10101001    
                                &     0111                                      
                                      0001  （十进制为1）
     
     -------------------------------------------                           
     第二个key：       hashcode值：11101000    
                               &     0111      
                                     0000  （十进制为0）
     
     --------------------------------------------               
     第三个key：       hashcode值：11101110    
                              &      0111      
                                     0110  （十进制为6）

这样得到的数，就会完整的得到原hashcode 值的低位值，不会受到与运算对数据的变化影响

如果数组长度不是2的n次幂

以7为例：

第一个key：      hashcode值：10101001    
                             &      0110                                      
                                    0000  （十进制为0）
     
      ------------------------------------------                           
      第二个key：      hashcode值：11101000    
                              &      0110      
                                     0000  （十进制为0）
     
     --------------------------------------------               
      第三个key：      hashcode值：11101110    
                              &      0111      
                                     0110  （十进制为6）

通过上边可以看到，当数组长度不为2的n次幂 的时候，hashCode 值与数组长度减一做与运算的时候，会出现重复的数据，

因为不为2的n次幂的话，对应的二进制数肯定有一位为0 , 这样不管hashCode 值对应的该位，是0还是1 ,

最终得到的该位上的数肯定是0，这带来的问题就是**HashMap上的数组元素分布不均匀**，而数组上的某些位置，永远也用不到

#### 7. HashMap与HashTable有什么区别？ ####

*  在`JDK1.7`之前，两者的实现极为相似，最大的区别在于`HashTable`的方法都用synchronized关键字修饰起来了，表明它是线程安全的，由于直接在方法上加`synchronized`关键字的同步效率较低，在并发情况下，官方推荐我们使用`ConcurrentHashMap`

在JDK1.8中，官方甚至没有对`HashTable`进行链表转树这样的优化，`HashTable`已经不被推荐使用了

#### 8. 请说一下ConcurrentHashMap的实现原理 ####

在`JDK1.7`中`ConcurrentHashMap`采用了一种分段锁的机制，它的底层实现是一个`segment`数组，每个`segment`的底层结构和HashMap相似，也是数组加链表

当对`segment`里面的元素进行操作之前，需要获得该segment独有的一把`ReentrantLock`，`ConcurrentHashMap`如果不进行手动设置的话，默认有16个`segment`，可以支持16个线程对16个不同的segment进行并发写操作

在`JDK1.8`之后摒弃了segment这种臃肿的设计，新的实现和`HashMap`非常相似，底层用的也是数组加链表加红黑树。

在新实现中，在put方法里使用了CAS + synchronized进行同步。如果插入元素的位置为空，则使用CAS进行插入。如果插入的位置不为空，则对当前位置的对象进行加锁，也就链表或红黑树的头节点，加锁后再进行后续的插入操作

这样设计的好处是：

1.  CAS是十分轻量的加锁操作，如果能够直接插入，用CAS能够大幅度节省加锁的开销
2.  如果发生冲突，只用锁住当前位置的头结点，理论上数组的长度有多大，并发操作的线程数就能有多少，比原来只能有16个线程效率更高

[6ea4001d1f51654cf18bf02b4b4d93d2.png]: /images/20221005/223130a2babf4de992a169ac5da4b1ae.png
[daeabc665df1d2f5da1b99d557574393.png]: /images/20221005/b41a477428e74893a85f385eef40c59b.png