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

Java多线程方法：

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

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

计算机资源=存储资源+计算资源
计算资源：由系统分配，操作系统按照一定的规则来分配什么时候由谁来获得CPU的计算资源（CPU是计算单元，对输入的数据和指令进行计算）
存储资源：就是内存，存储资源是操作系统管理和分配

1.进程
定义：一个程序在一个数据集上的一次运行
/一个程序在多个数据集上/一个程序在同一个数据集上运行多次/是不同的进程

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

2.线程：
定义：进程中的一个实体（进程中一段程序片段）

3.进程和线程的区别：
内存空间：
进程的内存空间是独立的，有独立的地址空间，不允许突破进程边界的存取其他进程的内存空间
线程共享同一进程中的内存空间（共享的是进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID）/（并且每个线程拥有自己的栈内存）

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

多个执行执行：
两个进程不能同时执行
多个线程可以同时执行
多线程程序只要有一个线程死掉，整个进程也死掉

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

  • 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.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。

线程的状态有几种

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. 创建线程池需要使用 ThreadPoolExecutor 类

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

corePoolSize: 表示常驻核心线程数。如果等于0，则任务执行完之后，没有任何请求进入时销毁线程池的线程；如果大于0，即使本地任务执行完毕，核心线程也不会被销毁。这个值的设置非常关键，设置过大会浪费资源，设置过小会导致线程频繁地创建或销毁。

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的时候，线程池通过该策略处理请求，这是一种简单的限流保护。

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

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

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的子类可以定义不同的资源实现不同性质的方法。

  1. 比如可重入锁ReentrantLock，定义state为0时可以获取资源并置为1。若已获得资源，state 不断加1，在释放资源时state减1，直至为0；
  2. CountDownLatch初始时定义了资源总量state=count，countDown()不断将state减1，当state=0时才能获得锁，释放后state就一直为0。所有线程调用await()都不会等待，所以CountDownLatch是一次性的，用完后如果再想用就只能重新创建一个；如果希望循环使用，推荐使用基于RentrantLock 实现的CyclicBarrier。
  3. 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。与互斥量类似，它不是通过休眠使进程阻塞，而是在获取锁之前一直处于忙等(自旋)阻塞状态。用在以下情况：锁持有的时间短，而且线程并不希望在重新调度上花太多的成本。"原地打转"。

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

 

Volatile关键字

每个线程都有独占的内存区域，如操作栈、本地变量表等。线程本地内存保存了引用变量在堆内存中的副本，线程对变量的所有操作都在本地内存区域中进行，执行结束后再同步到堆内存中去。这里必然有一个时间差，在这个时间差内，该线程对副本的操作，对于其他线程都是不可见的。
volatile的英文本义是“挥发、不稳定的”，延伸意义为敏感的。当使用volatile修饰变量时，意味着任何对此变量的操作都会在内存中进行，不会产生副本，以保证共享变量的可见性，局部阻止了指令重排的发生。

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

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

信号量同步

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

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

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

 

ThreadLocal 变量

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

我们看下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会根据此自动管理内存的分配与回收，不需要开发工程师干预。但在某些场景下，即使引用可达，也希望能够根据语义的强弱进行有选择的回收，以保证系统的正常运行。根据引用类型语义的强弱来决定垃圾回收的阶段，我们可以把引用分为强引用、软引用、弱引用和虚引用四类。后三类引用，本质上是可以让开发工程师通过代码方式来决定对象的垃圾回收时机。

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

  4. 虚引用，即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方法了。这就让阻塞的机会或者线程更少。让系统的性能更优越。

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)的实现原理

synchronized的机制

