五月14

算法：
239. 滑动窗口最大值
思路：滑动窗口+双端队列。队列用于维护最大值，入队时判断当前值与队尾元素的大小，当前值大于队尾元素则移除队尾元素,再加入当前元素，否则直接加入当前元素。当达到窗口大小时，将队头元素移除。同时将队头元素加入答案

for (int i =0; i < n; i ++) {
    while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) q.removeLast();
    q.addLast();

    if (i-q.getFirst() >= k) q.removeFirst();
    // 达到长度后 一直记录。
    if (i>=k-1) ans[i-k+1] = nums[q.getFirst()];
}

155. 最小栈
     思路：使用两个栈实现，一个栈用于实现基础的push、pop；另一个栈用于记录最小值，最小值维护在栈顶，添加、移除时进行判断即可。

156. 最大二叉树
     思路：常见的构建模板：build(nums, 0, n-1); 在方法内部查找当前区间的最大值，最大值即为根节点，递归处理左侧与右侧

TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;

    int index = 0;
    int max = Integer.MIN_VALUE;
    for (int i = lo; i < hi; i ++) {
        max = Math.max(max,nums[i]);
        index = i;
    }

    TreeNode root = new TreeNode(max);
    root.left = build(nums, left, index-1);
    root.right = build(nums, index+1, right);

    return root;
}

从中序、前序、后序遍历二叉树
思路：先处理节点映射。使用build模板，记使用的数组为a1、a2；build(a1,0,a1.length,a2,0,a2.length)；内部实现思路(与中序遍历相关的)：使用中序遍历记录根节点

TreeNode build() {
    if (a1Start );

    获取根节点
    获取根节点对应的下标
    获取根节点左侧的节点数，用于构建左右子树
    构建根节点
    构建左子树
    构建右子树
}

八股：
并发工具类 Semophore CountDownLatch Exchanger CyclicBarrier Phaser
Semaphore 与操作系统中的信号量概念一致，用于实现同步问题。默认非公平，主要为 acquire 方法与 release 方法。
acquire 获取资源， release 释放资源。 用于资源有限的情况下，限制资源数量。默认的 acquire 方法会让线程进入等待队列，抛出异常中断。 原理： Semaphore 内部有一个继承了 AQS 的同步器 Sync 重写了 tryAcquireShared 方法，获取失败返回负数，进入等待队列。
场景：读取⼏万个⽂件的数据，因为都是 IO 密集型任务，我们可以启动⼏⼗个线程并发地读取。但是在读到内存后，需要存储到数据库，⽽数据库连接数是有限的，⽐如说只有 10 个，那我们就必须控制线程的数量，保证同时只有 10 个线程在使⽤数据库连接。

Exchanger 用于线程交换数据，支持泛型。当一个线程调用了 exchange 方法后，线程会阻塞，直到另一个线程调用 exchange 方法。使用 park/unpark 来实现等待状态切换，在使用 park/unpark 方法之前，使用了 CAS 检查。Exchanger 类还有一个有超时参数的方法， 超时会抛异常。特性：此类提供对外的操作是同步的；用于成对出现的线程之间交换数据；可以视作双向的同步队列；可应用于基因算法、流水线设计，也可以⽤于校对⼯作等场景。

CountDownLatch 计数递减，适用场景：某个线程在执行任务之前，需要等待其它线程完成一些前置任务，必须等所有的前置任务都完成，才能开始执行本线程的任务。原理：一个继承了 AQS 的实现类 Sync。构造器中的计数值（count）实际上就是闭锁需要等待的线程数量。这个值只能被设置一次，而且 CountDownLatch没有提供任何机制去重新设置这个计数值。
场景题：假如要查10万多条数据，⽤线程池分成20个线程去执⾏，怎么做到等所有的线程都查找完之后，即最后⼀条结果查找结束了，才输出结果？

