第一模块--并发与多线程

Java多线程方法：

实现Runnable接口，继承thread类，使用线程池

操作系统层面的进程与线程（对JAVA多线程和高并发有了解吗？）

1.进程

定义：进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动, 进程是系统进行资源分配和调度的一个独立单位。

进程的三种基本状态：

1.就绪状态：除CPU外已分配所有资源，等待获得处理机执行
2.执行状态：获得处理机，程序正在执行
3.阻塞状态：因等待而无法执行，放弃处理机，处于等待状态。（等待I/O口完成，申请缓冲区不满足，等待信号等）

2.线程：

线程是进程的一个实体, 是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

3.进程和线程的区别：

进程的内存空间是独立的，有独立的地址空间，不允许突破进程边界的存取其他进程的内存空间；线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈), 但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。Linux的COW技术可以使得子线程只有在对数据段有改变行为的时候才作一个自己的备份。(线程共享同一进程中的内存空间（共享的是进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID）/（并且每个线程拥有自己的栈内存）)
线程的执行速度大于进程。

4. 隶属关系：
线程属于进程，进程退出时结束所有线程，线程占用资源少于进程。

多个执行：

两个进程不能同时执行（准确的说是在单个CPU上不能同时跑两个进程，但多个CPU每个核心可以跑多个进程）
多个线程可以同时执行（所谓的同时指的是concurrent, 采用时间片轮转的方式来给各个线程分配执行时间。）
多线程程序只要有一个线程死掉，整个进程也死掉

5. 线程通信常用的几种方式有:

一般来说因为同一进程下的线程间是共享内存资源，因此共享内存也成为理所应当的线程通信的方式。共享内存常用的数据结构有LRU和FIFO。

具体对JAVA来说，有如下的工具可以实现线程通信:

Object类的wait/notify 方法
Volatile 关键字将线程变量同步到主内存
Sychronized机制
CountDownLatch 、CyclicBarrier 、Semaphore等JUC下的并发工具

A.Wait/notify机制(JAVA特有);

方法wait()的作用是使当前执行代码的线程进行等待，wait()方法只能在同步方法中或同步块中调用，wait()方法执行后，当前线程释放锁，线程与其他线程竞争重新获取锁。方法notify()也要在同步方法或同步块中调用，该方法是用来通知那些可能等待该对象的对象锁的其他线程，对其发出通知notify，并使进入就绪态，等待获取锁。如果有多个线程等待，则有线程规划器随机挑选出一个呈wait状态的线程。在notify()方法后，当前线程不会马上释放该对象锁，要等到执行notify()方法的线程将程序执行完，也就是退出同步代码块中。

B. 共享内存(下面是JAVA实现)：

如果每个线程执行的代码相同，可以使用同一个Runnable对象，这个Runnable对象中有那个共享数据，例如，卖票系统就可以这么做。

如果每个线程执行的代码不同，这时候需要用不同的Runnable对象，例如，设计4个线程。其中两个线程每次对j增加1，另外两个线程对j每次减1，银行存取款

6.进程的通讯方式(本质上是不同进程的线程间通信的方式)：5种

无名管道：

数据只能在一个方向上流动
用于具有亲缘关系的进程之间的通信
特殊的文件，存在于内存

2.命名管道：

可以在无关的进程之间交换数据
文件形式存在于文件系统

write_fifo的作用类似于客户端，可以打开多个客户端向一个服务器发送请求信息，read_fifo类似于服务器，它适时监控着FIFO的读端，当有数据时，读出并进行处理，但是有一个关键的问题是，每一个客户端必须预先知道服务器提供的FIFO接口

3.消息队列：

消息的链表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。
消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
（消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。）

4.信号量：

一个计数器，实现进程间的互斥与同步，而不是用于存储进程间通信数据。
常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。主要作为进程间以及同一进程内不同线程之间的同步手段

5.共享内存：

两个或多个进程共享一个给定的存储区
共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
因为多个进程可以同时操作，所以需要进行同步。
信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

五种进程间通讯方式总结

1.管道：速度慢，容量有限，只有父子进程能通讯。
2.FIFO文件（即命名管道）：任何进程间都能通讯，但速度慢。
3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题；信号传递信息较管道多。
4.信号量：不能传递复杂消息，只能用来同步。
5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。

sleep()方法和wait()方法的区别

线程的资源有不少，但应该包含CPU资源和锁资源这两类。

sleep(long mills)：让出CPU资源，但是不会释放锁资源。Sleep方法退出CPU时间片的竞争，但锁住通往某些数据的操作。

wait()：让出CPU资源和锁资源。

锁是用来线程同步的，sleep(long mills)虽然让出了CPU，但是不会让出锁，其他线程可以利用CPU时间片了，但如果其他线程要获取sleep(long mills)拥有的锁才能执行，则会因为无法获取锁而不能执行，继续等待。

但是那些没有和sleep(long mills)竞争锁的线程，一旦得到CPU时间片即可运行了。

1. 这两个方法来自不同的类, wait是Object类中的方法， sleep是Thread类中的方法。

2. sleep方法没有释放锁(但释放了CPU)，而wait方法释放了锁(也释放了CPU)。

3. wait，notify和notifyAll只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用。

4. sleep必须捕获异常，而wait，notify和notifyAll不需要捕获异常。

线程的状态有几种

Java中的线程的生命周期大体可分为5种状态。

1. 新建(NEW)：新创建了一个线程对象。

