高频面经汇总：https://blog.csdn.net/qq_40262372/article/details/116075528
六、Java集合
6.1 List,Set,Map三者的区别？
List(对付顺序的好帮手)：存储的元素是有序的、可重复的。
Set(注重独一无二的性质)：存储的元素是无序的、不可重复的。
Map(用Key来搜索的专家)：使用键值对(key-Value)存储，里面key-value映射的规则是Hash函数映射，一个key只能映射到一个Value。
6.2 Arraylist与LinkedList区别？
1.是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
2.底层数据结构：ArrayList使用的是数组，LinkedList使用的是双向链表。
3.插入和删除是否受元素位置的影响：①ArrayList采用数组储存，所以插入和删除元素的时间复杂度受元素位置的影响。会将目标元素的后面所有元素进行移动。②LinkedList采用链表存储，所以插入和删除操作不受元素位置的影响。直接断开链表进行插入与删除，不必大规模操作之后的元素。
4.是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
5.内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为一个节点(双链表)要放前指针、值、后指针)。
6.3ArrayList与Vector区别呢？为什么要用Arraylist取代Vector呢？
ArrayList和Vector底层都是Object[ ]数组。
Vector是线程安全的，就是说某一个时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性。但是实现同步需要很高的花费，因此，访问它比访问Arraylist慢。
6.4ArrayList的扩容机制
1.首先空构造初始化，指向一个空数组
2.add方法(扩容的触发是添加)
第一次调用，会与默认值(10)比较，看谁大选谁
然后进行判断是否需要扩容
进入扩容函数
扩容后的数量是扩容前的1.5倍
这个是因为第一次的时候oldCapacity=0，所以newCapacity=0，所以这样才会小于0
然后把之前默认值(10)直接赋值给新容量.
规定最大的最大值，要-8(虚拟机的限制);
不能超过规定长度
然后将老数组的数组复制过去
总结：
1.构造方法：初始化一个空数组
2.add方法：1.扩容逻辑 2.赋值 3.返回true
扩容逻辑：①第一次直接初始化长度为10的数组
②后续按照1.5倍扩容(满足扩容条件)传入的长度(Mincapacity)大于了现有数组长度(elementData.length)。
6.5HashMap和Hashtable的区别
1.线程是否安全：HashMap是非线程安全的，HashTable是线程安全的，因为HashTable内部的方法基本都是经过synchronized修饰。
2.效率：因为线程安全的问题，HashMap要比HashTable效率高一点。另外，HashTable基本被淘汰了，不要在代码中使用它。
3.对Null key和Null value的支持：HashMap可以存储null的key和value，但null作为键只有一个，null作为值可以有多个；HahTable不允许有null键和null值，否则会抛出NullPoninterException。
4.初始容量大小和每次扩充容量大小的不同：①创建时如果不指定容量初始值，HashTable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16,。之后每次扩充，容量变为原来的2倍。②创建给了初始值，Hahstable就会这个值直接当做容量大小，但是HashMap会把将其扩充为2的幂次方大小。
5.底层数据结构：JDK1.8以后的HashMap在解决哈希冲突有了较大的变化，当链表长度大于8(链表转换为红黑树前会判断，如果当前数据的长度小于64，那么会选择先进行数组扩弄，而不是转换为红黑树。)时，将链表转化为红黑树，以减少搜索时间。Hashtable没有这样的机制。
6.6 HashMap和HashSet区别
HashSet底层是基于HashMap实现的。除了clone()、writeObject()、readObject()是HashSet自己不得不实现之外，其他方法都是直接调用HashMap中的方法。
6.7HashSet如何检查重复
当把对象加入到Set中，会计算对象的哈希值，与Set集合中的对象哈希值一一比较，如果没有相同的哈希值，说明无重复；发现有相同的哈希值，然后将该位置上的对象与新加入的对象用equals比较对象的属性是否真的相等，如果相等说明重复不能加入。
HashCode与equals的相关规定：
1.如果两个对象相等，则hashcode一定也是相同的
2.两个对象相等，对两个euqals方法返回true
3.两个对象有相同的hashcode值，他们也不一定是相等的
4.综上，equals()方法被覆盖过，则hashCode()方法也必须被覆盖
5.hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等（即时这两个对象指向相同的数据）
==与equals的区别
一基两引用
对于基本类型来说，==比较的是值是否相等。
对于引用类型来说，==比较的是两个引用是否指向同一个对象地址(两者在内存存放的地址(堆内存地址)是否指向同一个地方)
对于引用类型(包括包装类型)来说，equals如果没有被重写，对比他们的地址是否相等；如果equals()方法被重写(例如String)，则比较的是地址里的内容。
6.8HashMap的底层实现
6.8.1 JDK1.8之前
JDK1.8之前HashMap底层是数组和链表。HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置(这里的n是指数组的长度)，如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。拉链法是指遇到哈希冲突就将冲突的值加到链表中即可。
6.8.1 JDK1.8之后
JDK1.8以后的HashMap在解决哈希冲突有了较大的变化，当链表长度大于8(链表转换为红黑树前会判断，如果当前数据的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树。)时，将链表转化为红黑树，以减少搜索时间。
6.9HashMap的长度为什么是2的幂次方
为了能让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀。Hash值的范围是-2^31~2^31。虽然有这么多，但是计算机的内存没有这么多内存去储存这些数据，所以我们都会把hash值进行处理。我们先对数组的长度取模运算，得到的余数才能用来要存放的位置。计算方法是(n-1)&hash (n是数组的长度)。其中取模运算是%操作中除数是2的幂次方的话，可以把%等价为&(除数-1) ,这样就会加快速度。 这就解释了为什么要用2的幂次方。
6.10HashMap多线程操作导致死循环问题
主要原因在于并发下的Rehash会造成元素之间会形成一个循环链表。
JDK1.7才会出现。
单线程：
扩容：
到插入1,2,3的时候，如果计算出的hash值都一样就会出现如下情况。新来的Next指向之前位置上的位置。头插法！
1.先判断原来的容量是否达到最大值，达到了就不能扩容了
2.扩容transfer
循环数组的每个坑，然后在循环坑里的链表。把原来的元素转移到新的数组
E代表循环的元素
e.next=newTable[i]，将元素的Next指针指向新数组，转移第一步
newTable[i]=e;(向下移动)，转移第二步
第一次移动过来了，然后移动第二个。e=next;再把e指向老数组的next
然后开始循序，假设运气很不好，计算出的值又是在一个坑上。
扩完容 就变成这样。是因为JDK1.7插入链表的时候插入头结点的(多线程出现循环)。所以新来一个，之前的链表都要往下走。
多线程的时候：
线程1会扩容一个新的数组：
线程2会扩容一个新的数组：
共用的老数组：
线程2卡在红点不动了
然后线程1就进行单线程的操作，变成这样
然后到了线程进行操作的时候，e2仍然指向的是3
线程2进行转移，线程2是在线程1操作了，而不是之前的老数组操作(被GC回收)。将e2移到线程2的数组去，然后继续进行循环
当3移动过去后，继续移动2,2的下一个Next是3，所以线程2的next指针再次指向3。
然后2向下移动
然后将e2的next赋值给Next2。但是e2的next是空了
然后将e2里面的next再指向新数组(e.next=newTable[i])，万一又跑到同一个位置，就会这样了
然后这样就在一直循环了。
JDK1.8采用了尾节点，就避免了循环了。
JDK1.8不只是采用尾插法去解决了循环链表的问题，并且他还引入了高位链和低位链去解决(谢谢评论区的朋友指出)
6.11ConcurrentHashMap和Hashtable的区别
ConcurrentHashMap和Hashtable主要区别是体现线程安全的方式不同。
Hashtable：使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put添加元素，另一个线程不能使用Put添加元素，也不能使用get，竞争越激烈效率越低。
ConcurrentHashMap:在JDK1.7的时候，主要使用segement对整个桶数组进行分割，默认是16，每个锁只会锁segement，每个segement不会互相影响，当不同线程访问不同数据段的时候，不会发现锁竞争，进而提高效率。在JDK1.8，ConcurrentHashMap采用Node数组+链表+红黑树的数据结构实现，并发控制采用CAS+sychronized来操作。
JDK1.8的ConcurrentHashMap不再是Segment数组+HashEntry数组+链表，而是用Node数组+链表/红黑树。Node适用于链表，TreeNode适用于红黑树。因为会链表和红黑树转换（8-6,其中数组长度没有达到64就先扩容数组，如果达到了树化）
6.12ConcurrentHashMap线程安全的具体实现/底层具体实现
JDK1.7：分段锁，将数据分为一段一段存储，然后给每一个数据段分配一个锁。当一个线程占用了其中一个数据段，其他数据段仍然可以被其他线程访问。
一个ConcurrentHashMap包含一个Segment数组。Segement的结构和HashMap类似，是一种数组和链表结构，一个Segement包含一个Hashentry数组，每个HashEntry是一个链表结构的元素，每个Segement守护一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segement的锁。
JDK1.8：ConcurrentHashMap取消了Segment分段锁，采用CAS和sychronized来保证并发安全。数据结构跟HashMap1.8的结构相似，数组+链表/红黑树。Java8在链表长度超过一定阈值(8,并数组长度大于64)将链表(寻址时间复杂度O(N))转化为红黑树(寻址时间复杂度为O(log(N)))
Synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
6.13红黑树
属于二叉搜素树的一种。
NIL节点是空节点。
1.要么红要么黑
2.根节点是黑色
3.最后的叶子节点都是空，而且是黑色。上下黑
4.一个红节点有两个黑节点儿子，黑节点对儿子没有特定要求
5.任意一个节点到不同叶子节点的路径上包含的黑色节点(包含叶子NIL黑节点)都是相同的。
可以推出只要有了一个黑儿子，那么肯定是有两个黑儿子。因为到每个叶子节点上的路径黑节点一样。
三黑(一根，一叶，路径黑)一红(一红对二黑)一中(一红或一黑)
其中红黑树虽然不是完美的二叉平衡树，但是黑色节点的层数是一样的。所以称为黑色完全平衡。
红黑树自平衡靠三种操作：左旋，右旋，变色。
左旋右上(右儿子上位)，右旋左上(左儿子上位)
左旋：右儿子当祖先，右儿子的左儿子变为以前祖先的右儿子
右旋：左儿子变成祖先，左儿子的右儿子变成原来祖先的左儿子
变色：红色变黑色或者黑色变红色。
红黑树查找(自平衡)：
红黑树的插入：①查找插入的位置 ②插入后自平衡 新插入节点必须是红色的，红插
红黑树插入情景(红插)：
情景1：红黑树为空树
处理：直接把插入节点作为根节点，然后再染成黑色
情景2：插入节点的Key已存在
处理：更新当前节点的值为插入节点的值
情景3：如果插入元素的爸爸是黑色的，
处理：那么直接插入，没有破坏性质。无需做自平衡。
情景4：如果插入元素的爸爸是红色，会打破 一红(一红两黑)原则
4.1叔叔节点存在并且红节点
处理：
4.2叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点。
4.2.1 I节点在左边 LL双红
处理：1.P设置为黑色，将PP设置为红色
2.进行右旋。
4.2.2 I节点在右边 LR双红
处理：
1.左旋P节点，得到LL双红
2.
JAVA高频面试题：
https://blog.csdn.net/qq_40262372/article/details/112556249
B站视频讲解如何三个月学习JAVA拿到实习Offer:
https://www.bilibili.com/video/BV1dV411t71K
如果想要在学习的道路上和更多的小伙伴们交流讨论
请加Q群：725936761
欢迎每一位小伙伴的加入
我们一起朝着目标加油！冲锋陷阵！
更多笔记资源请关注微信公众号：万小猿
原文PDF笔记关注公众号回复“集合”即可获取
