2022届秋招Java后端高频知识点汇总②--Java集合
1. Java中有哪些集合
Java中的集合类主要由Collection和Map这两个接口派生出。
Collection接口又派生出三个子接口：Set、List、Queue
Set：HashSet、TreeSet
List：ArrayList、LinkedList、Vector
Queue：PriorityQueue、Deque
Map接口下的集合：
2. List、Set、Map三者的区别
List：存储的元素是有序的、可重复的。
Set：存储的元素是无序的、不可重复的。
3. ArrayList和LinkedList的区别
4. 有哪些线程安全的List
5. ArrayList和Vector的区别
ArrayList是不是线程安全的，Vector是线程安全的。
6. ArrayList的扩容机制
1.ArrayList以无参构造方法创建ArrayList时，初始化赋值的是一个空数组，当真正对数组进行添加元素操作时，才真正分配容量。
当向ArrayList中添加第一个元素时，数组容量默认扩容为10。
2.当需要扩容时，ArrayList每次扩容都以原来容量的1.5倍进行扩容
3.然后再判断新容量是否大于最小需要容量，如果还是小于最小需要容量，那就把最小需要容量当作数组的新容量
4.如果新的容量已经大于最大容量MAX_ARRAY_SIZE（MAX_ARRAY_SIZE，MAX_ARRAY_SIZE为Integer.MAX_VALUE-8，-8是为了避免oom）,
则会调用hugeCapacity(）方法，返回Integer的最大值。
7. HashMap底层实现
分JDK1.7和JDK1.8来答
在JDK1.7时，HashMap的底层数据结构是 数组+链表
put操作：
①首先判断数组是否为空，如果数组为空则进行第一次扩容（resize）
②根据key计算hash值并与上数组的长度-1（int index = key.hashCode()&(length-1)）得到键值对在数组中的索引。
③如果该位置为null，则直接插入
④如果该位置不为null,则判断key是否一样(hashCode和equals)，如果一样则直接覆盖value
⑤如果key不一样，则判断该元素是否为红黑树的节点，如果是，则直接在红黑树中插入键值对
⑥如果不是红黑树的节点，则就是链表，遍历这个链表执行插入操作，如果遍历过程中若发现key已存在，直接覆盖value即可。
如果链表的长度大于等于8且数组中元素数量大于等于阈值64，则将链表转化为红黑树，（先在链表中插入再进行判断）
如果链表的长度大于等于8且数组中元素数量小于阈值64，则先对数组进行扩容，不转化为红黑树。
get操作：
①计算key的hashCode的值，找到key在数组中的位置
②如果该位置为null，就直接返回null
③否则，根据equals()判断key与当前位置的值是否相等，如果相等就直接返回。
④如果不等，再判断当前元素是否为树节点，如果是树节点就按红黑树进行查找。
⑤否则，按照链表的方式进行查找。
8. HashMap的扩容机制
9.HashMap为什么是线程不安全的
分JDK1.7和JDK1.8来答
1.在JDK1.7中，当并发执行扩容操作时会造成死循环和数据丢失的情况。
在JDK1.7中，在多线程情况下同时对数组进行扩容，需要将原来数据转移到新数组中，在转移元素的过程中使用的是头插法，会造成死循环。
2.在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。
如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会通过判断，将执行插入操作。
假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
10. HashMap是如何解决哈希冲突的
拉链法（链地址法）
为了解决碰撞，数组中的元素是单向链表类型。当链表长度大于等于8时，会将链表转换成红黑树提高性能。
11. HashMap为什么使用红黑树而不是B树或平衡二叉树AVL或二叉查找树
1.不使用二叉查找树
二叉排序树在极端情况下会出现线性结构。例如：二叉排序树左子树所有节点的值均小于根节点，如果我们添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长。所以这是不用二叉查找树的原因。
2.不使用平衡二叉树
平衡二叉树是严格的平衡树，红黑树是不严格平衡的树，平衡二叉树在插入或删除后维持平衡的开销要大于红黑树。
红黑树的虽然查询性能略低于平衡二叉树，但在插入和删除上性能要优于平衡二叉树。
选择红黑树是从功能、性能和开销上综合选择的结果。
3.不使用B树/B+树
HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。
如果用B/B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。
12.HashMap和Hashtable的区别
①HashMap是⾮线程安全的，Hashtable是线程安全的。
Hashtable 内部的⽅法基本都经过 synchronized 修饰。
②因为线程安全的问题，HashMap要⽐Hashtable效率⾼⼀点。
③HashMap允许键和值是null，而Hashtable不允许键或值是null。
HashMap中，null 可以作为键，这样的键只有⼀个，可以有⼀个或多个键所对应的值为 null。
HashTable 中 put 进的键值只要有⼀个 null，直接抛出 NullPointerException。
④ Hashtable默认的初始⼤⼩为11，之后每次扩充，容量变为原来的2n+1。
HashMap默认的初始⼤⼩为16，之后每次扩充，容量变为原来的2倍。
⑤创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为2的幂次⽅⼤⼩。
⑥JDK1.8 以后的 HashMap 在解决哈希冲突时当链表⻓度⼤于等于8时，将链表转化为红⿊树，以减少搜索时间。Hashtable没有这样的机制。
Hashtable的底层，是以数组+链表的形式来存储。
13. ConcurrentHashMap底层实现
JDK1.7
底层数据结构：Segments数组+HashEntry数组+链表，采用分段锁保证安全性
一个ConcurrentHashMap中有一个Segments数组，一个Segments中存储一个HashEntry数组，每个HashEntry是一个链表结构的元素。
segment继承自ReentrantLock锁。
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。
get()操作：
HashEntry中的value属性和next指针是用volatile修饰的，保证了可见性，所以每次获取的都是最新值，get过程不需要加锁。
1.将key传入get方法中，先根据key的hashcode的值找到对应的segment段。
2.再根据segment中的get方法再次hash，找到HashEntry数组中的位置。
3.最后在链表中根据hash值和equals方法进行查找。
ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null
put()操作：
1.将key传入put方法中，先根据key的hashcode的值找到对应的segment段
2.再根据segment中的put方法，加锁lock()
3.再次hash确定存放的hashEntry数组中的位置
4.在链表中根据hash值和equals方法进行比较，如果相同就直接覆盖，如果不同就插入在链表中。
JDK1.8
底层数据结构：Node数组+链表+红黑树 采用Synchronized和CAS来保证线程安全。
get()操作：
get操作全程无锁。get操作可以无锁是由于Node元素的val和指针next是用volatile修饰的。
在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。
1.计算hash值，定位到Node数组中的位置
2.如果该位置为null，则直接返回null
3.如果该位置不为null，再判断该节点是红黑树节点还是链表节点
如果是红黑树节点，使用红黑树的查找方式来进行查找
如果是链表节点，遍历链表进行查找
put()操作：
1.先判断Node数组有没有初始化，如果没有初始化先初始化initTable();
2.根据key的进行hash操作，找到Node数组中的位置，如果不存在hash冲突，即该位置是null，直接用CAS插入
3.如果存在hash冲突，就先对链表的头节点或者红黑树的头节点加synchronized锁
4.如果是链表，就遍历链表，如果key相同就执行覆盖操作，如果不同就将元素插入到链表的尾部，
并且在链表长度大于8， Node数组的长度超过64时，会将链表的转化为红黑树。
14. ConcurrentHashMap和Hashtable的区别
1.底层数据结构：
JDK1.7的ConcurrentHashMap底层采用：Segments数组+HashEntry数组+链表
JDK1.8的ConcurrentHashMap底层采用：Node数据+链表+红黑树
Hashtable底层数据结构采用：数组+链表
2.实现线程安全的方式：
在JDK1.7中ConcurrentHashMap采用分段锁实现线程安全。
在JDK1.8中ConcurrentHashMap采用synchronized和CAS来实现线程安全。
15. HashSet和TreeSet的异同
相同点：HashSet和TreeSet的元素都是不能重复的，并且它们都是线程不安全的。
不同点：
①HashSet中的元素可以为null，但TreeSet中的元素不能为null
②HashSet不能保证元素的排列顺序，TreeSet支持自然排序、定制排序两种排序方式
③HashSet底层是采用哈希表实现的，TreeSet底层是采用红黑树实现的。
查看11道真题和解析