2. 就绪态(RUNNABLE)：线程对象创建后，其他线程(比如main线程）调用了该对象的start()方法。该状态的线程位于可运行线程池中，等待被线程调度选中，获取cpu 的使用权。

3. 运行态(RUNNING)：可运行状态(runnable)的线程获得了cpu 时间片（timeslice），执行程序代码。
4. 阻塞态(BLOCKED)：阻塞状态是指线程因为某种原因放弃了cpu 使用权，也即让出了cpu timeslice，暂时停止运行。直到线程进入可运行(runnable)状态，才有机会再次获得cpu timeslice 转到运行(running)状态。阻塞的情况分三种：

(一). 等待阻塞：运行(running)的线程执行o.wait()方法，JVM会把该线程放入等待队列(waitting queue)中。
(二). 同步阻塞：运行(running)的线程在获取对象的同步锁时，若该同步锁被别的线程占用，则JVM会把该线程放入锁池(lock pool)中。
(三). 其他阻塞：运行(running)的线程执行Thread.sleep(long ms)或t.join()方法，或者发出了I/O请求时，JVM会把该线程置为阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入可运行(runnable)状态。

5. 死亡态(DEAD)：线程run()、main() 方法执行结束，或者因异常退出了run()方法，则该线程结束生命周期。死亡的线程不可再次复生

死锁产生的原因及解决方法

死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

注意这里产生死锁的可以是资源竞争，也有可能是彼此的通信等待。

资源竞争: 进程A, B必须同时持有资源1和2才能执行。某一时刻进程A持有资源1并尝试抢占资源2，进程B持有资源2并尝试抢占资源1。这时就造成了死锁。

通信等待: 进程A需要收到B的信号才能继续往下执行(包括向其他进程发信号)，进程B需要收到进程A的信号才能继续往下执行。这个时候进程A和B就会因为相互等待对方的信号而死锁。

死锁产生的四个必要条件

1. 互斥条件：线程对资源的占有是排他性的，一个资源只能被一个线程占有，直到资源被释放。

2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3. 不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4. 环路等待条件：指在发生死锁时，存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。

避免死锁的方法

首先互斥条件一般是无法避免，否则也不会出线多线程的问题了。因此可以从其他三个条件出发，打破其中之一就能避免死锁。

1. 破坏“请求和保持”条件

　　当某个线程申请两个及以上的资源时，让它要么能一次性申请成功所有资源，要么就不申请任何资源(释放申请的部分资源)。

2. 破坏“不可抢占”条件

　　允许进程进行资源抢占。如果线程在持有部分资源的时候这部分资源发生了抢占，则允许这部分资源被抢占。更好的方法是允许操作系统抢占资源，让优先级大的线程可以抢占其他线程占有但未使用的资源。

3. 破坏“循环等待”条件

　　a. 将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序提出。

当多个线程需要相同的一些锁，但是按照不同的顺序加锁，死锁就很容易发生。

如果能确保所有的线程都是按照相同的顺序获得锁，那么死锁就不会发生。

如果一个线程（比如线程3）需要一些锁，那么它必须按照确定的顺序获取锁。它只有获得了从顺序上排在前面的锁之后，才能获取后面的锁。

例如，线程2和线程3只有在获取了锁A之后才能尝试获取锁C (获取锁A是获取锁C的必要条件)。因为线程1已经拥有了锁A，所以线程2和3需要一直等到锁A被释放。然后在它们尝试对B或C加锁之前，必须成功地对A加了锁。

b. 为线程设置加锁时限

　　在尝试获取锁的时候加一个超时时间，在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁，则会进行回退并释放所有已经获得的锁，然后等待一段随机的时间再重试。这段随机的等待时间让其它线程有机会尝试获取相同的这些锁。

4. 死锁检测及处理

　　死锁检测是一个更好的死锁预防机制，它主要是针对那些不可能实现按序加锁、不可设置锁超时、资源不可抢占、破坏请求保持条件的时间效率不高(如果一次性申请到所有的资源的可能性不大，则会出现频繁的资源申请、资源释放操作)。

死锁检测的方法

主要需要为所有的线程及资源建立一个资源分配图，根据资源分配图，如过资源分配图没有环，则系统没有发生死锁。(判断图是否成环使用拓扑排序算法)

检测到死锁了怎么办:

1. 一个可行的做法是释放所有锁，回退，并且等待一段随机的时间后重试虽然有回退和等待，但是如果有大量的线程竞争同一批锁，它们还是会重复地死锁（原因同超时类似，不能从根本上减轻竞争）。

2. 一个更好的方案是随机选取若干个线程而不是全部线程，让这些线程回退，剩下的线程就像没发生死锁一样继续保持着它们需要的锁。

竞态条件 & 临界区

当两个线程竞争同一资源时，如果对资源的访问顺序敏感，就称存在竞态条件。导致竞态条件发生的代码区称作临界区。在临界区中使用适当的同步就可以避免竞态条件。

如何开启一个新线程

继承Thread, 实现Runnable, 实现Callable(使用线程池， ExecutorService)

说一下线程池

A. 使用线程池的原因

- 利用线程池管理并复用线程、控制最大并发数等，节约资源，频繁的创建销毁线程对系统产生很大的压力。
- 实现任务线程队列缓存策略和拒绝机制。
- 实现某些与时间相关的功能，如定时执行、周期执行等。
- 隔离线程环境。比如，交易服务和搜索服务在同一台服务器上，分别开启两个线程池，交易线程的资源消耗明显要大；因此，通过配置独立的线程池，将较慢的交易服务与搜索服务隔离开，避免各服务线程相互影响。

B. 创建线程池需要使用 ThreadPoolExecutor 类

该类的几个核心的参数有:

corePoolSize: 表示常驻核心线程数。如果等于0，则任务执行完之后，没有任何请求进入时销毁线程池的线程；如果大于0，即使本地任务执行完毕，核心线程也不会被销毁。这个值的设置非常关键，设置过大会浪费资源，设置过小会导致线程频繁地创建或销毁。（初始化的时候线程池中并不是直接创建corePoolSize个线程，而是根据需要来创建。只不过在事务完成后向线程池交还线程的时候，如果线程池中线程的数量<=coolPoolSize，则空闲的线程不会被消除，而是常驻在线程池中等待被取用。）

maximumPoolSize: 表示线程池能够容纳同时执行的最大线程数。必须大于或等于1。如果待执行的线程数大于此值，需要借助workQueue参数的帮助，缓存在队列中。如果maximumPoolSize与corePoolSize相等，即是固定大小线程池。

keepAliveTime: 表示线程池中的线程空闲时间，当空闲时间达到keepAliveTime值时，线程会被销毁，直到只剩下corePoolSize个线程为止，避免浪费内存和句柄资源。在默认情况下，当线程池的线程数大于corePoolSize时，keepAliveTime 才会起作用。但是当ThreadPoolExecutor的allowCore Thread TimeOut变量设置为true时，核心线程超时后也会被回收。

TimeUnit: 表示时间单位。keepAliveTime的时间单位通常是TimeUnit.SECONDS。

workQueue: 表示缓存队列。当请求的线程数大于corePoolSize时，线程进入BlockingQee阻塞队列。后续示例代码中使用的LinkedBlockingQueue是单向链表，使用锁来控制入队和出队的原子性，两个锁分别控制元素的添加和获取，是一个生产消费模型队列。

threadFactory表示线程工厂。它用来生产一组相同任务的线程。线程池的命名是通过给这个ctoy增加组名前级来实现的。在虚拟机栈分析时，就可以知道线程任务是由哪个线程工厂产生的。

handler:表示执行拒绝策路的对象。当workQueue参数的任务缓有区到达上限后，并且活动线程数大于maximumPoolSize的时候，线程池通过该策略处理请求，这是一种简单的限流保护。

handler：表示当拒绝处理任务时的策略，有以下四种取值：

ThreadPoolExecutor.AbortPolicy:丢弃任务并抛出RejectedExecutionException异常。

ThreadPoolExecutor.DiscardPolicy：也是丢弃任务，但是不抛出异常。

ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复此过程）

ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务

C. JDK 为我们内置了五种常见线程池的实现：

1. 一个单线程的线程池。这个线程池只有一个线程在工作，也就是相当于单线程串行执行所有任务。此线程池保证所有任务的执行顺序按照任务的提交顺序执行。
2. FixedThreadPool 的核心线程数和最大线程数都是指定值，也就是说当线程池中的线程数超过核心线程数后，任务都会被放到阻塞队列中。
3. CachedThreadPool 没有核心线程，非核心线程数无上限，也就是全部使用外包，但是每个外包空闲的时间只有 60 秒，超过后就会被回收。
4. ScheduledThreadPool 此线程池支持定时以及周期性执行任务的需求。

D. 讲一下自定义线程池的工作流程

根据ThreadPoolExecutor源码，当试图通过excute方法将一个Runnable任务添加到线程池中时，按照如下顺序来处理：

1、如果线程池中的线程数量少于corePoolSize，即使线程池中有空闲线程，也会创建一个新的线程来执行新添加的任务；

2、如果线程池中的线程数量大于等于corePoolSize，但缓冲队列workQueue未满，则将新添加的任务放到workQueue中，按照FIFO的原则依次等待执行（线程池中有线程空闲出来后依次将缓冲队列中的任务交付给空闲的线程执行）；

3、如果线程池中的线程数量大于等于corePoolSize，且缓冲队列workQueue已满，但线程池中的线程数量小于maximumPoolSize，则会创建新的线程来处理被添加的任务；

4、如果线程池中的线程数量等于了maximumPoolSize，触发拒绝策略。

总结起来，也即是说，当有新的任务要处理时，先看线程池中的线程数量是否大于corePoolSize，再看缓冲队列workQueue是否满，最后看线程池中的线程数量是否大于maximumPoolSize。

另外，当线程池中的线程数量大于corePoolSize时，如果里面有线程的空闲时间超过了keepAliveTime，就将其移除线程池，这样，可以动态地调整线程池中线程的数量。

E. Executor 、ExecutorService 与 Executors 的区别与联系

1. ExecutorService 接口继承了 Executor 接口，是 Executor 的子接口
2. Executor 接口定义了 execute()方法用来接收一个Runnable接口的对象；而 ExecutorService 接口中的 submit()方法可以接受Runnable和Callable接口的对象。
3. Executor 中的 execute() 方法不返回任何结果，而 ExecutorService 中的 submit()方法可以通过一个 Future 对象返回运算结果。
4. 除了允许客户端提交一个任务，ExecutorService 还提供用来控制线程池的方法。比如：调用 shutDown() 方法终止线程池。
5. Executors 类提供五个静态工厂方法用来创建不同类型的线程池。

F. 任务排队策略(WorkQueue)(存疑)

1、直接提交。缓冲队列采用 SynchronousQueue，它将任务直接交给线程处理而不保持它们。如果不存在可用于立即运行任务的线程（即线程池中的线程都在工作），则试图把任务加入缓冲队列将会失败，因此会构造一个新的线程来处理新添加的任务，并将其加入到线程池中。直接提交通常要求无界 maximumPoolSizes（Integer.MAX_VALUE）以避免拒绝新提交的任务。newCachedThreadPool采用的便是这种策略。

2、无界队列。使用无界队列（典型的便是采用预定义容量的 LinkedBlockingQueue，理论上是该缓冲队列可以对无限多的任务排队）将导致在所有 corePoolSize 线程都工作的情况下将新任务加入到缓冲队列中。这样，创建的线程就不会超过 corePoolSize，也因此，maximumPoolSize 的值也就无效了。当每个任务完全独立于其他任务，即任务执行互不影响时，适合于使用无界队列。newFixedThreadPool采用的便是这种策略。

3、有界队列。当使用有限的 maximumPoolSizes 时，有界队列（一般缓冲队列使用ArrayBlockingQueue，并制定队列的最大长度）有助于防止资源耗尽，但是可能较难调整和控制，队列大小和最大池大小需要相互折衷，需要设定合理的参数。

E. Callable 与 Runnable

1. Runnable是一个接口，在它里面只声明了一个run()方法:

public interface Runnable {

    public abstract void run();

}

run()方法返回值为void类型，所以在执行完任务之后无法返回任何结果

2. Callable位于java.util.concurrent包下，它也是一个接口，在它里面也只声明了一个方法，只不过这个方法叫做call()

public interface Callable<V> {

    V call() throws Exception;

}

这是一个泛型接口，该接口声明了一个名称为call()的方法，同时这个方法可以有返回值V，也可以抛出异常。call()方法返回的类型就是传递进来的V类型

3. 如何使用Callable

一般情况下配合ExecutorService来使用callable，在ExecutorService接口中声明了若干个submit方法的重载版本：

<T> Future<T> submit(Callable<T> task);

<T> Future<T> submit(Runnable task, T result);

Future<?> submit(Runnable task);

第一个方法：submit提交一个实现Callable接口的任务，并且返回封装了异步计算结果的Future。

第二个方法：submit提交一个实现Runnable接口的任务，并且指定了在调用Future的get方法时返回的result对象。

第三个方法：submit提交一个实现Runnable接口的任务，并且返回封装了异步计算结果的Future。

因此我们只要创建好我们的线程对象（实现Callable接口或者Runnable接口），然后通过上面3个方法提交给线程池去执行即可。

Future就是对于具体的Runnable或者Callable任务的执行结果进行取消、查询是否完成、获取结果。必要时可以通过get方法获取执行结果，该方法会阻塞直到任务返回结果。

F. Future

Future就是对于具体的Runnable或者Callable任务的执行结果进行取消、查询是否完成、获取结果。必要时可以通过get方法获取执行结果，get方法会阻塞直到任务返回结果。

Future接口定义了下面5种方法:

cancel方法用来取消任务
isCancelled方法表示任务是否被取消成功
isDone方法表示任务是否已经完成
get()方法用来获取执行结果，这个方法会产生阻塞，会一直等到任务执行完毕才返回
get(long timeout, TimeUnit unit)用来获取执行结果，如果在指定时间内，还没获取到结果，就直接返回null。

也就是说Future提供了三种功能：

1）判断任务是否完成；

2）能够中断任务；

3）能够获取任务执行结果。

因为Future只是一个接口，所以是无法直接用来创建对象使用的,FutureTask是Future接口的一个唯一实现类。

Java并发包（JUC）相关

并发包主要分成以下几个类族:

线程同步类逐步淘汰了使用Object的wait()和notify()的同步方式，主要代表为CountDownLatch, Semaphore,CyclicBarrier等

并发集合类最著名的是ConcurrentHashMap, 由刚开始的分段锁到后来的CAS，不断提升并发性能，还有ConcurrentSkipListMap, CopyOnWriteArrayList, BlockingQueue等

线程管理类线程池，如使用Executors静态工厂或者使用ThreadPoolExecutor等，另外，使用ScheduledExecutorService来执行定时任务

锁相关类以Lock接口为核心，派生出一些类，最有名的是ReentrantLock

并发包中的锁类

Lock是JUC包的顶层接口，它的实现逻辑并未用到synchronized, 而是利用了volatile的可见性和CAS

ReentrantLock对于Lock接口的实现主要依赖了Sync，而Sync继承了AbstractQueuedSynchronizer（AQS），它是JUC包实现同步的基础工具。在AQS中，定义了一个volatile int state变量作为共享资源，如果线程获取资源失败，则进入同步FIFO队列中等待；如果成功获取资源就执行临界区代码。执行完释放资源时，会通知同步队列中的等待线程来获取资源后出队并执行。

AQS是抽象类，内置自旋锁实现的同步队列，封装入队和出队的操作，提供独占、共享、中断等特性的方法。AQS的子类可以定义不同的资源实现不同性质的方法。

比如可重入锁ReentrantLock，定义state为0时可以获取资源并置为1。若已获得资源，state 不断加1，在释放资源时state减1，直至为0；
CountDownLatch初始时定义了资源总量state=count，countDown()不断将state减1，当state=0时才能获得锁，释放后state就一直为0。所有线程调用await()都不会等待，所以CountDownLatch是一次性的，用完后如果再想用就只能重新创建一个；如果希望循环使用，推荐使用基于RentrantLock 实现的CyclicBarrier。
Semaphore 与CountDownLatch略有不同，同样也是定义了资源总量state=permits，当state>0时就能获得锁，并将state减1，当state=0时只能等待其他线程释放锁，当释放锁时state加1，其他等待线程又能获得这个锁。

当Semphore的permits定义为1时，就是互斥锁，当permits>1就是共享锁。总之，ReentrantLock, CountDownLatch, CyclicBarrier，Semaphore等工具都是基于AQS的不同配置来实现的。

自旋锁是一种互斥锁的实现方式而已，相比一般的互斥锁会在等待期间放弃cpu，自旋锁（spinlock）则是不断循环并测试锁的状态，这样就一直占着cpu。与互斥量类似，它不是通过休眠使进程阻塞，而是在获取锁之前一直处于忙等(自旋)阻塞状态。用在以下情况：锁持有的时间短，而且线程并不希望在重新调度上花太多的成本。"原地打转"。

互斥锁：用于保护临界区，确保同一时间只有一个线程访问数据。对共享资源的访问，先对互斥量进行加锁，如果互斥量已经上锁，调用线程会阻塞，直到互斥量被解锁。在完成了对共享资源的访问后，要对互斥量进行解锁。

sychronized关键字与lock的区别

Volatile关键字

每个线程都有独占的内存区域，如操作栈、本地变量表等。线程本地内存保存了引用变量在堆内存中的副本，线程对变量的所有操作都在本地内存区域中进行，执行结束后再同步到堆内存中去。这里必然有一个时间差，在这个时间差内，该线程对副本的操作，对于其他线程都是不可见的。
volatile的英文本义是“挥发、不稳定的”，延伸意义为敏感的。当使用volatile修饰变量时，意味着任何对此变量的操作都会在内存中进行，不会产生副本，以保证共享变量的可见性，局部阻止了指令重排的发生。(从JDK5开始java增强了volatile的内存语义，除了线程读取volatile变量要从主内存获取和线程写volatile变量要及时刷回到主内存以外，JDK5开始还严格限制编译器和处理器对volatile变量和普通变量的重排序，从而确保volatiled的写-读和锁的释放-获取具有相同的语义。)

锁也可以确保变量的可见性，但是实现方式和volatile略有不同。线程在得到锁时读入副本，释放时写回内存。
volatile解决的是多线程共享变量的可见性问题，类似于synchronized，但不具备synchronized的互斥性。

因为所有的操作同需要同步给内存，因此volatile一定使线程的执行速度变慢

volatile变量与锁的区别:

由于volatile仅仅保证对对单个volatile变量的读、写具有原子性(复合操作不保证原子性如volatie i, i++)，而锁的互斥执行的特性可以确保对整个临界区代码的执行具有原子性。在功能上，锁比volatile更强大，在可伸缩性上和执行性能上，volatile更有优势。

信号量同步

信号量同步是指在不同的线程之间，通过传递同步信号量来协调线程执行的先后次序。

CountDownLatch是基于执行时间的同步类。在实际编码中，可能需要处理基于空闲信号的同步情况。比如海关安检的场景，任何国家公民在出国时，都要走海关的查验通道。假设某机场的海关通道共有3个窗口，一批需要出关的人排成长队，每个人都是一个线程。当3个窗口中的任意一个出现空闲时，工作人员指示队列中第一个人出队到该空闲窗口接受查验。对于上述场景，JDK中提供了一个Semaphore的信号同步类，只有在调用Semaphore对象的acquire()成功后，才可以往下执行，完成后执行release()释放持有的信号量，下一个线程就可以马上获取这个空闲信号量进入执行。

1、CountDownLatch end = new CountDownLatch(N); //构造对象时候需要传入参数N

　　2、end.await() 能够阻塞线程直到调用N次end.countDown() 方法才释放线程

　　3、end.countDown() 可以在多个线程中调用计算调用次数是所有线程调用次数的总和

还有其他同步方式，如CyclicBarrier是基于同步到达某个点的信号量触发机制。CyclicBarrier从命名上即可知道它是一个可以循环使用（Cyclic）的屏障式（Barrier）多线程协作方式。采用这种方式进行刚才的安检服务，就是3个人同时进去，只有3个人都完成安检，才会放下一批进来。这是一种非常低效的安检方式。但在某种场景下就是非常正确的方式，假设在机场排队打车时，现场工作人员统一指挥，每次放3辆车进来，坐满后开走，再放下一批车和人进来。通过CyclicBarrier的reset）来释放线程资源。

ThreadLocal 变量

ThreadLocal是用来维护线程中的变量不被其他线程干扰而出现的一个结构，内部包含一个ThreadLocalMap类，该类为Thread类的一个局部变量，该Map存储的key为ThreadLocal对象所在线程对象，value为我们要存储的对象，这样一来，在不同线程中，持有的其实都是当前线程的变量副本，与其他线程完全隔离，以此来保证线程执行过程中不受其他线程的影响。利用ThreadLocal可以实现让所有的线程持有初始值相同的一个变量副本，但在初始化以后每个线程都只能操作自己的那个变量副本，不同线程之间的变量副本互不干扰。

ThreadLocal可能会造成内存泄漏的问题：

ThreadLocal中的键值对中的键是一个弱引用，那么在内存回收的时候，这个键很可能会被回收掉，然后键没了，就无法找到value的值，造成了内存泄漏；

我们看下set方法的实现：
public void set(T value) {

    Thread t = Thread.currentThread();

    ThreadLocalMap map = getMap(t);

    if (map != null)

        map.set(this, value);

    else

        createMap(t, value);

}        
可以看到，先通过Thread.currentThread()方法获取到了当前线程，然后如果取不到map对象，就会创建，下面看下create方法
void createMap(Thread t, T firstValue) {

    t.threadLocals = new ThreadLocalMap(this, firstValue);

}
很简单的方法，就是新建一个ThreadLocal的Map，这个map以ThreadLocal自身为key，以我们要设值的对象为value，创建出来map之后，将对象赋值到线程的局部变量去。
看到这里，就知道ThreadLocal主要目的就是将变量设值到当前的线程上，以此来保证线程安全。
那么下面看下get方法：
public T get() {

    Thread t = Thread.currentThread();

    ThreadLocalMap map = getMap(t);

    if (map != null) {

    ThreadLocalMap.Entry e = map.getEntry(this);

    if (e != null) {

        @SuppressWarnings("unchecked")

        T result = (T)e.value;

        return result;

    }

    }

    return setInitialValue();

}        
可以看出来，get方法就是拿的当前线程的局部变量threadLocals，然后从中取出map中存储的对象，这样每个线程中获取的一定是自己线程中存储的对象了。
由上述分析可知，使用ThreadLocal是可以保证线程安全的。
ThreadLocal实际上是为解决多线程程序的并发问题提供了一种新的思路（区别与sychronized关键字）。
ThreadLocal这个类提供线程本地的变量。这些变量与一般正常的变量不同，它们在每个线程中都是独立的。ThreadLocal实例最典型的运用就是在类的私有静态变量中定义，并与线程关联。

并且ThreadLocal不会产生内存泄漏的问题
原文：https://blog.csdn.net/caoyishuai100/article/details/68946037

详细解释

Java引用类型和GC时机

对象在堆上创建之后所持有的用基实是一种变量类型，引用之间可以通过赋值构成一条引用链。从GC Roots开始遍历，判断引用是否可达。引用的可达性是判断能否被垃圾回收的基本条件。JMM会根据此自动管理内存的分配与回收，不需要开发工程师干预。但在某些场景下，即使引用可达，也希望能够根据语义的强弱进行有选择的回收，以保证系统的正常运行。根据引用类型语义的强弱来决定垃圾回收的阶段，我们可以把引用分为强引用、软引用、弱引用和虚引用四类。后三类引用，本质上是可以让开发工程师通过代码方式来决定对象的垃圾回收时机。

强引用，即Strong Reference，最为常见。如Object object=new Objecto）；这样的变量声明和定义就会产生对该对象的强引用。只要对象有强引用指向，并且GC Roots可达，那么Java内存回收时，即使濒临内存耗尽，也不会回收该对象。
软引用，即Soft Reference，引用力度弱于“强引用”，是用在非必需对象的场景。在即将OMM之前，垃圾回收器会把这些软引用指向的对象加入回收范围，以获得更多的内存空间，让程序能够继续健康运行。主要用来缓存服务器中间计算结果及不需要实时保存的用户行为等。
弱引用，即Weak Reference，引用强度较前两者更弱，也是用来描述非必需对象的。如果弱引用指向的对象只存在弱引用这一条线路，则在下一次YGC时会被回收。由于YGC时间的不确定性，弱引用何时被回收也具有不确定性。弱引用主要用于指向某个易消失的对象，在强引用断开后，此引用不会劫持对象。
虚引用，即Phantom Reference，是极弱的一种引用关系，定义完成后，就无法通过该引用获取指向的对象。为一个对象设置虚引用的唯一目的就是希望能在这个对象被回收时收到一个系统通知。虚引用必须与引用队列联合使用，当垃圾回收时，如果发现存在虚引用，就会在回收对象内存前，把这个虚引用加入与之关联的引用队列中。

Static变量是线程安全的吗？

JAVA对象锁和方法锁的区别

首先的明白Java中锁的机制 synchronized

在修饰代码块的时候需要一个reference对象作为锁的对象.
在修饰方法的时候默认是当前对象作为锁的对象.
在修饰类时候默认是当前类的Class对象作为锁的对象.

方法锁（synchronized修饰方法时）

通过在方法声明中加入 synchronized关键字来声明 synchronized 方法。

synchronized 方法控制对类成员变量的访问：
每个类实例对应一把锁，每个 synchronized 方法都必须获得调用该方法的类实例的锁方能执行，否则所属线程阻塞，方法一旦执行，就独占该锁，直到从该方法返回时才将锁释放，此后被阻塞的线程方能获得该锁，重新进入可执行状态。这种机制确保了同一时刻对于每一个类实例，其所有声明为 synchronized 的成员函数中至多只有一个处于可执行状态，从而有效避免了类成员变量的访问冲突。

对象锁（synchronized修饰方法或代码块）

　　当一个对象中有synchronized method或synchronized block的时候调用此对象的同步方法或进入其同步区域时，就必须先获得对象锁。如果此对象的对象锁已被其他调用者占用，则需要等待此锁被释放。（方法锁也是对象锁）　　　　　

　　java的所有对象都含有1个互斥锁，这个锁由JVM自动获取和释放。线程进入synchronized方法的时候获取该对象的锁，当然如果已经有线程获取了这个对象的锁，那么当前线程会等待；synchronized方法正常返回或者抛异常而终止，JVM会自动释放对象锁。这里也体现了用synchronized来加锁的1个好处，方法抛异常的时候，锁仍然可以由JVM来自动释放。　

类锁(synchronized 修饰静态的方法或代码块)

　　由于一个class不论被实例化多少次，其中的静态方法和静态变量在内存中都只有一份。所以，一旦一个静态的方法被申明为synchronized。此类所有的实例化对象在调用此方法，共用同一把锁，我们称之为类锁。　

对象锁是用来控制实例方法之间的同步，类锁是用来控制静态方法（或静态变量互斥体）之间的同步。

总结：

1.类锁是对静态方法使用synchronized关键字后，无论是多线程访问单个对象还是多个对象的sychronized块，都是同步的。

2.对象锁是实例方法使用synchronized关键字后，如果是多个线程访问同个对象的sychronized块，才是同步的，但是访问不同对象的话就是不同步的。

3.类锁和对象锁是两种不同的锁，可以同时使用，但是注意类锁不要嵌套使用，这样子容易发生死锁。

类锁和对象锁区别

类锁所有对象一把锁
对象锁一个对象一把锁，多个对象多把锁

同步是对同一把锁而言的，同步这个概念是在多个线程争夺同一把锁的时候才能实现的，如果多个线程争夺不同的锁，那多个线程是不能同步的

两个线程一个取对象锁，一个取类锁，则不能同步
两个线程一个取a对象锁，一个取b对象锁，则不能同步

Sychronized方法加在方法上和加在代码块上有什么区别？

synchronize修饰方法的锁对象只能是this当前对象

　　 synchronize修饰代码块可以修改锁对象(可以是this对象，也可以自行指定)

使用this对象锁的好处:

这个锁由JVM自动获取和释放。线程进入synchronized方法的时候获取该对象的锁，当然如果已经有线程获取了这个对象的锁，那么当前线程会等待；synchronized方法正常返回或者抛异常而终止，JVM会自动释放对象锁。这里也体现了用synchronized来加锁的1个好处，方法抛异常的时候，锁仍然可以由JVM来自动释放。

坏处:

锁的粒度大，代码效率降低；

synchronized的缺陷：当某个线程进入同步方法获得对象锁，那么其他线程访问这个对象的其余的同步方法时，也必须等待或者阻塞，这对高并发的系统是致命的，这很容易导致系统的崩溃。如果某个线程在同步方法里面发生了死循环，那么它就永远不会释放这个对象锁，那么其他线程就要永远的等待。这是一个致命的问题。

当然同步方法和同步代码块都会有这样的缺陷，只要用了synchronized关键字就会有这样的风险和缺陷。既然避免不了这种缺陷，那么就应该将风险降到最低。这也是同步代码块在某种情况下要优于同步方法的方面。例如在某个类的方法里面：这个类里面声明了一个对象实例，SynObject so=new SynObject()；在某个方法里面调用了这个实例的方法so.testsy();但是调用这个方法需要进行同步，不能同时有多个线程同时执行调用这个方法。

这时如果直接用synchronized修饰调用了so.testsy();代码的方法，那么当某个线程进入了这个方法之后，这个对象其他同步方法都不能给其他线程访问了。假如这个方法需要执行的时间很长，那么其他线程会一直阻塞，影响到系统的性能。

如果这时用synchronized来修饰代码块：synchronized（so）{so.testsy();}，那么这个方法加锁的对象是so这个对象，跟执行这行代码的对象没有关系，当一个线程执行这个方法时，这对其他同步方法时没有影响的，因为他们持有的锁都完全不一样。

不过这里还有一种特例，就是上面演示的第一个例子，对象锁synchronized同时修饰方法和代码块，这时也可以体现到同步代码块的优越性，如果test1方法同步代码块后面有非常多没有同步的代码，而且有一个100000的循环，这导致test1方法会执行时间非常长，那么如果直接用synchronized修饰方法，那么在方法没执行完之前，其他线程是不可以访问test2方法的，但是如果用了同步代码块，那么当退出代码块时就已经释放了对象锁，当线程还在执行test1的那个100000的循环时，其他线程就已经可以访问test2方法了。这就让阻塞的机会或者线程更少。让系统的性能更优越。

Synchronized 锁的升级（膨胀）

Java1.6 中为了减少获得锁和释放锁带来的性能消耗而引入的偏向锁和轻量级锁。锁是按顺序膨胀的，且锁的膨胀是不可逆的。

偏向锁：大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。当一个线程A访问加了同步锁的代码块时，会在对象头中存储当前线程的id，后续这个线程进入和退出这段加了同步锁的代码块时，不需要再次加锁和释放锁。

轻量级锁：在偏向锁情况下，如果线程B也访问了同步代码块，比较对象头的线程id不一样，会升级为轻量级锁，并且通过自旋的方式来获取轻量级锁。

重量级锁：如果线程A和线程B同时访问同步代码块，则轻量级锁会升级为重量级锁，线程A获取到重量级锁的情况下，线程B只能入队等待，进入BLOCK状态。

多线程并发问题的技术选择

当只有一个线程写，其它线程都是读的时候，可以用 volatile 修饰变量
当多个线程写，那么一般情况下并发不严重的话可以用 Synchronized ，Synchronized并不是一开始就是重量级锁，在并发不严重的时候，比如只有一个线程访问的时候，是偏向锁；当多个线程访问，但不是同时访问，这时候锁升级为轻量级锁；当多个线程同时访问，这时候升级为重量级锁。所以在并发不是很严重的情况下，使用Synchronized是可以的。不过Synchronized有局限性，比如不能设置锁超时，不能通过代码释放锁。
ReentranLock 可以通过代码释放锁，可以设置锁超时。
高并发下，Synchronized、ReentranLock 效率低，因为同一时刻只有一个线程能进入同步代码块，如果同时有很多线程访问，那么其它线程就都在等待锁。这个时候可以使用并发包下的数据结构，例如 ConcurrentHashMap ， LinkBlockingQueue ，以及原子性的数据结构如： AtomicInteger 。

volatile和synchronized特点

乐观锁和悲观锁

悲观锁
总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现。

乐观锁
总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

CAS：

Compare and Swap(CAS)

CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS是一种非阻塞式的同步方式。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。”这其实和乐观锁的冲突检查+数据更新的原理是一样的。

两种锁的使用场景
从上面对两种锁的介绍，我们知道两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下（多读场景），即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。但如果是多写的情况，一般会经常产生冲突，这就会导致上层应用会不断的进行retry，这样反倒是降低了性能，所以一般多写的场景下用悲观锁就比较合适。

Java常见锁

公平锁/非公平锁
可重入锁
独享锁/共享锁
互斥锁/读写锁
乐观锁/悲观锁
分段锁
偏向锁/轻量级锁/重量级锁
自旋锁

重入锁与不可重入锁的区别

重入锁是可重复获得资源的锁，已经获得锁的线程可以对当前的资源重入加锁而不会引起阻塞；不可重入锁是不可重复获得资源的锁，当已经获得锁的线程对当前资源再次加锁时，会把自己阻塞。这样做的好处是可以防止死锁。

可重入性：

从名字上理解，ReenTrantLock的字面意思就是再进入的锁，其实synchronized关键字所使用的锁也是可重入的，两者关于这个的区别不大。同一个线程每进入一次，锁的计数器都自增1，所以要等到锁的计数器下降为0时才能释放锁。

可重入锁的设计思路

轻松学习java可重入锁(ReentrantLock)的实现原理

第二模块--计算机网路

TCP/IP结构有几层

TCP/IP参考模型

分为四个层次：应用层、传输层、网络互连层和主机到网络层。常见的协议如下：

基于UDP的常见的还有DNS、、RIP（路由选择协议）、DHCP 动态主机设置协议

在TCP/IP参考模型中，去掉了OSI参考模型中的会话层和表示层（这两层的功能被合并到应用层实现）。同时将OSI参考模型中的数据链路层和物理层合并为主机到网络层。

TCP/IP七层参考模型

物理层（Physical Layer）
数据链路层（Datalink Layer）
网络层（Network Layer）
传输层（Transport Layer）
会话层（Session Layer）
表示层（Presentation Layer）
应用层（Application Layer）

常用网络硬件设备分别工作在哪一层

1.网络层：路由器、防火墙
2.数据链路层：网卡、网桥、交换机
3.物理层：中继器、集线器

路由器（Router），是连接因特网中各局域网、广域网的设备，它会根据信道的情况自动选择和设定路由，以最佳路径，按前后顺序发送信号。路由和交换机之间的主要区别就是交换机发生在OSI参考模型第二层（数据链路层），而路由发生在第三层，即网络层。这一区别决定了路由和交换机在移动信息的过程中需使用不同的控制信息，所以说两者实现各自功能的方式是不同的。

解释TCP/IP 的三次握手

TCP建立连接的三次握手过程

TCP会话通过三次握手来初始化。三次握手的目标是使数据段的发送和接收同步。同时也向其他主机表明其一次可接收的数据量（窗口大小），并建立逻辑连接。这三次握手的过程可以简述如下：

●源主机发送一个同步标志位（SYN）置1的TCP数据段, 此段中同时包含一个初始值随机的客户端序列号,ClientISN；

●目标主机发回确认数据段，此段中的同步标志位（SYN）同样被置1，且确认标志位（ACK）也置1，同时将ClientISN + 1，此外，此段中还包含一个初始值随机的服务端序列号ServerISN;

●源主机收到目标主机确认数据段后，再回送一个数据段，包含ACK = 1, serverISN+1;

Source ---> Destination: 　　SYN = 1, Seq = ClientISN

Destination ---> Source: 　　SYN = 1, ACK =1, ClientISN + 1, Seq = ServerISN

Source ---> Destination: 　　ACK = 1, ServerISN+1

至此为止，TCP会话的三次握手完成。接下来，源主机和目标主机可以互相收发数据。整个过程可用下图表示。

解释TCP/IP四次挥手的过程

起初A和B处于ESTABLISHED状态

A发出连接释放报文段(Fin = 1, Seq = u;)并处于FIN-WAIT-1状态，A不再有数据发送，但仍然可以接受数据;

B发出确认报文段(ACK = 1, Seq = v, ack = u+1)且进入CLOSE-WAIT状态, 并继续发送剩下的数据, A收到确认后，进入FIN-WAIT-2状态，等待B的连接释放报文段；

B没有要向A发出的数据，B发出连接释放报文段(Fin = 1, ACK = 1, Seq = w, ack = u+1)且进入LAST-ACK状态;

A发出确认报文段(ACK = 1, Seq = w, ack = u+1)且进入TIME-WAIT状态, B收到确认报文段后进入CLOSED状态;

A经过等待计时器时间2MSL后，进入CLOSED状态。

A(FIN-WAIT-1) ---> B (ESTABLISHED): Fin = 1, Seq = u;

B(CLOSE-WAIT) ---> A: ACK = 1, Seq = v, ack = u+1 (继续发送剩余数据);

---> A (FIN-WAIT-2): A 收到上一步数据，A等待B的Fin;

B(LAST-ACK) ---> A : Fin = 1, ACK = 1, Seq = w, ack = u+1;

A(TIME-WAIT) ---> B: 收到上一步数据，发送ACK = 1, Seq = w, ack = u+1;

---> B(CLOSED): 收到上一步数据，ClOSED.

A(ClOSED): 等待2MSL, 进入CLOSED.

TCP的连接的拆除需要发送四个包，因此称为四次挥手(four-way handshake)。客户端或服务器均可主动发起挥手动作，在socket编程中，任何一方执行close()操作即可产生挥手操作。

为什么TCP/IP需要握手三次，挥手四次

为什么需要三次握手呢？

两个原因：信息对等和防止超时

信息对等: 假设A对B 发起连接请求，在第二次握手时，A机器能够确认自己的发报和收报能力正常并且B的发报收报能力正常，而B机器只能确定自己的收报能力和对方的发报能力正常，不能确定对方的收报能力和自己的发报能力是否正常，这些只能通过第三次握手确认；

防止超时 为了防止已失效的连接请求报文段突然又传送到了服务端，浪费服务端资源。

比如：client发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达server。本来这是一个早已失效的报文段，但是server收到此失效的连接请求报文段后，就误认为是client再次发出的一个新的连接请求，于是就向client发出确认报文段，同意建立连接。假设不采用“三次握手”，那么只要server发出确认，新的连接就建立了，由于client并没有发出建立连接的请求，因此不会理睬server的确认，也不会向server发送数据，但server却以为新的运输连接已经建立，并一直等待client发来数据。所以没有采用“三次握手”，这种情况下server的很多资源就白白浪费掉了。

为什么需要四次挥手呢？因为TCP是全双工模式，一方发送FIN报文时只是单方面没有信息发送了，但是另一方可以继续发送报文，只有双方都发送了FIN报文整个通信过程才能结束。

TCP是全双工模式，当client发出FIN报文段时，只是表示client已经没有数据要发送了，client告诉server，它的数据已经全部发送完毕了；但是，这个时候client还是可以接受来server的数据；当server返回ACK报文段时，表示它已经知道client没有数据发送了，但是server还是可以发送数据到client的；当server也发送了FIN报文段时，这个时候就表示server也没有数据要发送了，就会告诉client，我也没有数据要发送了，如果收到client确认报文段，之后彼此就会愉快的中断这次TCP连接。

为什么A在TIME-WAIT状态必须等待2MSL的时间？

MSL最长报文段寿命Maximum Segment Lifetime，MSL=2

两个理由：

1）保证A发送的最后一个ACK报文段能够到达B。

2）防止“已失效的连接请求报文段”出现在本连接中。

1）这个ACK报文段有可能丢失，使得处于LAST-ACK状态的B收不到对已发送的FIN+ACK报文段的确认，B超时重传FIN+ACK报文段，而A能在2MSL时间内收到这个重传的FIN+ACK报文段，接着A重传一次确认，重新启动2MSL计时器，最后A和B都进入到CLOSED状态，若A在TIME-WAIT状态不等待一段时间，而是发送完ACK报文段后立即释放连接，则无法收到B重传的FIN+ACK报文段，所以不会再发送一次确认报文段，则B无法正常进入到CLOSED状态。

2）A在发送完最后一个ACK报文段后，再经过2MSL，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失，使下一个新的连接中不会出现这种旧的连接请求报文段。

通过调整2MSL时间（可以手动更改），可以有效降低TIME_WAIT状态的连接数目，达到系统调优的目的。建议将高并发服务器的TIME_WAIT超时调小。

TCP协议和UDP协议的区别是什么

TCP协议是有连接的，有连接的意思是开始传输实际数据之前TCP的客户端和服务器端必须通过三次握手建立连接，会话结束之后也要结束连接，而UDP是无连接的。
TCP协议保证数据按序发送，按序到达，提供超时重传来保证可靠性，但是UDP不保证按序到达，甚至不保证到达，只是努力交付，即便是按序发送的序列，也不保证按序送到。
TCP有流量控制和拥塞控制，UDP没有，网络拥堵不会影响发送端的发送速率
TCP是一对一的连接，而UDP则可以支持一对一，多对多，一对多的通信。
TCP面向的是字节流的服务，UDP面向的是报文的服务。
TCP协议所需资源多，TCP首部需20个字节（不算可选项），UDP首部字段只需8个字节

TCP的特点是连序控点流: 有连接、有序、流量控制、点对点、字节流

面向字节流和面向报文：

用UDP传输100个字节的数据:

面向数据报
如果发送端调用一次sendto, 发送100个字节, 那么接收端也必须调用对应的一次recvfrom, 接收100个字节;
而不能循环调用10次recvfrom, 每次接收10个字节;

面向字节流
由于缓冲区的存在, TCP程序的读和写不需要一一匹配, 例如:
写100个字节数据时, 可以调用一次write写100个字节, 也可以调用100次write, 每次写⼀一个字节;
读100个字节数据时, 也完全不需要考虑写的时候是怎么写的, 既可以一次read 100个字节, 也可以一次read一个字节, 重复100次;

应用层交给UDP多长的报文, UDP原样发送, 既不会拆分, 也不会合并;
TCP有一个缓冲，当应用程序传送的数据块太长，TCP就可以把它划分短一些再传送。如果应用程序一次只发送一个字节，TCP也可以等待积累有足够多的字节后再构成报文段发送出去。

常见的应用中有哪些是应用TCP协议的，哪些又是应用UDP协议的，为什么它们被如此设计？

基于TCP的应用层协议有：HTTP、FTP、SMTP、TELNET、

基于UDP的应用层协议：DNS、RIP（路由选择协议）、DHCP、BOOTP（是DHCP的前身）、IGMP（Internet组管理协议）、TFTP（简单文件传输协议）

以下应用一般或必须用udp实现

多播的信息一定要用udp实现，因为tcp只支持一对一通信。
如果一个应用场景中大多是简短的信息，适合用udp实现，因为udp是基于报文段的，它直接对上层应用的数据封装成报文段，然后丢在网络中，如果信息量太大，会在链路层中被分片，影响传输效率。
如果一个应用场景重性能甚于重完整性和安全性，那么适合于udp，比如多媒体应用，缺一两帧不影响用户体验，但是需要流媒体到达的速度快，因此比较适合用udp
如果要求快速响应，那么udp比较合适
如果又要利用udp的快速响应优点，又想可靠传输，那么只能考上层应用自己制定规则了。
常见的使用udp的例子：ICQ,QQ的聊天模块。

UDP能不能实现可靠连接，怎么实现

UDP它不属于连接型协议，因而具有资源消耗小，处理速度快的优点，所以通常音频、视频和普通数据在传送时使用UDP较多，因为它们即使偶尔丢失一两个数据包，也不会对接收结果产生太大影响。传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，实现转移到了应用层。

实现确认机制、重传机制、窗口确认机制。

必须实现如下功能：

发送：包的分片、包确认、包的重发

接收：包的调序、包的序号确认

目前有如下开源程序利用udp实现了可靠的数据传输。分别为RUDP、RTP、UDT。

基于UDP的数据传输协议（UDP-basedData Transfer Protocol，简称UDT）是一种互联网数据传输协议

解释Server端受到SYN攻击

服务器端的资源分配是在二次握手时分配的，而客户端的资源是在完成三次握手时分配的，所以服务器容易受到SYN洪泛攻击，SYN攻击就是Client在短时间内伪造大量不存在的IP地址，并向Server不断地发送SYN包，Server则回复确认包，并等待Client确认，由于源地址不存在，因此Server需要不断重发直至超时，这些伪造的SYN包将长时间占用未连接队列，导致正常的SYN请求因为队列满而被丢弃，从而引起网络拥塞甚至系统瘫痪。

防范SYN攻击措施：降低主机的等待时间使主机尽快的释放半连接的占用，短时间受到某IP的重复SYN则丢弃后续请求

HTTP的八种请求方法

根据HTTP标准，HTTP请求可以使用多种请求方法。

HTTP1.0定义了三种请求方法： GET, POST 和 HEAD方法。

HTTP1.1新增了五种请求方法：OPTIONS, PUT, DELETE, TRACE 和 CONNECT 方法。

序号	方法	描述
1	GET	请求指定的页面信息，并返回实体主体。
2	HEAD	类似于get请求，只不过返回的响应中没有具体的内容，用于获取报头
3	POST	向指定资源提交数据进行处理请求（例如提交表单或者上传文件）。数据被包含在请求体中。POST请求可能会导致新的资源的建立和/或已有资源的修改。
4	PUT	从客户端向服务器传送的数据取代指定的文档的内容。
5	DELETE	请求服务器删除指定的页面。
6	CONNECT	HTTP/1.1协议中预留给能够将连接改为管道方式的代理服务器。
7	OPTIONS	允许客户端查看服务器的性能。
8	TRACE	回显服务器收到的请求，主要用于测试或诊断。

GET和POST两种基本请求方法的区别

“标准答案”：

浏览器行为:

GET在浏览器回退时是无害的，而POST会再次提交请求。

GET产生的URL地址可以被Bookmark，而POST不可以。

GET请求会被浏览器主动cache，而POST不会，除非手动设置。

GET请求只能进行url编码，而POST支持多种编码方式。

GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。

GET参数通过URL传递，且参数是有长度限制的，POST放在Request body中。

对参数的数据类型，GET只接受ASCII字符，而POST没有限制。

GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。GET提交的数据会放在URL之后，以?分割URL和传输数据，参数之间以&相连，如EditPosts.aspx?name=test1&id=123456. POST方法是把提交的数据放在HTTP包的Body中.

GET产生一个TCP数据包；POST产生两个TCP数据包。

对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；
而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）

GET和POST本质上没有区别！

GET和POST是HTTP协议中的两种发送请求的方法。

HTTP是是基于TCP/IP的关于数据如何在万维网中如何通信的协议。

HTTP的底层是TCP/IP。所以GET和POST的底层也是TCP/IP，也就是说，GET/POST都是TCP链接。GET和POST能做的事情是一样一样的。你要给GET加上request body，给POST带上url参数，技术上是完全行的通的。

但不同的浏览器（发起http请求）和服务器（接受http请求）在技术层面上不允许 url中无限加参数。他们会限制单次运输量来控制风险，数据量太大对浏览器和服务器都是很大负担。业界不成文的规定是，（大多数）浏览器通常都会限制url长度在2K个字节，而（大多数）服务器最多处理64K大小的url。超过的部分，恕不处理。如果你用GET服务，在request body偷偷藏了数据，不同服务器的处理方式也是不同的，有些服务器会帮你卸货，读出数据，有些服务器直接忽略，所以，虽然GET可以带request body，也不能保证一定能被接收到。

GET和POST还有一个重大区别，简单的说：

GET产生一个TCP数据包；POST产生两个TCP数据包。

对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；

而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

但并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。

HTTP和HTTPS

http协议与https协议的区别?

http 是超文本传输协议，信息是明文传输，https 则是具有安全性的 ssl 加密传输协议。
http 的连接很简单，是无状态的；HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，HTTPS为了数据传输的安全，在HTTP的基础上加入了SSL协议，SSL依靠证书来验证服务器的身份，并为浏览器和服务器之间的通信加密，比 http 协议安全。
http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80，后者是 443。
https 协议需要到 ca 申请证书，一般免费证书较少，因而需要一定费用。。

HTTPS的优点（确保数据发送到正确的客户机和服务器，确保数据的完整性，增加了中间人攻击的成本）

　　尽管HTTPS并非绝对安全，掌握根证书的机构、掌握加密算法的组织同样可以进行中间人形式的攻击，但HTTPS仍是现行架构下最安全的解决方案，主要有以下几个好处：

　　（1）使用HTTPS协议可认证用户和服务器，确保数据发送到正确的客户机和服务器；

　　（2）HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全，可防止数据在传输过程中不被窃取、改变，确保数据的完整性。

　　（3）HTTPS是现行架构下最安全的解决方案，虽然不是绝对安全，但它大幅增加了中间人攻击的成本。

HTTPS的缺点(效率低)

　　虽然说HTTPS有很大的优势，但其相对来说，还是存在不足之处的：

　　（1）HTTPS协议握手阶段比较费时，会使页面的加载时间延长近50%，增加10%到20%的耗电；

　　（2）HTTPS连接缓存不如HTTP高效，会增加数据开销和功耗，甚至已有的安全措施也会因此而受到影响；

Cookies和Session的区别

cookie和session的区别：

①存在的位置：

cookie 存在于客户端，临时文件夹中； session存在于服务器的内存中，一个session域对象为一个用户浏览器服务

②安全性
cookie是以明文的方式存放在客户端的，安全性低，可以通过一个加密算法进行加密后存放； session存放于服务器的内存中，所以安全性好

③网络传输量
cookie会传递消息给服务器； session本身存放于服务器，不会有传送流量

④生命周期(以20分钟为例)
cookie的生命周期是累计的，从创建时，就开始计时，20分钟后，cookie生命周期结束；
session的生命周期是间隔的，从创建时，开始计时如在20分钟，没有访问session，那么session生命周期被销毁。但是，如果在20分钟内（如在第19分钟时）访问过session，那么，将重新计算session的生命周期。关机会造成session生命周期的结束，但是对cookie没有影响

⑤访问范围
cookie为多个用户浏览器共享； session为一个用户浏览器独享
可以看自己的笔记: https://www.cnblogs.com/greatLong/articles/11146045.html

Session：

服务器为每个会话创建一个session对象，所以session中的数据可供当前会话中所有servlet共享。作用域：会话从用户打开浏览器开始，直到关闭浏览器才结束，一次会话期间只会创建一个session对象。session是服务器端对象，保存在服务器端，并且服务器可以将创建session后产生的 sessionid 通过一个 cookie 返回给客户端，以便下次验证。（session底层的一种实现依赖于cookie，session一般配合cookie来保存会话信息，但在不允许使用cookie的情况下，也可以使用url重写的形式传递信息）

Cookie

cookie是http协议提供的，不是java独有的；

cookie保存在客户端；

可以设置生命时长；

cookie有个属性是路径，但该路径指的是服务端路径；

cookie的形式是一个键值对，如uid:lxj；

http约定，单条cookie不超过4KB，单个会话最多保存20条cookie; 浏览器最多储存300条cookie;但一般浏览器对这个规定会有超出，如允许单个会话超过20个cookie;

与之对应的，session是Java独有的，全称是httpsession, 每个session 都有JSEESIONID;

session一般配合cookie来保存会话信息，但在不允许cookie的情况下，也可以使用url重写的形式传递信息

此部分知识不完全，需要进一步理解

中间人攻击和重放攻击

重放攻击是攻击者获取客户端发送给服务器端的包，不做修改，原封不动的发送给服务器用来实现某些功能。比如说客户端发送给服务器端一个包的功能是查询某个信息，攻击者拦截到这个包，然后想要查询这个信息的时候，把这个包发送给服务器，服务器就会做相应的操作，返回查询的信息。

防御方案: 加时间戳(需要时钟同步)，使用与当前事件有关的一次性随机数N

中间人攻击就不一样了，中间人攻击是攻击者把自己当作客户端与服务器端的中间人，客户端发送的信息会被攻击者截取然后做一些操作再发送给服务器端，服务器端响应返回的包也会被攻击者截取然后再发送给客户端。你可以看作是相对于客户端来说攻击者是服务器端，(攻击者假冒客户端需要证书，但是攻击者自己制作的证书不是信任的证书，会弹警告，但往往人们对于这些警告大意或不懂就忽略了);相对于服务器段来说攻击者是客户端，两边都欺骗，从而获取所有的信息。常见的有DNS劫持。

防御方案: 采用认证方式连接

转发与重定向的区别

forward(转发):是服务器内部重定向，程序收到请求后重新定向到另一个程序，客户机并不知道。服务器直接访问目标地址的URL，并把那个URL的相应内容读取过来，然后把这些内容再发给浏览器，浏览器根本不知道服务器发送的内容是从哪里来的，所以它的地址栏中还是原来的地址，转发时并不通知客户机，对象可以存储在请求中，并发给下一个资源使用，并且完全在服务器上面进行；

redirect(重定向):是服务器收到请求后发送一个状态头给客户，客户将再请求一次新的网址，这里多了两次网络通信的来往一般来说，浏览器会用刚才请求的所有参数重新请求，所以session，request参数都可以获取。重定向导致浏览器发出了新的请求，在重定向之前存储为请求属性的任何对象都会消失，这也是两者最大的区别。

HTTP状态码

1**：请求收到，继续处理

100——客户必须继续发出请求

101——客户要求服务器根据请求转换HTTP协议版本

2**：操作成功收到，分析、接受

200("OK") 一般来说，这是客户端希望看到的响应代码。它表示服务器成功执行了客户端所请求的动作

3XX 重定向

3XX系列响应代码表明：客户端需要做些额外工作才能得到所需要的资源

301 redirect: 301 代表永久性转移(Permanently Moved)

302 redirect: 302 代表暂时性转移(Temporarily Moved )

4**：客户端错误, 请求包含一个错误语法或不能完成

404——没有发现文件、查询或URl

401——未授权

5XX 服务端错误

这些响应代码表明服务器端出现错误。一般来说，这些代码意味着服务器处于不能执行客户端请求的状态，此时客户端应稍后重试。

500("Internal Server Error")

这是一个通用的服务器错误响应。对于大多数web框架，如果在执行请求处理代码时遇到了异常，它们就发送此响应代码。

说一说HTTP请求头的内容

HTTP请求报文由3部分组成（请求行+请求头+请求体）：

①是请求方法，GET和POST是最常见的HTTP方法，除此以外还包括DELETE、HEAD、OPTIONS、PUT、TRACE。

②为请求对应的URL地址，它和报文头的Host属性组成完整的请求URL，③是协议名称及版本号。

④是HTTP的报文头，报文头包含若干个属性，格式为“属性名:属性值”，服务端据此获取客户端的信息。

⑤是报文体，它将一个页面表单中的组件值通过param1=value1&param2=value2的键值对形式编码成一个格式化串，它承载多个请求参数的数据。不但报文体可以传递请求参数，请求URL也可以通过类似于“/chapter15/user.html? param1=value1&param2=value2”的方式传递请求参数。

常见的HTTP请求报文头属性

Accept：客户端接受什么类型的响应，常见的如Accept:text/plain，Accept属性的值可以为一个或多个MIME类型的值。

Cookie: 客户端的Cookie就是通过这个报文头属性传给服务端

Referer 表示这个请求是从哪个URL过来的

Cache-Control 对缓存进行控制，控制是否缓存及缓存时间为多久。

Accept-Language：接受的语言类型

User-Agent: 通过何种代理(浏览器)访问

Content-type, Content-Length等

Connection ：

Connection: keep-alive 当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，如果客户端再次访问这个服务器上的网页，会继续使用这一条已经建立的连接

Connection: close 代表一个Request完成后，客户端和服务器之间用于传输HTTP数据的TCP连接会关闭，当客户端再次发送Request，需要重新建立TCP连接。

谈谈HTTP响应报文

HTTP的响应报文也由三部分组成（响应行+响应头+响应体）：

以下是一个实际的HTTP响应报文：

①报文协议及版本；
②状态码及状态描述；
③响应报文头，也是由多个属性组成；
④响应报文体，即我们真正要的“干货”。

响应状态码
和请求报文相比，响应报文多了一个“响应状态码”，它以“清晰明确”的语言告诉客户端本次请求的处理结果。
HTTP的响应状态码由5段组成：

1xx 消息，一般是告诉客户端，请求已经收到了，正在处理，别急...
2xx 处理成功，一般表示：请求收悉、我明白你要的、请求已受理、已经处理完成等信息.
3xx 重定向到其它地方。它让客户端再发起一个请求以完成整个处理。
4xx 处理发生错误，责任在客户端，如客户端的请求一个不存在的资源，客户端未被授权，禁止访问等。
5xx 处理发生错误，责任在服务端，如服务端抛出异常，路由出错，HTTP版本不支持等。

从浏览器发出请求开始，到服务端应用接受到请求返回结果显示的过程

第一步，解析域名，找到ip

查本地缓存--查hosts文件--查ISP服务商的DNS缓存--从根域名开始递归搜索返回

浏览器会缓存DNS一段时间，一般2-30分钟不等，如果有缓存，直接返回ip，否则下一步。
缓存中无法找到ip，浏览器会进行一个系统调用，查询hosts文件。如果找到，直接返回ip，否则下一步。
进行1 和2 本地查询无果，只能借助于网络，路由器一般都会有自己的DNS缓存，ISP服务商DNS缓存，这时一般都能够得到相应的ip，如果还是无果，只能借助于DNS递归解析了。
这时ISP的DNS服务器就会开始从根域名服务器开始递归搜索，从.com 顶级域名服务器，到baidu的域名服务器。
到这里，浏览器就获得网络ip，在DNS解析过程中，常常解析出不同的IP。

第二步，浏览器于网站建立TCP连接

浏览器利用ip直接网站主机通信，浏览器发出TCP连接请求，主机返回TCP应答报文，浏览器收到应答报文发现ACK标志位为1，表示连接请求确认，浏览器返回TCP（）确认报文，主机收到确认报文，三次握手，TCP连接建立完成。

第三步，浏览器发起默认的GET请求

浏览器向主机发起一个HTTP-GET方法报文请求，请求中包含访问的URL，也就是http://www.baidu.com/还有User-Agent用户浏览器操作系统信息，编码等，值得一提的是Accep-Encoding和Cookies项。Accept-Encoding一般采用gzip，压缩之后传输html文件，Cookies如果是首次访问，会提示服务器简历用户缓存信息，如果不是，可以利用Cookies对应键值，找到相应缓存，缓存里面存放着用户名，密码和一些用户设置项

第四步，显示页面或返回其他

返回状态码200 OK，表示服务器可以响应请求，返回报文，由于在报头中Content-type为“text/html”,浏览器以HTML形式呈现，而不是下载文件。
但是对于大型网站存在多个主机站点，往往不会直接返回请求页面，而是重定向。返回的状态码就不是 200 OK，而是301,302以3开头的重定向吗。浏览器在获取了重定向响应后，在响应报文中Location项找到重定向地址，浏览器重新第一步访问即可。

第三模块--操作系统、Git

Linux常用指令 (查看内存、进程之类的）

文件处理

文件查找：find

文本搜索：grep

排序：sort

按列切分文本：cut

统计行和字符：wc

文本替换：sed

数据流处理：awk

性能分析

进程查询：ps

进程监控：top

打开文件查询：lsof

内存使用量：free

监控性能指标：sar

监控CPU -u

监控内存 -r

网络工具

网卡配置：ifconfig

查看当前网络连接：netstat

查看路由表：route

检查网络连通性：ping

转发路径：traceroute

命令行抓包：tcpdump

域名解析工具：dig

网络请求：curl

其他

终止进程：kill
修改文件权限：chmod
创建链接：ln
显示文件尾：tail
版本控制：git
设置别名：alias

根据程序名称结束该程序

以杀掉tomcat为例子

ps -ef|grep tomcat|grep -v|awk -F '{print $2}'|xargs kill -9

等同于

kill -9 `ps -ef | grep 'tomcat' | awk '{print $2}'`

xargs接收管道前面传过来的字符;

awk '{print $2}'的意思是选取并输出第二列的数据

kill 与kill -9的区别

kill 的默认参数是 -15, kill pid的效果等同于kill -15 pid。执行kill命令，系统会发送一个关闭信号给对应的程序。当程序接收到该信号后，将有机会释放资源、处理善后工作后再停止；
kill -9命令，系统给对应程序发送的信号是SIGKILL，即exit。exit信号不会被系统阻塞，所以kill -9能顺利杀掉进程。相当于强制关闭程序。

在使用 kill -9 前，应该先使用 kill -15，给目标进程一个清理善后工作的机会。如果没有，可能会留下一些不完整的文件或状态，从而影响服务的再次启动。

查询日志

1. 按行号查看---过滤出关键字附近的日志

首先: cat -n test.log |grep "keyword" 得到关键日志的行号

然后，得到"keyword"关键字所在的行号是102行. 此时如果想查看这个关键字前10行和后10行的日志:

cat -n test.log |tail -n +92|head -n 20

2. 刷新显示日志变动

tail -f test.log 查看日志的尾部，并刷新显示日志变动。此方法适合在调试程序的时候查看日志，日志变动会实时刷新显示到终端。

top指令能查看进程的哪些信息

包括进程的相关信息,包括进程ID,内存占用率,CPU占用率

待补充

守护进程了解吗

线程是调度的基本单位，进程是资源分配的基本单位。。

守护进程是生存期长的一种进程。它们独立于控制终端并且周期性的执行某种任务或等待处理某些发生的事件。他们常常在系统引导装入时启动，在系统关闭时终止。linux系统有很多守护进程，大多数服务器都是用守护进程实现的。linux上的守护进程类似于windows上的服务。

僵尸进程、孤儿进程

父进程在调用fork接口之后和子进程已经可以独立开，之后父进程和子进程就以未知的顺序向下执行（异步过程）。所以父进程和子进程都有可能先执行完。当父进程先结束，子进程此时就会变成孤儿进程，不过这种情况问题不大，孤儿进程会自动向上被init进程收养，init进程完成对状态收集工作。而且这种过继的方式也是守护进程能够实现的因素。如果子进程先结束，父进程并未调用wait或者waitpid获取进程状态信息，那么子进程描述符就会一直保存在系统中，这种进程称为僵尸进程。

Git常见指令

fetch和merge和pull的区别
pull相当于git fetch 和 git merge，即更新远程仓库的代码到本地仓库，然后将内容合并到当前分支。
git fetch：相当于是从远程获取最新版本到本地，不会自动merge
git merge : 将内容合并到当前分支
git pull：相当于是从远程获取最新版本并merge到本地

常用命令
git show # 显示某次提交的内容 git show $id
git add <file> # 将工作文件修改提交到本地暂存区
git rm <file> # 从版本库中删除文件
git reset <file> # 从暂存区恢复到工作文件
git reset HEAD^ # 恢复最近一次提交过的状态，即放弃上次提交后的所有本次修改
git diff <file> # 比较当前文件和暂存区文件差异 git diff
git log -p <file> # 查看每次详细修改内容的diff
git branch -r # 查看远程分支
git merge <branch> # 将branch分支合并到当前分支
git stash # 暂存
git stash pop #恢复最近一次的暂存
git pull # 抓取远程仓库所有分支更新并合并到本地
git push origin master # 将本地主分支推到远程主分支

第四模块--JAVA语言特性

Integer缓存数据的范围

java定义：在自动装箱时对于值从–128到127之间的值，它们被装箱为Integer对象后，会存在内存中被重用，始终只存在一个对象。这归结于java对于Integer与int的自动装箱与拆箱的设计，是一种模式：享元模式（flyweight）

而如果超过了从–128到127之间的值，被装箱后的Integer对象并不会被重用，即相当于每次装箱时都新建一个 Integer对象；以上的现象是由于使用了自动装箱所引起的，如果你没有使用自动装箱，而是跟一般类一样，用new来进行实例化，就会每次new就都一个新的对象。

https://www.cnblogs.com/greatLong/p/10776561.html

面向对象编程和面向过程编程的优缺点

面向过程

优点：性能比面向对象高，因为类调用时需要实例化，开销比较大，比较消耗资源;比如单片机、嵌入式开发、 Linux/Unix等一般采用面向过程开发，性能是最重要的因素。
缺点：没有面向对象易维护、易复用、易扩展

面向对象

优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护
缺点：性能比面向过程低

JAVA提供了几个类加载器？分别是？怎么对类进行加载的？

根加载器、扩展类加载器、系统类加载器

Bootstrap 是JVM在启动时创建的，通常由与操作系统相关的本地代码实现，是最根基的类加载器，负责装载最核心的JAVA类，如Object, System, String；

然后第二层在JDK9中称为Platform 加载器， JDK9之前叫Extension加载器，加载一些扩展的系统类，如XML, 加密，压缩相关的功能类；

第三层是Application 加载器，主要加载用户定义的CLASSPATH路径下的类。

类加载的双亲委任模型

低层次的当前类加载器，不能覆盖更高层次类加载器已经加载的类。如果低层次的类加载器想加载一个未知类，要非常礼貌地向上逐级询问：“请问，这个类已经加载了吗？”被询问的高层次类加载器会自问两个问题：第一，我是否已加载过此类？第二，如果没有，是否可以加载此类？只有当所有高层次类加载器在两个问题上的答案均为“否”时，才可以让当前类加载器加载这个未知类。如图4-6所示，左侧绿色箭头向上逐级询问是否已加载此类，直至Bootstrap ClassLoader，然后向下逐级尝试是否能够加载此类，如果都加载不了，则通知发起加载请求的当前类加载器，准予加载。

JAVA类的加载过程

在JVM中，类从被加载到虚拟机内存中开始，到卸载出内存为止，它的整个生命周期包括：加载、验证、准备、解析、初始化5个阶段。而解析阶段即是虚拟机将常量池内的符号引用替换为直接引用的过程。

加载：程序运行之前jvm会把编译完成的.class二进制文件加载到内存，供程序使用，用到的就是类加载器classLoader 2、
连接：分为三步验证》准备》解析

验证：确保类加载的正确性。

准备：为类的静态变量分配内存，将其初始化为默认值。

解析：把类中的符号引用转化为直接引用。

3. 初始化：为类的静态变量赋予正确的初始值，上述的准备阶段为静态变量赋予的是虚拟机默认的初始值，此处赋予的才是程序编写者为变量分配的真正的初始值

现在java程序的执行就可以分为

类成员初始化顺序总结：先静态，后父类普通构造，再子类普通构造，同级看书写顺序

1.先执行父类静态变量和静态代码块，再执行子类静态变量和静态代码块

2.先执行父类普通变量和代码块，再执行父类构造器(static方法)

3.先执行子类普通变量和代码块，再执行子类构造器(static方法)

4.static方法初始化先于普通方法，静态初始化只有在必要时刻才进行且只初始化一次。

反射机制

定义: 在运行状态中，对于任意一个类，都能够获取到这个类的所有属性和方法，对于任意一个对象，都能够调用它的任意一个方法和属性(包括私有的方法和属性)，这种动态获取的信息以及动态调用对象的方法的功能就称为java语言的反射机制。

使用: 想要使用反射机制，就必须要先获取到该类的字节码文件对象(.class)，通过字节码文件对象，就能够通过该类中的方法获取到我们想要的所有信息(方法，属性，类名，父类名，实现的所有接口等等)，每一个类对应着一个字节码文件也就对应着一个Class类型的对象，也就是字节码文件对象。
Java反射的三种实现方式

Foo foo = new Foo();

第一种：通过Object类的getClass方法

Class cla = foo.getClass();

第二种：通过对象实例方法获取对象

Class cla = foo.class;

第三种：通过Class.forName方式

Class cla = Class.forName("xx.xx.Foo");

HashCode 是干什么用的？如果重写HashCode 有哪些注意点？

hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了。

在每个类中，在重写 equals 方法的时侯，一定要重写 hashcode 方法。如果不这样做，就违反了hashCode的通用约定，这会阻止它在HashMap和HashSet这样的集合中正常工作。

如果两个对象根据equals(Object)方法比较是相等的，那么在两个对象上调用hashCode就必须产生的结果是相同的整数。
如果两个对象根据equals(Object)方法比较并不相等，则不要求在每个对象上调用hashCode都必须产生不同的结果。但是，程序员应该意识到，为不相等的对象生成不同的结果可能会提高散列表（hash tables）的性能。

JAVA集合类的常见问题

HashMap底层是怎么实现的

数组加链表的形式

在JAVA 8 中，改进为，当链表长度达到8及以上，转为红黑树来实现; 红黑树的数据数量将为6的时候又会自动转为链表。

（因为长度为6的链表平均查询次数是3，查找树的话，3次查询能查到8个数据）

HashMap 是一个用于存储Key-Value 键值对的集合，每一个键值对也叫做Entry。这些个Entry 分散存储在一个数组当中，这个数组就是HashMap 的主干。每个Entry都是链表的结构，含有可以指向一个Entry的next指针；
HashMap 数组每一个元素的初始值都是Null。

1. Put 方法的原理

调用Put方法的时候发生了什么呢？根据键计算哈希值，确定放在哪个Entry里，如果计算出index位置的entry已经有值，就将新加入的键值对挂在这个entry的链表尾部。
比如调用 hashMap.put(“apple”, 0) ，插入一个Key为“apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）：
index = Hash（"apple"）
假定最后计算出的index是2，那么结果如下：

但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样：

这时候该怎么办呢？我们可以利用链表来解决。
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可：

新来的Entry节点插入链表时，使用的是头插法。

2. Get方法的原理

使用Get方法根据Key来查找Value的时候，发生了什么呢？
首先会把输入的Key做一次Hash映射，得到对应的index：
index = Hash（“apple”）
由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”：

第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。
第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。
之所以把Entry放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

3. HashMap的初始长度

初始长度为16，且每次自动扩容或者手动初始化的时候必须是2的幂。

对于新插入的数据或者待读取的数据，HashMap将Key的哈希值对数组长度取模，结果作为该Entry在数组中的index。在计算机中，取模的代价远高于位操作的代价，因此HashMap要求数组的长度必须为2的N次方。此时将Key的哈希值对2^N-1进行与运算，其效果即与取模等效。HashMap并不要求用户在指定HashMap容量时必须传入一个2的N次方的整数，而是会通过Integer.highestOneBit算出比指定整数大的最小的2^N值。

如何进行位运算呢？有如下的公式（Length是HashMap的长度）：
之前说过，从Key映射到HashMap数组的对应位置，会用到一个Hash函数：
index = Hash（“apple”）
如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。
index = HashCode（Key） & （Length - 1）
下面我们以值为“book”的Key来演示整个过程：

计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。这里的位运算其实是一种快速取模算法。

HashMap 的size为什么必须是2的幂?。这是因为2的幂用二进制表示时所有位都为1，例如16-1=15 的二进制就是1111B。我们说了Hash算法是为了让hash 的分布变得均匀。其实我们可以把1111看成四个通道，表示跟1111 做&运算后分布是均匀的。假如默认长度取10，二进制表示为1010，这样就相当于有两个通道是关闭的，所以计算出来的索引重复的几率比较大。

HashMap的扩容条件：

(size>=threshold) && (null != table[bucketIndex]) 即达到阈值，并且当前需要存放对象的slot上已经有值。

解决hash冲突的办法

开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
再哈希法
链地址法
建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法

解决Hash冲突的开放地址检测是怎么实现的

这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))
其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。