CyclicBarrirer 循环屏障，优化后的 CountDownLatch， CountDownLatch 的计数器 count 减为零后不可重置， CyclicBarrirer提供了 reset 方法。如果参与者（线程）在等待的过程中，Barrier 被破坏，就会抛出 BrokenBarrierException。可以用isBroken()方法检测 Barrier 是否被破坏。使⽤的时候，我们需要先初始化⼀个 CyclicBarrier 对象，指定⼀个屏障值 N，表示需要等待的线程数量。然后每个线程执⾏ await() ⽅法，表示⾃⼰已经到达屏障，等待其他线程，此时屏障值会减 1。当所有线程都到达屏障后，也就是屏障值为 0 时，所有线程会继续执⾏。CyclicBarrier 内部使用的是 Lock + Condition 实现的等待/通知模式。

Phaser 对动态数量的线程的同步能力。Phaser 是多阶段的，可以同步不同阶段的多个操作。 CyclicBarrier 在构造方法里传入了“任务总量”parties之后，就不能修改这个值了，并且每次调用await()方法也只能消耗一个parties计数。但 Phaser 可以动态地调整任务总量。Phaser 是阶段性的，所以它有一个内部的阶段计数器。每当我们到达一个阶段的结尾时，Phaser 会自动前进到下一个阶段。原理：它内部使用了两个基于 Fork-Join 框架的原子类辅助：

ConcurrentHashMap 实现： 在 JDK1.7 以前，采用分段锁，对 Segment 进行加锁，每个段独立枷锁，Segment 数量有限； JDK 8 采用粒度更加细致的桶锁，对每个 Node 节点使用 CAS + synchronized 进行加锁。对于读操作，ConcurrentHashMap 使用 volatile 实现； 对于写操作， 优先使⽤ CAS 尝试插⼊，如果成功就直接返回；否则使⽤ synchronized 代码块进⾏加锁处理。
JDK 7 中使用分段锁，整个 map 被分为若干个 Segment，每个段独立加锁类似一个 HashTable，每个段维护⼀个键值对数组 HashEntry 类似一个单向链表结构， Segment 继承了 ReentrantLock 每个段都是一个可重入锁，实现并发。put 流程：与HashMap类似，先定位到具体的段，再通过 ReentrantLock 操作，步骤如下：第⼀步，计算 key 的 hash，定位到段，段如果是空就先初始化；第⼆步，使⽤ ReentrantLock 进⾏加锁，如果加锁失败就⾃旋，⾃旋超过次数就阻塞，保证⼀定能获取到锁；第三步，遍历段中的键值对 HashEntry，key 相同直接替换，key 不存在就插⼊。第四步，释放锁。get 流程：先计算 key 的 hash 找到段，再遍历段中的键值对，找到就直接返回 value。
JDK 8 中 ConcurrentHashMap 取消了分段锁，采⽤ CAS + synchronized 来实现更细粒度的桶锁，并且使⽤红⿊树来优化链表以提⾼哈希冲突时的查询效率。 put 流程：第⼀步，计算 key 的 hash，以确定桶在数组中的位置。如果数组为空，采⽤ CAS 的⽅式初始化，以确保只有⼀个线程在初始化数组。第⼆步，如果桶为空，直接 CAS 插⼊节点。如果 CAS 操作失败，会退化为 synchronized 代码块来插⼊节点。插⼊的过程中会判断桶的哈希是否⼩于 0（f.hash >= 0），⼩于 0 说明是红⿊树，⼤于等于 0 说明是链表(，红⿊树节点 TreeBin 的 hash 值固定为 -2。)。第三步，如果链表⻓度超过 8，转换为红⿊树。第四步，在插⼊新节点后，会调⽤ addCount() ⽅法检查是否需要扩容。get 流程：通过 key 的 hash 进⾏定位，如果该位置节点的哈希匹配且键相等，则直接返回值。如果节点的哈希为负数，说明是个特殊节点，⽐如说如树节点或者正在迁移的节点，就调⽤ find ⽅法查找。否则遍历链表查找匹配的键。如果都没找到，返回 null。
项目应用：异步⼯具类 AsyncUtil 中，就使⽤了ConcurrentHashMap 来存储任务的名称和它们的运⾏时间，以便观察和分析任务的执⾏情况。

