大三Java后端暑期实习面经总结——Java容器篇

今天药忘吃喽~ 2022-10-15 08:58 179阅读 0赞

> ![img][]  
> 博主现在大三在读，从三月开始找暑期实习，暑假准备去tx实习啦！总结下了很多面试真题，希望能帮助正在找工作的大家！相关参考都会标注原文链接，尊重原创！

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

### 目录 ###

*   *  1. List和Set区别
     *  2. hashMap和hashTable区别及底层实现
     *  3. hashmap初始化容量为什么是16
     *  4. concurrentHashmap在jdk7和jdk8的区别
     *  5. LinkedList为什么要用双向链表
     *  6. ArrayList和LinkedList区别

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

**参考：**

*  [https://zhuanlan.zhihu.com/p/64147696][https_zhuanlan.zhihu.com_p_64147696]
 *  [https://www.bilibili.com/video/BV1Eb4y1R7zd?p=2&t=4948][https_www.bilibili.com_video_BV1Eb4y1R7zd_p_2_t_4948]

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

## 1. List和Set区别 ##

*  **List有序**，按对象进入的顺序保存；而**Set无序**
 *  **List可以重复**，允许**多个null**元素对象；而**Set不可重复**，最多允许**一个null**元素对象
 *  List获取指定元素时可以使用Iterator取出所有元素再逐一遍历，也可以直接使用**get(int index)方法**直接获取指定下标元素；而Set只能使用Iterator接口取得所有元素，再逐一遍历

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

## 2. hashMap和hashTable区别及底层实现 ##

**区别**：

*  hashMap方法没有synchronized修饰，线程不安全，允许元素为null
 *  hashTable线程安全，不允许元素为null

**底层实现**：数组+链表  
![image-20210429215157710][]

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

## 3. hashmap初始化容量为什么是16 ##

**参考**：[https://blog.csdn.net/csj731742019/article/details/107488833][https_blog.csdn.net_csj731742019_article_details_107488833]

*  1<<4，位运算性能就好，直接操作内存
 *  数组长度必须为2的整数幂：`hash值 = hashcode&(数组长度-1)`
 *  获得更好的散列效果

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

## 4. concurrentHashmap在jdk7和jdk8的区别 ##

*  [ConcurrentHashMap 1.7和1.8区别][ConcurrentHashMap 1.7_1.8]
 *  [CurrentHashMap在1.8的新特性][CurrentHashMap_1.8]
 *  [java8的ConcurrentHashMap为何放弃分段锁][java8_ConcurrentHashMap]

1️⃣ **JDK1.7的实现**

> 数据结构：ReentrantLock+Segment数组+Entry数组
> 
> ![image-20210429215825218][]

`ConcurrentHashMap`融合了`hashtable`和`hashmap`二者的优势，但是hashtable每次同步执行的时候都要锁住整个结构，是一个全局锁，效率十分低下，如下图所示  
![image-20210426235403749][]  
ConcurrentHashMap的出现正是为了解决这个问题，其锁的方式是稍微**细粒度**的，引入了`分段锁`的概念

ConcurrentHashMap的数据结构是由一个Segment数组和Entry\[\] table位桶数组组成：

*  把Map分成了N个Segment，put和get的时候，都是根据key.hashCode()算出放到哪个Segment中，Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的**分段锁**技术，而每一个Segment元素存储的是Entry\[\] table数组+链表，同HashMap的数据存储结构一样  
    ![img][img 1]
 *  通过把整个Map分为N个Segment（类似HashTable），可以提供相同的线程安全；原来只能一个线程进入，现在却能同时16个写线程进入（写线程才需要锁定，而读线程几乎不受限制），并发性的提升是显而易见的

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

2️⃣ **jdk1.8的实现**

> synchronized+CAS+Entry数组+红黑树
> 
> ![image-20210429220039571][]

*  **改进一**：取消segment字段，也就是**抛弃了分段锁**；直接采用transient volatile Entry<K,V>\[\] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
 *  **改进二**：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。
    
    纯链表的形式时间复杂度为O(n)，红黑树则为O(log2n)，性能提升很大。当key值相等的元素形成的链表中元素个数超过8个并且数组大小大于64的时候链表转红黑树，如果容量小于64就直接扩容。
    
    ![image-20210426235815954][]

**总结**：

*  JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个Entry，而JDK1.8锁的粒度就是HashEntry（首节点）
 *  JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
 *  JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档
 *  JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，我觉得有以下几点
    
    1.  因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
    2.  JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然
    3.  在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据

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

## 5. LinkedList为什么要用双向链表 ##

双向链表具有单向链表的所有功能，只是在存储上会多一个前驱指针，在不考虑空间浪费的情况下，双链表更通用，覆盖面更广，还可以解决单向链表的缺点：

*  单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找
 *  单向链表不能自我删除，需要靠辅助节点，总是需要找到待删除结点的前一个结点；而双向链表可以自我删除

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

## 6. ArrayList和LinkedList区别 ##

1️⃣ **ArrayList**

*  基于动态数组，连续内存存储，适合下标访问（随机访问）
 *  扩容机制：由于数组长度固定，超出存取长度时创建新的数组，然后将老数组的数据拷贝到新数组中
 *  如果不是尾插数据会涉及元素的移动（往后复制一份，然后插入新数据），但是如果采用尾插法并指定初始容量会极大提升性能，甚至超过LinkedList，因为LinkedList插入的元素都要封装成node对象，性能消耗较大

2️⃣ **LinkedList**

*  基于双向链表，可以存储在分散的内存中
 *  数据插入删除操作效率高，查询效率低
 *  遍历LinkedList必须用iiterator不能用for循环，因为每次for循环都是通过get(i)来获取元素就需要对list进行重新的遍历，性能消耗极大
 *  另外不要试图使用indexOf等方法返回索引，因为其对list进行了遍历，如果结果为空就白白遍历了整个链表，效率很低

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

[img]: /images/20221014/565b9f7d840b46339b993c49992b94f0.png
[https_zhuanlan.zhihu.com_p_64147696]: https://zhuanlan.zhihu.com/p/64147696
[https_www.bilibili.com_video_BV1Eb4y1R7zd_p_2_t_4948]: https://www.bilibili.com/video/BV1Eb4y1R7zd?p=2&t=4948
[image-20210429215157710]: /images/20221014/3541e401670a4e11bdc7aca1da97f655.png
[https_blog.csdn.net_csj731742019_article_details_107488833]: https://blog.csdn.net/csj731742019/article/details/107488833
[ConcurrentHashMap 1.7_1.8]: https://blog.csdn.net/xingxiupaioxue/article/details/88062163
[CurrentHashMap_1.8]: https://blog.csdn.net/qq_36375195/article/details/100122751
[java8_ConcurrentHashMap]: https://cloud.tencent.com/developer/article/1509556
[image-20210429215825218]: /images/20221014/51b5fbba313d4f1996e2b9c08e23913c.png
[image-20210426235403749]: https://gitee.com/zhong_siru/images/raw/master//img/image-20210426235403749.png
[img 1]: https://gitee.com/zhong_siru/images/raw/master//img/926638-20170809132445011-2033999443.png
[image-20210429220039571]: /images/20221014/1b5df84cb5564ed897eb7bf4b1fb9622.png
[image-20210426235815954]: /images/20221014/58e360393d454693b0fd301d038d28a0.png