增量 d 可以有不同的取法，并根据其取法有不同的称呼：
（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列；
（ 3 ） d i ＝伪随机序列伪随机再散列；

从哈希表中删除一个元素，再加入元素时恰好与原来的那个哈希冲突，这个元素会放在哪

放在冲突Entry最开始的地方，因为哈希表在冲突时采用的是头插法，之所以把Entry放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

并发容器, hashtable和concurrenthashmap的区别

HashMap为什么线程不安全？

主要有死链和高并发下的数据用丢失两个问题

死链

https://www.jianshu.com/p/e2f75c8cce01

主要发生在多线程情况下rezise时迁移数据的transfer()方法，put(), get()方法。多个线程同时扩容时， hashmap会可能产生环，造成死循环。

高并发下的数据丢失

新增对象丢失的原因一般有:

- 并发赋值时被覆盖
- resize线程已遍历区间新增元素会丢失
- 多个线程同时resize“新表“被覆盖
- 迁移丢失

1. 数据丢失场景：在表扩容时，当前线程迁移数据的过程中，其他线程新增的元素有可能落在迁移线程已经遍历过的哈希槽上；在遍历完成之后，table数组引用指向了newTable, 这时刚才新增的元素就会失去引用，被GC回收。

2. 数据覆盖场景:

put的时候导致的多线程数据不一致：有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

或者多个线程同时执行resize，也会造成table的覆盖问题。

ConcurrentHashMap

Hashtable 在JDK1.0引入，以全互斥方式处理并发问题，性能极差；

HashMap在JDK1.2引入，非线程安全，在并发写的情形下，容易出现死链的问题；

ConcurrentHashMap在JDK5中引入，是线程安全的哈希式集合，JDK1.8之前采用分段锁的设计理念，相当于Hashtable和HashMap的折衷版。分段锁由内部类Segment实现，继承于ReentrantLock, 用它来管辖辖区每个HashEntry。JDK11对JDK7做了如下优化:

取消分段锁机制，进一步降低冲突的概率；
引入红黑树结构，同一个哈希槽上的元素个数超过一定阈值后（8），将单向链表转为红黑树结构（在转化中，使用同步块锁住当前槽的首元素，防止其他线程对当前槽进行修改，转化完成后利用CAS替换原有链表）；当某个槽的元素减少至6个时，由红黑树重新转回链表；
使用更加优化的方式统计集合内的元素数量

待补充：

快排

索引

LinkedHashMap

LinkedHashMap是有序的HashMap

map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false)

第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存 ;
第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存 ;

关于使用LinkedHashMap实现LRU和FIFO