ConcurrentHashMap 对 HashMap 改进： hash 的计算⽅法上，ConcurrentHashMap 的 spread ⽅法接收⼀个已经计算好的hashCode，然后将这个哈希码的⾼ 16 位与⾃身进⾏异或运算。⽐ HashMap 的 hash 计算多了⼀个 & HASH_BITS 的操作。这⾥的 HASH_BITS 是⼀个常数，值为 0x7fffffff，它确保结果是⼀个⾮负整数；ConcurrentHashMap 对节点 Node 做了进⼀步的封装，⽐如说⽤ Forwarding Node 来表示正在进⾏扩容的节点； put ⽅法，通过 CAS + synchronized 代码块来进⾏并发写⼊。
ConcurrentHashMap 可见性保障：Node 节点中，value 和 next 都是 volatile 的，这样就可以保证对 value 或 next 的更
新会被其他线程⽴即看到。
为什么 ConcurrentHashMap ⽐ Hashtable 效率⾼：Hashtable 在任何时刻只允许⼀个线程访问整个 Map，是通过对整个 Map 加锁来实现线程安全的。⽐如 get 和 put ⽅法，是直接在⽅法上加的 synchronized 关键字。⽽ ConcurrentHashMap 在 JDK 8 中是采⽤ CAS + synchronized 实现的，仅在必要时加锁。

CopyOnWriteArrayList：ArrayList 的线程安全版本，适⽤于读多写少的场景。它的核⼼思想是写操作时创建⼀个新数组，修改后再替换原数组，这样就能够确保读操作⽆锁，从⽽提⾼并发性能。内部使⽤ volatile 变量来修饰数组 array，以读操作的内存可⻅性。写操作的时候使⽤ ReentrantLock 来保证线程安全。
BlockingQueue：JUC 包下的⼀个线程安全队列，⽀持阻塞式的“⽣产者-消费者”模型。当队列容器已满，⽣产者线程会被阻塞，直到消费者线程取⾛元素后为⽌；当队列容器为空时，消费者线程会被阻塞，直⾄队列⾮空时为⽌。
阻塞队列的实现：使⽤ ReentrantLock + Condition 来确保并发安全。

线程池：线程池是⽤来管理和复⽤线程的⼯具，它可以减少线程的创建和销毁开销。ThreadPoolExecutor 是线程池的核⼼实现，它通过核⼼线程数、最⼤线程数、任务队列和拒绝策略来控制线程的创建和执⾏。
应用：异步⼯具类 AsyncUtil，内置了可配置的线程池，基于 ThreadPoolExecutor，适⽤于 IO 密集型任务。其中 corePoolSize 为 CPU 核⼼数的两倍，因为技术派中的⼤多数任务都是 IO 密集型的，maxPoolSize 设置为 50，是⼀个⽐较理想的值，尤其是在本地环境中；阻塞队列为 SynchronousQueue，意味着任务被创建后可以直接提交给等待的线程处理。

线程池工作流程：第一步：线程池通过 submit() 提交任务。第二步：线程池创建核心线程执行任务。第三步：核心线程不足时，放入任务队列。第四步：任务队列已满，线程数量小于最大线程数时，创建新线程执行。第五步：线程数量达到最大线程数，执行拒绝策略。
线程池核心参数：
线程池拒绝策略：AbortPolicy：默认的拒绝策略，会抛 RejectedExecutionException 异常。CallerRunsPolicy：让提交任务的线程⾃⼰来执⾏这个任务，也就是调⽤ execute ⽅法的线程。DiscardOldestPolicy：等待队列会丢弃队列中最⽼的⼀个任务，也就是队列中等待最久的任务，然后尝试重新提交被拒绝的任务。DiscardPolicy：丢弃被拒绝的任务，不做任何处理也不抛出异常。通过实现 RejectedExecutionHandler 接⼝来定义⾃⼰的淘汰策略。

线程池阻塞队列：有界队列 ArrayBlockingQueue，⼀个有界的先进先出的阻塞队列，底层是⼀个数组，适合固定⼤⼩的线程池；⽆界队列 LinkedBlockingQueue，底层是链表，如果不指定⼤⼩，默认⼤⼩是 Integer.MAX_VALUE，⼏乎相当于⼀个⽆界队列；优先级队列 PriorityBlockingQueue，⼀个⽀持优先级排序的⽆界阻塞队列。任务按照其⾃然顺序或 Comparator 来排序；延迟队列 DelayQueue，类似于 PriorityBlockingQueue，由⼆叉堆实现的⽆界优先级阻塞队列；同步队列 SynchronousQueue，每个插⼊操作必须等待另⼀个线程的移除操作，同样，任何⼀个移除操作都必须等待另⼀个线程的插⼊操作。