一段synchronized的代码被一个线程执行之前，要先拿到执行这段代码的权限，在 java里边就是拿到某个同步对象的锁（一个对象只有一把锁）； 如果这个时候同步对象的锁被其他线程拿走了，这个线程就只能等了（线程阻塞在锁池 等待队列中）。 取到锁后，该线程可以就开始执行同步代码(被synchronized修饰的代码）；线程执行完同步代码后马上就把锁还给同步对象，其他在锁池中 等待的某个线程就可以拿到锁执行同步代码了。这样就保证了同步代码在统一时刻只有一个线程在执行。

一个线程可以多次对同一个对象上锁（可重入锁）。对于每一个对象，java虚拟机维护一个加锁计数器，线程每获得一次该对象，计数器就加1，每释放一次，计数器就减 1，当计数器值为0时，锁就被完全释放了。

 

第二模块--计算机网路

TCP/IP结构有几层

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

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

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

解释TCP/IP 的三次握手

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

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

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

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

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

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

 

 

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

起初A和B处于ESTABLISHED状态

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

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

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

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

A经过等待计时器时间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协议的区别是什么

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

面向字节流 和面向报文：

用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的应用层协议有： SMTP、TELNET、HTTP、FTP

 

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

 

以下应用一般或必须用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没有。
  • 对参数的数据类型，GET只接受ASCII字符，而POST没有限制。
  • GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。GET提交的数据会放在URL之后，以?分割URL和传输数据，参数之间以&相连，如EditPosts.aspx?name=test1&id=123456. POST方法是把提交的数据放在HTTP包的Body中.
  • GET参数通过URL传递，POST放在Request body中。
  • GET产生一个TCP数据包；POST产生两个TCP数据包。

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协议的区别?

  1. http 是超文本传输协议，信息是明文传输，https 则是具有安全性的 ssl 加密传输协议。
  2. http 的连接很简单，是无状态的；HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，HTTPS为了数据传输的安全，在HTTP的基础上加入了SSL协议，SSL依靠证书来验证服务器的身份，并为浏览器和服务器之间的通信加密，比 http 协议安全。
  3. http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80，后者是 443。
  4. 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为一个用户浏览器独享

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

中间人攻击和重放攻击

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

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

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

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

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")

  1. 这是一个通用的服务器错误响应。对于大多数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”报文头属性告诉服务端 客户端接受什么类型的响应，常见的如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版本不支持等。

以下是几个常见的状态码： 
200 OK 
你最希望看到的，即处理成功！ 
303 See Other 
我把你redirect到其它的页面，目标的URL通过响应报文头的Location告诉你。

404 Not Found 

你最不希望看到的，即找不到页面。如你在google上找到一个页面，点击这个链接返回404，表示这个页面已经被网站删除了，google那边的记录只是美好的回忆。

 500 Internal Server Error

看到这个错误，你就应该查查服务端的日志了，肯定抛出了一堆异常，别睡了，起来改BUG去吧

 

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

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

浏览器会缓存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

kill杀死具体进程

# 加具体进程PID
​
kill 12345

杀死某进程相关进程

# 加上"-9"杀死某进程相关进程
​
kill -9 12345

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语言特性

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

面向过程

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

面向对象

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

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

 

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

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

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

类加载的双亲委任模型

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

 

JAVA类的加载过程

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

  1. 加载：程序运行之前jvm会把编译完成的.class二进制文件加载到内存，供程序使用，用到的就是类加载器classLoader 2、
  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这样的集合中正常工作。

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

 

HashMap底层是怎么实现的

数组加链表的形式

在JAVA 8 中，改进为，当链表长度达到3及以上，转为红黑树来实现

（因为长度为3的链表最坏查询次数是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来演示整个过程：

  1. 计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
  2. 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
  3. 把以上两个结果做与运算，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冲突的办法

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

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的问题：

  • 死链

主要发生在rezise时迁移数据的transfer()方法，put(),get()方法等

  • 高并发下的数据丢失

在表扩容时，当前线程迁移数据的过程中，其他线程新增的元素有可能落在迁移线程已经遍历过的哈希槽上；在遍历完成之后，table数组引用指向了newTable, 这时刚才新增的元素就会失去引用，被GC回收。或者多个线程同时执行resize，也会造成table的覆盖问题。新增对象丢失的原因一般有；

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

ConcurrentHashMap

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

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

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

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

 

待补充：

快排

 

索引

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接口。


什么是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中通过以下步骤实现不可变

  1. 对于属性不提供设值方法
  2. 所有的属性定义为private final
  3. 类声明为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更好的提高性能。
  • 线程安全： 当多线程访问时，不可变对象是线程安全的，不需要什么高深的逻辑解释，如果对象不可变，线程也不能改变它。

设计模式有哪些

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

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

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

工厂模式: 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(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。

       相比于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树不支持这样的操作（或者说效率太低）。

八大排序的特点

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

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

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

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

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

第六模块--数据库

Reids 支持的数据类型

Redis支持五种数据类型：

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

redis的替换策略

  • noeviction: 不进行置换，表示即使内存达到上限也不进行置换，所有能引起内存增加的命令都会返回error
  • allkeys-lru: 优先删除掉最近最不经常使用的key，用以保存新数据

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

数据库事物特性(acid)：

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

什么是事务？

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

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

张三向转账李四 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 是最高的事务隔离级别，同时代价也花费最高，性能很低，一般很少使用，在该级别下，事务顺序执行，不仅可以避免脏读、不可重复读，还避免了幻读。

解释数据库设计三大范式

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

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

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

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

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

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

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

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

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

数据库索引

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

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

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

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

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

非聚集（unclustered）索引。

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

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

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

 

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

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

哪些引擎支持聚集索引

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. 表中的其他列不能和主键直接相关，不符合数据库设计的第三范式；

 

数据库主键和外键

 

如何提高数据库查询效率

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

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

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

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

如何提高插入和修改效率

 

数据库

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

  • redis的hash算法用的是啥

一致性哈希算法

  • nosql为啥比sql快

nosql不需要满足sql关系数据库数据一致性等复杂特性，非关系型一般是缓存数据库，数据加载到内存中自然更快

  • 常见关系型数据库：

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的区别

  1. MyISAM：它是基于传统的ISAM类型，ISAM是Indexed Sequential Access Method (有索引的顺序访问方法) 的缩写，它是存储记录和文件的标准方法。不是事务安全的，而且不支持外键，如果执行大量的select，insert MyISAM比较适合。
  2. InnoDB：支持事务安全的引擎，支持外键、行锁、事务是他的最大特点。如果有大量的update和insert，建议使用InnoDB，特别是针对多个并发和QPS较高的情况。

  3. MyISAM索引实现：MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

  4. 在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

第七模块--算法题

 

LRU原理及其实现

 

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

 

实现

 

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

 

证明一个数是2的N次方

1、通过循环除2；这种方法不值一提，略过；

2、针对32位/64位只有有限个 2 的N次方的常量值，逐个进行比较；额。。。这个也略过；

3、通过正则表达式进行文本匹配，判断是否2的后面都是 0 ；这个绕得更远了。。。

4、最后，有一种最简洁优雅的写法：(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字节码动态地编译成可以直接发送给处理器指令执行地机器码。

内存布局：

本地方法栈(Native Method Stacks)

程序计数器(Program Counter Register)

虚拟机栈(JVM Stacks)

堆区(Heap)

永久代（元数据区 Metaspace）

堆区(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对象可以是：类静态属性中引用的对象、常量引用的对象、虚拟机栈中引用的对象、本地方法栈中引用的对象等。

  • 垃圾回收算法

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

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

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

  1. Serial回收器是一个主要应用于YGC的垃圾回收器，采用串行单线程的方式完成GC任务，其中“Stop The World”简称STW，即垃圾回收的某个阶段会暂停整个应用程序的执行。FGC的时间相对较长，频繁FGC会严重影响应用程序的性能
  2. 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再在老年代执行空间碎片整理。
  3. G1回收器 是HotSpot在JDK7中推出的新一代G1垃圾回收器，在JDK11中，G1是默认的回收器。G1采用的是”Mark-Copy“，有较好的空间整理能力，不会产生大量空间碎片。G1的优势是具有可预测的停顿时间，能够尽快在指定时间完成垃圾回收任务。
  4. 另外还有在JDK11中引入的实验性的ZGC，是一个可伸缩的低延迟垃圾收集器。

怎样分析查找OOM的原因

  1. 使用jmap将当前的内存 Dump成一个 hprof格式的文件，MAT 读取这个文件后会给出方便阅读的信息，配合它的查找，对比功能，就可以定位内存泄漏的原因。
  2. 用的最多的功能是 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

第九模块--个人

 

项目总结

关于三维模型搜索引擎项目相关度排序算法是怎么做的:

以文字搜模型:

基于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大的数，非递归二分查找，链表相加