JAVA创建对象的方法有哪些

Java中有5种创建对象的方式，下面给出它们的例子还有它们的字节码

使用new关键字	} → 调用了构造函数
使用Class类的newInstance方法	} → 调用了构造函数
使用Constructor类的newInstance方法	} → 调用了构造函数
使用clone方法	} → 没有调用构造函数
使用反序列化	} → 没有调用构造函数

使用Class类的newInstance方法：我们也可以使用Class类的newInstance方法创建对象，这个newInstance方法调用无参的构造器创建对象
使用Constructor类的newInstance方法我们可以通过这个newInstance方法调用有参数的和私有的构造函数。这两种newInstance的方法就是大家所说的反射，事实上Class的newInstance方法内部调用Constructor的newInstance方法。
调用一个对象的clone方法，JVM就会创建一个新的对象，将前面的对象的内容全部拷贝进去，用clone方法创建对象并不会调用任何构造函数。要使用clone方法，我们必须先实现Cloneable接口并实现其定义的clone方法。
使用反序列化：当我们序列化和反序列化一个对象，JVM会给我们创建一个单独的对象，在反序列化时，JVM创建对象并不会调用任何构造函数。为了反序列化一个对象，我们需要让我们的类实现Serializable接口。

Object 类有哪些方法？

九个方法：clone, getclass, toString, finalize, equals, hashcode, wait, notify, notifyAll

什么是JAVA序列化

把对象转换为字节序列的过程称为对象的序列化。
把字节序列恢复为对象的过程称为对象的反序列化。
　　对象的序列化主要有两种用途：
　　1）把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中；
　　2）在网络上传送对象的字节序列。

String, stringbuilder, stringbuffer区别

首先说运行速度（特指修改的操作），在这方面运行速度快慢为：StringBuilder > StringBuffer > String

　　String最慢的原因：

String为字符串常量，String对象一旦创建之后该对象是不可更改的，Java中对String对象进行的更改操作实际上是一个不断创建新的对象并且将旧的对象回收的一个过程，所以执行速度很慢。而StringBuilder和StringBuffer均为字符串变量，对变量进行操作就是直接对该对象进行更改，而不进行创建和回收的操作，所以速度要比String快很多。

在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的。

如果一个StringBuffer对象在字符串缓冲区被多个线程使用时，StringBuffer中很多方法可以带有synchronized关键字，所以可以保证线程是安全的，但StringBuilder的方法则没有该关键字，所以不能保证线程安全。

String：适用于少量的字符串操作的情况

　　StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况

　　StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况

string的不可变如何实现

通常情况下，在java中通过以下步骤实现不可变

对于属性不提供设值方法
所有的属性定义为private final
类声明为final不允许继承

如果读了String 的源码的话，在Java中String类其实就是对字符数组的封装, JDK6中, value是String封装的数组，offset是String在这个value数组中的起始位置，count是String所占的字符的个数。会发现String 类的所有变量（value，offset和count等）都是 private final 声明的，且没有对外提供任何set方法。所以在String类的外部无法修改String。也就是说一旦初始化就不能修改，并且在String类的外部不能访问这三个成员。一旦String初始化了，也不能被改变。所以可以认为String对象是不可变的了。

string为何设计为不可变

1. 字符串常量池的需要

字符串常量池(String pool, String intern pool, String保留池) 是Java堆内存中一个特殊的存储区域, 当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。假若字符串对象允许改变,那么将会导致各种逻辑错误,比如改变一个对象会影响到另一个独立对象. 严格来说，这种常量池的思想,是一种优化手段。

2. 允许String对象缓存HashCode

Java中String对象的哈希码被频繁地使用, 比如在hashMap 等容器中。字符串不变性保证了hash码的唯一性,因此可以放心地进行缓存.这也是一种性能优化手段,意味着不必每次都去计算新的哈希码.

3. 安全性

String被许多的Java类(库)用来当做参数,例如网络连接地址URL,文件路径path,还有反射机制所需要的String参数等, 假若String不是固定不变的,将会引起各种安全隐患。

总体来说, String不可变的原因包括 设计考虑,效率优化问题,以及安全性这三大方面。

为什么String被设计为不可变？

安全：首要原因是安全，不仅仅体现在你的应用中，而且在JDK中，Java的类装载机制通过传递的参数（通常是类名）加载类，这些类名在类路径下，想象一下，假设String是可变的，一些人通过自定义类装载机制分分钟黑掉应用。如果没有了安全，Java不会走到今天。
性能： string不可变的设计出于性能考虑，当然背后的原理是string pool，当然string pool不可能使string类不可变，不可变的string更好的提高性能。
线程安全：当多线程访问时，不可变对象是线程安全的，不需要什么高深的逻辑解释，如果对象不可变，线程也不能改变它。

异常

Java把异常当作对象来处理，并定义一个基类java.lang.Throwable作为所有异常的超类。Throwable 下又分为 Error 和 Exception。

Error 用来表示 JVM 无法处理的错误

Error：Error类对象由 Java 虚拟机生成并抛出，大多数错误与代码编写者所执行的操作无关。

最常见的erro是当JVM不再有继续执行操作所需的内存资源时，将出现 OutOfMemoryError。这些异常发生时，Java虚拟机（JVM）一般会选择线程终止；

Exception 分为两种：

1. 受检异常：需要用 try...catch... 语句捕获并进行处理，并且可以从异常中恢复；
2. 非受检异常：是程序运行时错误，例如除 0 会引发 Arithmetic Exception，此时程序崩溃并且无法恢复。

设计模式有哪些

单例模式: (懒汉模式、饥汉模式)
1、构造方法私有化，除了自己类中能创建外其他地方都不能创建

2、在自己的类中创建一个单实例（饱汉模式是一出来就创建创建单实例，而饥汉模式需要的时候才创建）

3、提供一个方法获取该实例对象(创建时需要进行方法同步)

饿汉模式

饿汉模式就是立即加载，在方法调用前，实例就已经被创建了，所以是线程安全的。

public class MyObject1 {

    private static MyObject1 myObject1 = new MyObject1();

    private MyObject1() {}

    public static MyObject1 getInstance() {

        return myObject1;

    }

}

懒汉模式

懒汉就是延迟化加载，当需要使用的时候才进行实例化。

线程不安全方式:

public class MyObject2 {

    private static MyObject2 myObject2;

    private MyObject2() {}

    public static MyObject2 getInstance() {

        if (myObject2 == null) {

            myObject2 = new MyObject2();

        }

        return myObject2;

    }

}

线程安全但是效率低下的方式:

public class MyObject3 {

    private static MyObject3 myObject3;

    private MyObject3() {}

    synchronized public static MyObject3 getInstance() {

        if (myObject3 == null) {

            myObject3 = new MyObject3();

        }

        return myObject3;

    }

}

使用DCL双检查锁(双重检查锁定)，线程安全而且效率得到提高，只将进行实例化的代码进行加锁:

public class MyObject4 {

    private volatile static MyObject4 myObject4;

    private MyObject4() {}

    public static MyObject4 getInstance() {

        if (myObject4 == null) {

            synchronized (MyObject4.class) {

                if (myObject4 == null) {

                    myObject4 = new MyObject4();

                }

            }

        }

        return myObject4;

    }

}

但要注意实例化的对象一定要声明位volatile型，以禁止指令重排序，否则仍然出现线程安全问题，分析见此。

还有其他初始化的手段，见本博客

工厂模式: Spring IOC就是使用了工厂模式.
对象的创建交给一个工厂去创建。在工厂方法模式中，核心的工厂类不再负责所有的产品的创建，而是将具体创建的工作交给子类去做。

抽象工厂模式：抽象工厂模式可以向客户端提供一个接口，使客户端在不必指定产品的具体的情况下，创建多个产品族中的产品对象。

代理模式: Spring AOP就是使用的动态代理。

观察者模式:在对象之间定义了一对多的依赖，这样一来，当一个对象改变状态，依赖它的对象会收到通知并自动更新。

装饰器模式:在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责，在Java源码中典型的装饰器模式就是java I/O, 其实装饰者模式也有其缺点，就是产生了太多的装饰者小类，有类爆炸的趋势。

第五模块--数据结构：

BST 二叉搜索树

1 首先它也是一个二叉树，故满足递归定义;

2 需满足左子树值<=根值<=右子树，BST的中序遍历必定是严格递增的。

3. 任意节点的左右子树也分别是二叉查找树.

4. 没有键值相等的节点.

5. 对于某些情况,二叉查找树会退化成一个有n个节点的线性链

AVL树

1. 是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,

2. 左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).

3. 不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

红黑树的六大特征

本质上是一个平衡搜索二叉树，和Btree不一样，可以说是AVL树的变种，牺牲了一定查询效率，减少了维护平衡的时间。log(n) 中序排序都能得到递增序列。

1）每个结点要么是红的，要么是黑的。（没有其他颜色）

2）根结点是黑的。

3）每个叶结点（叶结点即指树尾端NIL(Nothing In the Leaf)指针或NULL结点）是黑的。（叶子节点即为树尾端的NIL指针，或者说NULL节点。）

4）一条路径上不能出现相邻的两个红色节点

5）对于任一结点而言，其到叶结点(树尾端NIL指针)的每一条路径都包含相同数目的黑结点。（最长路径是最小路径的2倍）

6）最多三次旋转，可以达到平衡

上述条件保证红黑树的新增、查找、删除的最坏时间复杂度均为O(logN)。

通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是弱平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

红黑树相比于BST和AVL树有什么优点？

红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(logN)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多

在插入时，红黑树和AVL树都能在至多2次旋转内恢复平衡；在删除时，红黑树由于只追求大致上的平衡，能在至多3次旋转内恢复平衡，而追求绝对平衡的AVL树至多需要O(logN)次旋转。

B-树（B树、平衡多路树）

B-tree是一种平衡多路搜索树（并不一定是二叉的）B-tree树即B树

B树，一般用于外存储索引结构。系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的。二叉树、红黑树 [复杂度O(h)]导致树高度非常高(平衡二叉树一个节点只能有左子树和右子树),逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，IO次数多查找慢,效率低。

特点：

（1）根节点的左子树和右子树的深度最多相差1.(确保了不会出现上图右边的极端现象)

（2）是一个平衡多路搜索树，单个节点能放多个子节点

（3）所有结点都有存储关键字（数据）；

（4）不太稳定，可能走不到叶子节点

B+TREE

B+树是B-树的变体，也是一种平衡多路搜索树，非叶子节点只做索引，所有数据都保存在叶子节点中。

和B树区别

1：根节点和分支节点中不保存数据，只用于索引。数据和索引分离

2：所有数据都保存在叶子节点中

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+Tree内节点去掉了data域，只做索引，减少了io次数，因此可以拥有更大的出度，拥有更好的性能。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

B+树和B树的区别

一篇详尽的解析

为什么用B+树作为数据库索引，而不是平衡树或者B树？

为什么平衡二叉树或者红黑树不适合作为索引

