Java面试题以及答案（二）集合

红太狼 2023-10-07 19:33 66阅读 0赞

**2.1常见的数据结构（了解）**

常用的数据结构有：数组，栈，队列，链表，树，散列，堆，图等  
![在这里插入图片描述][d8d0d0e268dc473d8b5d959bba73deaf.png]  
**数组**是最常用的数据结构，数组的特点是长度固定，数组的大小固定后就无法扩容了 ，数组只能存储一种类型的数据 ，添加，删除的操作慢，因为要移动其他的元素。

**栈**是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

**队列**是一种基于先进先出（FIFO）的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读取出来。

**链表**是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结节（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

**树**是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构等等。有二叉树、平衡树、红黑树、B树、B+树。  
**散列表**，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

**堆**是计算机学科中一类特殊的数据结构的统称，堆通常可以被看作是一棵完全二叉树的数组对象。

**图**的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

**2.2集合和数组的区别（了解）**

**区别**：数组长度固定 集合长度可变

**数组**中存储的是同一种数据类型的元素，可以存储基本数据类型，也可以存储引用数据类型；  
集合存储的都是对象，而且对象的数据类型可以不一致。在开发当中一般当对象较多的时候，使用集合来存储对象。

**2.3List 和 Map、Set 的区别（必会）**

**List**和Set是存储单列数据的集合，Map是存储键值对这样的双列数据的集合；

**List**中存储的数据是有顺序的，并且值允许重复；

**Map**中存储的数据是无序的，它的键是不允许重复的，但是值是允许重复的；

**Set**中存储的数据是无顺序的，并且不允许重复，但元素在集合中的位置是由元素的hashcode决定，即位置是固定的（Set集合是根据hashcode来进行数据存储的，所以位置是固定的，但是这个位置不是用户可以控制的，所以对于用户来说set中的元素还是无序的）。

**2.4 List 和 Map、Set 的实现类（必会）**

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

**(1)Connection接口:**

**List 有序,可重复**

ArrayList  
优点: 底层数据结构是数组，查询快，增删慢。  
缺点: 线程不安全，效率高

Vector  
优点: 底层数据结构是数组，查询快，增删慢。  
缺点: 线程安全，效率低, 已给舍弃了

LinkedList  
优点: 底层数据结构是链表，查询慢，增删快。  
缺点: 线程不安全，效率高

**Set 无序,唯一**

HashSet  
底层数据结构是哈希表。(无序,唯一)  
如何来保证元素唯一性?  
依赖两个方法：hashCode()和equals()

LinkedHashSet  
底层数据结构是链表和哈希表。(FIFO插入有序,唯一)  
1.由链表保证元素有序  
2.由哈希表保证元素唯一

TreeSet  
底层数据结构是红黑树。(唯一，有序)  
1. 如何保证元素排序的呢?  
自然排序  
比较器排序  
2.如何保证元素唯一性的呢?  
根据比较的返回值是否是0来决定

**(2)Map接口有四个实现类：**

**HashMap**  
基于 hash 表的 Map 接口实现，非线程安全，高效，支持 null 值和 null 键， 线程不安全。  
**HashTable**  
线程安全，低效，不支持 null 值和 null 键；  
**LinkedHashMap**  
线程不安全，是 HashMap 的一个子类，保存了记录的插入顺序；  
TreeMap  
能够把它保存的记录根据键排序，默认是键值的升序排序，线程不安全。

**2.5Hashmap的底层原理（高薪常问）**

HashMap在JDK1.8之前的实现方式 数组+链表,  
但是在JDK1.8后对HashMap进行了底层优化,改为了由 数组+链表或者数值+红黑树实现,主要的目的是提高查找效率  
![在这里插入图片描述][7bd0349e7f434834989ae49de31f4c10.png]  
1.Jdk8数组+链表或者数组+红黑树实现，当链表中的元素超过了 8 个以后， 会将链表转换为红黑树，当红黑树节点 小于 等于6 时又会退化为链表。

