自我介绍
项目介绍
项目挑战，redis缓存了啥? 为啥要用redis? 为啥要用redis而不是用数据库?
redis缓存了文件路径，因为文件路径是不变的，而文件内容是变化的，所以可以将文件路径缓存到redis中，这样可以减少对数据库的访问，提高性能。
JVM的堆，栈分配的内存物理地址有什么区别
1、物理地址
堆的物理地址是不连续的，性能相对较慢，是垃圾回收区工作的区域。在GC时，会考虑物理地址不连续，而使用不同的算法，比如复制算法，标记-整理算法，标记-清楚算法等。
栈中的物理地址是连续的，LIFO原则，性能较快。
2、内存分别
堆因为是不连续的，所以分配的内存是在运行期确认的，因此大小不固定，一般堆大小远远大于栈。
栈是固定大小的，所以在编译期就确认了。
3、存放内容
堆中存放的是对象实例和数组，该区域更关注的是数据的存储
（静态变量放在方法区，静态对象仍然放在堆中）
栈中存放的是局部变量，栈针，操作数栈，返回结果等。该区更关注的是程序方法的执行。
4、程序的可见度
堆是线程共有的，栈是线程私有的。
5、异常错误
如果栈内存没有可用的空间存储方法调用和局部变量，JVM会抛出java.lang.StackOverFlowError。而如果是堆内存没有可用的空间存储生成的对象，JVM会抛出java.lang.OutOfMemoryError。-Xss选项设置栈内存的大小。-Xms选项可以设置堆的开始时的大小，-Xmx选项可以设置堆的最大值
GC发生在哪个区域，GC算法有哪些
GC一般情况下是发生在堆和方法区
GC算法有以下几种：
1.标记-清除算法:通过标记所有活动对象，然后清除所有没有标记的对象来回收内存。缺点是效率低，内存碎片化严重。分为两个过程：标记过程和清除过程。在标记阶段，垃圾回收器会从根对象开始遍历所有可达对象，并将其标记为活动对象。在清除阶段，垃圾回收器会清除所有未标记的对象，然后回收它们所占用的内存。
2.复制算法：它将内存分为两个区域，每次只使用其中一个区域，当这个区域用完了，就将还活着的对象复制到另一个区域，然后清除已经使用过的区域。这样保证了每次回收的内存都是连续的，避免了内存碎片的问题。缺点是内存利用率低，但是效率高，适用于存活对象较少的场景。
3.标记整理法：是改进的一种标记清理法，它在清除阶段不仅会回收未标记的对象，还会将所有活动对象移动到内存的一端，然后将令一端全部清空，这样保证了内存的连续性问题，避免了内存碎片化的问题。
4.分代收集法：分代收集法是一种常见的垃圾回收方法，它将内存分为不同的代，每一代都有不同的回收策略，一般来说，新创建的对象会被分配到年轻代，年轻代使用复制法进行垃圾回收，老年代使用标记清除法或标记整理法进行垃圾回收。
新生代，老生代使用的是哪种GC算法
新生代使用的是复制算法，老生代使用的是标记清除算法或标记整理算法。
hashmap原理
首先要了解三种数据结构
数组：其实所谓的数组指的就是一组相关类型的变量集合，并且这些变量彼此之间没有任何的关联。存储区间连续，占用内存严重，数组有下标，查询数据快，但是增删比较慢；
链表：一种常见的基础数据结构，是一种线性表，但是不会按照线性的顺序存储数据，而是每一个节点里存到下一个节点的指针。存储区间离散，占用内存比较宽松，使用链表查询比较慢，但是增删比较快；
哈希表：Hash table 既满足了数据的快速查询（根据关键码值key value 而直接进行访问的数据结构），也不会占用太多的内存空间，十分方便。哈希表是数组加链表组成。
HashMap是基于哈希表的Map接口的非同步实现。底层使用红黑树+数组+链表实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
hashmap中链表的作用
当hashmap中的链表长度大于8时，链表会转换为红黑树，这样可以提高查询效率。
当hashmap中的红黑树长度小于6时，红黑树会转换为链表，这样可以节省内存空间。
如何解决hashmap的hash冲突
1.开放地址法：当发生冲突时，使用某种探测方法在散列表中形成一个探测序列，直到找到一个空的散列地址，将其插入其中。探测方法的特点是：从基本的散列地址出发，每次探测下一个散列地址，直到找到空的散列地址为止。常用的探测方法有线性探测法、二次探测法、伪随机探测法等。
2.再散列函数法：当发生冲突时，使用一种函数计算另一个散列地址，直到找到空的散列地址为止。这种方法不仅要求散列函数计算速度快，而且要求计算结果能够均匀分布在整个散列表中。
3.链地址法：将散列到同一个地址的所有元素都放在一个链表中，即为该地址建立一个链表，将元素存储在链表中。这种方法简单，但是需要额外的空间存储指针，而且在查找时需要遍历链表，效率较低。
4.公共溢出区法：将散列到同一个地址的所有元素都放在一个公共溢出区中，即为所有冲突元素建立一个公共溢出区，将元素存储在公共溢出区中。这种方法不需要指针，但是在查找时需要遍历公共溢出区，效率较低。
hashmap中链表转换为红黑树的过程
当hashmap中的链表长度大于8时，链表会转换为红黑树，这样可以提高查询效率。
首先，判断HashMap中的元素个数是否达到了链表转换为红黑树的阈值。如果没有达到阈值，则不进行转换。
如果元素个数达到了阈值，HashMap会将链表的元素按照哈希值重新计算，并重新分配到新的红黑树节点上。
在将链表转换为红黑树的过程中，HashMap会根据元素的哈希值进行插入操作。具体的插入操作遵循红黑树的插入规则，确保红黑树的平衡性。
在插入操作完成后，HashMap会将原来的链表节点从链表中移除，并将新的红黑树节点插入到HashMap中。
//红黑树数据结构
public class RedBlackTreeNode{
/*
红黑树定义：
1. 根节点的颜色是黑色
2. 节点只有红色和黑色两种
3. 如果一个节点的颜色是红色，则子节点必须是黑色，也就是不能有连续的两个红色节点
4. 每个叶子节点都是黑色
5. 从任意节点到叶子节点的路径都包含相同数目的黑色节点
*/
public static final boolean RED = false;
public static final boolean BLACK = true;
private int data;
private RedBlackTreeNode left;
private RedBlackTreeNode right;
private RedBlackTreeNode parent;
private boolean color;
public RedBlackTreeNode(int data){
this.data = data;
color = RED;
}
public boolean isColor(){
return color;
}
public void setColor(boolean color){
this.color = color;
}
public int getData(){
return data;
}
public void setData(int data){
this.data = data;
}
public RedBlackTreeNode getLeft(){
return left;
}
public void setLeft(RedBlackTreeNode left){
this.left = left;
}
public RedBlackTreeNode getRight(){
return right;
}
public void setRight(RedBlackTreeNode right){
this.right = right;
}
public RedBlackTreeNode getParent(){
return parent;
}
public void setParent(RedBlackTreeNode parent){
this.parent = parent;
}
}
public class RedBlackTree{
private RedBlackTreeNode root;
public static void main(String[] args){
RedBlackTree tree = new RedBlackTree();
tree.insert(12);
tree.insert(1);
tree.insert(9);
tree.insert(2);
tree.insert(0);
tree.insert(11);
tree.insert(7);
tree.insert(19);
tree.insert(4);
tree.insert(15);
tree.insert(18);
tree.insert(5);
tree.insert(14);
tree.insert(13);
tree.insert(10);
tree.insert(16);
tree.insert(6);
tree.insert(3);
tree.insert(8);
tree.insert(17);
tree.delete(12);
tree.delete(1);
tree.delete(9);
tree.delete(2);
tree.delete(0);
tree.delete(11);
tree.delete(7);
tree.delete(19);
tree.delete(4);
tree.delete(15);
tree.delete(18);
tree.delete(5);
tree.delete(14);
tree.delete(13);
tree.delete(10);
tree.delete(16);
//tree.delete(6);
//tree.delete(3);
//tree.delete(8);
//tree.delete(17);
System.out.println("层级");
levelTraversal(tree.root);
System.out.println();
System.out.println("前序");
recursivelyPreTraversal(tree.root);
System.out.println();
System.out.println("中序");
recursivelyInTraversal(tree.root);
System.out.println();
System.out.println("后序");
recursivelyPostTraversal(tree.root);
}
// 插入节点
public RedBlackTreeNode insert(int data){
RedBlackTreeNode insert = new RedBlackTreeNode(data);
if(root==null){
root = insert;
setBlack(insert);
}else{
RedBlackTreeNode current = root;
RedBlackTreeNode parent = null;
while(current!=null){
parent = current;
if(current.getData()>data){
// 左子树
current = current.getLeft();
}else{
// 右子树
current = current.getRight();
}
}
if(parent.getData()>=data){
parent.setLeft(insert);
}else{
parent.setRight(insert);
}
node.setParent(parent);
// 旋转和调整节点颜色保持红黑树平衡
insertFix(insert);
}
return insert;
}
// 旋转和调整节点颜色保持红黑树平衡
private void insertFix(RedBlackTreeNode node){
while(node.getParent()!=null && isRed(node.getParent())){
RedBlackTreeNode parent = node.getParent();
RedBlackTreeNode grandFather = parent.getParent();
if(grandFather.getLeft() == parent){
//F为G左儿子的情况
RedBlackTreeNode uncle = grandFather.getRight();
if(uncle != null && isRed(uncle)){
setBlack(parent);
setBlack(uncle);
setRed(grandFather);
node = grandFather;
continue;
}
if(parent.getRight() == node){
//插入节点为父节点的右子树
//左旋
leftRotate(parent);
//将旋转后的parent看作插入节点
RedBlackTreeNode tmp = node;
node = parent;
parent = tmp;
}
setBlack(parent);
setRed(grandFather);
rightRotate(grandFather);
break;
}else{
//F为G的右儿子的情况，对称操作
RedBlackTreeNode uncle = grandFather.getLeft();
if(uncle != null && isRed(uncle)){
setBlack(parent);
setBlack(uncle);
setRed(grandFather);
node = grandFather;
continue;
}
if(parent.getLeft() == node){
//插入位置为父节点的左子树
//右旋
rightRotate(parent);
RedBlackTreeNode tmp = node;
node = parent;
parent = tmp;
}
setBlack(parent);
setRed(grandFather);
leftRotate(grandFather);
break;
}
}
setBlack(root);
}
/**
* 删除节点
* @param data
* @return
*/
public RedBlackTreeNode delete(int data){
RedBlackTreeNode node = query(data);
if(node == null){
return null;
}
deleteNode(node);
return node;
}
/**
* 查询节点
* @param data
* @return
*/
public RedBlackTreeNode query(int data){
if(root == null){
return null;
}
RedBlackTreeNode node = root;
while(node != null){
if(node.getData() == data){
return node;
}else if(node.getData() >= data){
node = node.getLeft();
}else {
node = node.getRight();
}
}
return null;
}
private void deleteNode(RedBlackTreeNode node) {
if (node == null){
return;
}
//替换节点
RedBlackTreeNode replaceNode = null;
if(node.getLeft() != null && node.getRight() != null){
//存在左右子树
RedBlackTreeNode tmp = node.getRight();
while(tmp != null){
replaceNode = tmp;
tmp = tmp.getLeft();
}
//将替换节点的值放到原本需要删除的节点
node.setData(replaceNode.getData());
//删除替换节点
node = replaceNode;
}
if(node.getLeft() != null){
replaceNode = node.getLeft();
}else{
replaceNode = node.getRight();
}
RedBlackTreeNode parent = node.getParent();
if(parent == null){
root = replaceNode;
if(replaceNode != null){
replaceNode.setParent(null);
}
}else{
if(parent.getLeft() == node){
parent.setLeft(replaceNode);
}else{
parent.setRight(replaceNode);
}
if(replaceNode != null){
replaceNode.setParent(parent);
}
}
if(isBlack(node)){
//replaceNode为了保持平衡，多了一个黑色，需修复
removeFix(parent, replaceNode);
}
}
/**
* 修复
* @param parent
* @param node 多了一个黑色
*/
private void removeFix(RedBlackTreeNode parent, RedBlackTreeNode node) {
while(isBlack(node) && node != root){
if(parent.getLeft() == node){
//S是P的左儿子
RedBlackTreeNode brother = parent.getRight();
if(isRed(brother)){
setBlack(brother);
setRed(parent);
leftRotate(parent);
brother = parent.getRight();
}
if(brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))){
setRed(brother);
node = parent;
parent = node.getParent();
continue;
}
if(isRed(brother.getLeft()) && isBlack(brother.getRight())){
setRed(brother);
setBlack(brother.getLeft());
rightRotate(brother);
brother = parent.getRight();
}
brother.setColor(parent.isColor());
setBlack(parent);
setBlack(brother.getRight());
leftRotate(parent);
node = root;
}else{
//S是P的右儿子
RedBlackTreeNode brother = parent.getLeft();
if(isRed(brother)){
setBlack(brother);
setRed(parent);
rightRotate(parent);
brother = parent.getLeft();
}
if(brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))){
setRed(brother);
node = parent;
parent = node.getParent();
continue;
}
if(isRed(brother.getRight()) && isBlack(brother.getLeft())){
setBlack(brother.getRight());
setRed(brother);
leftRotate(brother);
brother = parent.getLeft();
}
brother.setColor(parent.isColor());
setBlack(parent);
setBlack(brother.getLeft());
rightRotate(parent);
node = root;
}
}
if(node != null){
setBlack(node);
}
}
/**
* 左旋
* @param node
*/
private void leftRotate(RedBlackTreeNode node) {
RedBlackTreeNode right = node.getRight();
RedBlackTreeNode parent = node.getParent();
node.setRight(right.getLeft());
if(right.getLeft() != null){
right.getLeft().setParent(node);
}
node.setParent(right);
right.setLeft(node);
if(parent == null){
root = right;
right.setParent(null);
}else{
right.setParent(parent);
if(parent.getLeft() != null && parent.getLeft() == node){
parent.setLeft(right);
}else{
parent.setRight(right);
}
}
}
/**
* 右旋
* @param node
*/
private void rightRotate(RedBlackTreeNode node) {
RedBlackTreeNode left = node.getLeft();
RedBlackTreeNode parent = node.getParent();
node.setLeft(left.getRight());
if(left.getRight() != null){
left.getRight().setParent(node);
}
node.setParent(left);
left.setRight(node);
if(parent == null){
root = left;
left.setParent(null);
}else{
left.setParent(parent);
if(parent.getLeft() != null && parent.getLeft() == node){
parent.setLeft(left);
}else{
parent.setRight(left);
}
}
}
/**
* 设置颜色为黑
* @param node
*/
public static void setBlack(RedBlackTreeNode node) {
if(node == null){
return;
}else{
node.setColor(RedBlackTreeNode.Black);
}
}
/**
* 设置颜色为红
* @param node
*/
public static void setRed(RedBlackTreeNode node) {
if(node == null){
return;
}else{
node.setColor(RedBlackTreeNode.Red);
}
}
/**
* 是否是黑色节点
* @param node
* @return
*/
public static boolean isBlack(RedBlackTreeNode node){
if(node == null){
return true;
}else{
return node.isColor() == RedBlackTreeNode.Black;
}
}
/**
* 是否是红色节点
* @param node
* @return
*/
public static boolean isRed(RedBlackTreeNode node){
if(node == null){
return false;
}else{
return node.isColor() == RedBlackTreeNode.Red;
}
}
/**
* 层级遍历
* @param root
*/
public static void levelTraversal(RedBlackTreeNode root){
if(root == null){
return;
}
Queue<RedBlackTreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
RedBlackTreeNode poll = queue.poll();
String color = "Black";
if(isRed(poll)){
color = "Red";
}
System.out.print(poll.getData()+"(" + color + ") ");
if(poll.getLeft() != null){
queue.offer(poll.getLeft());
}
if(poll.getRight() != null){
queue.offer(poll.getRight());
}
}
}
/**
* 前序遍历
* @param node
*/
public static void recursivelyPreTraversal(RedBlackTreeNode node){
if(node == null){
return;
}
String color = "Black";
if(isRed(node)){
color = "Red";
}
System.out.print(node.getData()+"(" + color + ") ");
recursivelyPreTraversal(node.getLeft());
recursivelyPreTraversal(node.getRight());
}
/**
* 中序遍历
* @param node
*/
public static void recursivelyInTraversal(RedBlackTreeNode node){
if(node == null){
return;
}
recursivelyInTraversal(node.getLeft());
String color = "Black";
if(isRed(node)){
color = "Red";
}
System.out.print(node.getData()+"(" + color + ") ");
recursivelyInTraversal(node.getRight());
}
/**
* 后序遍历
* @param node
*/
public static void recursivelyPostTraversal(RedBlackTreeNode node){
if(node == null){
return;
}
recursivelyPostTraversal(node.getLeft());
recursivelyPostTraversal(node.getRight());
String color = "Black";
if(isRed(node)){
color = "Red";
}
System.out.print(node.getData()+"(" + color + ") ");
}
}
hashmap的扩容机制
HashMap的扩容机制是当HashMap中的元素个数超过了负载因子与当前数组长度的乘积时，就会进行扩容，扩容后的数组长度为原来的2倍。负载因子默认为0.75，这是在HashMap中定义的一个常量，可以通过构造方法来指定负载因子的大小。
// HashMap的扩容方法
void resize(int newCapacity) {
Node<K,V>[] oldTable = table;
int oldCapacity = (oldTable == null) ? 0 : oldTable.length;
int threshold = (int)(oldCapacity * loadFactor);
Node<K,V>[] newTable = (Node<K,V>[]) new Node[newCapacity];
// 将所有原来的元素重新计算其在新数组中的位置，并放入相应位置
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)(newCapacity * loadFactor);
// 更新阈值
initHashSeedAsNeeded(newCapacity);
}
// 将原来的元素重新计算其在新数组中的位置
void transfer(Node<K,V>[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Node<K,V> e : table) {
while (null != e) {
Node<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
最左匹配原则
Mysql最左匹配原则是指在使用索引进行查询时，索引的最左边的列将被优先使用，而后续的列只有在最左边的列相等的情况下才会被使用。
举个例子来说明，假设有一个表格”users”，包含以下几列：id、name、age、gender，并且创建了一个复合索引(index)包括name和age两列。
如果我们执行以下查询语句：
SELECT * FROM users WHERE name = ‘John’ AND age = 25;
根据最左匹配原则，Mysql将首先使用索引中的name列来过滤数据，然后再使用age列进行进一步的筛选。这样可以大大提高查询效率。
但是如果我们执行以下查询语句：
SELECT * FROM users WHERE age = 25 AND name = ‘John’;
尽管查询条件相同，但是由于age列在name列之前，根据最左匹配原则，Mysql将无法使用索引来加速查询，而是需要对整个表格进行全表扫描，效率将大大降低。
因此，在创建索引时，需要根据实际的查询需求和条件顺序来确定索引的列顺序，以便最大限度地利用最左匹配原则提高查询效率。
TCP/IP四层模型
1.应用层：应用层是TCP/IP协议族中最靠近用户的一层，它为用户提供应用服务，例如FTP、DNS和HTTP。应用层决定了向用户提供应用服务时通信的活动。比如FTP协议就是一种应用层协议，它规定了一些文件传输的规范，比如规定了客户端和服务器之间如何建立连接，如何传输数据，传输数据的格式等等。HTTP协议也是一种应用层协议，它规定了浏览器和服务器之间如何传输数据，传输数据的格式等等。
2.传输层：传输层主要为两台主机上的应用程序提供端到端的通信。它主要有两个协议：TCP(传输控制协议)和UDP(用户数据报协议)。TCP协议提供面向连接的通信，数据传输的单位是TCP报文段。UDP协议提供无连接的通信，数据传输的单位是UDP数据报。TCP协议提供可靠的数据传输，UDP协议不保证数据传输的可靠性。
3.网络层：网络层主要为主机提供数据传输服务。它主要有三个协议：IP协议、ICMP协议和ARP协议。IP协议主要解决数据如何在网络中传输，规定了数据传输时的编址和路由选择。ICMP协议主要解决如何在网络中进行错误报告，它是IP协议的辅助协议。ARP协议主要解决如何将IP地址转换成物理地址，它是IP协议的辅助协议。
4.网络接口层：网络接口层也叫做数据链路层，它包括操作系统中的设备驱动程序和计算机中对应的网络接口卡。它们一起处理操作系统和网络之间的通信。网络接口层对应的协议包括以太网协议、ARP协议、RARP协议、MTU协议和PPP协议等。
为什么是三次握手，而不是两次或四次，第三次握手的作用是什么
确认双方的通信能力：在进行握手之前，客户端和服务器都不知道对方的可靠性和通信能力。通过三次握手，双方可以互相确认对方的存在和可靠性。
防止已失效的连接请求被错误接受：如果只有两次握手，那么在客户端发送连接请求后，如果网络延迟或其他原因导致该请求长时间未到达服务器，服务器可能会在一段时间后错误地接受该连接请求。而通过三次握手，可以确保只有真正的连接请求才会被接受。
防止已失效的连接请求被错误拒绝：如果只有两次握手，那么在客户端发送连接请求后，如果网络延迟或其他原因导致该请求长时间未到达服务器，服务器可能会在一段时间后错误地拒绝该连接请求。而通过三次握手，可以确保只有真正的连接请求才会被接受。
确保双方都能够同步序列号和初始序列号：三次握手过程中，双方会交换初始序列号和确认序列号，以确保双方都能够正确地同步序列号。这对于后续的数据传输和连接维护非常重要。
三次握手的作用是为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误。
代码题：删除链表的倒数第N个节点
// 删除链表的倒数第N个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* first = dummy;
ListNode* second = dummy;
for(int i=0;i<n+1;i++){
first = first->next;
}
while(first!=NULL){
first = first->next;
second = second->next;
}
second->next = second->next->next;
return dummy->next;
}