索引是存在于索引文件中，是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。另外一点，平衡二叉树和红黑树都是二叉树，数据量较大的时候，树的高度也比较高，因此会产生较多的磁盘IO。B树的查询，由于每层可以储存多个节点，因此可以作磁盘预读，将相关的数据一次性读进内存里，因此他的查找主要发生在内存中，而平衡二叉树的查询，则是发生在磁盘读取中。因此，虽然B树查询查询的次数不比平衡二叉树的次数少，但是相比起磁盘IO速度，内存中比较的耗时就可以忽略不计了。因此，B树更适合作为索引。

为什么B+树比B树更适合作索引

B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；

B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。

B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持范围查找非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
比如要查 5-10之间的，B+树一次找到到5这个标记，再一次找到10这个标记，然后串起来就行了，B树就非常麻烦。

举个例子来对比。
B树：

比如说，我们要查找关键字范围在3到7的关键字，在找到第一个符合条件的数字3后，访问完第一个关键字所在的块后，得遍历这个B树，获取下一个块，直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的。

B+树：

相比之下，B+树的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针，因此从块1到块2的访问，通过块1指向块2的指针即可。从块2到块3也是通过一个指针即可。

数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

B+树由于非叶子节点也有数据，这样在做范围查找的时候有可能某个范围的数据散落在叶子节点和非叶子节点(各层)，这样就需要多次扫描B树才能找全数据，会产生多次的磁盘IO；而B+树所有的数据都在叶子节点，且叶子节点的数据前后用指针相连，只要通过索引找到范围数据在叶子节点中的起始或结束位置，就可以顺着叶子节点链表把这个范围内的数据全都读出来，避免了再次扫描，从而提高范围查找的效率。

八大排序的特点

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法（快选希堆），

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

链表的倒数第K个节点(快排)

树的深度优先遍历和广度优先遍历

搜索方法有哪些，稳定性怎么样

第六模块--数据库

Reids 支持的数据类型

Redis支持五种数据类型：

string（字符串）
hash（哈希）是一个键值(key=>value)对集合。
list（列表）是简单的字符串列表，按照插入顺序排序
set（集合），Set是string类型的无序集合。集合是通过哈希表实现的
zset(sorted set：有序集合)，是string类型元素的集合,且不允许重复的成员，不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

redis的替换策略

替换对象分为 allkeys 和 volatile,

替换方式分为LRU、random 和ttl

总的策略 = 2*3 = 6

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

腾讯一面后端问了LRU的算法原理，自己怎么实现LRU

volatile-lru : 对具有生存周期的key（设置失效（expire set）的key）进行LRU算法置换.
volatile-random : 对具有生存周期的key进行随机置换.
volatile-ttl : 对具有生存周期的key随机进行抽样, 置换出抽样中生存周期最短的.
allkeys-lru : 对整个db进行LRU算法置换.
allkeys-random : 对整个db进行随机置换.
noeviction : 不进行置换.

Redis 持久化方法

redis提供两种方式进行持久化:

一种是RDB(快照)持久化（原理是将Reids在内存中的数据库记录定时dump到磁盘上的RDB持久化）
另外一种是AOF（append only file）持久化（原理是将Reids的操作日志以追加的方式写入文件）

RDB持久化是指在指定的时间间隔内将内存中的数据集快照写入磁盘，实际操作过程是fork一个子进程，先将数据集写入临时文件，写入成功后，再替换之前的文件，用二进制压缩存储。

AOF持久化以日志的形式记录服务器所处理的每一个写、删除操作，查询操作不会记录，以文本的方式记录，可以打开文件看到详细的操作记录。

什么时候用RDB什么时候用AOF:

备份、全量复制时使用RDB;需要实时备份的时候采用AOF

RDB的优点：

RDB是一个紧凑压缩的二进制文件，代表Redis在某个时间点上的数据快照。非常适用于备份，全量复制等场景。比如每6小时执行bgsave备份，并把RDB文件拷贝到远程机器或者文件系统中（如hdfs），用于灾难恢复。
Redis加载RDB恢复数据远远快于AOF的方式。

RDB的缺点：·

RDB方式数据没办法做到实时持久化/秒级持久化。因为bgsave每次运行都要执行fork操作创建子进程，属于重量级操作，频繁执行成本过高。
RDB文件使用特定二进制格式保存， Redis版本演进过程中有多个格式的RDB版本，存在老版本Redis服务无法兼容新版RDB格式的问题。

AOF: 通过追加写命令到文件实现持久化，通过appendfsync参数可以控制实时/秒级持久化。因为需要不断追加写命令，所以AOF文件体积逐渐变大，

需要定期执行重写操作来降低文件体积。 Redis执行AOF恢复数据远远慢于加载RDB的方式。

Redis其他知识：

1）Redis提供5种数据结构，每种数据结构都有多种内部编码实现。
2）纯内存存储、IO多路复用技术、单线程架构是造就Redis高性能的三个因素。
3）由于Redis的单线程架构，所以需要每个命令能被快速执行完，否则会存在阻塞Redis的可能，理解Redis单线程命令处理机制是开发和运维Redis的核心之一。
4）批量操作（例如mget、mset、hmset等）能够有效提高命令执行的效率，但要注意每次批量操作的个数和字节数。
5）了解每个命令的时间复杂度在开发中至关重要，例如在使用keys、hgetall、smembers、zrange等时间复杂度较高的命令时，需要考虑数据规模对于Redis的影响。
6）persist命令可以删除任意类型键的过期时间，但是set命令也会删除字符串类型键的过期时间，这在开发时容易被忽视。
7）move、dump+restore、migrate是Redis发展过程中三种迁移键的方式，其中move命令基本废弃，migrate命令用原子性的方式实现了dump+restore，并且支持批量操作，是Redis Cluster实现水平扩容的重要工具。
8）scan命令可以解决keys命令可能带来的阻塞问题，同时Redis还提供了hscan、sscan、zscan渐进式地遍历hash、set、zset。

Redis应用场景:

1. 缓存功能

Redis作为缓存层，MySQL作为存储层，绝大部分请求的热点数据都从Redis中获取。由于Redis具有支撑高并发的特性，所以缓存通常能起到加速读写和降低后端压力的作用。

2. 限速

为了短信接口不被频繁访问，会限制用户每分钟获取验证码的频率，例如一分钟不能超过5次。此功能可以使用Redis来实现，利用Redis可以设置键过期的功能，在用户首次访问时为其新建一个带有过期时间的key（如60秒）,在这个key过期之前，都不允许用户再次申请短信验证码。

3. 消息队列

Redis的lpush+brpop命令组合即可实现阻塞队列，生产者客户端使用lrpush从列表左侧插入元素，多个消费者客户端使用brpop命令阻塞式的“抢”列表尾部的元素，多个客户端保证了消费的负载均衡和高可用性。

4. 用户标签系统

集合类型比较典型的使用场景是标签（tag）。例如一个用户可能对娱乐、体育比较感兴趣，另一个用户可能对历史、新闻比较感兴趣，这些兴趣点就是标签。可以通过redis set找出集合的交集并集等

5. 排行榜系统

有序集合比较典型的使用场景就是排行榜系统。例如视频网站需要对用户上传的视频做排行榜，榜单的维度可能是多个方面的：按照时间、按照播放数量、按照获得的赞数。

https://www.cnblogs.com/davygeek/p/7995072.html

数据库事物特性(acid)：

数据库事务必须具备ACID特性，ACID是Atomic原子性，Consistency一致性，Isolation隔离性，Durability持久性

MySQL的架构

MySQL 主要分为 Server 层和引擎层，Server 层主要包括连接器、查询缓存、分析器、优化器、执行器，同时还有一个日志模块（binlog），这个日志模块所有执行引擎都可以共用,redolog 只有 InnoDB 有。

连接器：身份认证和权限相关(登录 MySQL 的时候)。
查询缓存: 执行查询语句的时候，会先查询缓存（MySQL 8.0 版本后移除，因为这个功能不太实用）。
分析器: 没有命中缓存的话，SQL 语句就会经过分析器，分析器说白了就是要先看你的 SQL 语句要干嘛，再检查你的 SQL 语句语法是否正确。
优化器：按照 MySQL 认为最优的方案去执行。
执行器: 执行语句，然后从存储引擎返回数据。

引擎层是插件式的，目前主要包括，MyISAM,InnoDB,Memory 等。

一条SQL语句的执行过程

SQL 等执行过程分为两类

对于查询等过程如下：权限校验—》查询缓存—》分析器—》优化器—》权限校验—》执行器—》引擎
对于更新等语句执行流程如下：分析器----》权限校验----》执行器—》引擎—redo log prepare—》binlog—》redo log commit

内连接、外连接与左连接、右连接

驱动表与被驱动表:

在两表连接查询中，驱动表只需要访问一次，被驱动表可能被访问多次。

内连接与外连接:

对于内连接的两个表，驱动表中的记录在被驱动表中找不到匹配的记录，该记录不会加入到最后的结果集，我们上边提到的连接都是所谓的内连接。

对于外连接的两个表，驱动表中的记录即使在被驱动表中没有匹配的记录，也仍然需要加入到结果集。在MySQL中，根据选取驱动表的不同，外连接仍然可以细分为2种：
左外连接选取左侧的表为驱动表

右外连接选取右侧的表为驱动表

过滤条件where 和 on:

WHERE子句中的过滤条件

WHERE子句中的过滤条件就是我们平时见的那种，不论是内连接还是外连接，凡是不符合WHERE子句中的过滤条件的记录都不会被加入最后的结果集。

ON子句中的过滤条件

对于外连接的驱动表的记录来说，如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段使用NULL值填充。

需要注意的是，这个ON子句是专门为外连接驱动表中的记录在被驱动表找不到匹配记录时应不应该把该记录加入结果集这个场景下提出的，所以如果把ON子句放到内连接中，MySQL会把它和WHERE子句一样对待，也就是说：内连接中的WHERE子句和ON子句是等价的。

一般情况下，我们都把只涉及单表的过滤条件放到WHERE子句中，把涉及两表的过滤条件都放到ON子句中，我们也一般把放到ON子句中的过滤条件也称之为连接条件

左连接与右连接：

左连接和右连接是左外连接和右外连接简称， 只有外连接才分左右，且外连接一定会分左右。

可以据此来分辨内连接和外连接:

如果join语句前面有left或者right, 则一定是外连接，此时on的语义与where的语义不同；

如果join语句前面没有left或者right, 则一定是内连接，此时on的语义与where相同。

标识内连接和外连接的关键字inner|cross 和 outer都是可以省略的。

什么是事务？

事务指的是逻辑上的一组操作，这组操作要么全部发生，要么全部失败。

举例：张三和李四进行转账的操作

张三向转账李四 1000元张三余额-1000元李四余额+1000元

不应该出现的是在转账过程中由于一些意外，使张三的余额减去了1000元，而李四并没有收到这笔钱。使用事务来进行管理。必须一起成功或者一起失败

事务四大特性（ACID）

1、原子性：事务包含的所有数据库操作要么全部成功，要不全部失败回滚

2、一致性：一个事务执行之前和执行之后都必须处于一致性状态。拿转账来说，假设用户A和用户B两者的钱加起来一共是5000，那么不管A和B之间如何转账，转几次账，事务结束后两个用户的钱相加起来应该还得是5000，这就是事务的一致性。

3、隔离性：一个事务未提交的业务结果是否对于其它事务可见。级别一般有：read_uncommit，read_commit，read_repeatable，串行化访问。

4、持久性：一个事务一旦被提交了，那么对数据库中数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。

什么是脏数据，脏读，不可重复读，幻觉读

1、脏数据所指的就是未提交的数据。。也就是说，一个事务正在对一条记录做修改，在这个事务完成并提交之前，这条数据是处于待定状态的（可能提交也可能回滚），这时，第二个事务来读取这条没有提交的数据，并据此做进一步的处理，就会产生未提交的数据依赖关系。一个事务中访问到了另外一个事务未提交的数据，这种现象被称为脏读。

2、不可重复读（Non-Repeatable Reads）：一个事务先后读取同一条记录，而事务在两次读取之间该数据被其它事务所修改，则两次读取的数据不同，我们称之为不可重复读。所谓不可重复读是指在一个事务内根据同一个条件对行记录进行多次查询，但是搜出来的结果却不一致。发生不可重复读的原因是在多次搜索期间查询条件覆盖的数据被其他事务修改了。

3、幻读（Phantom Reads）：一个事务按相同的查询条件重新读取以前检索过的数据，却发现其他事务插入了满足其查询条件的新数据，这种现象就称为幻读。

4、所谓幻读是指同一个事务内多次查询返回的结果集不一样（比如增加了或者减少了行记录）。比如同一个事务A内第一次查询时候有n条记录，但是第二次同等条件下查询却又n+1条记录，这就好像产生了幻觉，为啥两次结果不一样那。其实和不可重复读一样，发生幻读的原因也是另外一个事务新增或者删除或者修改了第一个事务结果集里面的数据。不同在于不可重复读是同一个记录的数据内容被修改了，幻读是数据行记录变多了或者少了。

数据库隔离级别:

数据库事务的隔离级别有4个，由低到高依次为Read uncommitted 、Read committed 、Repeatable read 、Serializable ，这四个级别可以逐个解决脏读、不可重复读、幻读这几类问题。

√: 可能出现 ×: 不会出现

	脏读	不可重复读	幻读
Read uncommitted	√	√	√
Read committed	×	√	√
Repeatable read	×	×	√
Serializable	×	×	×

当隔离级别设置为Read uncommitted 时，就可能出现脏读;

当隔离级别设置为Read committed 时，避免了脏读，但是可能会造成不可重复读。大多数数据库的默认级别就是Read committed，比如Sql Server , Oracle。

当隔离级别设置为Repeatable read 时，可以避免不可重复读。

Mysql的默认隔离级别就是Repeatable read。

Serializable 是最高的事务隔离级别，同时代价也花费最高，性能很低，一般很少使用，在该级别下，事务顺序执行，不仅可以避免脏读、不可重复读，还避免了幻读。

MVCC的原理 | MySQL 的事务是怎样实现的?

https://www.cnblogs.com/AnXinliang/p/9955331.html

1. 未提交读隔离级别总是读取最新的数据行，无需使用 MVCC;

2. 提交读和可重复读这两种隔离级别, MySQL 的 InnoDB 存储引擎用多版本并发控制（Multi-Version Concurrency Control, MVCC) 实现；

3. 可串行化隔离级别需要对所有读取的行都加锁。

MVCC的原理

MVCC通过版本号、记录隐藏的两个列(创建版本号、删除版本号)和Undo日志(通过回滚指针将所有的快照连接成版本链)

版本号

系统版本号：是一个递增的数字，每开始一个新的事务，系统版本号就会自动递增。

事务版本号：事务开始时的系统版本号。

隐藏的列

MVCC 在每行记录后面都保存着两个隐藏的列，用来存储两个版本号：

创建版本号：指示创建一个数据行的快照时的系统版本号；

删除版本号：如果该快照的删除版本号大于当前事务版本号表示该快照有效，否则表示该快照已经被删除了。

Undo 日志

每次对记录进行改动，都会记录一条undo日志。MVCC 使用到的快照存储在 Undo 日志中，该日志通过回滚指针把一个数据行（Record）的所有快照连接起来。

对于使用READ COMMITTED和REPEATABLE READ隔离级别的事务来说，都必须保证读到已经提交了的事务修改过的记录，也就是说假如另一个事务已经修改了记录但是尚未提交，是不能直接读取最新版本的记录的，核心问题就是：需要判断一下版本链中的哪个版本是当前事务可见的。为此，InnoDB提出了一个ReadView的概念。

还需要读掘金小册的相关部分

MySQL 主从复制的原理以及流程

复制基本原理流程

1. 主：binlog线程——记录下所有改变了数据库数据的语句，放进master上的binlog中；

2. 从：io线程——在使用start slave 之后，负责从master上拉取 binlog 内容，放进自己的relay log中；

3. 从：sql执行线程——执行relay log中的语句；

解释数据库设计三大范式

为了建立冗余较小、结构合理的数据库，设计数据库时必须遵循一定的规则。在关系型数据库中这种规则就称为范式。

1．第一范式(确保每列保持原子性)

第一范式是最基本的范式。如果数据库表中的所有字段值都是不可分解的原子值，就说明该数据库表满足了第一范式。

第一范式的合理遵循需要根据系统的实际需求来定。比如某些数据库系统中需要用到“地址”这个属性，本来直接将“地址”属性设计成一个数据库表的字段就行。但是如果系统经常会访问“地址”属性中的“城市”部分，那么就非要将“地址”这个属性重新拆分为省份、城市、详细地址等多个部分进行存储，这样在对地址中某一部分操作的时候将非常方便。

2．第二范式(确保表中的每列都和主键相关)

第二范式在第一范式的基础之上更进一层。第二范式需要确保数据库表中的每一列都和主键相关，而不能只与主键的某一部分相关（主要针对联合主键而言）。也就是说在一个数据库表中，一个表中只能保存一种数据，不可以把多种数据保存在同一张数据库表中。

3．第三范式(确保每列都和主键列直接相关,而不是间接相关)

第三范式需要确保数据表中的每一列数据都和主键直接相关，而不能间接相关。

比如在设计一个订单数据表的时候，可以将客户编号作为一个外键和订单表建立相应的关系。而不可以在订单表中添加关于客户其它信息（比如姓名、所属公司等）的字段。

数据库索引

索引是关系型数据库中给数据库表中一列或多列的值排序后的存储结构，聚集索引以及非聚集索引用的是B+树索引。

MySQL 索引类型有：唯一索引，主键（聚集）索引，非聚集索引，全文索引

聚集（clustered）索引，也叫聚簇索引，MySQL里主键就是聚集索引。

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。查询方面，聚集索引的速度往往会更占优势。

数据行的物理顺序与列值的顺序相同，如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。而且由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。

非聚集（unclustered）索引。

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

非聚集索引的二次查询问题

非聚集索引叶节点仍然是索引节点，只是有一个指针指向对应的数据块，此如果使用非聚集索引查询，而查询列中包含了其他该索引没有覆盖的列，那么他还要进行第二次的查询，查询节点上对应的数据行的数据。

SQL语句查询太慢怎么找原因、优化?

https://www.cnblogs.com/kubidemanong/p/10734045.html

分类:

1、大多数情况是正常的，只是偶尔会出现很慢的情况。

