[toc]
-
数组中的第
K个最大元素：PriorityQueue小根堆或利用快排partition过程对topk个元素进行快速选择排序。 -
合并两个有序数组：数组一有多余空间存储数组二，直接从后向前遍历两个数组，数组一越界则填充数组二。
-
搜索旋转排序数组：二分，旋转数组一定有一边是有序的，如果不在有序这边则换边。
-
最大子序和：一维
dp，每个数要么自成一派，要么与前面合并形成最大和。 -
两数之和：暴力遍历；哈希表额外空间。
-
三数之和：先排序，穷举第一个数，剩下的求所有两数之和的情况，两数之和用双指针，需要过滤掉重复的值。
-
最长递增子序列：一维
dp初始化为1，dp[i]表示以nums[i]结尾的最长递增子序列的长度。
-
螺旋矩阵：左上->右上、右上->右下、右下->左下、左下->左上，依次进行遍历。
-
合并区间：先按区间起始值排序（
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]))），注意排序写法。然后如果当前区间起始值小于上一个区间的最大值则进行合并，否则是单独的区间。
-
字符串相加：用中间变量记录产生的进位，
charAt(index) - '0'可得到整数值，从后往前遍历累加，用StringBuilder保存结果，reverse反转后返回。 -
最长回文子串：从中间向两边扩散寻找回文子串。
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
public String palindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
// 从中间向两边扩散开
left--;
right++;
}
return s.substring(left + 1, right);
}
1. 去除前导空格
2. 记录第一个字符的正负号
3. 循环处理后续字符
3.1 如果遇到非0-9的字符则立即退出
3.2 如果大于Integer.MAX_VALUE则返回Integer.MAX_VALUE
3.3 如果小于Integer.MIN_VALUE则返回Integer.MIN_VALUE
3.4 累加结果
-
反转链表：递归和迭代两种写法。
-
反转链表
II：指定区间[m, n]反转链表，递归[m - 1, n - 1]区间反转，直到m == 1转变为反转前N个节点。 -
环形链表：快慢指针，如果有环则一定在环中相遇，且快指针比慢指针多走
n圈（一圈等于环的长度）。 -
环形链表
II：快慢指针判定有环，相遇后将快指针重置在链表头部，再和慢指针同时走，再次相遇的地方即为环的入口节点。 -
合并两个有序链表：递归或迭代，迭代需引入虚拟哨兵节点。
-
相交链表：双指针。指针一在链表一上走完了则置为链表二头部；指针二在链表二上走完了则置为链表一头部。双指针相遇时即为交点。
-
合并
K个排序链表：小根堆PriorityQueue初始化每个链表的头节点，每次弹出堆顶最小元素，如果存在下一个节点则入堆。 -
链表中倒数第
K个节点：双指针。指针一先走k - 1步，指针二再从头开始和指针一同步走。 -
删除链表中倒数第
N个节点：先找到倒数第N + 1个节点，然后再删除倒数第N个节点。 -
重排链表：先找链表中点，断开左右两边的链表连接，然后反转链表后半段，最后合并两个链表。
-
删除排序链表中的重复元素 II：用虚拟哨兵节点，如果下一个节点和下下个节点值相等，则用中间变量记录一下这个值，然后循环删除值相等的节点。
-
二叉树的层序遍历：
Queue队列。 -
二叉树的之字形遍历：
Deque双端队列。先左后右，左进右出；先右后左，右进左出。 -
二叉树的最近公共祖先：递归。
- 11.20 不知道思路，需要重点看
- 11.20 思路不清晰，需要重点看。二叉树的基本遍历方式
- 11.20 思路正确，一次通过。
- 11.20 快排思路不够熟练，需要加强看
- 11.20 需要反复练习
- 11.20 需要加强记忆
- 11.20 思路正确，需加强练习。
- 11.20 思路模糊，需重点记忆
- 11.20 思路较为清晰，需反复练习。
- 11.20 思路较为清晰，需反复练习。
- 11.20 思路不清晰，需要重点反复看
- 11.20 思路正确，一次通过
- 11.20 思路基本正确，可以再加强记忆
TCP三次握手和四次挥手过程- 为什么要三次握手？为什么要四次挥手？
- 为什么客户端第四次挥手完后还要
TIME-WAIT等待2MSL? TIME-WAIT状态链接数量过多怎么解决？TCP粘包原因和解决办法HTTP1.0、HTTP1.1、HTTP2.0区别HTTP和HTTPS区别HTTP常见响应状态码- 浏览器从输入
URL到页面加载发生了什么？
https://blog.csdn.net/qzcsu/article/details/72861891
第一次握手：
客户端 => 服务端：发送带有SYN标志的数据包。客户端进入SYNC_SEND状态。
第二次握手：
服务端 => 客户端：回应带有ACK标志的数据包，同时携带客户端的SYN。服务端进入SYNC_RCVD状态。
第三次握手：
客户端 => 服务端：回应带有ACK标志的数据包。链接进入ESTABLISHED状态。
第一次挥手：
客户端 => 服务端：发送带有FIN标志的数据包。关闭与服务端的连接，客户端进入FIN-WAIT-1状态。
第二次挥手：
服务端 => 客户端：回应带有ACK标志的数据包，确认序列号seq为收到的序列号+1。服务端进入CLOSE-WAIT状态。
第三次挥手：
服务端 => 客户端：发送带有FIN标志的数据包。关闭与客户端的连接，客户端进入FIN-WAIT-2状态。
第四次挥手：
客户端 => 服务端：客户端收到FIN后，回应一个ACK标志的数据包，并将确认序列号设置为收到的序列号+1，客户端进入TIME_WAIT状态。
三次握手主要是为了防止已失效链接请求报文突然又传送到了服务端，从而产生错误。如果只有两次握手，假设第一次握手的报文在网络中滞留了，由于客户端迟迟未收到ACK回应报文，以为服务端未收到从而重发，此后这个重发的请求完成了两次握手链接，传输数据，然后关闭连接。这个时候如果那个在网络中滞留的请求报文重新到达了服务器，该报文本应该失效，但是由于两次握手机制它会与服务端建立连接，从而导致不必要的错误和资源浪费。如果是三次握手，那即便第一次滞留的报文重新到达服务端，服务端回应ACK，但是客户端不会再次发出第三次握手的确认ACK。由于服务端收不到确认，就知道客户端并没有请求连接。
四次挥手是为了确保客户端和服务端之间的数据能够传输完成。第一次挥手服务端收到客户端的FIN报文后，仅表示客户端不再发送数据了但是客户端还能接收数据，而服务端也未必将全部数据都发送给了客户端，所以服务端可以立即关闭，也可以发送一些数据后再发送FIN报文给客户端表示同意关闭连接，因此，服务端的ACK和FIN会分开发送，从而导致要四次挥手。
保证第四次挥手客户端发送的ACK报文能到达服务端，因为这个ACK报文可能丢失，站在服务端的角度来看，我已经发送了ACK和FIN报文请求关闭连接了，客户端还没有给我回应，应该是我发送的FIN报文它还没有收到，于是服务端会重传FIN报文，客户端就能在这个2MSL时间段内收到这个重传的报文进行回应。
出现这种情况的可能原因是在高并发短连接的服务器上。可以调整系统内核参数，降低MSL周期（tcp_fin_timeout的值），同时增加time_wait的队列（tcp_max_tw_buckets）。
TCP粘包是指发送方发送的若干包数据到接收方接收时粘成一包。
发送方原因：
TCP默认使用Nagle算法（主要作用：减少网络中报文段的数量）：收集多个小分组，在一个确认到来时一起发送，导致发送方可能会出现粘包问题。
接收方原因：
TCP将接收到的数据包保存在接收缓存中，如果TCP接收数据包到缓存的速度大于应用程序从缓存中读取数据包的速度，多个包就会被同时缓存，应用程序就有可能读到多个首尾相连粘到一起的包。
解决粘包问题：
最本质原因是接收方无法分辨包和包之间的边界在哪。可以通过一些方案给出边界，例如：
- 发送定长包。每个包的大小都是一样的，接收方只要不断接收数据，直到数据等于一个定长的数值就将它作为一个包。
- 包尾加上
\r\n标记。FTP协议就是这么做的，但问题在于如果数据正文中也有\r\n，则会误判为包的边界。 - 包头加上包体长度。包头是定长
4个字节，表示包体的长度。接收方首先接收包体长度，再根据包体长度来接收包体。
HTTP1.0和HTTP1.1的主要区别是：
- 缓存处理：添加更多的缓存控制策略
- 网络连接优化：支持断点续传
- 错误状态码增加：新增了一些错误状态码。
- 支持长连接：减少建立和关闭连接的消耗和延迟。
HTTP1.1和HTTP2.0的主要区别是：
- 新的传输格式：
2.0使用二进制格式，1.1基于文本格式。 - 多路复用：连接共享，不同的
request请求可以使用同一个连接传输。 header压缩：由于1.1中header携带大量信息，并且每次得重复传输，2.0使用encoder来减少需要传输的header大小- 服务端推送
HTTP3.0基于UDP协议。
- 用户态、内核态
- 用户态切换到内核态的
3种方式 - 进程和线程区别
- 进程间的通信方式
- 线程同步方式
- 用户态：只能受限的访问内存，运行所有的应用程序
- 内核态：运行操作系统程序，
CPU可以访问内存的所有数据，包括外围设备。
- 系统调用：主动调用，系统调用的机制核心还是使用了操作系统为用户特别开放的一个中断来实现，例如
Linux的int 80h中断 - 异常
- 外围设备的中断
- 进程：资源分配的最小单位，一个进程可以有多个线程。从
Java虚拟机的角度看，多个线程共享虚拟机进程的堆和方法区资源，不共享栈、程序计数器。 - 线程：任务调度和执行的最小单位。线程并行执行存在资源竞争和上下文切换的问题。
- 协程：轻量级的线程，一个线程可以拥有多个协程。
- 管道
- 信号
- 信号量
- 消息队列
- 共享内存
- 套接字
内存管理方式：分段管理、分页管理、段页式管理。
页面置换算法：FIFO先进先出、LRU最近最久未使用
ArrayList：底层基于数组实现，通过数组下标实现对元素的随机快速访问。默认初始容量为10，当数组容量不足时，触发扩容机制，每次扩容1.5倍，需要开辟新的数组空间，将原数组进行拷贝。当从ArrayList中间位置插入或删除元素时，需要对后面的元素进行拷贝移动，代价较高。ArrayList适合读多写少的场景。
LinkedList：底层基于双向链表实现，插入和删除的时间复杂度是O(1)。不仅实现了List接口，还实现了Deque接口，所以它还可以当做堆、栈、队列、双向队列数据结构来使用。LinkedList适合写多读少的场景。
比较：都是线程不安全的容器，ArrayList适合读多写少的场景，而LinkedList适合写多读少的场景。
Vector：使用synchronized关键字对每个方法加锁实现线程安全，已不推荐使用。
CopyOnWriteArrayList：JUC包下的并发容器之一，采用了写时复制的方法，写时加锁保证线程安全，读操作不加锁。
可以从以下角度来介绍HashMap：数据结构、扩容机制、put过程、哈希函数、容量、1.7和1.8区别
HashMap底层数据结构采用数组 + 链表 + 红黑树，通过散列映射来存储键值对。
默认的负载因子loadFactor为0.75，即如果数组中已经存储的元素个数大于数组长度的75%，将会触发扩容。
- 创建一个长度为原来数组长度两倍的新数组
1.7采用Entry的rehash运算；1.8采用高位与运算。
- 计算
hash值，判断数组是否为空，为空则初始化数组。 - 数组不为空，
(n - 1) & hash计算数组下标。 - 如果数组下标位置没有元素，直接构造
Node节点进行插入。 - 如果数组下标位置有元素，说明出现哈希冲突，判断
key是否相等，如果相等，则进行值覆盖。 - 如果不相等，判断当前节点是否为红黑树节点，如果是红黑树节点，则构造新的红黑树节点执行红黑树的插入。
- 如果不是红黑树节点，则遍历链表，判断链表中的
key是否等于待插入的key，如果相等则进行值覆盖。 - 如果一直遍历到链表尾部都没有相等的
key，则创建新的链表节点执行尾插。 - 判断链表长度是否大于
8，大于则转化为红黑树。 - 判断元素个数
size是否超过阀值，超过则扩容。
key的hashCode的高16位和低16位进行异或运算。
容量总是为2的n次幂，便于快速计算数组下标(n - 1) & hash。
1.7采用数组 + 链表。链表采用头插法会在扩容反转时导致死循环。
1.8采用数组 + 链表 + 红黑树。链表采用尾插法解决死循环，当链表长度大于8，数组长度大于64时转化为红黑树。
HashTable：为每个方式使用synchronized关键字加锁实现线程安全，效率较低。
ConcurrentHashMap：1.7采用数组 + 链表 + 分段锁实现。默认将整个数组分为16个Segment，每个锁只锁定其中一个Segment，当多线程访问不同Segment下的数据时不会发生竞争，从而提升并发效率。
1.8摒弃了分段锁，直接用数组 + 链表 + 红黑树实现，使用synchronized和CAS来保证线程安全。如果数组下标位置没有元素则直接用CAS插入，如果有元素，则用synchronized加锁插入。
JDK中用java.lang.Thread.State枚举定义了Java线程的6种状态。分别是：
NEW：就绪态RUNNABLE：运行态BLOCKED：阻塞态WAITING：等待态TIMED_WAITING：计时等待态TERMINATED：终止态
核心都是实现Runnable接口。
1、继承Thread类
2、实现Runnable接口
3、实现Callable接口实现带有返回值的线程
4、使用线程池
java.util.concurrent.ThreadPoolExecutor是JDK中的线程池实现。
1、corePoolSize：核心线程数
2、maximumPoolSize：最大线程数
3、keepAliveTime：空闲线程的最大存活时间
4、unit：keepAliveTime的时间单位
5、workQueue：任务队列
6、threadFactory：线程工厂
7、rejectedExecutionHandler：任务拒绝策略
1、判断是否达到核心线程数，未达到则创建核心线程执行任务。 2、核心线程满，判断任务队列是否已满，未满则存入任务队列。 3、任务队列已满，判断是否达到最大线程数，未达到则创建非核心线程执行任务。 4、最大线程数满，执行拒绝策略。
1、AbortPolicy：抛异常。
2、CallerRunsPolicy：用调用者线程（当前线程）执行任务。
3、DiscardOldestPolicy：丢弃任务队列头部的任务，提交当前任务。
4、DiscardPolicy：丢弃当前任务。
1、高并发、任务执行时间短的任务。线程数设置为CPU核数加一，减少上下文的切换。
2、并发不高、任务执行时间长的任务要分开看：
CPU密集型：设置为CPU核数加一，减少上下文切换。IO密集型：可以设置为CPU核数的两倍。也可以用公式：CPU核心数 *（1 + 平均等待时间/平均工作时间） 3、并发高、任务执行时间长的任务。这类任务的关键不在于线程池，而在于整体架构的设计。第一步先看任务中的数据是否可以做缓存，第二步可以增加服务器，最后，任务执行时间长的问题，可能需要分析一下具体原因，看是否能用一些中间件进行解耦。
总是乐观的认为数据不会被其它线程修改。不会主动加锁。在更新数据时会去判断数据是否被更新过。一般通过版本号机制或者CAS来实现。乐观锁适用于读多写少的场景，可以提高系统并发度。JUC的子包atomic下的原子变量类就是使用CAS来实现乐观锁的。
Compare And Swap比较并替换。不使用锁机制实现同步。CAS算法过程：
内存中的值V、进行比较的值A和准备写入的值B，当且仅当A的值等于V的值时，才用B去更新V的值，否则进行自旋重试。
会出现ABA问题：其它线程将内存中的值从A改为B再改为A，实际数据已经被修改过。这种情况可以新增版本号字段来解决，内存中的值每发生一次变化版本号都加一，在CAS时不仅比较内存中的值，还比较版本号，当两者都没有变化时才进行更新。atomic包下的AtomicStampedReference类就使用了版本号机制。
同步代码块底层是用monitorenter和monitorexit指令实现的；同步方法底层是用flags：ACC_SYNCHRONIZED来实现的。
synchronized申请锁、上锁和释放锁等都和对象头有关。对象头主要由Mark Word组成，Mark Word主要存储对象的hashCode、锁信息、分代年龄和GC标志等信息。
JDK6之后对synchronized进行了很多优化，包括自适应自旋、锁粗化和锁消除等。
自旋锁可以避免等待竞争锁进入阻塞挂起状态被唤醒造成的内核态和用户态之间的切换造成的损耗，它们只需要等一等重新尝试（自旋），但是如果锁被其它线程长时间占用，一直不释放CPU，自旋就会带来更多的性能开销，默认的自旋次数是10次。
对上述自旋锁进一步优化的方式是，不再固定其自旋次数，其自旋次数由上一次在同一个锁上的自旋时间及锁的拥有者状态来决定。
大部分情况下我们是要让锁的粒度最小化，锁的粗化则是要增大锁的粒度；例如在循环体中对同一对象加锁，即使没有线程竞争，频繁的进行加锁解锁也会造成不必要的性能损耗。当虚拟机探测到这种情况时，会将加锁同步的范围粗化到整个操作的外部。
如果逃逸分析判断出在一段代码中，堆上的所有数据都不会逃逸出去被其它线程访问到，那就可以把它们当做栈上数据对待，认为它们是线程私有的，自然不需要同步加锁。
JDK6之后为锁新增了偏向锁和轻量级锁两种状态。升级过程如下：
初始状态为无锁状态，当线程1来访问同步代码块获取锁对象时，检查对象头Mark Word中是否存储了自己的线程ID，如果没有则使用CAS将Mark Word中的线程ID设置为自己的，即进入偏向锁状态。
偏向锁不会主动释放锁，当线程1再次获取锁时，只需要比较对象头中的线程ID是否和自己的线程ID一致，如果一致，则立即获得偏向锁。否则进行竞争（线程2来尝试获取锁）。查看对象头中记录的线程ID对应的线程（线程1）是否存活，如果没有存活，将锁对象重置为无锁状态，线程2可以竞争将其设置为偏向锁；如果存活，则查找线程1的栈帧信息，如果还需要继续持有该锁对象，那么暂停线程1，撤销偏向锁，升级为轻量级锁。如果线程1不再需要使用该锁对象，则撤销偏向，重置为无锁状态，重新偏向新的线程。
线程1获取轻量级锁时会先把锁对象的对象头Mark Word复制一份到线程1的栈帧中创建的用于存储锁记录的空间（成为DisplacedMarkWord），然后使用CAS将对象头中的Mark Word替换为线程1存储锁记录的地址；
如果线程1在复制对象头的同时（线程1CAS之前），线程2也准备获取锁，复制了对象头到线程2的锁记录空间中，但是在线程2CAS的时候，发现线程1已经把对象头换了，线程2CAS失败，那么线程2就会尝试使用自旋锁来等待线程1释放锁。
自适应自旋有次数限制，如果达到自旋次数后线程1仍未释放锁，这个时候轻量级锁就会膨胀为重量级锁。
重量级锁把除了拥有锁的线程都阻塞，避免CPU空转。
作用：
1、保证数据可见性：被volatile修饰的变量每次修改后立即同步到主存；每次使用时从主存刷新。
2、禁止指令重排序：例如i++指令，i没有被volatile修饰时会进行指令重排序。
底层实现：
lock前缀指令，即内存屏障。它提供三个功能：
1、确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面。
2、强制将对缓存的修改立即同步写入到主存。
3、如果是写操作，导致其它CPU中对应的缓存行无效。
可修饰变量、方法和类
修饰变量：基本类型则无法修改值；引用类型则无法指向其它对象。 修饰方法：方法无法被重写。 修饰类：类无法被继承。
API层面提供的可重入锁。底层基于AQS，通过循环调用CAS来实现加锁，避免使线程进入内核态的阻塞状态。有公平和非公平两种模式，默认为非公平。
与synchronized区别：
1、底层实现：synchronized是关键字，JVM层面实现的锁；ReentrantLock是JUC包下的一个类，API层面的锁。
2、实现原理：synchronized的实现涉及到锁的升级过程，具体为无锁、偏向锁、轻量级锁、重量级锁；ReentrantLock是通过CAS自旋+volatile变量来实现锁的功能。
3、是否可手动释放：synchronized由系统自动释放；ReentrantLock需用户手动调用unlock释放锁。
4、是否可中断：synchronized不可中断，除非加锁的代码中出现异常或正常执行完成；ReentrantLock则可以中断，可通过tryLock设置超时时间或者将lockInterruptibly方法放到代码块中，调用interrupted方法进行中断。
5、是否公平锁：synchronized为非公平锁；ReentrantLock默认为非公平锁，可通过构造方法指定为公平锁。公平锁模式下每个线程均需排队，性能较低。
AbstractQueuedSynchronizer：抽象同步队列管理器
多个线程遵循FIFO先进先出原则，后来的线程即使锁空闲，也要先检查有没有其它线程在等待，如果有自己要挂起，进入队尾进行排队等待，然后唤醒队列最前面的线程。
优点：所有线程都能得到资源，不会饿死在队列中，适合大任务。
缺点：吞吐量下降，队列中除第一个线程外，其余线程均会阻塞，CPU唤醒阻塞线程开销大。
多个线程获取锁时，每个线程都会先直接尝试获取锁，如果获取不到，再进入等待队列，如果能获取到，就直接获取到锁。
优点：减少了CPU需要唤醒的阻塞线程的数量，整体的吞吐量会高点。
缺点：可能导致队列中的线程长时间获取不到锁的情况。
ReentrantReadWriteLock：读写锁。读操作加读锁，可并发读；写操作加写锁，只能单线程写。
线程本地变量。内部维护了一个ThreadLocalMap，Map中的Entry的key是ThreadLocal类对象，它是一个WeakReference弱引用，value是需要设置的变量，为强引用。该Map采用开放地址法解决哈希冲突问题。
由于Entry是一个弱引用，如果ThreadLocal没有被外部强引用，下次垃圾回收时必然被清理掉，会导致ThreadLocalMap中使用这个ThreadLocal的key被清理掉，但是value是强引用，不会被清理，导致value永远无法被访问到，从而产生内存泄漏。所以每次使用完ThreadLocal必须手动调用remove()方法。
并发工具包基于AQS。
通过计数法让多个线程并行执行，每个线程执行完任务后让闭锁减一，主线程阻塞等待所有线程都执行完后进行结果的汇总。
让一组线程到达一个同步点时被阻塞，直到所有线程都到达时，栅栏会被打开，所有线程同时执行。
维护许可证的数量，每个线程进入时消耗一个许可证，使用完成后再归还许可证。一般用来做限流。
- 程序计数器：线程私有，记录当前线程正在执行的虚拟机字节码的地址。
- 虚拟机栈：每一个方法的执行都对应着一个栈帧在虚拟机栈中入栈和出栈的过程。栈帧用于存储局部变量表、操作数栈、动态链接和方法出口等信息。局部变量表中存储了基本数据类型和对象句柄。
- 本地方法栈：执行本地 native 方法时的栈，作用和虚拟机栈类似。
- 堆：通过 new 关键字创建的对象都在堆中。堆内存线程共享，需要考虑线程安全问题，有自动垃圾回收机制。开启逃逸分析后，某些未逃逸的对象可以通过标量替换的方式在栈上分配。细分：新生代和老年代，新生代又细分为 eden 区和两个 surviver 幸存区。
- 方法区：存储 JVM 已加载的 Class 类信息、常量和静态变量等；Java8 之前由永久代实现（堆内存）；Java8 后使用元空间替代永久代（本地内存）。
- 运行时常量池：方法区的一部分。存放字面量和符号引用。
- 直接内存：堆外内存。可通过 Unsafe 和 NIO 下的 DirectByteBuffer 直接进行操作。
堆内存细分为新生代和老年代，其中新生代又细分为伊甸园区和两个幸存区。每个线程在伊甸园区有一个预先分配的缓冲区，称为 Thread Local Allocation Buffer（TLAB）。
- 开启了逃逸分析后，局部变量直接栈上分配。
- 对象优先分配在伊甸园区（优先 TLAB 缓冲区），如果伊甸园区内存不足，触发一次 MinorGC，称为 Young GC。采用可达性分析，标记存活对象，复制所有存活的对象到一个空白的幸存区。
- 大对象直接进入老年代（超过 -XX:PretenureSizeThreshold 参数设置的阈值称为大对象）。避免在伊甸园区和两个幸存区之间发生大量的内存拷贝。
- 长期存活的对象进入老年代。每次 Young GC 之后存活的对象年龄加一，当达到阈值（默认 15 次）后，进入老年代。
- 每次进行 Young GC 或者大对象直接进入老年代时，虚拟机会计算所需空间大小如小于老年代的剩余值大小，则进行一次 Full GC。
动态对象年龄判定：程序从年龄最小的对象开始累加，如果累加的对象大小大于幸存区的一半，则将当前的对象年龄作为新的阈值，年龄大于此阈值的对象直接进入老年代。
类加载检查、分配内存、初始化零值、设置对象头和执行 init 方法。
- 类加载检查：虚拟机遇到 new 指令时，首先去检查常量池中是否存在该类的符号引用，并检查该符号引用代表的类是否已被加载、解析和初始化过。如果没有，则先执行相应的类加载过程。
- 分配内存：通过类加载检查后，虚拟机开始为新对象分配内存，分配方式有“指针碰撞”和“空闲列表”两种，选择哪种分配方式由 Java 堆是否规整决定，而 Java 堆是否规整又由所采用的垃圾收集器是否具有内存压缩整理功能决定。
- 初始化零值：内存分配完成后，虚拟机将分配到的内存空间都初始化为零值。这个操作保证了对象的实例字段在 Java 代码中不赋初始值就能直接使用。
- 设置对象头：设置对象头 Mark Word，包含哈希码 hashCode、GC 分代年龄、锁状态标志和偏向线程 ID 等信息。
- 执行 init 方法：即调用构造函数。
分为强软弱虚四种。
- 强引用：普通等于号赋值的引用关系就是强引用。
- 软引用：SoftReference，当堆内存不足时，系统才会回收软引用对象，如果回收后内存仍不足，则抛出内存溢出异常。
- 弱引用：WeakReference，只能存活到下一次垃圾回收之前。
- 虚引用：PhantomReference，跟踪对象被垃圾回收的活动。
加载、验证、准备、解析和初始化。
- 加载：通过类的全限定类名获取类的二进制字节流，将字节流中的静态结构存放在方法区，在堆中创建对应的 Class 类对象，作为方法区这些数据的访问入口。
- 验证：文件格式验证、元数据验证、字节码验证和符号引用验证。
- 准备：赋零值。
- 解析：将常量池内的符号引用替换为直接引用。
- 初始化：执行构造函数。
将 GC Roots 对象作为起始点，向下进行引用搜索，搜索走过的路径称为引用链，引用链上没有的对象被判定为不可达，需要进行回收。
GC Roots 主要包含全局性的引用（常量或类静态属性）和执行上下文（栈帧中的局部变量表）：
- 虚拟机栈的栈帧中的局部变量表引用的对象。
- 方法区中类静态属性引用的对象。
- 方法区中常量引用的对象。
- 本地方法栈中 JNI（native 方法）引用的对象。
标记阶段标记出所有需要回收的对象；回收阶段直接回收被标记的对象。
缺点：产生内存碎片。
新生代采用的回收算法。将内存划分为两块区域，每次只使用其中一块，当这块内存用完后，标记存活对象并复制到另一块上，然后将原来的那块一次性清理。
由于大部分对象都是“朝生夕死”的，现代虚拟机一般将新生代分为一个伊甸园（eden）区和两个幸存（survivor）区，大小比例为 8:1:1。
优点：不易产生内存碎片。 缺点：每次都有 10% 的幸存区被浪费。
标记阶段标记出所有需要回收的对象；整理阶段让所有存活对象往一端进行移动，然后清理掉端边界以外的内存。
能让程序长时间执行的指令：方法调用、循环跳转和异常跳转等。
一段引用关系不会发生变化的代码片段。可称为安全区域。
标记 - 复制算法，单线程收集。Stop The World 无法避免。
Serial 收集器的多线程版本。
吞吐量优先收集器。提供以下两个参数控制吞吐量：
- -XX:MaxGCPauseMillis：最大垃圾回收停顿时间；
- -XX:GCTimeRatio：垃圾回收时间与总时间占比。
Serial 收集器的老年代版本。标记 - 整理算法，单线程收集。Stop The World 无法避免。
Parallel Scavenge 收集器的老年代版本。
基于标记 - 清除算法，分为四个阶段：
- 初始标记（CMS initial mark）：扫描 GC Roots 往下的第一层对象，需要 Stop The World。
- 并发标记（CMS concurrent mark）：与用户线程并发，从第一层对象往下扫描 GC Roots 的引用链。没有 Stop The World。
- 重新标记（CMS remark）：修正并发标记期间，因用户线程继续运作导致标记发生变动的那一部分对象的标记记录（增量更新）。需要 Stop The World。
- 并发清除：与用户线程并发，清除 GC Roots 不可达的对象。
并发标记阶段如果老年代内存无法满足用户线程需要，会出现 Concurrent Mode Failure 失败，虚拟机临时采用 Serial Old 收集器回收老年代。
针对标记 - 清除算法产生内存碎片的问题。CMS 收集器提供参数 -XX:CMSFullGCsBeforeCompaction 用来设置执行多少次不压缩的 Full GC 后进行内存整理。默认值为 0，即每次都进行内存碎片整理。
化整为零，将堆划分为大小相等，内存连续的 Region 区，每个 Region 对应 Eden、Survivor、Old、Humongous 四种角色之一。
Humongous 区：简称 H 区，专门用于存放超大对象的区域，通常 >= 1/2 Region Size。只有 Full GC 才会回收 H 区。
为了提高扫描根对象和标记的效率，G1 使用了两个新的辅助存储结构：
- Remembered Sets：简称 RSets，记录每个 Region 中的对象的引用来源（“谁引用了我”）。
- Collection Sets：简称 CSets，记录等待回收的 Region 集合。
回收过程：
- 初始标记：扫描 GC Roots 往下的第一层对象，需要 Stop The World。
- 并发标记：与用户线程并发，从第一层对象往下扫描 GC Roots 的引用链。没有 Stop The World。
- 最终标记：修正并发标记期间因用户线程继续运作而导致标记产生变动的那一部分标记记录，虚拟机将这段时间对象变化记录在线程 Remember Set Logs 中，最终标记阶段将 logs 中的数据合并至 RSets。
- 筛选回收：对各个 Region 的回收价值和成本进行排序，根据用户期望的停顿时间来制定回收计划，可只回收一部分 Region。
- 动态调整大小的 Region
- 不分代：没有 RSets，每次并发对所有 Region 回收
- 带颜色的指针：加快标记过程
- 读屏障：无 Stop The World，仅需要修改指针颜。
- 重定位：减少对 Region 的整理
- 多重映射
- 支持 NUMA 架构：申请内存时根据当前线程被哪个 cpu 核心执行，就近申请该 cpu 能使用的内存。
- 首先是内存大小问题，为每一个内存区域设置一个上限避免内存溢出。
- 通常，堆大小设置为操作系统的 2/3，超过 8G 的堆，优先选择 G1 收集器。
- 然后对 JVM 进行初步优化，根据老年代空间使用率的提升速度，调整老年代和新生代之间的比例。
- 根据系统容量、访问延迟、吞吐量等进行专项优化。
- 查看详细的 GC 日志，分析找到瓶颈点。
5种基础类型：字符串（String）、列表（List）、哈希（Hash）、集合（Set）、有序集合（ZSet）。6个数据结构：简单动态字符串（SDS）、链表（双向无环）、字典、跳表、整数集合、压缩列表。
一般用来统计页面的UV（Unique Visitor）独立访客数。
UV重要的是去重，保证同一个电脑终端一天之内的多次访问请求只被计数一次。这就要求每一个网页请求都要带上用户的ID，无论是登录用户还是未登录用户都需要一个唯一ID来标识。
如果我们简单的使用集合来记录UV，那当一个爆款页面独立访问量非常大时，集合是非常浪费空间的。为了一个去重功能耗费非常多的存储空间是完全没有必要的。
Redis中提供的HyperLogLog结构就是用来解决这种去重统计问题的，它提供了一种不精确的去重计数方案，这种不精确的标准误差是0.81%。
位图。内部可以理解成一个bit数组，通过一个bit位来标识某个元素对应的值或状态。
使用场景：
- 记录用户签到
- 统计活跃用户
- 记录用户在线状态
GeoHash，地理位置距离排序算法。可用来实现查找附近的人类似功能。
新的强大的支持多播的可持久化的消息队列。Redis 5.0版本新增的一种数据结构。
跳表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。
在做范围查询时，平衡树比跳表操作要复杂，元素插入后可能还要做一些rebalance的操作。
全局Hash表用来保存Redis中所有的K-V。当发生哈希冲突时，使用链地址法解决哈希冲突。
当满足以下任意一个条件时，触发扩容。
1、服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
2、服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
使用两个Hash表实现渐进式rehash。避免一次性rehash造成阻塞。
redis的字典持有两个哈希表引用，分别为ht[0]和ht[1]，通常情况下redis只会使用其中一个哈希表ht[0]，当发生扩容时，redis会将哈希表ht[0]中的键值对分多次、渐进式的rehash到ht[1]中。
rehash步骤如下：
1、首先在字典中维护一个索引计数器变量rehashidx，初始化为0，表示rehash开始。
2、每次对字典执行crud时，redis除了执行指定的命令外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，然后将rehashidx加一。
3、随着系统不断运行，最终会在某个时间点，ht[0]上的数据全部被rehash到ht[1]上，这时将rehashidx的值设置为-1，表示rehash结束。
一个线程处理多个IO流，Linux系统使用select和epoll实现；还有基于FreeBSD的kqueue实现；以及基于Solaris的evport实现。
AOF：写后日志。记录Redis执行的每一条命令。
RDB：快照数据。一次性记录内存全量数据。Redis提供了同步save命令和异步bgsave命令执行全量快照。
1、Redis中事务执行失败只有两个原因：命令错误和操作了不正确的键。这两原因开发过程就可以避免。
2、事务回滚会带来额外复杂度，并且收益不高。
appendfsync配置项有三个可选值：
1、Always：同步写，每次执行完命令同步写AOF文件。
2、Everysec：每秒写，每次执行完命令，将命令写到缓冲区，每间隔一秒同步缓冲区内容到磁盘AOF文件。
3、No：交给操作系统控制，每次执行完命令，只将命令写到缓冲区，有操作系统决定何时将缓存区内容同步到磁盘。
如何做选择？
- 同步写可以做到基本不丢数据，但每次执行命令都有一个同步落盘操作，影响性能。
- 由操作系统控制何时写磁盘，一旦宕机数据可能会严重丢失。
- 每秒写回使用缓冲区，避免同步落盘的性能开销，但是如果发生宕机，上一秒内未落盘的数据会丢失，属于一个折中方案。
总结：想要高性能选择No；想要高可靠性保证选择Always；允许数据丢失一秒且性能还适中选择Everyesc。
AOF文件采用追加写的方式记录每次执行的命令，随着命令越来越多，AOF文件会越来越大，此时会进行AOF重写。
AOF重写的实现方式一般是基于数据库的现状创建一个新的AOF文件，即读取全局哈希表得到所有的KV，再对每一个KV使用写命令写入AOF文件。
重写过程由异步线程bgrewrireaof执行，每次重写时会拷贝一份主线程的全量内存。此时主线程并未阻塞，新的写命令会同时记录到AOF缓冲区和AOF重写缓冲区。
RDB快照日志。
1、从库与主库之间建立连接，从库发送命令psync ? -1告知主库即将进行同步，主库接收命令后返回FULLRESYNC {runID} {offset}给从库。
2、主库执行bgsave命令生成RDB快照文件发送给从库，从库收到RDB文件后清空数据库加载RDB文件。
3、主库发送RDB文件过程中会用replication buffer缓冲区保存后续到来的写命令，RDB文件发送完成后会将缓冲区内的命令发送给从库。
主从：一主一从。 主从从：一主多从。
多个从节点并非都和主节点进行数据同步，部分从节点会挂在已经完成同步的从节点上，减少主节点fork线程执行bgsave的压力。
不可写，如果可写会造成主库数据不一致。
主从同步未完成，主库宕机。
单机很难撑住十万，需要集群。
网络IO耗时
Redis官方提供的分片集群方案。去中心化。将Redis分为16384个哈希槽，集群中的每个节点负责一部分槽位，槽位的信息存储于每个节点中。当需要操作一个key时，对key使用crc16算法进行哈希得到一个整数值，然后用这个整数值对16384取模得到具体槽位，如果槽位不在当前节点，则会返回携带槽位真实所在节点地址的MOVED指令告诉客户端进行跳转。
- 如果槽位为
65536，发送心跳信息的消息头达8k，发送的心跳包过于庞大，浪费带宽。 Redis集群主节点数量基本不可能超过1000个，集群节点越多，心跳包的消息体内携带的数据也越多，同样会造成网络拥堵。1000个节点以内的集群，16384个槽位够用了。- 槽位数越小，节点少的情况下，存储哈希槽信息的
bitmap压缩率高。
因为Redis Cluster是去中心化的，如果集群中一个节点认为某个节点失联了，那我们称为可能下线，它会使用Gossip协议将这个失联信息向整个集群进行广播，如果集群中超过半数的节点都认为指定节点失联，那就将该节点标记为确定下线状态，然后再次向整个集群广播，强迫其它节点接受该节点下线的事实，并立即对该失联节点进行主从切换。
普通的哈希取模算法如果要新增或者下线一台服务器，需要对集群中的所有key进行rehash重新映射，非常耗时。
在一致性哈希算法中，首先想象有一个具有2^32个位置的哈希环，集群中的每一台机器，根据机器ip进行哈希取模运算，映射到环中相应位置。当要设置一个key时，对key也进行哈希取模运算得到环中位置，然后沿顺时针方向寻找到的第一台机器即为该key所在节点。
当要添加或删除机器时，部分数据会重新分配，如果其中包含热点数据，则很容易将下一个节点打挂，并且会沿顺时针方向循环扩散，导致所有机器节点循环崩溃。
如果集群机器数量过少，很容易出现数据倾斜问题，导致集群内机器负载不均衡。
为了解决循环崩溃和数据倾斜问题，一致性哈希引入虚拟节点的概念，将真实机器节点经过多个哈希函数运算得到多个哈希环位置。
- 哈希槽不闭合，它一共有
16384个槽位，使用CRC16算法计算key的哈希值，然后与16384取模确定槽的位置，从而找到所属的Redis节点；而一致性哈希表示一个0到2^32的圆环，对key进行哈希运算后与2^32取模得到其在环中的位置，然后沿顺时针方向寻找到的第一个节点为其应在的节点。 - 一致性哈希通过虚拟节点的方式避免循环崩溃和数据倾斜等问题；而哈希槽集群中每个节点使用主从模式，主节点提供读写服务，从节点进行数据同步备份，当主节点挂掉时，主从切换提供服务。
Codis Proxy代理集群。默认分为1024个槽位，使用zk或etcd等中间件存储槽位映射关系。
分片集群 + 主从 + 哨兵
部署哨兵节点集群，负责监控主从节点的健康，当主节点挂掉后，自动选择一个最优从节点进行主从切换。客户端来连接集群时，首先会连接哨兵节点，通过哨兵节点查询到主节点的地址，然后再去和主节点进行数据交互，如果主节点发生故障，客户端会重新找哨兵节点查询最新主节点地址。
默认情况下，哨兵节点会和主从服务器间基于pub/sub机制维持心跳检测，如果一个哨兵节点在指定时间内没有收到某个主节点的心跳回复，则标记该主节点进入主观下线状态。
然后该哨兵节点询问哨兵集群中的其它节点，是否该主节点已进入主观下线状态，如果超过半数的哨兵判定主节点进入主观下线状态，那么该哨兵节点就会将该主节点标记为客观下线状态。
当一个主节点被标记为客观下线后，哨兵集群会进行通过Raft算法进行leader选举，选出一个leader哨兵来对该主节点进行故障转移。
故障转移过程：
- 在已客观下线节点的从节点中选出一个从节点，将其升级为主节点。
- 让其它从节点改为复制新的主节点。
- 将下线的主节点设置为新主节点的从节点，当下线的主服务器重新上线时会成为新的主节点的从节点。
Raft协议是用来解决分布式系统一致性问题的协议。 Raft协议描述的节点共有三种状态:Leader, Follower, Candidate。 Raft协议将时间切分为一个个的Term(任期)，可以认为是一种“逻辑时间”。 选举流程: ①Raft采用心跳机制触发Leader选举系统启动后，全部节点初始化为Follower，term为0
②节点如果收到了 RequestVote 或者 AppendEntries，就会保持自己的 Follower 身份
③节点如果一段时间内没收到 AppendEntries 消息，在该节点的超时时间内还没发现 Leader，Follower 就会转换成 Candidate，自己开始竞选 Leader。一旦转化为 Candidate，该节点立即开始下面几件事情: --增加自己的 term，启动一个新的定时器 --给自己投一票，向所有其他节点发送 RequestVote，并等待其他节点的回复。
④如果在计时器超时前，节点收到多数节点的同意投票，就转换成 Leader。同时通过 AppendEntries，向其他节点发送通知。
⑤每个节点在一个 term 内只能投一票，采取先到先得的策略，Candidate 投自己，Follower 会投给第一个收到 RequestVote 的节点。
⑥Raft 协议的定时器采取随机超时时间（选举的关键），先转为 Candidate 的节点会先发起投票，从而获得多数票。
leader哨兵节点会将已下线主节点的所有从节点保存到一个列表里面，然后按照以下筛选条件进行筛选过滤：
- 删除列表中所有处于下线或者断线状态的从节点，保证剩余从节点都是正常的。
- 删除列表中最近五秒内没有回复过
leader哨兵节点的INFO命令的从节点，保证剩余从节点都是最近成功进行过通信的。 - 删除所有与已下线主节点连接断开超过
down-after-milliseconds * 10毫秒的从节点，保证剩余从节点中数据都是比较新的。（down-after-milliseconds配置项指定了判断主节点下线所需要的时间）
单个key在缓存过期的一瞬间，大量请求到来，瞬间对下游造成过大压力。
解决方案：
- 对于变化频率较高的
key，使用定时任务定时刷新。 - 对于变化频率很低的
key，设置为永不过期。 - 对于变化频率一般的
key，使用互斥锁让一个线程去加载缓存，其余线程阻塞等待。
多个key同时过期的瞬间，大量请求到来，瞬时压力过大。
对过期时间进行随机打散。
使用不存在的key进行查询，绕过缓存，打到下游。
解决方案：
- 对不存在的
key缓存null值。 - 布隆过滤器。
有一个bit数组，数组中每个元素初始化为0。初始化布隆过滤器时需将所有已存在的key进行初始化，对每一个key，都需要经过n个哈希函数的运算，然后对bit数组长度取模得到n个数组下标，将这n个数组下标对应的值改为1就表示放入了一个key。当要判断某个key是否存在于布隆过滤器中时，对key进行同样的n个哈希函数运算并对数组长度取模得到n个数组下标，只要有一个数组下标不为1，就可以断定该key不存在；如果全部都为1，那该key可能在布隆过滤器中也可能不在，有一个误判率，误判率和已添加元素数量、bit数组长度和哈希函数数量均有关。
分布式锁基本条件：
- 不同的
JVM均可见 - 能保证互斥
实现方式：
- 基于文件
- 基于
MySQL数据库行锁 - 基于
Redis的setnx expire原子命令 - 基于
Redisson框架 - 基于
Zookeeper临时节点 - 基于
etcd的事务、租约及watch监听
LUA脚本，hash结构实现可重入，看门狗机制延长超时时间。
多个命令同时执行，中间某个命令失败不会影响其它命令的执行。可以理解为命令的批量执行，它不同于数据库的事务。
某些key访问频率非常低甚至只访问一次，但过期时间又很长，导致缓存空间被浪费，这种情况称为缓存污染。
noevictionvolatile-randomvolatile-ttlvolatile-lruvolatile-lfuallkeys-lruallkeys-lfuallkeys-random
Redis默认会记录每个数据的最近一次访问的时间戳（由键值对RedisObject中的lru字段记录）。然后，Redis在决定淘汰的数据时，第一次会随机选出N个数据，把它们作为一个候选集合。接下来，Redis会比较这N个数据的lru字段，把lru字段值最小的数据从缓存中淘汰出去。
- 如果业务中有明显的冷热数据区分，建议优先选择
allkeys-lru策略。 - 如果业务中数据访问频率相差不大，没有明显的冷热数据区分，建议使用
allkeys-random策略。 - 如果业务中有置顶的需求，比如置顶新闻、置顶视频等，可以使用
volatile-lru策略，同时给这些置顶数据设置为永不过期。这样一来，这些需要置顶的数据不会被删除，而其它数据会进行lru淘汰。
- 定期删除，定时随机检查一批
key，删除其中已经过期的。如果过期的key数量超过一定比例则继续随机。最长持续25ms，所以要避免大量key同时过期造成卡顿。为了平衡CPU和内存的开销，和JVM的G1收集器思想有点类似，对局部Region进行回收，平衡STW停顿时间。 - 惰性删除，访问时过期则删除。如果开启了持久化，
RDB加载时会忽略已过期的key，AOF重写时会忽略已过期的key。主从模式下，从服务器只会等待主服务器同步删除命令。
-
延时双删：先删除缓存，后更新
DB，休眠一会，再次删除缓存。 -
缓存旁路模式：先更新
DB，后删除缓存。
问题：
删除失败：用MQ，更新DB后发送MQ消息，利用MQ的重试机制。
主从延迟：如果发生了较严重的主从延迟，删除缓存后有请求读到了从库中的旧数据刷到缓存就会产生脏数据。需要保证更新DB到删除缓存时间间隔大于主从同步时间间隔。
- top 命令查看占用 CPU 最多的进程 PID
top -Hp ${PID}命令查看进程中占用 CPU 最多的线程 TID。- 或者用命令
ps H -eo pid,tid,%cpu | grep ${PID}查看占用 CPU 最多的线程 TID。 - 将线程 TID 转十六进制，可用命令
printf %x ${TID}转换。 - 用 jstack 工具查看进程堆栈快照。命令
jstack ${PID}。 - 在进程堆栈快照中寻找 nid 等于线程 TID 十六进制的线程，从而定位问题。
首先红黑树和AVL树都是常用的平衡二叉搜索树，它们的插入、删除和查找的时间复杂度都是O(logN)。
但是，两者之间有以下几点比较：
AVL树更加严格平衡，因此可以提供更快的查找效率。对于查找密集型任务，使用AVL树。- 红黑树更适用于插入修改密集型任务。
- 通常，
AVL树的旋转比红黑树的旋转更加难以平衡和调试。
- 范围查询时，红黑树等平衡二叉树操作比跳表操作要复杂。在平衡树上，找到指定范围的小值后，还要以中序遍历的顺序继续寻找其它不超过范围大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而跳表在进行范围查询时就非常简单，只需要找到小值后，对第一层链表进行若干步的遍历即可。
- 平衡树的插入和删除可能需要对子树进行平衡调整，逻辑复杂。而跳表的插入和删除只需要修改相邻节点的指针，逻辑简单易实现。
- 算法实现难度上来说，跳表实现比平衡树要简单。
B+树磁盘读写代价更低，只有叶子节点存储数据，其余节点用来做索引。B+树带有顺序访问指针，每个叶子节点之间有指针相连，形成了一个链表，便于进行区间访问。B+树查询效率更稳定，由于只有叶子节点存储数据，任何查询都必须经过一条从根节点到叶子节点的路径，所有查询的路径长度相同，查询效率相当。如果是其它的树，例如B树，它的非叶子节点也存储数据，很可能在非叶子节点中获取到数据后就返回了，查询效率不稳定。
- 数据指标底层是记录在团长维度的，数仓很难按任意关系维度进行聚合。查询离线数据时，用
MySQL中实时的关系去查询离线的数据，数据会有问题。
方案一：告诉数仓同事业务表字段含义，让他们去理解业务表结构，然后join业务表按不同的维度进行聚合。
方案二：维护一张打平的维度关系表，记录每个团长的各个维度。提供接口给实时数据实时查询；产出离线hive表给离线数据join维度。
最终选择方案二。
写2个缓存，key1和key2，key1过期时间设置较短保证一定的准实时性，key2过期时间设置较长，如果key1过期请求到下游接口被限流，则读key2中上一次的正常数据。