2.当new HashMap():底层没有创建数组，首次调用put()方法示时，底层创建长度为16的数组，jdk8底层的数组是：Node\[\],而非Entry\[\]，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容，在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.默认的负载因子大小为0.75，数组大小为16。也就是说，默认情况下，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍。

3.在我们Java中任何对象都有hashcode，hash算法就是通过hashcode与自己进行向右位移16的异或运算。这样做是为了计算出来的hash值足够随机，足够分散，还有产生的数组下标足够随机，

**map.put(k,v)实现原理**  
（1）首先将k,v封装到Node对象当中（节点）。  
（2）先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。  
（3）下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

**map.get(k)实现原理**  
(1)、先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。  
(2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

4.Hash冲突  
不同的对象算出来的数组下标是相同的这样就会产生hash冲突，当单线链表达到一定长度后效率会非常低。

5.在链表长度大于8的时候，将链表就会变成红黑树，提高查询的效率。

**2.6 Hashmap和hashtable ConcurrentHashMap区别（高薪常问）**

**区别对比一(HashMap 和 HashTable 区别)：**

1、HashMap 是非线程安全的，HashTable 是线程安全的。  
2、HashMap 的键和值都允许有 null 值存在，而 HashTable 则不行。  
3、因为线程安全的问题，HashMap 效率比 HashTable 的要高。  
4、Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线  
程环境，而 Hashtable 适合于多线程环境。一般现在不建议用 HashTable, ①  
是 HashTable 是遗留类，内部实现很多没优化和冗余。②即使在多线程环境下，  
现在也有同步的 ConcurrentHashMap 替代，没有必要因为是多线程而用  
HashTable。

**区别对比二(HashTable 和 ConcurrentHashMap 区别)：**

HashTable 使用的是 Synchronized 关键字修饰，ConcurrentHashMap 是JDK1.7使用了锁分段技术来保证线程安全的。JDK1.8ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。  
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

**Java基础入门：**

[**java零基础自学首Java入门教程（含Java项目和Java真题）**][java_Java_Java_Java]

**Javaweb核心基础**

[**JavaWeb基础教程，Java web从入门到企业实战完整版**][JavaWeb_Java web]

**Spring Cloud最全微服务架构**：

[**史上最全面的springcloud微服务技术栈**][springcloud]

**Spring全套教程，入门到精通**

[**Spring视频教程，全面深度讲解spring5底层原理**][Spring_spring5]

**SSM框架教程：**

[**SSM框架教程\_Spring+SpringMVC+Maven高级+Spring**][SSM_Spring_SpringMVC_Maven_Spring]

**SpringBoot2全套视频教程：**

[**SpringBoot2全套视频教程，springboot零基础到项目实战**][SpringBoot2_springboot]

[d8d0d0e268dc473d8b5d959bba73deaf.png]: https://img-blog.csdnimg.cn/d8d0d0e268dc473d8b5d959bba73deaf.png
[ce3ba4d3d8f24b98b07c6052650be0b4.png]: https://img-blog.csdnimg.cn/ce3ba4d3d8f24b98b07c6052650be0b4.png
[7bd0349e7f434834989ae49de31f4c10.png]: https://img-blog.csdnimg.cn/7bd0349e7f434834989ae49de31f4c10.png
[java_Java_Java_Java]: https://www.bilibili.com/video/BV1Cv411372m?spm_id_from=333.999.0.0
[JavaWeb_Java web]: https://www.bilibili.com/video/BV1Qf4y1T7Hx?spm_id_from=333.999.0.0
[springcloud]: https://www.bilibili.com/video/BV1LQ4y127n4?spm_id_from=333.999.0.0
[Spring_spring5]: https://www.bilibili.com/video/BV1P44y1N7QG?spm_id_from=333.999.0.0
[SSM_Spring_SpringMVC_Maven_Spring]: https://www.bilibili.com/video/BV1Fi4y1S7ix?spm_id_from=333.999.0.0
[SpringBoot2_springboot]: https://www.bilibili.com/video/BV15b4y1a7yG