2、在数据量不变的情况下，这条SQL语句一直以来都执行的很慢。

偶发性:

a. 数据库在刷新脏页。例如 redo log 写满了需要同步到磁盘。

b. 拿不到锁。要执行的这条语句涉及到的表，别人在用，并且加锁了，我们拿不到锁，只能慢慢等待别人释放锁。要判断是否真的在等待锁，我们可以用 show processlist这个命令来查看当前的状态

经常性:

a. 没用到索引

b. 索引失效 (可以用explain 看一下这条语句，查看possible-key字段看一下可能用到的索引，key字段查看实际用到的索引)

c. 数据库索引选择错误。MySQL在执行一条语句的时候会通过分析器估计各种查询计划的查询代价，然后在其中选择代价最小的执行。如果分析器估计走索引的代价比较大，可能就放弃索引而走全表扫描。但分析器的代价估计有可能是不准确的(涉及到一个索引区分度的概念，这个区分度是用采样来统计的，采样会有偏差)。解决方法，可以强制走索引force index(a); 可以强制数据库重新统计索引区分度: analyze table t.

可以解释一下explain 一个查询语句后的一些字段吗?

一条查询语句在经过MySQL查询优化器的各种基于成本和规则的优化会后生成一个所谓的执行计划。

explain 就是用来查看一条查询语句的执行计划的。

查询计划由如下几个关键的字段:

id ：在一个大的查询语句中每个SELECT关键字都对应一个唯一的id

table: 该查询语句涉及的表名

type: 针对单表访问的方法 (有 const[主键或者唯一二级索引列与常数进行等值匹配]、ref[普通的二级索引列与常量进行等值匹配]、all[全表扫描]、index[可以使用索引覆盖，但需要扫描全部的索引记录]等)。

possible_key：该查询可能用到的索引。

key : 该查询实际用到的索引。

rows: 执行该查询计划需要扫描的行数。(如果查询优化器决定使用全表扫描的方式对某个表执行查询时，执行计划的rows列就代表预计需要扫描的行数，如果使用索引来执行查询时，执行计划的rows列就代表预计扫描的索引记录行数)

如何查看执行计划的执行成本？

在EXPLAIN单词和真正的查询语句中间加上FORMAT=JSON。

这样我们就可以得到一个json格式的执行计划，里边儿包含该计划花费的成本

联合索引和单列索引的区别是什么?

https://www.cnblogs.com/greatLong/articles/11573588.html

联合索引本质：

是对多个列建立一个索引，称为联合索引。当创建(a,b,c)联合索引时，相当于创建了(a)单列索引，(a,b)联合索引以及(a,b,c)联合索引。所以只有查询条件满足a 或者 (a,b) 或者 (a,b,c)的时候，才会用上联合索引。这就是所谓的最左匹配原则。意思是以最左边的为起点任何连续的索引都能匹配上。

单列索引只是对一个字段建立索引。

MySQL索引失效的情况有哪些？

1.如果条件中有or，假如or连接的两个查询条件字段中有一个没有索引的话,引擎会放弃索引而产生全表扫描。

2.对于多列索引，不是使用的第一部分(第一个)，则不会使用索引

3.like查询是以%开头(以%结尾的情况可以使用)

4. 查询时，采用is null条件时，不能利用到索引，只能全表扫描

5. 如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引

6.如果mysql估计使用全表扫描要比使用索引快,则不使用索引

7. 查询条件使用函数在索引列上，或者对索引列进行运算，运算包括(+，-，*，/，! 等) 错误的例子：select * from test where id-1=9; 正确的例子：select * from test where id=10;

8. 使用IN 关键字进行范围查找，有可能不走索引(IN 的范围里面有超过200个单点区间的时候会放弃索引，因为这个时候优化器对这200个单点区间作成本估计的成本很高。MySQL 5.7.3之前这个单点区间的上限是10， 5.7.3之后上限是200)

如何提高数据库查询效率

a. 对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引；

b. 应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描；

c. 索引并不是越多越好，索引固然可以提高相应的 select 的效率，但同时也降低了 insert 及 update 的效率，因为 insert 或 update 时有可能会重建索引，所以怎样建索引需要慎重考虑，视具体情况而定。

d. 应尽量避免在 where 子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描

数据库可以有几个聚集索引

一个，主键是聚集索引，数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同

哪些引擎支持聚集索引

InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

简单的SQL语句(更新)

如何创建索引

MySQL中innodb表主键设计原则

InnoDB主键设计的原则：

1. 一定要显式定义主键
2. 采用与业务无关的单独列
3. 采用自增列
4. 数据类型采用int，并尽可能小，能用tinyint就不用int，能用int就不用bigint
5. 将主键放在表的第一列

这样设计的原因：
1. 在innodb引擎中只能有一个聚集索引，我们知道，聚集索引的叶子节点上直接存有行数据，所以聚集索引列尽量不要更改，而innodb表在有主键时会自动将主键设为聚集索引，如果不显式定义主键，会选第一个没有null值的唯一索引作为聚集索引，唯一索引涉及到的列内容难免被修改引发存储碎片且可能不是递增关系，存取效率低，所以最好显式定义主键且采用与业务无关的列以避免修改；如果这个条件也不符合，就会自动添加一个不可见不可引用的6byte大小的rowid作为聚集索引

2. 需采用自增列来使数据顺序插入，新增数据顺序插入到当前索引的后面，符合叶子节点的分裂顺序，性能较高；若不用自增列，数据的插入近似于随机，插入时需要插入到现在索引页的某个中间位置，需要移动数据，造成大量的数据碎片，索引结构松散，性能很差

3. 在主键插入时，会判断是否有重复值，所以尽量采用较小的数据类型，以减小比对长度提高性能，且可以减小存储需求，磁盘占用小，进而减少磁盘IO和内存占用；而且主键存储占用小，普通索引的占用也相应较小，减少占用，减少IO，且存储索引的页中能包含较多的数据，减少页的分裂，提高效率

自己的项目中：取三维模型的名称+描述+标签组成的字符串，用MD5或者SHA1计算哈希码作为主键。哈希碰撞的概率极小。或者直接使用自增的序号作为主键，索引的效率比较高，但是也存在两个问题: 1. 如果要从库中删除一条记录，会引起整个索引的重新计算；2. 表中的其他列不能和主键直接相关，不符合数据库设计的第三范式；

数据库主键和外键

数据库

Mysql的三大引擎:

InnoDB, MyISAM和Memory, 默认InnoDB, 支持事务；memory完全在内存中，除了大小限制还有断电丢失；

redis的hash算法用的是啥

一致性哈希算法

nosql为啥比sql快

nosql不需要满足sql关系数据库数据一致性等复杂特性，非关系型一般是缓存数据库，数据加载到内存中自然更快。redis是单线程执行的，任务都放到队列中。

常见关系型数据库：

Oracle、Microsoft Access、MySQL

常见非关系型数据库：

MongoDb、redis、HBase

关系型数据库和非关系型数据库的区别与联系：

非关系型数据库中，我们查询一条数据，结果出来一个数组；关系型数据库中，查询一条数据结果是一个对象。

数据库

类型

特性

优点

缺点

关系型数据库

SQLite、Oracle、mysql

1、关系型数据库，是指采用了关系模型来组织

数据的数据库；

2、关系型数据库的最大特点就是事务的一致性；

3、简单来说，关系模型指的就是二维表格模型，

而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织。

1、容易理解：二维表结构是非常贴近逻辑世界一个概念，关系模型相对网状、层次等其他模型来说更容易理解；

2、使用方便：通用的SQL语言使得操作关系型数据库非常方便；

3、易于维护：丰富的完整性(实体完整性、参照完整性和用户定义的完整性)大大减低了数据冗余和数据不一致的概率；

4、支持SQL，可用于复杂的查询。

1、为了维护一致性所付出的巨大代价就是其读写性能比较差；

2、固定的表结构；

3、高并发读写需求；

4、海量数据的高效率读写；

非关系型数据库

MongoDb、redis、HBase

1、使用键值对存储数据；

2、分布式；

3、一般不支持ACID特性；

4、非关系型数据库严格上不是一种数据库，应该是一种数据结构化存储方法的集合。

1、无需经过sql层的解析，读写性能很高；

2、基于键值对，数据没有耦合性，容易扩展；

3、存储数据的格式：nosql的存储格式是key,value形式、文档形式、图片形式等等，文档形式、图片形式等等，而关系型数据库则只支持基础类型。

1、不提供sql支持，学习和使用成本较高；

2、无事务处理，附加功能bi和报表等支持也不好；

注1：数据库事务必须具备ACID特性，ACID是Atomic原子性，Consistency一致性，Isolation隔离性，Durability持久性。

注2：数据的持久存储，尤其是海量数据的持久存储，还是需要一种关系数据库。

Myisam 和innodb的区别

MyISAM：它是基于传统的ISAM类型，ISAM是Indexed Sequential Access Method (有索引的顺序访问方法) 的缩写，它是存储记录和文件的标准方法。不是事务安全的，而且不支持外键，如果执行大量的select，insert MyISAM比较适合。
InnoDB：支持事务安全的引擎，支持外键、行锁、事务是他的最大特点。如果有大量的update和insert，建议使用InnoDB，特别是针对多个并发和QPS较高的情况。
MyISAM索引实现：MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

第七模块高并发与分布式

什么是负载均衡?有哪些常用的负载均衡策略?

负载均衡

由一个独立的统一入口来收敛流量(接收请求)，再由做二次分发的过程就是「负载均衡」。

负载均衡实现方法的分类

根据实现技术不同，可分为DNS负载均衡，HTTP负载均衡，IP负载均衡，反向代理负载均衡、链路层负载均衡等。

HTTP重定向负载均衡

当用户向服务器发起请求时，请求首先被集群调度者截获；调度者根据某种分配策略，选择一台服务器，并将选中的服务器的IP地址封装在HTTP响应消息头部的Location字段中，并将响应消息的状态码设为302，最后将这个响应消息返回给浏览器。

当浏览器收到响应消息后，解析Location字段，并向该URL发起请求，然后指定的服务器处理该用户的请求，最后将结果返回给用户。

缺点:

调度服务器只在客户端第一次向网站发起请求的时候起作用。当调度服务器向浏览器返回响应信息后，客户端此后的操作都基于新的URL进行的(也就是后端服务器)，此后浏览器就不会与调度服务器产生关系。

由于不同用户的访问时间、访问页面深度有所不同，从而每个用户对各自的后端服务器所造成的压力也不同。而调度服务器在调度时，无法知道当前用户将会对服务器造成多大的压力，因此这种方式无法实现真正意义上的负载均衡，只不过是把请求次数平均分配给每台服务器罢了。

若分配给该用户的后端服务器出现故障，并且如果页面被浏览器缓存，那么当用户再次访问网站时，请求都会发给出现故障的服务器，从而导致访问失败。做不到高可用。

DNS负载均衡

当用户向我们的域名发起请求时，DNS服务器会自动地根据我们事先设定好的调度策略选一个合适的IP返回给用户，用户再向该IP发起请求。它的作用与HTTP重定向类似。问题是DNS会缓存IP，如果某一IP不可用(如机器故障)会导致部分用户无法正常访问，此时可以用动态DNS解决。

反向代理负载均衡

用户发来的请求都首先要经过反向代理服务器，服务器根据用户的请求要么直接将结果返回给用户，要么将请求交给后端服务器处理，再返回给用户。

优点：

隐藏后端服务器。与HTTP重定向相比，反向代理能够隐藏后端服务器，所有浏览器都不会与后端服务器直接交互，从而能够确保调度者的控制权，提升集群的整体性能。

故障转移。与DNS负载均衡相比，反向代理能够更快速地移除故障结点。当监控程序发现某一后端服务器出现故障时，能够及时通知反向代理服务器，并立即将其删除。

合理分配任务。HTTP重定向和DNS负载均衡都无法实现真正意义上的负载均衡，也就是调度服务器无法根据后端服务器的实际负载情况分配任务。但反向代理服务器支持手动设定每台后端服务器的权重。我们可以根据服务器的配置设置不同的权重，权重的不同会导致被调度者选中的概率的不同。

像安全防护、故障转移等都是反向代理才有的好处。

缺点：

调度者压力过大。由于所有的请求都先由反向代理服务器处理，那么当请求量超过调度服务器的最大负载时，调度服务器的吞吐率降低会直接降低集群的整体性能。

制约扩展。当后端服务器也无法满足巨大的吞吐量时，就需要增加后端服务器的数量，可没办法无限量地增加，因为会受到调度服务器的最大吞吐量的制约。

负载均衡的作用

1.解决并发压力，提高应用处理性能（增加吞吐量，加强网络处理能力）；

2.提供故障转移，实现高可用；

3.通过添加或减少服务器数量，提供网站伸缩性（扩展性）；

4.安全防护；（负载均衡设备上做一些过滤，黑白名单等处理）

常见的负载均衡策略

1. 轮询

2. 加权轮询

3. 最少连接次数

4. 最快响应

5. 源地址Hash法

第七模块--算法题

LRU原理及其实现

JAVA实现LRU

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

实现

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。
分析
【命中率】
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

证明一个数是2的N次方

(value & (value -1)) == 0;

Top K 问题

找出一个大数组里面前K个最大数，如1亿个数字中找出最大或最小的前100个数字（考虑判重和内存空间限制）？

如果不判重，可以将前100个数字做成最大堆或最小堆的数据结构（找最大的Top100用最小堆，找最小的Top100用最大堆），然后依次遍历所有数字，符合条件时替换根节点后并重新构建堆。堆的缺点是允许有重复数字！！！

如果要判重，则创建一个100个空间的空数组，遍历1亿个数字依次插入值（按照升序），使用二分查找算法判断新值在数组中的位置并插入，该数组最多容纳100个值。当有101个值时先判重，如果重复继续向后遍历，如果值大于数组最小值则插入到指定位置，数组第一个元素移出数组，因为数组是连续的，所有可以用内存拷贝方式赋值，只有新插入的值要单独赋值到对应的下标(原理类似于android.util.SparseArray)。因内存拷贝可认为不占用时间，该思路的总会时间复杂度是O(1亿*log100）， log100是二分查找的复杂度。

关于大数据处理的相关问题这个博客讲的非常好

热词统计问题

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

如果只有一台设备：

第一步：Query统计 (统计出每个Query出现的次数) Query统计有以下两个个方法

1、直接排序法

首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数了。

但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。

让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlgN)。排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。综合分析一下，排序的时间复杂度是O(NlgN)，而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NlgN)=O（NlgN）。

2、Hash Table法 (这种方法统计字符串出现的次数非常好) 在第1个方法中，我们采用了排序的办法来统计每个Query出现的次数，时间复杂度是NlgN，那么能不能有更好的方法来存储，而时间复杂度更低呢？

题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query 255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

那么，我们的算法就有了：

维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

本方法相比算法1：在时间复杂度上提高了一个数量级，为O（N），但不仅仅是时间复杂度上的优化，该方法只需要IO数据文件一次，而算法1的IO次数较多的，因此该算法2比算法1在工程上有更好的可操作性。

第二步：找出Top 10 (找出出现次数最多的10个)

算法一：普通排序（我们只用找出top10，所以全部排序有冗余） 我想对于排序算法大家都已经不陌生了，这里不在赘述，我们要注意的是排序算法的时间复杂度是NlgN，在本题目中，三百万条记录，用1G内存是可以存下的。

算法二：部分排序 题目要求是求出Top 10，因此我们没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，然后遍历这300万条记录，每读一条记录就和数组最后一个Query对比，如果小于这个Query，那么继续遍历，否则，将数组中最后一条数据淘汰(还是要放在合适的位置，保持有序)，加入当前的Query。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。

不难分析出，这样，算法的最坏时间复杂度是N*K，其中K是指top多少。

算法三：堆在算法二中，我们已经将时间复杂度由NlogN优化到N*K，不得不说这是一个比较大的改进了，可是有没有更好的办法呢？

分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是K，因为要把元素插入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了logK，可是，随之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改进。

基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？

回答是肯定的，那就是堆。借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此到这里，我们的算法可以改进为这样，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。思想与上述算法二一致，只是在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O（K）降到了O（logK）。那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了N*logK，和算法二相比，又有了比较大的改进。

10亿个数中找出最大的10000个数（top K问题）

先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。

针对top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树活着Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
---------------------

总结：

至此，算法就完全结束了，经过上述第一步、先用Hash表统计每个Query出现的次数，O（N）；然后第二步、采用堆数据结构找出Top 10，N*O（logK）。所以，我们最终的时间复杂度是：O（N） + N'*O（logK）。（N为1000万，N’为300万）。

优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。

如果有多台设备：

可参考Map-Reduce 的思想

核心是“分治”、“归并”和哈希，第一次遍历将关键词散列到不同的文件中（散列算法是性能关键，哈希函数的性能直接影响散列的结果，尽量避免“数据倾斜”），同一个关键词一定会散列到同一个文件，理想情况是所有关键词均匀散列到不同的文件中（即分治思想，将大文件分解为小问题）。

读取每个文件并记录各关键词的次数，做个排序，从每个文件中排序出前100的关键词；

取第一个文件的记录结果，和第二个文件做“合并”，即200个结果中排序出前100个关键词，然后依次合并第三个、第四个。。。。第N个文件(将子结果合并为总结果)

第八模块--JVM

JVM执行模式

主流的JVM是Oracle的HotSpot JVM，采用解释和编译混合执行的模式，JIT技术采用分层编译，极大的提高了Java的执行速度。

三种执行模式：

1. 解释执行

2.JIT编译执行

3.JIT编译与解释混合执行

混合执行的优势在于解释器在启动时先解释执行，省去编译时间。随着时间推进，JVM通过热点代码统计分析，识别高频的代码，基于强大的JIT动态编译技术，将热点代码转换成机器码，直接交给CPU执行。JIT的作用是将Java字节码动态地编译成可以直接发送给处理器指令执行地机器码。

内存布局：

程序计数器(Program Counter Register)：线程私有的，记录当前线程的行号指示器，为线程的切换提供保障

虚拟机栈(JVM Stacks)//本地方法栈： 线程私有的，主要存放局部变量表，操作数栈，动态链接和方法出口等；