常见的线程池：
固定⼤⼩的线程池 Executors.newFixedThreadPool(int nThreads)，适合⽤于任务数量确定，且对线程数有
明确要求的场景。例如，IO 密集型任务、数据库连接池等。corePoolSize == maximumPoolSize ，默认使⽤ LinkedBlockingQueue 作为阻塞队列，适⽤于任务量稳定的场景，如数据库连接池、RPC 处理等。使用无界队列，容易导致 OOM。
缓存线程池 Executors.newCachedThreadPool()，适⽤于短时间内任务量波动较⼤的场景。例如，短时间内有⼤量的⽂件处理任务或⽹络请求。corePoolSize = 0 ，maximumPoolSize = Integer.MAX_VALUE 。使⽤ SynchronousQueue 作为阻塞队列，适⽤于短时间内有⼤量任务的场景。线程数没有上限，在⾼并发情况下可能导致 OOM 。
定时任务线程池 Executors.newScheduledThreadPool(int corePoolSize)，适⽤于需要定时执⾏任务的场景。例如，定时发送邮件、定时备份数据等。定时任务线程池的⼤⼩可配置，⽀持定时 & 周期性任务执⾏，使⽤ DelayedWorkQueue 作为阻塞队列，适⽤于周
期性执⾏任务的场景。
单线程线程池 Executors.newSingleThreadExecutor()，适⽤于需要按顺序执⾏任务的场景。例如，⽇志记录、⽂件处理等。线程池只有 1 个线程，保证任务按提交顺序执⾏，使⽤ LinkedBlockingQueue 作为阻塞队列，适⽤于需要按顺序执⾏任务的场景。⽆法并⾏处理任务，线程数没有上限。

线程池提交 execute 和 submit 有什么区别：submit 会有返回值
线程池关闭：shutdown或shutdownnow，shutdownNow 不会真正终⽌正在运⾏的任务，只是给任务线程发送 interrupt 信号，任务是否能、真正终⽌取决于线程是否响应 InterruptedException。
线程池线程数配置：CPU 密集型：CPU+1， IO密集型：2CPU；判断线程数设置：通过 top 命令观察 CPU 的使⽤率，如果 CPU 使⽤率较低，可能是线程数过少；如果 CPU 使⽤率接近 100%，但吞吐量未提升，可能是线程数过多。也可以使⽤ jstack 命令查看线程堆栈信息，查看线程是否处于阻塞状态。
线程池调优：根据任务类型设置核⼼线程数参数，⽐如 IO 密集型任务会设置为 CPU 核⼼数2 的经验值。其次我会结合线程池动态调整的能⼒，在流量波动时通过 setCorePoolSize 平滑扩容，或者直接使⽤ DynamicTp 实现线程池参数的⾃动化调整。最后，我会通过内置的监控指标建⽴容量预警机制。⽐如通过 JMX 监控线程池的运⾏状态，设置阈值，当线程池的任务队列⻓度超过阈值时，触发告警
线程池异常处理：try-catch；future 捕获异常；⾃定义 ThreadPoolExecutor 重写 afterExecute ⽅法；使⽤ UncaughtExceptionHandler 捕获异常。
线程池状态：RUNNING 状态的线程池可以接收新任务，并处理阻塞队列中的任务；SHUTDOWN 状态的线程池不会接收新任务，但会处理阻塞队列中的任务；STOP 状态的线程池不会接收新任务，也不会处理阻塞队列中的任务，并且会尝试中断正在执⾏的任务；TIDYING 状态表示所有任务已经终⽌；TERMINATED 状态表示线程池完全关闭，所有线程销毁。
线程池动态参数修改：线程池提供的 setter ⽅法就可以在运⾏时动态修改参数。利⽤ Nacos 配置中⼼，或者实现⾃定义的线程池，监听参数变化去动态调整参数。
场景：手写线程池和数据库连接池。

线下面+1 感谢信+1(搜狐畅游)