堆区(Heap): 堆是所有线程共享的，主要用来存储对象。其中，堆可分为：年轻代和老年代两块区域。使用NewRatio参数来设定比例。对于年轻代，一个Eden区和两个Suvivor区，使用参数SuvivorRatio来设定大小。

元数据区 (Metaspace): JDK8才有，保存JDK8之前永久代中的类的元信息

本地方法栈(Native Method Stacks)

永久代和方法区的区别

HotSpot使用永久代来实现方法区。永久代是HotSpot对方法区的实现，方法区是Java虚拟机规范中的定义，是一种规范。而永久代是一种实现，一个是标准一个是实现。在Java虚拟机(JVM)内部，class文件中包括类的版本、字段、方法、接口等描述信息，还有运行时常量池，用于存放编译器生成的各种字面量和符号引用。在过去（自定义类加载器还不是很常见的时候），类大多是”static”的，很少被卸载或收集，因此被称为“永久的(Permanent)”

对于Java8， HotSpots取消了永久代，那么是不是也就没有方法区了呢？当然不是，方法区是一个规范，规范没变，它就一直在。那么取代永久代的就是元空间。

永久代和元空间的区别

1. 存储位置不同，永久代物理上是堆的一部分，和新生代，老年代地址是连续的，而元空间属于本地内存；

2. 存储内容不同，元空间存储类的元信息，静态变量和常量池等并入堆中。相当于永久代的数据被分到了堆和元空间中。

https://blog.csdn.net/u011635492/article/details/81046174

为什么使用 元空间+堆 取代永久代

1. 字符串存在永久代中，容易出现性能问题和内存溢出。

2. 类及方法的信息等比较难确定其大小，因此对于永久代的大小指定比较困难，太小容易出现永久代溢出，太大则容易导致老年代溢出。永久代的垃圾收集是和老年代(old generation)捆绑在一起的，因此无论谁满了，都会触发永久代和老年代的垃圾收集。

3. 永久代会为 GC 带来不必要的复杂度，并且回收效率偏低

https://blog.csdn.net/zhushuai1221/article/details/52122880

什么时候会发生堆溢出什么时候会发生栈溢出？

1. 栈溢出

栈是线程私有的，他的生命周期与线程相同，每个方法在执行的时候都会创建一个栈帧，用来存储局部变量表，操作数栈，动态链接，方法出口灯信息。局部变量表又包含基本数据类型，对象引用类型（局部变量表编译器完成，运行期间不会变化）

栈溢出就是方法执行是创建的栈帧超过了栈的深度。那么最有可能的就是方法递归调用产生栈溢出。

2. 堆溢出

heap space表示堆空间，堆中主要存储的是对象。如果不断的new对象则会导致堆中的空间溢出。

3. 永久代溢出(OutOfMemoryError: PermGen space)

永久代物理上是堆的一部分，和新生代，老年代地址是连续的，永久代溢出的表现就是堆溢出。(永久代的GC是和老年代(old generation)捆绑在一起的，因此无论谁满了，都会触发永久代和老年代的垃圾收集。)

由于JDK7、8移除永久带，所以只有JDK1.6及以下会出现永久带溢出的现象

堆区(Heap)：

堆区储存着几乎所有的实例对象，堆由垃圾收集器自动回收，堆区由各子线程共享使用，可以通过-Xms设置最小堆容量，和-Xmx来设置最大堆容量。

堆分成两大块:新生代和老年代。

对象产生之初在新生代，步入暮年时进入老年代，但是老年代也接纳在新生代无法容纳的超大对象。

新生代=1个Eden区+2个Survior区。绝大部分对象在Eden区生成，当Eden区装填满的时候，会触发Young Garbage Collection，即YGC。垃圾回收的时候，在Eden区实现清除策略，没有被引用的对象则直接回收。依然存活的对象会被移送到Suvivor区。Suvivor区分为S0和S1两块内存空间，送到哪块空间呢？每次YGC的时候，它们将存活的对象复制到未使用的那块空间，然后将当前正在使用的空间完全清除，交换两块空间的使用状态。如果YGC要移送的对象大于Survivor区容量的上限，则直接移交给老年代。如果老年代也无法放下，则会触发Full Garbage Collection, FGC。如果依然无法放下，则抛出OOM。

假如一些没有进取心的对象以为可以一直在新生代的Survivor区交换来交换去，那就错了。每个对象都有一个计数器，每次YGC都会加1。 -XXiMax Tenuring Threshold参数能配置计数器的值到达某个阈值的时候，对象从新生代晋升至老年代。如果该参数配置为1，那么从新生代的Eden区直接移至老年代。默认值是15，可以在Survivor区交换14次之后，晋升至老年代。

JVM Stack(虚拟机栈)：

栈（Stack）是一个先进后出的数据结构。
JVM中的虚拟机栈是描述Java方法执行的内在区域，它是线程私有的。栈中的元素用于支持虚拟机进行方法调用，每个方法从开始调用到执行完成的过程，就是栈帧从入栈到出栈的过程。在活动线程中，只有位于栈顶的帧才是有效的，称为当前栈帧。正在执行的方法称为当前方法，栈帧是方法运行的基本结构。
在执行引擎运行时，所有指令都只能针对当前栈施进行操作。而StackOverflowError表示请求的栈溢出，导致内存耗尽，通常出现在递归方法中。

虚拟机栈通过压栈和出栈的方式，对每个方法对应的活动栈帧进行运算处理，方法正常执行结束，肯定会跳转到另一个栈帧上。在执行的过程中，如果出现异常，会进行常回溯，返回地址通过异常处理表确定。栈帧在整个JVM体系中的地位颇高，包括局部变量表、操作栈、动态连接、方法返回地址等。
（1）局部变量表
　　局部变量表是存放方法参数和局部变量的区域。

（2）操作栈
　　操作栈是一个初始状态为空的桶式结构栈。在方法执行过程中，会有各种指令往栈中写入和提取信息。

(3) 动态连接

　　每个栈帧中包含一个在常量池中对当前方法的引用，目的是支持方法调用过程的动态连接。

(4) 方法返回地址

　　方法执行遇到退出情况，将返回至方法当前被调用的位置

Native Method Stacks（本地方法栈）

本地方法栈在JVM内存布局中，也是线程对象私有的，但虚拟机“主内”，本地方法栈“主外”。这个“内外”是针对JVM来说的，线程调用本地方法时，会进入一个不再受JVM约束的世界。本地方法栈可以通过JNI（Java Native Interface）来访问虚拟机运行时的数据区，甚至可以调用寄存器，具有和JVM相同的能力和权限。最著名的本地方法应该是System.currentTimeMillis(), JNI使Java深度使用操作系统的特性功能，复用非Java代码。

Program Counter Register（程序计数寄存器）

在程序计数寄存器（Program Counter Register，PC）中，Register的命名源于CPU的寄存器，CPU只有把数据装载到寄存器才能够运行。寄存器存储指令相关的现场信息，由于CPU时间片轮限制，众多线程在并发执行过程中，任何一个确定的时刻，一个处理器或者多核处理器中的一个内核，只会执行某个线程中的一条指令。这样必然导致经常中断或恢复，如何保证分毫无差呢？每个线程在创建后，都会产生自己的程序计数器和栈帧，程序计数器用来存放执行指令的偏移量和行号指示器等，线程执行或恢复都要依赖程序计数器。程序计数器在各个线程之间互不影响，此区域也不会发生内存溢出异常。
最后，从线程共享的角度来看，堆和元空间是所有线程共享的，而虚拟机栈、本地方法栈、程序计数器都是线程内部私有的。从这个角度看一下Java的内存结构:

GC（垃圾回收）

GC如何判断对象是否可以回收

为了判断对象是否存活，JVM 引入了GC Roots。如果一个对象与GC Roots之间没有直接或间接的引用关系，比如某个失去任何引用的对象，或者两个互相环岛状循环引用的对象等，判决这些对象“死缓”，是可以被回收的。可以作为GC Roots对象可以是：类静态属性中引用的对象、常量引用的对象、虚拟机栈中引用的对象、本地方法栈中引用的对象等。

垃圾回收算法

有了判断对象是否存活的标准后，再了解一下垃圾回收的相关算法。

“标记--清除算法”，该算法会从每个GC Roots出发，依次标记有引用关系的对象，最后将没有被标记的对象清除。但是这种算法会带来大量的空间碎片，导致需要分配一个较大连续空间时容易触发FGC。典型的例子是CMS回收器。
“标记--整理算法”，该算法类似计算机的磁盘整理，首先会从GC Roots出发标记存活的对象，然后将存活对象整理到内存空间的一端，形成连续的已使用空间，最后把已使用空间之外的部分全部清理掉，这样就不会产生空间碎片的问题。典型的例子是老年代的FullGC, G1回收器。
复制算法，为了能够并行地标记和整理将空间分为两块，每次只激活其中一块，垃圾回收时只需把存活的对象复制到另一块未激活空间上，将未激活空间标记为已激活，将已激活空间标记为未激活，然后清除原空间中的原对象。堆内存空间分为较大的Eden和两块较小的Survivor，每次只使用Eden和Survivor区的一块。这种情形下的“Mark-Copy”减少了内存空间的浪费。典型的例子是年轻代的minGC。

垃圾回收器（Garbage Collector）

是实现垃圾回收算法并应用在JVM环境中的内存管理模块。当前实现的垃圾回收器有数十种，常见的有Serial、CMS、G1三种。

Serial回收器是一个主要应用于YGC的垃圾回收器，采用串行单线程的方式完成GC任务，其中“Stop The World”简称STW，即垃圾回收的某个阶段会暂停整个应用程序的执行。FGC的时间相对较长，频繁FGC会严重影响应用程序的性能
CMS回收器（Concurrent Mark Sweep Collector）是回收停顿时间比较短、目前比较常用的垃圾回收器。它通过初始标记（Initial Mark）、并发标记（ConcurrentMark）、重新标记（Remark）、并发清除（Concurrent Sweep）四个步骤完成垃圾回收工作。第1、3步的初始标记和重新标记阶段依然会引发STW，而第2、4步的并发标记和并发清除两个阶段可以和应用程序并发执行，也是比较耗时的操作，但并不影响应用程序的正常执行。由于CMS采用的是“标记一清除算法”，因此产生大量的空间碎片。为了解决这个问题，CMS可以通过配置-XX：+UseCMSCompactAtFullCo lection参数，强制JVM在FGC完成后对老年代进行压缩，执行一次空间碎片整理，但是空间碎片整理阶段也会引发STW。为了减少STW次数，CMS还可以通过配置一XX：+CMSFullGCsBeforeCompaction=n参数，在执行了n次FGC后，JVM再在老年代执行空间碎片整理。
G1回收器 是HotSpot在JDK7中推出的新一代G1垃圾回收器，在JDK11中，G1是默认的回收器。G1采用的是”Mark-Copy“，有较好的空间整理能力，不会产生大量空间碎片。G1的优势是具有可预测的停顿时间，能够尽快在指定时间完成垃圾回收任务。
另外还有在JDK11中引入的实验性的ZGC，是一个可伸缩的低延迟垃圾收集器。

怎样分析查找OOM的原因

使用jmap将当前的内存 Dump成一个 hprof格式的文件，MAT 读取这个文件后会给出方便阅读的信息，配合它的查找，对比功能，就可以定位内存泄漏的原因。
用的最多的功能是 Histogram，它按类名将所有的实例对象列出来，可以点击表头进行排序,在表的第一行可以输入正则表达式来匹配结果

举例一个典型的分析内存泄漏的过程：

1.  使用 Heap查看当前堆大小为 23.00M

2.  添加一个页后堆大小变为 23.40M

3.  将添加的一个页删除，堆大小为 23.40M

4.  多次操作，结果仍相似，说明添加/删除页存在内存泄漏 (也应注意排除其它因素的影响)

5.  Dump 出操作前后的 hprof 文件 (1.hprof,2.hprof)，用 mat打开,并得到 histgram结果

6.  使用 HomePage字段过滤 histgram结果，并列出该类的对象实例列表，看到两个表中的对象集合大小不同，操作后比操作前多出一个 HomePage，说明确实存在泄漏

7.  将两个列表进行对比，找出多出的一个对象，用查找 GC Root的方法找出是谁串起了这条引用线路，定位结束

PS :

·        很多时候堆增大是 Bitmap引起的，Bitmap在 Histogram中的类型是 byte [],对比两个 Histogram中的 byte[] 对象就可以找出哪些 Bitmap有差异

·        多使用排序功能，对找出差异很有用

2 内存泄漏的原因分析

总结出来只有一条：存在无效的引用!
良好的模块设计以及合理使用设计模式有助于解决此问题。

参考：

https://blog.csdn.net/liao0801_123/article/details/82900874

https://www.cnblogs.com/lovecindywang/p/10800593.html

http://blog.sina.com.cn/s/blog_73b4b91f0102wze4.html

内存溢出的原因及解决方法

1. 内存溢出原因：

1.内存中加载的数据量过于庞大，如一次从数据库取出过多数据；
2.集合类中有对对象的引用，使用完后未清空，使得JVM不能回收；
3.代码中存在死循环或循环产生过多重复的对象实体；
4.使用的第三方软件中的BUG；
5.启动参数内存值设定的过小

2. 内存溢出的原因及解决方法：

修改JVM启动参数，直接增加内存。(-Xms，-Xmx参数一定不要忘记加。)
检查错误日志，查看“OutOfMemory”错误前是否有其它异常或错误。
对代码进行走查和分析，找出可能发生内存溢出的位置。
使用内存查看工具动态查看内存使用情况

对代码分析找出可能发生内存溢出的位置，可能出现的几种情况：

1、检查对数据库查询中，是否有一次获得全部数据的查询。一般来说，如果一次取十万条记录到内存，就可能引起内存溢出。这个问题比较隐蔽，在上线前，数据库中数据较少，不容易出问题，上线后，数据库中数据多了，一次查询就有可能引起内存溢出。因此对于数据库查询尽量采用分页的方式查询。

2、检查代码中是否有死循环或递归调用。

3、检查是否有大循环重复产生新对象实体。

4、检查List、MAP等集合对象是否有使用完后，未清除的问题。List、MAP等集合对象会始终存有对对象的引用，使得这些对象不能被GC回收。

第九模块--个人

项目总结

关于三维模型搜索引擎项目相关度排序算法是怎么做的:

以文字搜模型:

基于Lucene文本搜索引擎，查找最匹配的；

以图片搜模型:

计算图片特征，对图片特征计算HashCode, 搜索的时候匹配HashCode;

以模型搜模型：

计算模型的特征得到n维特征矩阵，对特征矩阵计算HashCode, 搜索的时候匹配HashCode;

去重和检测url有效性是怎么做的：

对外网数据去重:

一开始直接使用条件逐个字段比较判断是否重复；

后来对关键字段连接建立联合哈希值保存，用这个哈希值去重；

后来想到其实外网的url是唯一的，直接对url建立哈希值来去重；后来设想直接用url哈希之后作为主键保存，建立聚集索引；

有效性检测比较简单:

使用java.net 下的类来实现，主要用到了 URL和HttpURLConnection :

刚开始使用openStream()方法，这样使用倒是可以，但是速度慢；

最后使用了getResponseCode（）方法，可以得到请求的响应状态，该方法返回一个 int 分别是 200 and 404 如无法从响应中识别任何代码则返回 -1, 如果对该url发起的5次请求都没有应答则认为链接失效;

你的项目用了哪些技术？

Lucene, Solr

MySQL,

Redis,

Java多线程

遇到过什么问题？你是怎么解决的？

去重的过程经历了多次迭代:

刚开始直接对记录逐个字段比较判断是否重复 ——>然后对关键字段建立HashCode作为标识，对比该Hash字段——>再是对外网URL建立HashCode对比;

有什么可以改进的地方？

可以对URL使用布隆过滤器做去重；（位图+多个哈希函数）

使用缓存数据库来提高并发访问；(缓存穿透（查询一个数据库一定不存在的数据），缓存击穿（一个key非常热点，在不停的扛着大并发，大并发集中对这一个点进行访问，当这个key在失效的瞬间，持续的大并发就穿破缓存），缓存雪崩（缓存集中过期失效）)

使用Elesticsearch来替代Solr（Elasticsearch是分布式的, 不需要其他组件，分发是实时的;solr需要结合依赖其他分布式组件来实现分布式）;

第九模块--待整理问题

阿里：

一面

全局唯一有序ID：

Snowflake, timestamp, 机器id等

冯诺伊曼体系：

shell命令的执行体系：

信息熵：

程序运行中的栈式结构

TCP/IP, TCP传输层加端口号，IP网络层加ip地址；路由器主要工作在IP网络层

各层常见的协议有哪些

同步与阻塞

并行与并发

java线程的本质、内核线程与用户进程，线程调度，并行级别

内核态与用户态，中断

CPU与内存与硬盘

缓存行与伪共享

内存分配管理，段业式 jemalloc

二面：

java程序的运行原理：

缓存行与伪共享

一个线程忙碌，多个线程闲置怎么解决

Java多线程引发的性能问题以及调优策略

多重继承会带来哪些问题

单点登陆

正向代理与反向代理

反爬机制，爬虫模拟浏览器行为

cglib方法拦截

动态代理

依赖注入

servlet的本质

TCP长连接心跳包 websocket

Netty 百万级长连接优化

DSL解析到AST

JVM 相关（gc的源码）

代码规范，包命名规范

现在流行的线程调度算法是什么(时间片轮转法)

项目用到了数据库，谈谈对事物的理解

假设你要做一个银行app，有可能碰到多个人同时向一个账户打钱的情况，有可能碰到什么问题，如何解决（还有可能出现重复提交的问题，保证服务的幂等性）

排序算法

给定一个文件名，如何在d盘找出这个文件

java对象头

知道哪些排序算法

快排怎么实现

堆排怎么实现

找出两个有序数组中的相同元素

常用集合框架

介绍下hashtable

快排如何实现

一个集合里有1000万个随机元素，快速求和(多线程)

排他锁的改进策略

map怎么实现

红黑树有什么特性

快排的思路讲一下

给大量的qq号，怎么排序(数据库外排)，问算法时间复杂度

代码:

数组里搜索第K大的数，非递归二分查找，链表相加

2019春招面试高频题(Java版)，持续更新(答案来自互联网)