一 Java基础+集合+多线程+JVM

1.1 Java基础

1.1.1 Java基础知识

（1）Java的特点？

面向对象（封装、继承、多态）
Java和平台无关，一次编译，多地运行
编译和解释并存：Java源码→（javac编译）→.class字节码→（JVM解释）→机器码
- 为了加速解释过程，引入运行时编译，即JIT，当 JIT 编译器完成第一次编译后，会将字节码对应的机器码保存下来，下次可以直接使用。
支持网络编程和多线程，能很方便地编写出多线程程序和网络程序。
自动内存管理，无需像C++一样要手动管理内存。

（2）面向过程和面向对象？

面向过程：分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。

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

面向对象：把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在整个解决问题的步骤中的行为。

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

（3） JVM、JDK、JRE的区别和联系？

JVM，Java Virtual Machine：运行Java字节码的虚拟机，在不同平台上有不同的实现（win、linux、macos），是Java语言跨平台的基础。
JRE，Java Runtime Environment：Java运行时环境，是运行已编译Java程序所需要内容的集合，包括Java虚拟机（JVM），Java类库，java命令和其他一些基础组件，但是它不能创建新程序。
JDK，Java Development Kit：它是JRE的超集，还包括编译器javac、工具如javadoc、jdb等，能够创建、编译和调试Java程序。

（4） Java和C++的区别和联系

Java是面向对象的语言，C++既可以面向对象，也可以面向过程。
Java不能操作指针，更加安全，C++可以操作指针，更加灵活。
Java有自动内存管理机制，无需程序员手动释放内存，而C++需要。
Java的类只支持单继承，C++类支持多继承，Java接口可以多继承。
C/C++的字符串以’\0’表示结束，但Java中没有这一概念。原因：Java中一切都是对象，字符串对象本身会记录自己的长度，无需浪费额外的空间存储’\0’。

（5）为什么说Java编译和解释并存？

Java编写的程序首先需要进行编译，生成字节码文件*.class，这种文件必须由Java解释器来解释执行，同时为了加快解释速度，引入运行时编译JIT，当 JIT 编译器完成第一次编译后，会将字节码对应的机器码保存下来，下次可以直接使用。

![Java程序运行过程](java-all-in-one/Java 程序运行过程.png)

（6）字符型常量和字符串常量的区别？

形式上：字符常量是单引号引起的一个字符；字符串常量是双引号引起的0个或多个字符。
含义上：字符常量相当于一个整型值，可以参与表达式运算；字符串常量代表字符串在内存中存放的位置。
占内存大小：字符常量占用2字节；字符串常量占用若干字节。

（7）重载和重写的区别？

重载：同样的一个方法能够根据输入数据的不同，做出不同的处理。
重写：当子类继承自父类的相同方法，输入数据一样，但要做出有别于父类的响应时，就要对父类方法进行覆盖，这个过程就叫重写。

以下方法无法被重写：

返回值类型、方法名、参数列表必须相同，抛出的异常范围小于等于父类，访问修饰符范围大于等于父类。

如果父类方法访问修饰符为 private/final/static 则子类就不能重写该方法，但是被 static 修饰的方法能够被再次声明。

构造方法无法被重写

区别点	重载方法	重写方法
发生范围	同一个类	子类
参数列表	必须修改	一定不能修改
返回类型	可修改	子类方法返回值类型应比父类方法返回值类型更小或相等
异常	可修改	子类方法声明抛出的异常类应比父类方法声明抛出的异常类更小或相等；
访问修饰符	可修改	一定不能做更严格的限制（可以降低限制）
发生阶段	编译期	运行期

（8）== 和 equals 的区别？⭐

== ：如果是基本数据类型，==比较的是值是否相同；如果是引用数据类型，==比较的是内存地址是否相等。
equals()：所有对象的父类Object提供的方法，用于判断两个对象是否相等。分为两种情况：如果子类没有重写equals，效果等同于==。如果子类覆盖了equals()方法，通常用来比较两个对象的值是否相同。
String 中的 equals 方法被重写过，判断两个String对象相等的方法：s1.equals(s2) == true或者s1.compareTo(s2) == 0

（9）hashCode()与equals()⭐

说一说hashCode()？

hashCode() 定义在Object类中，Java中的任何类都含有hashCode()方法。它的作用是获取哈希码，即一个int整数，用于确定该对象在哈希表中的索引位置。

为什么要有hashCode？

加快对象比较的速度，在插入Map时有很大的作用。如果两个对象的hashCode不同，则这两个对象一定不等，如果hashCode相等，可以再比较对象的值，大大减少了 equals 的次数，相应就大大提高了执行速度。

为什么重写equals时必须要重写hashCode？

equals方法内部会调用 hashcode 只是用来缩小查找成本，而hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等。

为什么两个对象拥有相同的hashcode它们也不一定想等？

因为 hashCode() 所使用的杂凑算法也许刚好会让多个对象传回相同的杂凑值。越糟糕的杂凑算法越容易碰撞，但这也与数据值域分布的特性有关（所谓碰撞也就是指的是不同的对象得到相同的 hashCode。

我们刚刚也提到了 HashSet,如果 HashSet 在对比的时候，同样的 hashcode 有多个对象，它会使用 equals() 来判断是否真的相同。也就是说 hashcode 只是用来缩小查找成本。

（10）自动装箱和自动拆箱

装箱：将基本类型用它们对应的引用类型包装起来；
拆箱：将包装类型转换为基本数据类型；

（11）常量池

Java基本类型的包装类大部分（Byte、Short、Integer、Long、Character、Boolean）都实现了常量池，前面4种包装类创建了数值[-128,127]的缓存数据，Character创建了[0,127]范围内的缓存数据，Boolean直接返回True or False，如果超出范围仍然会创建新的对象。

 public static void main(String[] args) {
    Integer i0 = 127;
    Integer i1 = 127;
    System.out.println(i0 == i1);// true

    Integer i2 = 128;
    Integer i3 = 128;
    System.out.println(i2 == i3); // false

    Integer i4 = 40;
    Integer i5 = 10;
    Integer i6 = 30;
    System.out.println(i4 == i5 + i6); // true
    System.out.println(40 == i5 + i6); // true
    // 语句 i4 == i5 + i6
    // 因为+这个操作符不适用于 Integer 对象
    // 首先 i5 和 i6 进行自动拆箱操作，进行数值相加，即 i4 == 40
    // 然后 Integer 对象无法与数值进行直接比较，所以 i4 自动拆箱转为 int 值 40
    // 最终这条语句转为 40 == 40 进行数值比较。
}

（12）深拷贝和浅拷贝

浅拷贝：对基本数据类型进行值传递，对引用数据类型进行引用传递的拷贝
深拷贝：对基本数据类型进行值传递，对引用数据类型，创建一个新的对象，并复制其内容

deep and shallow copy

（13）`StringBuffer`和`StringBuilder`的区别和联系？

底层采用char[]保存数据，具有公共父类AbstractStringBuilder

StringBuffer：线程安全，效率低
StringBuilder：线程不安全，效率高

（14）`String`为什么是不可变的？

String对象用private final char value[]保存字符串，因此不可变（JDK 9 之后采用private final byte value[]保存）

jdk9之前采用utf-16保存，一个char占用2字节，因此ascii码字符有一个字节填充0，浪费空间；jdk9之后采用编码节省空间，部分字符仅占用1字节。

（15）一个char占用多少字节？

java中的一个char占用2个字节。java采用unicode，2个字节来表示一个字符。一个数字或英文或汉字都是一个字符，只不过数字和英文时，存储的2个字节的第一个字节都为0，就是浪费了点空间。存汉字就占满了2个字节。

1.1.2 面向对象

（1）面向对象的三大特性：封装、继承、多态

封装：将对象的一些属性或方法隐藏在内部，不允许外部对象直接访问对象信息，但可以给外部提供一些方法来操作属性。
继承：
- 子类拥有父类的所有属性和方法，包括私有的，但私有的只是拥有，无法访问。
- 子类可以拓展父类，拥有自己的属性和方法。
- 子类可以重写父类方法进行覆盖。
多态：父类指向子类的实例
- 对象类型和引用类型之间具有继承（类）/实现（接口）的关系；
- 引用类型变量发出的方法调用的到底是哪个类中的方法，必须在程序运行期间才能确定；
- 多态不能调用“只在子类存在但在父类不存在”的方法；
- 如果子类重写了父类的方法，真正执行的是子类覆盖的方法，如果子类没有覆盖父类的方法，执行的是父类的方法。

（2）成员变量和局部变量的区别？

成员变量属于对象，对象存在于堆内存，局部变量则存在于栈内存。特别地，被static修饰的成员变量属于类，位于方法区。

（3）对象相等和它们的引用相等

对象相等：对象保存在内存中的数据相等
引用相等：对象的内存地址相等

（4）final关键字

修饰变量：变量数值在初始化后不能被更改（可以利用反射机制修改）

修饰方法：不能被子类重写覆盖（可以利用动态代理机制修改）

修饰类：类不能被继承，类中所有成员方法会被隐式地指定为final方法

（5）一个空字符串占用多少字节

空字符串是一个对象，一个对象包含：对象头、实例数据、对齐填充

对象头：8字节（32位系统下）、16字节（64位系统下）、12字节（64位系统下开启指针压缩）

实例数据：（32位系统下）

String{
    private final char value[];
    private int hash;
    private static final long serialVersionUID = -6849794470754667710L;	
}

char[]的引用：4字节

hash：4字节

long的引用：4字节

总共是8+12=20字节，考虑对齐填充需要为8的倍数，总共占用24字节

（6）String Pool的底层结构

String的String Pool是一个固定大小的Hashtable，默认值大小长度是1009。

1.1.3 异常

（1）异常的分类

在 Java 中，所有的异常都有⼀个共同的祖先 java.lang 包中的 Throwable 类。Throwable：有两个重要的⼦类：Exception（异常）和 Error（错误）

Error：程序无法处理，例如虚拟机运行错误，错误发生时JVM一般会选择线程终止

Exception：程序可以处理，使用catch捕获

（2）异常处理

try：⽤于捕获异常。其后可接零个或多个 catch 块，如果没有 catch 块，则必须跟⼀个 finally 块

catch：⽤于处理 try 捕获到的异常

finally：⽆论是否捕获或处理异常， finally 块⾥的语句都会被执⾏。当在 try 块或 catch 块中遇到 return 语句时， finally 语句块将在⽅法返回之前被执⾏

不执行finally的情形：

使用System.exit()退出程序
程序所在线程死亡
关闭CPU

1.1.4 Java IO

（1）IO流分类

按数据单位：字节流（8bit）、字符流（16bit）
按数据流向：输入流、输出流
按流的角色：节点流、处理流

抽象基类	字节流	字符流
输入流	InputStream	Reader
输出流	OutputStream	Wrider

（2）BIO、NIO、AIO地区别

BIO (Blocking I/O): 同步阻塞 I/O 模式，数据的读取写⼊必须阻塞在⼀个线程内等待其完成。在活动连接数不是特别⾼（⼩于单机 1000）的情况下，这种模型是⽐较不错的，可以让每⼀个连接专注于⾃⼰的 I/O 并且编程模型简单，也不⽤过多考虑系统的过载、限流等问题。线程池本身就是⼀个天然的漏⽃，可以缓冲⼀些系统处理不了的连接或请求。但是，当⾯对⼗万甚⾄百万级连接的时候，传统的 BIO 模型是⽆能为⼒的。因此，我们需要⼀种更⾼效的 I/O 处理模型来应对更⾼的并发量。

NIO (Non-blocking/New I/O): NIO 是⼀种同步⾮阻塞的 I/O 模型，在 Java 1.4 中引⼊了 NIO 框架，对应 java.nio 包，提供了 Channel , Selector，Buffer 等抽象。NIO 中的 N 可以理解为 Non-blocking，不单纯是 New。它⽀持⾯向缓冲的，基于通道的 I/O 操作⽅法。 NIO 提供了与传统 BIO 模型中的 Socket 和 ServerSocket 相对应的 SocketChannel 和 ServerSocketChannel 两种不同的套接字通道实现,两种通道都⽀持阻塞和⾮阻塞两种模式。阻塞模式使⽤就像传统中的⽀持⼀样，⽐较简单，但是性能和可靠性都不好；⾮阻塞模式正好与之相反。对于低负载、低并发的应⽤程序，可以使⽤同步阻塞 I/O 来提升开发速率和更好的维护性；对于⾼负载、⾼并发的（⽹络）应⽤，应使⽤ NIO 的⾮阻塞模式来开发

AIO (Asynchronous I/O): AIO 也就是 NIO 2。在 Java 7 中引⼊了 NIO 的改进版 NIO 2,它是异步⾮阻塞的 IO 模型。异步 IO 是基于事件和回调机制实现的，也就是应⽤操作之后会直接返回，不会堵塞在那⾥，当后台处理完成，操作系统会通知相应的线程进⾏后续的操作。AIO 是异步 IO 的缩写，虽然 NIO 在⽹络操作中，提供了⾮阻塞的⽅法，但是 NIO 的 IO ⾏为还是同步的。对于 NIO 来说，我们的业务线程是在 IO 操作准备好时，得到通知，接着就由这个线程⾃⾏进⾏ IO 操作，IO 操作本身是同步的。查阅⽹上相关资料，我发现就⽬前来说 AIO 的应⽤还不是很⼴泛，Netty 之前也尝试使⽤过 AIO，不过⼜放弃了。

BIO (Blocking I/O)，即同步阻塞I/O，用户发起I/O请求会会一直阻塞，直到内核把数据拷贝到用户空间，不适合高并发场景。

NIO (Non-blocking/New I/O)，即同步非阻塞 IO
- 应用程序会一直发起 read 调用，等待数据内核把数据拷贝到用户空间。
- 优点：相比于BIO，同步非阻塞 IO 通过轮询操作，避免了一直阻塞。
- 缺点：轮询过程消耗 CPU 资源。

NIO的I/O 多路复用模型
- 线程首先发起 select 调用，询问内核数据是否准备就绪，等内核把数据准备好了，用户线程再发起 read 调用。
- 优点：通过减少无效的系统调用，减少了对 CPU 资源的消耗。

AIO (Asynchronous I/O)
- AIO 是基于事件和回调机制实现的，也就是应用操作之后会直接返回，不会堵塞在那里，当后台处理完成，操作系统会通知相应的线程进行后续的操作。

Summary

1.1.5 程序、进程和线程

（1）程序、进程、线程的定义

程序：含有指令和数据的文件，被存储在磁盘或其他的数据存储设备中，也就是说程序是静态的代码。
进程：正在运行的一个程序。是资源分配的单位。
线程：进程可进一步细化为线程，是一个程序内部的一条执行路径。是调度和执行的单位。

1.1.6 String类和常量池

（1）String

 	@Test
    void test() {
        String str1 = "abcd";//如果字符串常量池中没有"abcd"，则创建一个，然后 str1 指向字符串常量池中的对象，如果有，则直接将 str1 指向"abcd"；
        String str2 = new String("abcd");//堆中创建一个新对象
        String str3 = new String("abcd");//堆中创建一个新对象
        String str4 = new StringBuilder("ab").append("cd").toString();//堆中创建一个新对象
        String str5 = new StringBuilder("ab").append("cd").toString();//堆中创建一个新对象
        String str6 = new StringBuilder("ab").append("cd").toString().intern();//常量池中有"abcd"，因此str6指向它

        System.out.println("str1:" + System.identityHashCode(str1));
        System.out.println("str2:" + System.identityHashCode(str2));
        System.out.println("str3:" + System.identityHashCode(str3));
        System.out.println("str4:" + System.identityHashCode(str4));
        System.out.println("str5:" + System.identityHashCode(str5));
        System.out.println("str6:" + System.identityHashCode(str6));
    }

/*
str1:711327356
str2:1297978429
str3:915349526
str4:1280851663
str5:1764696127
str6:711327356
*/

只要使用 new 方法，便需要创建新的对象。

intern()方法：如果运行时常量池中已经包含一个等于此 String 对象内容的字符串，则返回常量池中该字符串的引用；如果没有，JDK1.6及之前的处理方式是在常量池中创建与此 String 内容相同的字符串，并返回常量池中创建的字符串的引用，JDK1.7及之后的处理方式是在常量池中记录此字符串的引用，并返回该引用。

（2）String s=new String(“xyz”)会创建几个对象

1个或2个。首先去找字符串常量池找，看能不能找到“xyz”字符串对应对象的引用。

如果字符串常量池中找不到：

在常量池创建一个String对象和char数组对象，并将String对象放到字符串常量池中

字符串常量池：将创建的String对象封装成HashtableEntry，作为StringTable的value进行存储，本是上是一个HashTable

new String(“xyz”)会在堆区又创建一个String对象，char数组直接指向创建好的char数组对象

如果字符串常量池中能找到：

new String(“xyz”)会在堆区创建一个对象，char数组直接指向已经存在的char数组对象

同时在栈区还会有一个对new出来的String实例的引用s。

String s1 = new String(“xyz”);

String s2 = “xyz”;

1.2 集合

1.2.1 常见容器的比较

（1）List、Set、Map的比较

List：保存的元素是可重复、有序的。
Set：保存的元素是不可重复、无序的。
Map：使用Key-Value存储，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

（2）ArrayList和Vector的区别

ArrayList是List的主要实现类，底层采用Object[]存储，线程不安全，效率高。
Vector是List的古老实现类，底层采用Object[]存储，线程安全，效率低。

（3）ArrayList和LinkedList区别

线程安全性：都是线程不安全的.
底层数据结构：ArrayList底层采用**Object[]，LinkedList底层采用双向链表**.
插入或删除元素
- ArrayList采用数组存储，在非尾部插入元素会产生数据移动，时间复杂度O(n)。
- LinkedList采用链表存储，插入元素时不会产生数据移动，时间复杂度O(n)。
快速随机访问
- ArrayList支持，LinkedList不支持。
内存空间占用
- ArrayList会预留一定的空间保存新的元素，LinkedList的每一个元素需要更多的空间保存（前继和后继）

（4）HashMap和HashTable的区别

线程安全性：HashMap线程不安全，HashTable线程安全（因为其内部的方法都通过synchronized修饰）。
效率：HashMap效率高，HashTable因锁的原因效率低。
对null的支持：HashMap可以存储值为null的key和value，HashTable不允许。
初始容量大小和扩容机制：HashTable默认大小为11，扩容为2n+1；HashMap初始大小为16，扩容为2n。
底层数据结构：数据+链表；JDK1.8之后，HashMap发生了变化：当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

（5）HashSet、LinkedHashSet、TreeSet的异同

HashSet是Set的主要实现类，HashSet的底层是HashMap，线程不安全，可存储null值

LinkedHashSet是HashSet的子类，能够按照元素添加的顺序遍历

TreeSet底层使用红黑树，能够按照添加元素的顺序遍历，排序的方式有自然排序和定制排序

（6）无序性和不可重复性的含义是什么？

无序性：存储对象在底层数据结构中的位置不是由对象插入的顺序决定的，而是根据对象的哈希值决定的。
不可重复性：不重复的对象指使用equals()比较时返回false。

（7）Comparable和Comparator的区别

Comparable接口位于java.lang包，它有一个compareTo(Object obj)方法来排序，是一个内比较器。
Comparator接口位于java.util包，它有一个compare(Object obj1, Object obj2)方法来排序，是一个外比较器。
集合自定义排序：重写compareTo()方法或compare()方法。

1.2.2 容器结构的底层实现

（1） List、Set、Map

List
- ArrayList：**Object[]**，List的常见实现类，线程不安全。
- Vector：**Object[]**，List的古老实现类，线程安全。
- LinkedList：双向链表，JDK7之前采用双向循环链表
Set
- HashSet：基于HashMap实现。
- LinkedHashSet：基于LinkedHashMap实现。
Map
- HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 及以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。是Map的常见实现类，线程
- HashTable：数组+链表，Map的古老实现类，线程安全。
- LinkedHashMap：在HashMap的基础上增加了一个双向链表，用来记录键值对的插入顺序，通过链表实现了访问顺序的相关逻辑
- TreeMap：红黑树。

（2）ArrayList的扩容机制

https://snailclimb.gitee.io/javaguide/#/docs/java/collection/ArrayList%E6%BA%90%E7%A0%81+%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6%E5%88%86%E6%9E%90

（3）HashMap的底层实现

JDK1.8之前： 数组和链表 结合在一起，即 链表散列，使用拉链法解决哈希冲突。

JDK1.8及之后：当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

（4）HashSet如何检查重复

会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

（5）HashMap 的⻓度为什么是2的幂次⽅

为了能让 HashMap 存取⾼效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上⾯也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得⽐较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。（n代表数组⻓度）。这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。
这个算法应该如何设计呢？
我们⾸先可能会想到采⽤%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作（也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的 n 次⽅；）。” 并且采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次⽅。

1.2.3 ConcurrentHashmap

（1）ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashTable

ConcurrentHashMap（JDK1.7）：Segment 数组 + HashEntry 数组 + 链表

ConcurrentHashMap（JDK1.8）：Node 数组 + 链表 / 红黑树，冲突链表达到一定长度时，链表会转换成红黑树。

Java8 ConcurrentHashMap 存储结构（图片来自 javadoop）

（2）ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

//ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
//Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

（3）ConcurrentHashMap读写过程（JDK1.7）

Get方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象。

3.再次通过hash值，定位到Segment当中数组的具体位置。

Put方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象。

3.获取可重入锁。

4.再次通过hash值，定位到Segment当中数组的具体位置。

5.插入或覆盖HashEntry对象。

6.释放锁。

size方法：

1.遍历所有的Segment。

2.把Segment的元素数量累加起来。

3.把Segment的修改次数累加起来。

4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。

5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。

6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经全部加锁，统计过程中肯定没有修改，统计的一定是正确的结果。

7.释放锁，统计结束。

1.3 多线程

1.3.1 基本概念

（1）什么是进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配的基本单位。

（2）什么是线程

线程是程序的一条执行路径，是现代操作系统调度的基本单位。

在Java中，同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈。

（3）什么是协程

协程，英文Coroutines，是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。

协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。

（4）进程和线程的关系

进程是系统运行程序和资源分配的基本单位，线程是系统调度的基本单位。

进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动
区别：
- 程序是指令的有序集合，是一个静态概念
- 进程是一个能独立运行的单位，能与其他进程并行地活动
- 线程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。

（5）线程的上下文切换

当前任务在执⾏完 CPU 时间⽚切换到另⼀个任务之前会先保存⾃⼰的状态，以便下次再切换回这个任务时，可以再加载这个任务的状态。任务从保存到再加载的过程就是⼀次上下⽂切换

（6）并发和并行的区别

并发：同一时间段内，多个任务都执行了（例如时间片法）

并行：同一时刻，执行多个任务（例如多核）

（7）为什么使用多线程？

从计算机底层来说：计算机有多任务调度的需求，最早是基于进程实现的多任务调度，但是进程切换成本较高，由此诞生了更加轻量的线程，满足多任务调度需求。

从互联网发展趋势来说：现在的系统动不动就要求百万级甚至千万级的并发量，而多线程并发编程正是开发高并发系统的基础，利用好多线程机制可以大大提高系统整体的并发能力以及性能。

（8）使用多线程带来的问题

内存泄漏

一致性问题（线程同步）

死锁

（9）内核线程实现

使用内核线程实现的方式也被称为1：1实现。内核线程（Kernel-Level Thread，KLT）就是直接由操作系统内核（Kernel，下称内核）支持的线程，这种线程由内核来完成线程切换，内核通过操纵调度器（Scheduler）对线程进行调度，并负责将线程的任务映射到各个处理器上。每个内核线程可以视为内核的一个分身，这样操作系统就有能力同时处理多件事情，支持多线程的内核就称为多线程内核（Multi-Threads Kernel）。

内核线程（Kernel-Level Thread，KLT）

轻量级进程（Light Weight Process，LWP）

一个进程（P）拥有多个线程（LWP），每一个LWP被映射为KLT，由线程调度器调度到物理CPU上执行。

（10）用户线程实现

即协程

（11）上下文切换

当线程发生中断，或者用完当前时间片，就会触发上下文切换，操作系统会将CPU的使用权分配给其他线程。

保护现场、恢复现场。

1.3.2 Java的多线程

（1）程序计数器为什么是私有的？

每个线程拥有不同的执行路径，因此需要程序计数器来记录当前执行到的位置，保证线程切换后能恢复到正确的执行位置。

（2）虚拟机栈和本地方法栈为什么是私有的？

每个线程的方法拥有自己独立的栈帧，以保证线程中的局部变量不被别的线程访问到。

（3）堆和方法区

堆和方法区为进程所有，由线程共享。

堆主要用于存放新创建的对象；方法区主要用去存放编译后的代码等信息（例如已被加载的类信息、常量、静态变量）

（4）线程的生命周期和状态

（5）sleep() 和 wait()

两者最主要的区别在于：**sleep() 方法没有释放锁，而 wait() 方法释放了锁** 。
两者都可以暂停线程的执行。
wait() 通常被用于线程间交互/通信，sleep() 通常被用于暂停执行。
wait() 方法被调用后，线程不会自动苏醒，需要别的线程调用同一个对象上的 notify() 或者 notifyAll() 方法。sleep() 方法执行完成后，线程会自动苏醒。或者可以使用 wait(long timeout) 超时后线程会自动苏醒。

（6）start() 和 run()

new 一个 Thread，线程进入了新建状态。调用 start()方法，会启动一个线程并使线程进入了就绪状态，当分配到时间片后就可以开始运行了。 start() 会执行线程的相应准备工作，然后自动执行 run() 方法的内容，这是真正的多线程工作。但是，直接执行 run() 方法，会把 run() 方法当成一个 main 线程下的普通方法去执行，并不会在某个线程中执行它，所以这并不是多线程工作。

总结：调用 start() 方法方可启动线程并使线程进入就绪状态，直接执行 run() 方法的话不会以多线程的方式执行。

1.3.3 synchronized

（1）synchronized关键字

synchronized关键字解决的是多个线程之间访问资源的同步性，synchronized关键字可以保证被它修饰的⽅法或者代码块在任意时刻只能有⼀个线程执⾏。另外，在 Java 早期版本中，synchronized属于重量级锁，效率低下，因为监视器锁（monitor）是依赖于底层的操作系统的 Mutex Lock 来实现的，Java 的线程是映射到操作系统的原⽣线程之上的。如果要挂起或者唤醒⼀个线程，都需要操作系统帮忙完成，⽽操作系统实现线程之间的切换时需要从⽤户态转换到内核态，这个状态之间的转换需要相对⽐较⻓的时间，时间成本相对较⾼，这也是为什么早期的 synchronized 效率低的原因。庆幸的是在 Java 6 之后 Java 官⽅对从 JVM 层⾯对synchronized 较⼤优化，所以现在的 synchronized 锁效率也优化得很不错了。JDK1.6对锁的实现引⼊了⼤量的优化，如⾃旋锁、适应性⾃旋锁、锁消除、锁粗化、偏向锁、轻量级锁等技术来减少锁操作的开销

（2）synchronized的三种使用方式

修饰实例⽅法: 作⽤于当前对象实例加锁，进⼊同步代码前要获得当前对象实例的锁

修饰静态⽅法: 也就是给当前类加锁，会作⽤于类的所有对象实例，因为静态成员不属于任何⼀个实例对象，是类成员（ static 表明这是该类的⼀个静态资源，不管new了多少个对象，只有⼀份）。所以如果⼀个线程A调⽤⼀个实例对象的⾮静态 synchronized ⽅法，⽽线程B需要调⽤这个实例对象所属类的静态synchronized ⽅法，是允许的，不会发⽣互斥现象，因为访问静态 synchronized ⽅法占⽤的锁是当前类的锁，⽽访问⾮静态 synchronized ⽅法占⽤的锁是当前实例对象锁。

修饰代码块: 指定加锁对象，对给定对象加锁，进⼊同步代码库前要获得给定对象的锁。

总结： synchronized 关键字加到 static 静态⽅法和 synchronized(class)代码块上都是是给 Class 类上锁。synchronized 关键字加到实例⽅法上是给对象实例上锁。尽量不要使⽤ synchronized(String a) 因为JVM中，字符串常量池具有缓存功能！

（3）synchronized底层原理

（4）JDK1.6之后对synchronized做的优化

JDK1.6 对锁的实现引⼊了⼤量的优化，如偏向锁、轻量级锁、⾃旋锁、适应性⾃旋锁、锁消除、锁粗化等技术来减少锁操作的开销。
锁主要存在四种状态，依次是：⽆锁状态、偏向锁状态、轻量级锁状态、重量级锁状态，他们会随着竞争的激烈⽽逐渐升级。注意锁可以升级不可降级，这种策略是为了提⾼获得锁和释放锁的效率。

（5）synchronized和ReentrantLock的区别

① 两者都是可重⼊锁
两者都是可重⼊锁。“可重⼊锁”概念是：⾃⼰可以再次获取⾃⼰的内部锁。⽐如⼀个线程获得了某个对象的锁，此时这个对象锁还没有释放，当其再次想要获取这个对象的锁的时候还是可以获取的，如果不可锁重⼊的话，就会造成死锁。同⼀个线程每次获取锁，锁的计数器都⾃增1，所以要等到锁的计数器下降为0时才能释放锁。

② synchronized 依赖于 JVM ⽽ ReentrantLock 依赖于 API
synchronized 是依赖于 JVM 实现的，前⾯我们也讲到了虚拟机团队在 JDK1.6 为 synchronized 关键字进⾏了很多优化，但是这些优化都是在虚拟机层⾯实现的，并没有直接暴露给我们。 ReentrantLock 是 JDK 层⾯实现的（也就是 API 层⾯，需要 lock() 和 unlock() ⽅法配合 try/finally 语句块来完成），所以我们可以通过查看它的源代码，来看它是如何实现的。

③ ReentrantLock ⽐ synchronized 增加了⼀些⾼级功能

相⽐synchronized，ReentrantLock增加了⼀些⾼级功能。主要来说主要有三点：①等待可中断；②可实现公平锁；③可实现选择性通知（锁可以绑定多个条件）

ReentrantLock提供了⼀种能够中断等待锁的线程的机制，通过lock.lockInterruptibly()来实现这个机制。也就是说正在等待的线程可以选择放弃等待，改为处理其他事情。

ReentrantLock可以指定是公平锁还是⾮公平锁。⽽synchronized只能是⾮公平锁。所谓的公平锁就是先等待的线程先获得锁。 ReentrantLock默认情况是⾮公平的，可以通过 ReentrantLock 类的ReentrantLock(boolean fair)构造⽅法来制定是否是公平的。

synchronized关键字与wait()和notify()/notifyAll()⽅法相结合可以实现等待/通知机制， ReentrantLock类当然也可以实现，但是需要借助于Condition接⼝与newCondition() ⽅法。 Condition是JDK1.5之后才有的，它具有很好的灵活性，⽐如可以实现多路通知功能也就是在⼀个Lock对象中可以创建多个Condition实例（即对象监视器），线程对象可以注册在指定的 Condition中，从⽽可以有选择性的进⾏线程通知，在调度线程上更加灵活。在使⽤ notify()/notifyAll()⽅法进⾏通知时，被通知的线程是由 JVM 选择的，⽤ReentrantLock类结合Condition实例可以实现“选择性通知” ，这个功能⾮常重要，⽽且是Condition接⼝默认提供的。⽽synchronized关键字就相当于整个Lock对象中只有⼀个Condition实例，所有的线程都注册在它⼀个身上。如果执⾏notifyAll()⽅法的话就会通知所有处于等待状态的线程这样会造成很⼤的效率问题，⽽Condition实例的signalAll()⽅法只会唤醒注册在该Condition实例中的所有等待线程。

（6）volatile关键字和Java内存模型

在 JDK1.2 之前，Java的内存模型实现总是从主存（即共享内存）读取变量，是不需要进⾏特别的注意的。⽽在当前的 Java 内存模型下，线程可以把变量保存本地内存（⽐如机器的寄存器）中，⽽不是直接在主存中进⾏读写。这就可能造成⼀个线程在主存中修改了⼀个变量的值，⽽另外⼀个线程还继续使⽤它在寄存器中的变量值的拷⻉，造成数据的不⼀致。
要解决这个问题，就需要把变量声明为 volatile ，这就指示 JVM，这个变量是共享且不稳定的，每次使⽤它都到主存中进⾏读取。所以， volatile 关键字除了防⽌ JVM 的指令重排，还有⼀个重要的作⽤就是保证变量的可见性

（7）并发编程的三个重要特性

原⼦性 : ⼀个的操作或者多次操作，要么所有的操作全部都得到执⾏并且不会收到任何因素的⼲扰⽽中断，要么所有的操作都执⾏，要么都不执⾏。synchronized 可以保证代码⽚段的原⼦性。

可⻅性：当⼀个变量对共享变量进⾏了修改，那么另外的线程都是⽴即可以看到修改后的最新值。volatile 关键字可以保证共享变量的可⻅性。

有序性：代码在执⾏的过程中的先后顺序，Java 在编译器以及运⾏期间的优化，代码的执⾏顺序未必就是编写代码时候的顺序。volatile 关键字可以禁⽌指令进⾏重排序优化。

（8）说说 synchronized 关键字和 volatile 关键字的区别

volatile关键字是线程同步的轻量级实现，所以volatile性能肯定⽐synchronized关键字要好。但是volatile关键字只能⽤于变量⽽synchronized关键字可以修饰⽅法以及代码块。

volatile关键字能保证数据的可⻅性，但不能保证数据的原⼦性。synchronized关键字两者都能保证。

volatile关键字主要⽤于解决变量在多个线程之间的可⻅性，⽽ synchronized关键字解决的是多个线程之间访问资源的同步性。

1.3.4 ThreadLocal

1.3.5 线程池

（1）为什么要使用线程池？

降低资源消耗：通过重复利用已创建的线程降低线程创建和销毁造成的消耗

提高响应速度：当任务到达时，不需要等待线程创建完毕就能立即执行

提高线程的可管理性：利用线程池可以进行线程的统一分配、调优和监控

1.4 JVM

1.4.1 Java内存管理

（1）Java内存区域

JDK1.7及之前：

JDK1.8：

线程私有的：

程序计数器：一块较小的内存空间，用于记录当前线程所执行的字节码的行号指示器。
虚拟机栈：Java虚拟机栈是线程私有的，生命周期与线程相同。每一个方法被执行时，Java虚拟机都会创建一个栈帧，用于存储局部变量表、操作数栈、动态链接、方法出口等信息。
本地方法栈：为虚拟机使用到的本地方法服务。在 HotSpot 虚拟机中和 Java 虚拟机栈合二为一。

线程共享的：

堆：Java堆是被所有线程共享的一块内存区域，在虚拟机启动时创建，唯一目的是用于存放对象实例。Java堆同时是垃圾收集器管理的内存区域，因此又称“GC堆”（Garbage Collected Heap）。
方法区：存放已被虚拟机加载的类型信息、常量、静态变量、即时编译器编译后的代码缓存等数据。
直接内存：基于通道（Channel）与缓冲区（Buffer）的I/O方式，它可以使用Native函数库直接分配堆外内存，然后通过一个存储在Java堆里面的 DirectByteBuffer对象作为这块内存的引用进行操作。

（2）为什么要将永久代(PermGen)替换为元空间(MetaSpace)呢?

整个永久代有⼀个 JVM 本身设置固定⼤⼩上限，⽆法进⾏调整，⽽元空间使⽤的是直接内存，受本机可⽤内存的限制，虽然元空间仍旧可能溢出，但是⽐原来出现的⼏率会更⼩

元空间⾥⾯存放的是类的元数据，这样加载多少类的元数据就不由 MaxPermSize 控制了, ⽽由系统的实际可⽤空间来控制，这样能加载的类就更多了。

在 JDK8，合并 HotSpot 和 JRockit 的代码时, JRockit 从来没有⼀个叫永久代的东⻄, 合并之后就没有必要额外的设置这么⼀个永久代的地⽅了

（3）Java对象的创建过程

对象的创建

（1）类加载检查：当Java虚拟机遇到一条字节码new指令时，首先去检查这个指令的参数是否能在常量池中定位到一个类的符号引用，并且检查这个符号引用代表的类是否被加载、解析和初始化过。如果没有，需要先执行相应的类加载过程

（2）分配内存：类加载检查通过后，虚拟机将为新生对象分配内存，分配方式有“指针碰撞“和”空闲列表“两种，选择哪种分配方式由Java堆是否规整决定，而Java堆是否规整由垃圾收集器是否带有压缩整理功能决定。

内存分配的方法：①指针碰撞：空闲空间和使用空间位于分界线两侧，把指向空闲空间的指针向下移动一个对象的大小 ②：空闲列表：由虚拟机维护一张列表，用于记录哪些内存块可用，在分配的时候从列表中找到一块足够大的空间分配给对象实例。

内存分配时的并发问题：①对分配动作进行同步处理（加锁） ②本地线程分配缓冲：把内存分配的动作按照线程划分在不同的空间之中进行，即每个线程在Java堆中预先分配一小块内存，当本地缓冲用完时，分配新的缓冲区才需要同步锁定，减少了同步的开销。

CAS+失败重试： CAS 是乐观锁的一种实现方式。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。虚拟机采用 CAS 和失败重试的方式保证更新操作的原子性。

TLAB： 为每一个线程预先在 Eden 区分配一块儿内存，JVM 在给线程中的对象分配内存时，首先在 TLAB 分配，当对象大于 TLAB 中的剩余内存或 TLAB 的内存已用尽时，再采用上述的 CAS 进行内存分配

（3）初始化零值：内存分配完毕后，虚拟机会将内存区域置零。

（4）设置对象头：接下来，虚拟机会对对象进行设置，包括标识对象属于哪个类、类的元数据信息的位置、对象的GC分代年龄、哈希码，这些信息会被记录到对象头中。

（5）执行init方法：new指令执行完毕后会接着执行()方法，对对象进行初始化。

（4）对象位置的定位

通过句柄访问对象

优点：reference中存储的是句柄地址，在对象被移动时（例如整理内存碎片）无需改变reference本身

缺点：存在两次寻址开销

通过直接指针访问对象

优点：reference中存储的是对象地址，访问速度快，节省了一次寻址开销（HotSpot采用的方式）

（5）堆内存中对象分配的基本策略

堆的基本结构：

上图所示的 eden区、s0区、s1区都属于新⽣代，tentired 区属于⽼年代。⼤部分情况，对象都会⾸先在 Eden 区域分配，在⼀次新⽣代垃圾回收后，如果对象还存活，则会进⼊ s0 或者 s1，并且对象的年龄还会加 1(Eden区i>Survivor 区后对象的初始年龄变为1)，当它的年龄增加到⼀定程度（默认为15 岁），就会被晋升到⽼年代中。

堆常见分配策略：

对象优先在eden区分配
大对象直接进入老年代（通过-XX:MaxTenuringThreshold设置）
长期存活对象进入老年代

1.4.2 Java对象内存空间占用

java对象在内存中占用的空间分为3类：

对象头（Header）；
实例数据（Instance Data）;
对齐填充（Padding）。

我们常说的基础数据类型大小，如byte占1字节、int占4字节、long占8字节等，主要是指第二类实例数据。下图是Java对象内存占用的示意图。

（1）对象头

HotSpot虚拟机的对象头包括两部分信息：markword和klass 。

对象头组成介绍

第一部分markword，用于存储对象自身的运行时数据，如哈希码（HashCode）、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等。
另外一部分是klass类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。
如果对象是一个数组, 那在对象头中还必须有一块数据用于记录数组长度，也就是一个int类型的对象，占4字节。

对象头占用空间

在32位系统下，存放Class指针的空间大小是4字节，MarkWord是4字节，对象头为8字节。
在64位系统下，存放Class指针的空间大小是8字节，MarkWord是8字节，对象头为16字节。
在64位开启指针压缩的情况下（默认开启）-XX:+UseCompressedOops，存放Class指针的空间大小是4字节，MarkWord是8字节，对象头为12字节。
如果对象是数组，那么额外增加4个字节，这块儿用来记录数组的长度。

（2）实例数据

实例数据部分是对象真正存储的有效信息，也是在程序代码中所定义的各种类型的字段内容。无论是从父类继承下来的，还是在子类中定义的，都需要记录起来。
这部分空间的占用，就等于对象各个成员变量的空间占用加和。

（3）对齐填充

对齐填充空间并不是必然存在的，也没有特别的含义，它仅仅起着占位符的作用。这是由于HotSpot VM的自动内存管理系统要求对象起始地址必须是8字节的整数倍，换句话说，就是对象的大小必须是8字节的整数倍。
很多其它编程语言在内存管理时，也有对齐填充的概念。

1.4.2 Java垃圾回收

（1）Minor Gc和Full Gc有什么不同？

⼤多数情况下，对象在新⽣代中 eden 区分配。当 eden 区没有⾜够空间进⾏分配时，虚拟机将发起⼀次Minor GC。

新⽣代GC（Minor GC）:指发⽣新⽣代的的垃圾收集动作，Minor GC⾮常频繁，回收速度⼀般也⽐较快。
⽼年代GC（Major GC/Full GC）:指发⽣在⽼年代的GC，出现了Major GC经常会伴随⾄少⼀次的 Minor GC（并⾮绝对），Major GC的速度⼀般会⽐Minor GC的慢10倍以上。

进行GC的分类：

部分收集 (Partial GC)：
- 新⽣代收集（Minor GC / Young GC）：只对新⽣代进⾏垃圾收集；
- ⽼年代收集（Major GC / Old GC）：只对⽼年代进⾏垃圾收集。需要注意的是 Major GC 在有的语境中也⽤于指代整堆收集；
- 混合收集（Mixed GC）：对整个新⽣代和部分⽼年代进⾏垃圾收集。
整堆收集 (Full GC)：收集整个 Java 堆和⽅法区。

（2）判断对象是否死亡

引用计数法：

给对象中添加⼀个引⽤计数器，每当有⼀个地⽅引⽤它，计数器就加1；当引⽤失效，计数器就减1；任何时候计数器为0的对象就是不可能再被使⽤的。

适合大多数场景，但是存在例外情况（例如循环引用），需要大量的额外处理才能解决内存泄漏。

可达性分析法：

这个算法的基本思想就是通过⼀系列的称为 “GC Roots” 的对象作为起点，从这些节点开始向下搜索，节点所⾛过的路径称为引⽤链，当⼀个对象到 GC Roots 没有任何引⽤链相连的话，则证明此对象是不可⽤的。

（3）强引用、软引用、弱引用、虚引用

强引用：形如 Object obj = new Object() 及 obj1.friends = obj2 的形式，垃圾收集器永远不会回收存在强引用的对象。
软引用：一些还有用、但非必须的对象，在内存发生溢出前被回收。使用 SoftReference 类来实现软引用。
弱引用：非必须对象，强度弱于软引用，在下一次垃圾收集时回收。使用 WeakReference 类来实现弱引用。
虚引用：最弱的一种引用关系，只是为了能在对象被回收时收到一个系统通知。使用 PhantomReference 来实现虚引用。

（4）如何判断一个常量是废弃常量

运⾏时常量池主要回收的是废弃的常量。那么，我们如何判断⼀个常量是废弃常量呢？

假如在常量池中存在字符串 “abc”，如果当前没有任何String对象引⽤该字符串常量的话，就说明常量 “abc” 就是废弃常量，如果这时发⽣内存回收的话⽽且有必要的话，”abc” 就会被系统清理出常量池。

（5）如何判断一个类是无用类

⽅法区主要回收的是⽆⽤的类，那么如何判断⼀个类是⽆⽤的类的呢？
判定⼀个常量是否是“废弃常量”⽐较简单，⽽要判定⼀个类是否是“⽆⽤的类”的条件则相对苛刻许多。类

需要同时满⾜下⾯3个条件才能算是 “⽆⽤的类” ：

该类所有的实例都已经被回收，也就是 Java 堆中不存在该类的任何实例。

加载该类的 ClassLoader 已经被回收。

该类对应的 java.lang.Class 对象没有在任何地⽅被引⽤，⽆法在任何地⽅通过反射访问该类的⽅法。虚拟机可以对满⾜上述3个条件的⽆⽤类进⾏回收，这⾥说的仅仅是“可以”，⽽并不是和对象⼀样不使⽤了就会必然被回收。

（6）回收方法区的考量

回收方法区的收益低

垃圾收集通常可以回收70%-90%的空间，相比之下，方法区回收囿于苛刻的判定条件，回收效果远低于此。

方法区的垃圾收集的内容
- 废弃的常量
  - 回收行为和Java堆很类似。
  - 例如：一个字符串 “java” 曾进入常量池，但程序中没有任何字符串对象引用“Java”常量，且虚拟机也没有其他地方引用这个字面量，此时如果发生内存回收，且垃圾收集器判断有必要时，该常量将被清理出常量池。常量池中的其他类、方法、字段的符号同理。
- 不再使用的类型
  - 判定条件苛刻
    - 该类的所有实例被回收
    - 类加载器被回收
    - 类的 java.lang.Class 对象没有在任何地方被应用，无法通过反射创建该类的方法
  - 通过参数 -Xnoclassgc 参数进行控制

（7）分代收集理论

弱分代假说：绝大多数对象都是朝生夕灭的。
强分代解说：熬过越多次垃圾收集过程的对象就越难以消亡。
跨代引用假说：跨代引用相较于同代引用来说仅占极少数。

垃圾收集器的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄分配到不同区域之中存储。

新生代：存活时间短的对象
老生代：存活时间长的对象

（8）标记-清除算法

标记

标记出所有需要回收的对象

清除

标记完成过后统一回收所有被标记的对象

缺点

① 执行效率不稳定，尤其是当Java堆中存在大量需要被回收的对象时。

② 内存碎片化。

（9）标记-复制算法

半区复制

将一块内存分为两块，当一块的内存用完后，将还存活的对象复制到另一块，然后将已使用过的内存空间一次清理掉。

缺点

浪费空间，可用空间只有原空间的1/2。

应用

现在的商用Java虚拟机采用该算法回收新生代，但由于新生代的大多数对象的存活时间很短，因此可以修改内存分配比例，例如HotSpot的将划分比例设置为为8：1（Eden：Survivor）。

（10）标记-整理算法

标记

标记出所有需要回收的对象

整理

让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存。

（11）分代收集算法

当前虚拟机的垃圾收集都采⽤分代收集算法，这种算法没有什么新的思想，只是根据对象存活周期的不同将内存分为⼏块。⼀般将java堆分为新⽣代和⽼年代，这样我们就可以根据各个年代的特点选择合适的垃圾收集算法。
⽐如在新⽣代中，每次收集都会有⼤量对象死去，所以可以选择复制算法，只需要付出少量对象的复制成本就可以完成每次垃圾收集。⽽⽼年代的对象存活⼏率是⽐较⾼的，⽽且没有额外的空间对它进⾏分配担保，所以我们必须选择“标记-清除”或“标记-整理”算法进⾏垃圾收集。

（12）HotSpot为什么要分为新⽣代和⽼年代？

主要是为了提升GC效率。上⾯提到的分代收集算法已经很好的解释了这个问题。

1.4.3 常见垃圾回收器

没有适用全部场景的垃圾收集器，我们能做的就是根据具体应⽤场景选择适合⾃⼰的垃圾收集器

（1）Serial收集器

（2）ParNew收集器

（3）Parallel Scavenge收集器

（4）Serial Old收集器

（5）Parallel Old收集器

（6）CMS收集器

（7）G1收集器

1.4.3 Java类文件

（1）类文件结构

ClassFile {
    u4             magic; //Class 文件的标志
    u2             minor_version;//Class 的小版本号
    u2             major_version;//Class 的大版本号
    u2             constant_pool_count;//常量池的数量
    cp_info        constant_pool[constant_pool_count-1];//常量池
    u2             access_flags;//Class 的访问标记
    u2             this_class;//当前类
    u2             super_class;//父类
    u2             interfaces_count;//接口
    u2             interfaces[interfaces_count];//一个类可以实现多个接口
    u2             fields_count;//Class 文件的字段属性
    field_info     fields[fields_count];//一个类会可以有多个字段
    u2             methods_count;//Class 文件的方法数量
    method_info    methods[methods_count];//一个类可以有个多个方法
    u2             attributes_count;//此类的属性表中的属性数
    attribute_info attributes[attributes_count];//属性表集合
}

魔数: 确定这个⽂件是否为⼀个能被虚拟机接收的 Class ⽂件。
Class ⽂件版本：Class ⽂件的版本号，保证编译正常执⾏。
常量池：常量池主要存放两⼤常量：字⾯量和符号引⽤。
访问标志：标志⽤于识别⼀些类或者接⼝层次的访问信息，包括：这个 Class 是类还是接⼝，是否为 public 或者 abstract 类型，如果是类的话是否声明为 final 等等。
当前类索引,⽗类索引：类索引⽤于确定这个类的全限定名，⽗类索引⽤于确定这个类的⽗类的全限定名，由于 Java 语⾔的单继承，所以⽗类索引只有⼀个，除了 java.lang.Object 之外，所有的 java 类都有⽗类，因此除了 java.lang.Object 外，所有 Java 类的⽗类索引都不为 0。
接⼝索引集合：接⼝索引集合⽤来描述这个类实现了那些接⼝，这些被实现的接⼝将按implents (如果这个类本身是接⼝的话则是extends ) 后的接⼝顺序从左到右排列在接⼝索引集合中。
字段表集合：描述接⼝或类中声明的变量。字段包括类级变量以及实例变量，但不包括在⽅法内部声明的局部变量。
⽅法表集合：类中的⽅法。
属性表集合：在 Class ⽂件，字段表，⽅法表中都可以携带⾃⼰的属性表集合。

（2）类加载过程

JavaGuide (gitee.io)

Class 文件需要加载到虚拟机中之后才能运行和使用，那么虚拟机是如何加载这些 Class 文件呢？

系统加载 Class 类型的文件主要三步：加载->连接->初始化。连接过程又可分为三步：验证->准备->解析。

（3）加载步骤的流程

通过全类名获取类文件的二进制字节流

将字节流代表的静态存储结构转换为方法区的运行时数据结构

在内存中生成一个代表该类的Class对象，作为方法区这些数据的访问入口

（4）类加载器的分类

VM 中内置了三个重要的 ClassLoader，除了 BootstrapClassLoader 其他类加载器均由 Java 实现且全部继承自java.lang.ClassLoader：

BootstrapClassLoader(启动类加载器) ：最顶层的加载类，由C++实现，负责加载 %JAVA_HOME%/lib目录下的jar包和类或者或被 -Xbootclasspath参数指定的路径中的所有类。

ExtensionClassLoader(扩展类加载器) ：主要负责加载目录 %JRE_HOME%/lib/ext 目录下的jar包和类，或被 java.ext.dirs 系统变量所指定的路径下的jar包。

AppClassLoader(应用程序类加载器) ：面向我们用户的加载器，负责加载当前应用classpath下的所有jar包和类。

（5）双亲委派机制

每⼀个类都有⼀个对应它的类加载器。系统中的 ClassLoder 在协同⼯作的时候会默认使⽤双亲委派模型。即在类加载的时候，系统会⾸先判断当前类是否被加载过。已经被加载的类会直接返回，否则才会尝试加载。加载的时候，⾸先会把该请求委派该⽗类加载器的 loadClass() 处理，因此所有的请求最终都应该传送到顶层的启动类加载器 BootstrapClassLoader 中。当⽗类加载器⽆法处理时，才由⾃⼰来处理。当⽗类加载器为null时，会使⽤启动类加载器 BootstrapClassLoader 作为⽗类加载器。

ClassLoader

（6）双亲委派机制的好处

双亲委派模型保证了Java程序的稳定运⾏，可以避免类的重复加载（JVM 区分不同类的⽅式不仅仅根据类名，相同的类⽂件被不同的类加载器加载产⽣的是两个不同的类），也保证了 Java 的核⼼ API 不被篡改。如果不⽤没有使⽤双亲委派模型，⽽是每个类加载器加载⾃⼰的话就会出现⼀些问题，⽐如我们编写⼀个称为 java.lang.Object 类的话，那么程序运⾏的时候，系统就会出现多个不同的 Object 类。

（7）如果我们不想⽤双亲委派模型怎么办？

继承 ClassLoader 实现自定义类加载器，并重写 loadClass() 方法

（8）如何⾃定义类加载器?

除了 BootstrapClassLoader 其他类加载器均由 Java 实现且全部继承⾃ java.lang.ClassLoader。如果我们要⾃定义⾃⼰的类加载器，很明显需要继承 ClassLoader。

1.4.4

二计算机基础

2.1 计算机网络

2.1.1 基础知识

（1）五层协议

应用层：DNS、HTTP、SMTP；

运输层：TCP、UDP

网络层：IP、ICMP、ARP

数据链路层：Ethernet、IEEE802.3、PPP

物理层

（2）TCP与UDP是啥，TCP与UDP的区别是啥？

TCP：传输控制协议（Transmission Control Protocol）

UDP：用户数据报协议（User Datagram Protocol）

TCP面向连接的，UDP是无连接的。
TCP提供可靠交付，UDP尽可能交付。
TCP面向字节流，UDP面向报文。
TCP提供流量控制，拥塞控制，UDP没有。
TCP是点对点的，UDP支持一对一，一对多，多对一，多对多。

为了提供可靠的传输，TCP报文首部需要添加除了UDP具有的源端口号，目的端口号，报文长度，检验和意外的字段，比如：

序号：报文编号，用于分段数据的正确重组
确认号：期望收到的下一个报文段的序号
ACK：确认应答有效
FIN：断开连接时候用
SYN：建立连接时候用
……

TCP与UDP的编程区别：

通常我们在说到网络编程时默认是指TCP编程，即用前面提到的socket函数创建一个socket用于TCP通讯，函数参数我们通常填为SOCK_STREAM。即socket(PF_INET, SOCK_STREAM, 0)，这表示建立一个socket用于流式网络通讯。
SOCK_STREAM这种的特点是面向连接的，即每次收发数据之前必须通过connect建立连接，也是双向的，即任何一方都可以收发数据，协议本身提供了一些保障机制保证它是可靠的、有序的，即每个包按照发送的顺序到达接收方。

而SOCK_DGRAM这种是User Datagram Protocol协议的网络通讯，它是无连接的，不可靠的，因为通讯双方发送数据后不知道对方是否已经收到数据，是否正常收到数据。任何一方建立一个socket以后就可以用sendto发送数据，也可以用recvfrom接收数据。根本不关心对方是否存在，是否发送了数据。它的特点是通讯速度比较快。大家都知道TCP是要经过三次握手的，而UDP没有。

基于上述不同，UDP和TCP编程步骤也有些不同，如下：
TCP编程的服务器端一般步骤是：
　　1、创建一个socket，用函数socket()；
　　2、设置socket属性，用函数setsockopt(); * 可选
　　3、绑定IP地址、端口等信息到socket上，用函数bind();
　　4、开启监听，用函数listen()；
　　5、接收客户端上来的连接，用函数accept()；
　　6、收发数据，用函数send()和recv()，或者read()和write();
　　7、关闭网络连接；
　　8、关闭监听；

new socket—>bing(ip,port)—>listen—>accept—>read and write

TCP编程的客户端一般步骤是：
　　1、创建一个socket，用函数socket()；
　　2、设置socket属性，用函数setsockopt();* 可选
　　3、绑定IP地址、端口等信息到socket上，用函数bind();* 可选
　　4、设置要连接的对方的IP地址和端口等属性；
　　5、连接服务器，用函数connect()；
　　6、收发数据，用函数send()和recv()，或者read()和write();
　　7、关闭网络连接；

new socket—>connect(ip,port)—>read and write.

与之对应的UDP编程步骤要简单许多，分别如下：
UDP编程的服务器端一般步骤是：
　　1、创建一个socket，用函数socket()；
　　2、设置socket属性，用函数setsockopt();* 可选
　　3、绑定IP地址、端口等信息到socket上，用函数bind();
　　4、循环接收数据，用函数recvfrom();
　　5、关闭网络连接；

new socket—>bind()—>recv.

UDP编程的客户端一般步骤是：
　　1、创建一个socket，用函数socket()；
　　2、设置socket属性，用函数setsockopt();* 可选
　　3、绑定IP地址、端口等信息到socket上，用函数bind();* 可选
　　4、设置对方的IP地址和端口等属性;
　　5、发送数据，用函数sendto();
　　6、关闭网络连接；

new socket—>bind—>send.

（2）TCP三次握手⭐

三次握手

一次握手：A 向 B 发送连接请求报文，SYN=1，ACK=0，选择一个初始的序号 x。

二次握手：B 收到连接请求报文，如果同意建立连接，则向 A 发送连接确认报文，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。

三次握手：A 收到 B 的连接确认报文后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。

B 收到 A 的确认后，连接建立。

为什么要三次握手？

验证客户端与服务端是否具有对数据的收发能力。

第一次客户端发起，服务端收到确认客户端的发数据的能力。

第二次服务端发起，客户端收到确认服务端收发数据的能力。

第三次客户端发起，服务端收到确认客户端具有收数据的能力。

通过三次握手，客户端与服务端的收发数据的能力得以验证。

通过上述的方式确认客户端与服务端的数据收发能力，可以防止：

服务器多次连接。由于数据传输的时延，客户机可能在等待一段时间之后，重新发起连接请求，如果不采取三次握手机制，那么服务器很可能存在多次连接的情况。只有正确经过三次握手的连接的才是正确的连接。
失效连接，让服务器打开错误的连接。

（3）第2次握手传回了ACK，为什么还要传回SYN？

SYN 同步序列编号(Synchronize Sequence Numbers) 是 TCP/IP 建立连接时使用的握手信号。在客户机和服务器之间建立正常的 TCP 网络连接时，客户机首先发出一个 SYN 消息，服务器使用 SYN-ACK 应答表示接收到了这个消息，最后客户机再以 ACK消息响应。这样在客户机和服务器之间才能建立起可靠的 TCP 连接，数据才可以在客户机和服务器之间传递。

（4）TCP四次挥手⭐

四次挥手

客户端发送FIN，关闭客户端到服务器的数据传输
服务器收到FIN，并返回ACK确认收到客户端的FIN
服务器关闭和客户端的连接，发送FIN给客户端
客户端返回ACK确认收到服务器的FIN

为什么要四次挥手

TCP连接是双向传输的对等模式，收发数据的成功与连接的建立与关闭都要告诉对方。

上层应用让客户端向服务端一个FIN请求，服务端收到应答，进入CLOSE_WAIT状态，继续发送还没发送完的报文。

当报文发送完毕之后，服务端主动发起FIN请求，客户端收到该请求并应答，此时客户端没有立即断开，而是进入TIME-WAIT。原因：

确保最后一个报文收到，如果不回复ACK，服务端一段时候后重新发送该报文。

（5）TCP协议如何保证可靠数据传输？

有序性：TCP给每一个发送的包编号，接收方对数据包进行排序，把有序的数据传送给应用层
校验和：TCP保存它首部和数据块的校验和，如果收到数据的校验和有错，TCP将丢弃该报文
流量控制：TCP连接的每一方都有固定大小的缓冲空间，TCP接收端只允许发送端发送接收端缓冲区能容纳的数据。（TCP利用滑动窗口实现流量控制）
拥塞控制：当网络拥塞时，减少数据的发送
ARQ协议：每发完一个分组就停止发送，等待对方确认，收到确认后再发送下一个分组
超时重传：当TCP发送报文后，启动一个定时器，若一段时间内未收到ACK确认，则重发该报文

（6）HTTP的长连接如何实现的？

HTTP短连接：客户端每进⾏⼀次HTTP操作，就同服务器建⽴⼀次连接，任务结束就中断连接。
HTTP长连接：响应头包含字段：Connection:keep-alive；⼀个⽹⻚打开完成后，客户端和服务器之间⽤于传输HTTP数据的 TCP连接不会关闭，客户端再次访问这个服务器时，会继续使⽤这⼀条已经建⽴的连接。

HTTP协议的⻓连接和短连接实质上是TCP协议的⻓连接和短连接。

HTTP长连接、短连接究竟是什么？ - dai.sp - 博客园 (cnblogs.com)

（7）ssh关闭连接后命令还会继续执行吗？

不会。

可以通过nohup命令实现关闭连接后继续执行命令。使用方式：nohup Command [ Arg … ] [　& ]

&：后台运行，忽略SIGINT信号（即ctrl+c）
nohup：忽略SIGHUP信号（即关闭shell）

（8）HTTP和HTTPS

端⼝：HTTP的URL由“http://”起始且默认使⽤端⼝80，⽽HTTPS的URL由“https://”起始且默认使⽤端⼝443。
安全性和资源消耗： HTTP协议运⾏在TCP之上，所有传输的内容都是明⽂，客户端和服务器端都⽆法验证对⽅的身份。HTTPS是运⾏在SSL/TLS之上的HTTP协议，SSL/TLS 运⾏在 TCP之上。所有传输的内容都经过加密，加密采⽤对称加密，但对称加密的密钥⽤服务器⽅的证书进⾏了⾮对称加密。所以说，HTTP 安全性没有 HTTPS⾼，但是 HTTPS ⽐HTTP耗费更多服务器资源。
对称加密：密钥只有⼀个，加密解密为同⼀个密码，且加解密速度快，典型的对称加密算法有DES、AES等；
⾮对称加密：密钥成对出现（且根据公钥⽆法推知私钥，根据私钥也⽆法推知公钥），加密解密使⽤不同密钥（公钥加密需要私钥解密，私钥加密需要公钥解密），相对对称加密速度较慢，典型的⾮对称加密算法有RSA、DSA等。

（9）为什么要有半关闭状态？

例如：在Unix中的rsh( 1 )命令，它将完成在另一个系统上执行一个命令。
命令 sun % rsh bsdi sort < datafile
将在主机bsdi上执行sort排序命令，rsh命令的标准输入来自文件datafile。rsh将在它与在另一主机上执行的程序间建立一个 TCP连接。 rsh的操作很简单：它将标准输入（datafile）复制给TCP连接，并将结果从 TCP连接中复制给标准输出。（牢记TCP连接是全双工的）

在这里插入图片描述

sort程序只有读取到所有输入的数据后才能产生输出。而仅通过TCP来传输数据，会出现一些难以解决的问题，比如发送方数据已经发完后，没有数据可发，但是接收方无法知道数据已经发完，而会继续等待发送方发送数据，发送方只能通过发一下特定的东西来提示接收方数据已经发完，但又可能出现接收方并不认识发送方的提示，而将该提示也当作待处理的数据，这样两方就都会处于尴尬的阻塞，来等待对方的消息。现在半关闭就可以将此问题很简单的处理，发送方发现数据到达文件尾时，即没有数据发送了，这时发送方发送一个FIN来通知接收方我数据已经发送完了，接收方收到FIN后，向发送发回复一个ACK表示收到发送方的状态，此时发送方进入了半关闭的状态，但是还可以就收对方发送的数据，于是就等待对方对数据进行操作并把结果反馈给我。

2.1.2 ARQ协议

自动重传请求（Automatic Repeat-reQuest, ARQ）是OSI模型中数据链路层和传输层的错误纠正协议之⼀。它通过使⽤确认和超时这两个机制，在不可靠服务的基础上实现可靠的信息传输。如果发送⽅在发送后⼀段时间之内没有收到确认帧，它通常会重新发送。ARQ包括停⽌等待ARQ 协议和连续ARQ协议。

（1）停止等待ARQ协议

停⽌等待协议是为了实现可靠传输的，它的基本原理就是每发完⼀个分组就停⽌发送，等待对⽅确认（回复ACK）。如果过了⼀段时间（超时时间后），还是没有收到 ACK 确认，说明没有发送成功，需要重新发送，直到收到确认后再发下⼀个分组；

在停⽌等待协议中，若接收⽅收到重复分组，就丢弃该分组，但同时还要发送确认；

优点：简单

缺点：信道利用率低、等待时间长

无差错情形：

发送方发送分组,接收⽅在规定时间内收到,并且回复确认.发送⽅再次发送。

出现差错情形（超时重传）：

停⽌等待协议中超时重传是指只要超过⼀段时间仍然没有收到确认，就重传前⾯发送过的分组（认为刚才发送过的分组丢失了）。因此每发送完⼀个分组需要设置⼀个超时计时器，其重传时间应⽐数据在分组传输的平均往返时间更⻓⼀些。这种⾃动重传⽅式常称为⾃动重传请求 ARQ 。另外在停⽌等待协议中若收到重复分组，就丢弃该分组，但同时还要发送确认。连续 ARQ 协议可提⾼信道利⽤率。发送维持⼀个发送窗⼝，凡位于发送窗⼝内的分组可连续发送出去，⽽不需要等待对⽅确认。接收⽅⼀般采⽤累积确认，对按序到达的最后⼀个分组发送确认，表明到这个分组位置的所有分组都已经正确收到了。

确认丢失和确认迟到：

确认丢失：确认消息在传输过程丢失。当A发送M1消息，B收到后，B向A发送了一个M1确认消息，但却在传输过程中丢失。而A并不知道，在超时计时过后，A重传M1消息，B再次收到该消息后采取以下两点措施：1. 丢弃这个重复的M1消息，不向上层交付。 2. 向A发送确认消息。（不会认为已经发送过了，就不再发送。A能重传，就证明B的确认消息丢失）。
确认迟到：确认消息在传输过程中迟到。A发送M1消息，B收到并发送确认。在超时时间内没有收到确认消息，A重传M1消息，B仍然收到并继续发送确认消息（B收到了2份M1）。此时A收到了B第二次发送的确认消息。接着发送其他数据。过了一会，A收到了B第一次发送的对M1的确认消息（A也收到了2份确认消息）。处理如下：1. A收到重复的确认后，直接丢弃。2. B收到重复的M1后，也直接丢弃重复的M1。

（2）连续ARQ协议

连续 ARQ 协议可提高信道利用率。发送方维持一个发送窗口，凡位于发送窗口内的分组可以连续发送出去，而不需要等待对方确认。接收方一般采用累计确认，对按序到达的最后一个分组发送确认，表明到这个分组为止的所有分组都已经正确收到了。

优点：信道利用率高，容易实现，即使确认丢失，也不必重传。

缺点：不能向发送方反映出接收方已经正确收到的所有分组的信息。比如：发送方发送了 5条消息，中间第三条丢失（3号），这时接收方只能对前两个发送确认。发送方无法知道后三个分组的下落，而只好把后三个全部重传一次。这也叫 Go-Back-N（回退 N），表示需要退回来重传已经发送过的 N 个消息。

2.1.3 网络算法

（1）拥塞控制

在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。这种情况就叫拥塞。拥塞控制就是为了防止过多的数据注入到网络中，这样就可以使网络中的路由器或链路不致过载。拥塞控制所要做的都有一个前提，就是网络能够承受现有的网络负荷。拥塞控制是一个全局性的过程，涉及到所有的主机，所有的路由器，以及与降低网络传输性能有关的所有因素。相反，流量控制往往是点对点通信量的控制，是个端到端的问题。流量控制所要做到的就是抑制发送端发送数据的速率，以便使接收端来得及接收。

为了进行拥塞控制，TCP 发送方要维持一个 拥塞窗口(cwnd) 的状态变量。拥塞控制窗口的大小取决于网络的拥塞程度，并且动态变化。发送方让自己的发送窗口取为拥塞窗口和接收方的接受窗口中较小的一个。

TCP的拥塞控制采用了四种算法，即 慢开始 、 拥塞避免 、快重传 和 快恢复。在网络层也可以使路由器采用适当的分组丢弃策略（如主动队列管理 AQM），以减少网络拥塞的发生。

慢开始： 慢开始算法的思路是当主机开始发送数据时，如果立即把大量数据字节注入到网络，那么可能会引起网络阻塞，因为现在还不知道网络的符合情况。经验表明，较好的方法是先探测一下，即由小到大逐渐增大发送窗口，也就是由小到大逐渐增大拥塞窗口数值。cwnd初始值为1，每经过一个传播轮次，cwnd加倍。
拥塞避免： 拥塞避免算法的思路是让拥塞窗口cwnd缓慢增大，即每经过一个往返时间RTT就把发送放的cwnd加1.
快重传与快恢复： 在 TCP/IP 中，快速重传和恢复（fast retransmit and recovery，FRR）是一种拥塞控制算法，它能快速恢复丢失的数据包。没有 FRR，如果数据包丢失了，TCP 将会使用定时器来要求传输暂停。在暂停的这段时间内，没有新的或复制的数据包被发送。有了 FRR，如果接收机接收到一个不按顺序的数据段，它会立即给发送机发送一个重复确认。如果发送机接收到三个重复确认，它会假定确认件指出的数据段丢失了，并立即重传这些丢失的数据段。有了 FRR，就不会因为重传时要求的暂停被耽误。　当有单独的数据包丢失时，快速重传和恢复（FRR）能最有效地工作。当有多个数据信息包在某一段很短的时间内丢失时，它则不能很有效地工作。

（2）滑动窗口和流量控制

TCP 利用滑动窗口实现流量控制。流量控制是为了控制发送方发送速率，保证接收方来得及接收。 接收方发送的确认报文中的窗口字段可以用来控制发送方窗口大小，从而影响发送方的发送速率。将窗口字段设置为 0，则发送方不能发送数据。

2.1.4 综合应用

（1）浏览器中键入www.google.com发生了什么

DHCP 配置主机信息：

假设主机最开始没有 IP 地址以及其它信息，那么就需要先使用 DHCP 来获取。
主机生成一个 DHCP 请求报文，并将这个报文放入具有目的端口 67 和源端口 68 的 UDP 报文段中。
该报文段则被放入在一个具有广播 IP 目的地址(255.255.255.255) 和源 IP 地址（0.0.0.0）的 IP 数据报中。
该数据报则被放置在 MAC 帧中，该帧具有目的地址 FFFFFF，将广播到与交换机连接的所有设备。
连接在交换机的 DHCP 服务器收到广播帧之后，不断地向上分解得到 IP 数据报、UDP 报文段、DHCP 请求报文，之后生成 DHCP ACK 报文，该报文包含以下信息：IP 地址、DNS 服务器的 IP 地址、默认网关路由器的 IP 地址和子网掩码。该报文被放入 UDP 报文段中，UDP 报文段又被放入 IP 数据报中，最后放入 MAC 帧中。
该帧的目的地址是请求主机的 MAC 地址，因为交换机具有自学习能力，之前主机发送了广播帧之后就记录了 MAC 地址到其转发接口的交换表项，因此现在交换机就可以直接知道应该向哪个接口发送该帧。
主机收到该帧后，不断分解得到 DHCP 报文。之后就配置它的 IP 地址、子网掩码和 DNS 服务器的 IP 地址，并在其 IP 转发表中安装默认网关。

ARP 解析 MAC 地址

主机通过浏览器生成一个 TCP 套接字，套接字向 HTTP 服务器发送 HTTP 请求。为了生成该套接字，主机需要知道网站的域名对应的 IP 地址。
主机生成一个 DNS 查询报文，该报文具有 53 号端口，因为 DNS 服务器的端口号是 53。
该 DNS 查询报文被放入目的地址为 DNS 服务器 IP 地址的 IP 数据报中。
该 IP 数据报被放入一个以太网帧中，该帧将发送到网关路由器。
DHCP 过程只知道网关路由器的 IP 地址，为了获取网关路由器的 MAC 地址，需要使用 ARP 协议。
主机生成一个包含目的地址为网关路由器 IP 地址的 ARP 查询报文，将该 ARP 查询报文放入一个具有广播目的地址FFFFFF）的以太网帧中，并向交换机发送该以太网帧，交换机将该帧转发给所有的连接设备，包括网关路由器。
网关路由器接收到该帧后，不断向上分解得到 ARP 报文，发现其中的 IP 地址与其接口的 IP 地址匹配，因此就发送一个 ARP 回答报文，包含了它的 MAC 地址，发回给主机。

DNS 解析域名

知道了网关路由器的 MAC 地址之后，就可以继续 DNS 的解析过程了。
网关路由器接收到包含 DNS 查询报文的以太网帧后，抽取出 IP 数据报，并根据转发表决定该 IP 数据报应该转发的路由器。
因为路由器具有内部网关协议（RIP、OSPF）和外部网关协议（BGP）这两种路由选择协议，因此路由表中已经配置了网关路由器到达 DNS 服务器的路由表项。
到达 DNS 服务器之后，DNS 服务器抽取出 DNS 查询报文，并在 DNS 数据库中查找待解析的域名。
找到 DNS 记录之后，发送 DNS 回答报文，将该回答报文放入 UDP 报文段中，然后放入 IP 数据报中，通过路由器反向转发回网关路由器，并经过以太网交换机到达主机。

HTTP 请求页面

有了 HTTP 服务器的 IP 地址之后，主机就能够生成 TCP 套接字，该套接字将用于向 Web 服务器发送 HTTP GET 报文。
在生成 TCP 套接字之前，必须先与 HTTP 服务器进行三次握手来建立连接。生成一个具有目的端口 80 的 TCP SYN 报文段，并向 HTTP 服务器发送该报文段。
HTTP 服务器收到该报文段之后，生成 TCP SYN ACK 报文段，发回给主机。
连接建立之后，浏览器生成 HTTP GET 报文，并交付给 HTTP 服务器。
HTTP 服务器从 TCP 套接字读取 HTTP GET 报文，生成一个 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。
浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

总结一下就是：

首先如果没有IP配置，并且采用的自动IP配置，这个时候则会使用到DHCP协议获取主机IP地址，描述一下DHCP协议。在域名解析的过程中，发现首先需要找到网关路由器（DHCP过程中并没有学习网关路由器的MAC地址的过程），这个时候则需要借助ARP协议，描述一下ARP协议。获得了网关路由器的MAC地址，于是DNS请求报文继续发送，通过网络传输，这个过程涉及的协议包括：RIP，OSPF，BGP等一下。最终DNS服务器收到DNS请求报文并解析回复。当主机获得目的IP地址之后，便可以进行HTTP连接了，包括熟悉的三次握手机制等。最后通过四次挥手结束连接。

（2）ping的过程

ping的过程主要分为3个过程：DNS解析、ARP查找MAC地址、ICMP发送ping命令

ping是基于运行在网络层的ICMP协议传输的，如果ping的地址是域名，则首先要通过DNS查找域名所对应的ip，在查找域名的过程中涉及到利用ARP协议查找下一跳的MAC地址，获取到ip地址后，就使用ICMP协议向目标发送ping，发送的过程也涉及到通过ARP协议查找下一跳的mac地址这一过程。

（3）TCP异常断开连接会发生什么？

进程A和进程B建立了TCP连接，有一下四种异常断开场景

一：进程B Crash，但进程B所在的宿主机仍然正常工作。

这种情况我们通过 kill 命令直接杀进程就会出现，它的表现和进程调用Close类似，进程终止后，Socket会变成 Orphan Socket，会一个优雅的方式结束连接，即会向对端发送Fin报文，走正常关闭连接的那一套逻辑。

二：进程B所在的宿主机宕机，又迅速重启。

这种情况下，如果A进程恰好有发往B进程的Tcp报文，B重启前都会被丢弃，此时A可能会进入Rto状态，不断重发重传队列内的报文，在B主机被拉起后，重发的报文会被Linux协议栈接收，经过ip层处理，函数 tcp_v4_rcv 会在全局Socket哈希表中找处理该报文的Socket（监听目标端口的Socket，或者已建立连接的Socket），找到则交由该Socket处理，找不到则会向发送端回复Rst报文。

假设 B 主机启动后没有监听相关端口，则A的报文便会被 tcp_v4_rcv 函数判定为无效报文，回复 Rst 了事。

三：进程B所在的宿主机宕机，短时间内没有重启，从A出发的所有报文都被网络丢弃。

这种情况下，A与B的连接处于黑洞状态，A发送向B的所有报文都被丢弃，且没有任何回复，一定时长后便会触发RTO定时器，定时器处理函数会重发丢失的报文，重发的报文由于对端宕机也会被丢弃，就这样一直重传一直被丢弃，直到达到一定阈值，协议栈便会判定链路出现了故障，并通过Socket接口告诉应用程序链路故障，一般就是ETIMEOUT状态码。

四：B已经断网/宕机/进程Crash，但此时A主机也没有需要向B发送的数据。

如果恰巧A 进程没有任何要发往B的数据， A 进程就没有任何途径感知到进程B已经断开了连接了，这种状态也就是我们熟悉的Tcp半打开状态，也就是冷战状态，双方都不知道对方状态，也无探测报文去触发对方Rst或者Ack。这种情况下，就要有一方主动一点，抛出个橄榄枝，看看对方是要回个Rst拒绝你，还是要回个Ack接受你，还是啥也不回继续冷战，但至少通过这次探测，我们就可以知道对方的状态。这就是Tcp的KeepAlive 机制，Tcp KeepAlive 是协议栈里用来检测半打开状态的机制，在上面介绍的 tcp_init_xmit_timers 函数内，Tcp 启动了一个 keepAlive 定时器（默认时长是2个小时），2个小时后链路处于空闲状态，便会触发这个定时器，定时器的主要工作就是向对方发送探测报文。

（4）TCP粘包与拆包

什么是粘包与拆包

TCP协议会将多个数据包打包成一个TCP报文发送出去，这就是所谓的粘包。而如果通讯的一端发送的数据包超过一次TCP报文所能传输的最大值时，就会将一个数据包拆成多个最大TCP长度的TCP报文分开传输，这就叫做拆包。

MTU(链路层的最大传输单元)=TCP（Header）+IP（header）+MSS(最大报文长度)

粘包发生的情况：

要发送的数据小于 TCP 发送缓冲区的大小，TCP 将多次写入缓冲区的数据一次发送出去，将会发生粘包。
接收数据端的应用层没有及时读取接收缓冲区中的数据，将发生粘包。

拆包发生的情况：

要发送的数据大于 TCP 发送缓冲区剩余空间大小，将会发生拆包。
待发送数据大于 MSS（最大报文长度），TCP 在传输前将进行拆包。

为什么常说 TCP 有粘包和拆包的问题而不说 UDP ？

基于UDP与TCP头部的字段的差别，UDP通过报文长度字段指定报文的长度，在应用层能很好的将不同的数据报文区分开，从而避免粘包和拆包的问题。

TCP粘包与拆包的解决方案：

消息定长，每个数据包封装为固定的长度。接收端读取固定长度即可。
消息边界，通过特殊边界确定不同消息之间的分段。
消息头部指定消息长度。

（5）窗口是什么？

窗口是缓存的一部分，用来暂时存放字节流。发送方和接收方各有一个窗口，接收方通过 TCP 报文段中的窗口字段告诉发送方自己的窗口大小，发送方根据这个值和其它信息设置自己的窗口大小。主要用于流量控制。

什么是流量控制？

流量控制就是通过控制发送方的窗口大小来控制发送速率，保证接收方能正确的接受数据。

什么是拥塞控制？

网络中出现拥塞，则会丢包，丢包则出发重传，从而进一步导致拥塞。拥塞情况出现需要控制发送发的发送速率，像流量控制一样，但是与流量控制是为了让接收方正确接受数据，而拥塞控制是要解决整个网络的拥塞情况。

拥塞控制的四个算法是什么？

慢启动
快恢复
快速重传
拥塞避免

在这里插入图片描述

基本原则：超时很严重，3个ACK代表网络情况还好。

慢开始和快恢复的快慢指的是 cwnd 的设定值.

出现超时情况，网络情况很糟糕，进入慢启动阶段。

但是如果发送端接收到3个以上的重复ACK，TCP就意识到数据发生丢失，需要重传。这个机制不需要等到重传定时器超时，所以叫做快速重传，而快速重传后没有使用慢启动算法，而是拥塞避免算法，所以这又叫做快速恢复算法。

什么是Nagle算法

Nagle算法是为了减少广域网的小分组数目，从而减小网络拥塞的出现，从而提高网络的利用率。该算法要求一个tcp连接上最多只能有一个未被确认的未完成的小分组，在该分组ack到达之前不能发送其他的小分组，tcp需要收集这些少量的分组，并在ack到来时以一个分组的方式发送出去；其中小分组的定义是小于MSS的任何分组。

（6）什么是ICMP协议？

ICMP协议：

由于互联网之间通讯会涉及很多网关和主机，为了能够报告数据错误，所以产生了 ICMP协议。也就是说 ICMP 协议就是为了更高效的转发 IP数据报和提高交付成功的机会。

ARP协议：

在一个局域网中，计算机通信实际上是依赖于 MAC地址进行通信的，那么 ARP（ AddressResolutionProtocol）的作用就是根据 IP地址查找出对应的 MAC地址。

ping的基本过程：

前提设定：ping www.abc.com

首先通过DNS协议解析出www.abc.com的IP地址，然后发起广播的ARP请求，通过ARP请求找到www.abc.com的MAC地址进行通信。

（7）什么是HTTP协议

HTTP与HTTPS的区别是什么

HTTP 协议以明文方式发送内容，数据都是未加密的，安全性较差。HTTPS 数据传输过程是加密的，安全性较好。
HTTP 和 HTTPS 使用的是完全不同的连接方式，用的端口也不一样，前者是 80 端口，后者是 443 端口。
HTTPS 协议需要到数字认证机构（Certificate Authority, CA）申请证书，一般需要一定的费用。
HTTP 页面响应比 HTTPS 快，主要因为 HTTP 使用 3 次握手建立连接，客户端和服务器需要握手 3 次，而
HTTPS 除了 TCP 的 3 次握手，还需要经历一个 SSL 协商过程。

HTTPS加密方式：

对称加密：双方拥有同一个一个密钥，进行加密与解密。

公开密钥：分为私钥与公钥，公钥可以解密私钥加密的数据，私钥可以解密公钥加密的数据。

加密通信：公钥加密，私钥解密。

数字签名：使用私钥加密形成的签名。验证发送方的身份的合法性。

HTTPS 采用对称加密和非对称加密相结合的方式，首先使用 SSL/TLS 协议进行加密传输，为了弥补非对称加密的缺点，HTTPS 采用证书来进一步加强非对称加密的安全性，通过非对称加密，客户端和服务端协商好之后进行通信传输的对称密钥，后续的所有信息都通过该对称秘钥进行加密解密，完成整个 HTTPS 的流程。

HTTP 是不保存状态的协议,如何保存用户状态

① 基于 Session 实现的会话保持

在客户端第一次向服务器发送 HTTP 请求后，服务器会创建一个 Session 对象并将客户端的身份信息以键值对的形式存储下来，然后分配一个会话标识（SessionId）给客户端，这个会话标识一般保存在客户端 Cookie 中，之后每次该浏览器发送 HTTP 请求都会带上 Cookie 中的 SessionId 到服务器，服务器根据会话标识就可以将之前的状态信息与会话联系起来，从而实现会话保持。

优点：安全性高，因为状态信息保存在服务器端。

缺点：由于大型网站往往采用的是分布式服务器，浏览器发送的 HTTP 请求一般要先通过负载均衡器才能到达具体的后台服务器，倘若同一个浏览器两次 HTTP 请求分别落在不同的服务器上时，基于 Session 的方法就不能实现会话保持了。

【解决方法：采用中间件，例如 Redis，我们通过将 Session 的信息存储在 Redis 中，使得每个服务器都可以访问到之前的状态信息】

② 基于 Cookie 实现的会话保持

当服务器发送响应消息时，在 HTTP 响应头中设置 Set-Cookie 字段，用来存储客户端的状态信息。客户端解析出 HTTP 响应头中的字段信息，并根据其生命周期创建不同的 Cookie，这样一来每次浏览器发送 HTTP 请求的时候都会带上 Cookie 字段，从而实现状态保持。基于 Cookie 的会话保持与基于 Session 实现的会话保持最主要的区别是前者完全将会话状态信息存储在浏览器 Cookie 中。

优点：服务器不用保存状态信息，减轻服务器存储压力，同时便于服务端做水平拓展。

缺点：该方式不够安全，因为状态信息存储在客户端，这意味着不能在会话中保存机密数据。除此之外，浏览器每次发起 HTTP 请求时都需要发送额外的 Cookie 到服务器端，会占用更多带宽。

DNS工作方式

递归查询：本地DNS服务器如果没有IP地址，则向根DNS服务器发送请求，依次进行。
迭代查询：本地DNS服务器如果没有IP地址，则根服务器发送请求，如果根没有，回复下一个需要查询的DNS服务器。

DNS为啥采用UDP协议：

快！

（8）什么是ARP协议？

ARP（Address Resolution Protocol）是地址解析协议的缩写，该协议提供根据 IP 地址获取物理地址的功能，它工作在第二层，是一个数据链路层协议，其在本层和物理层进行联系，同时向上层提供服务。当通过以太网发送 IP 数据包时，需要先封装 32 位的 IP 地址和 48位 MAC 地址。在局域网中两台主机进行通信时需要依靠各自的物理地址进行标识，但由于发送方只知道目标 IP 地址，不知道其 MAC 地址，因此需要使用地址解析协议。 ARP 协议的解析过程如下：

① 首先，每个主机都会在自己的 ARP 缓冲区中建立一个 ARP 列表，以表示 IP 地址和 MAC 地址之间的对应关系；

② 当源主机要发送数据时，首先检查 ARP 列表中是否有 IP 地址对应的目的主机 MAC 地址，如果存在，则可以直接发送数据，否则就向同一子网的所有主机发送 ARP 数据包。该数据包包括的内容有源主机的 IP 地址和 MAC 地址，以及目的主机的 IP 地址。

③ 当本网络中的所有主机收到该 ARP 数据包时，首先检查数据包中的目的主机IP 地址是否是自己的 IP 地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的 IP 和 MAC 地址写入到 ARP 列表中，如果已经存在，则覆盖，然后将自己的 MAC 地址写入 ARP 响应包中，告诉源主机自己是它想要找的 MAC 地址。

④ 源主机收到 ARP 响应包后。将目的主机的 IP 和 MAC 地址写入 ARP 列表，并利用此信息发送数据。如果源主机一直没有收到 ARP 响应数据包，表示 ARP 查询失败。

（9）SYN FLOOD 是什么

SYN Flood 是种典型的 DoS（拒绝服务）攻击，其目的是通过消耗服务器所有可用资源使服务器无法用于处理合法请求。通过重复发送初始连接请求（SYN）数据包，攻击者能够压倒目标服务器上的所有可用端口，导致目标设备根本不响应合法请求。

2.1.5 Web

（1）状态码

状态码

（2）HTTP如何保存用户状态？

HTTP 是一种不保存状态，即无状态（stateless）协议。也就是说 HTTP 协议自身不对请求和响应之间的通信状态进行保存。那么我们保存用户状态呢？Session 机制的存在就是为了解决这个问题，Session 的主要作用就是通过服务端记录用户的状态。典型的场景是购物车，当你要添加商品到购物车的时候，系统不知道是哪个用户操作的，因为 HTTP 协议是无状态的。服务端给特定的用户创建特定的 Session 之后就可以标识这个用户并且跟踪这个用户了（一般情况下，服务器会在一定时间内保存这个 Session，过了时间限制，就会销毁这个Session）。

在服务端保存 Session 的方法很多，最常用的就是内存和数据库(比如是使用内存数据库redis保存)。既然 Session 存放在服务器端，那么我们如何实现 Session 跟踪呢？大部分情况下，我们都是通过在 Cookie 中附加一个 Session ID 来方式来跟踪。

Cookie 被禁用怎么办?

最常用的就是利用 URL 重写把 Session ID 直接附加在URL路径的后面。

（3）Cookie和Session的区别？

Cookie 和 Session都是用来跟踪浏览器用户身份的会话方式，但是两者的应用场景不太一样。

Cookie 一般用来保存用户信息 比如①我们在 Cookie 中保存已经登录过得用户信息，下次访问网站的时候页面可以自动帮你登录的一些基本信息给填了；②一般的网站都会有保持登录也就是说下次你再访问网站的时候就不需要重新登录了，这是因为用户登录的时候我们可以存放了一个 Token 在 Cookie 中，下次登录的时候只需要根据 Token 值来查找用户即可(为了安全考虑，重新登录一般要将 Token 重写)；③登录一次网站后访问网站其他页面不需要重新登录。

Session 的主要作用就是通过服务端记录用户的状态。 典型的场景是购物车，当你要添加商品到购物车的时候，系统不知道是哪个用户操作的，因为 HTTP 协议是无状态的。服务端给特定的用户创建特定的 Session 之后就可以标识这个用户并且跟踪这个用户了。

Cookie 数据保存在客户端(浏览器端)，Session 数据保存在服务器端。

Cookie 存储在客户端中，而Session存储在服务器上，相对来说 Session 安全性更高。如果要在 Cookie 中存储一些敏感信息，不要直接写入 Cookie 中，最好能将 Cookie 信息加密然后使用到的时候再去服务器端解密。

（4）URI和URL的区别？

URI(Uniform Resource Identifier) 是统一资源标志符，可以唯一标识一个资源。
URL(Uniform Resource Location) 是统一资源定位符，可以提供该资源的路径。它是一种具体的 URI，即 URL 可以用来标识一个资源，而且还指明了如何 locate 这个资源。

URI的作用像身份证号一样，URL的作用更像家庭住址一样。URL是一种具体的URI，它不仅唯一标识资源，而且还提供了定位该资源的信息。

（5）HTTP和HTTPS的区别？

端口：HTTP的URL由“http://”起始且默认使用端口80，而HTTPS的URL由“https://”起始且默认使用端口443。

安全性和资源消耗：

HTTP协议运行在TCP之上，所有传输的内容都是明文，客户端和服务器端都无法验证对方的身份。HTTPS是运行在SSL/TLS之上的HTTP协议，SSL/TLS 运行在TCP之上。所有传输的内容都经过加密，加密采用对称加密，但对称加密的密钥用服务器方的证书进行了非对称加密。所以说，HTTP 安全性没有 HTTPS高，但是 HTTPS 比HTTP耗费更多服务器资源。

对称加密：密钥只有一个，加密解密为同一个密码，且加解密速度快，典型的对称加密算法有DES、AES等；
非对称加密：密钥成对出现（且根据公钥无法推知私钥，根据私钥也无法推知公钥），加密解密使用不同密钥（公钥加密需要私钥解密，私钥加密需要公钥解密），相对对称加密速度较慢，典型的非对称加密算法有RSA、DSA等。

（6）Https的CA证书放了什么，公钥放在CA里吗？证书中包含公钥

HTTPS中CA证书的签发及使用过程 - xdyixia - 博客园 (cnblogs.com)

2.2 数据结构

2.2.1 解决哈希冲突的方法

1，开放定址法：
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
公式为：fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1)
※ 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者
碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表
中无待查的关键字，即查找失败。
比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。我们用散列函数f(key) = key mod l2
当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：

这里写图片描述
计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。
于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置：

2，再哈希法：
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

3，链地址法：
链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向
链表连接起来，如：
键值对k2, v2与键值对k1, v1通过计算后的索引值都为2，这时及产生冲突，但是可以通道next指针将k2, k1所在的节点连接起来，这样就解决了哈希的冲突问题
这里写图片描述
4，建立公共溢出区：
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

2.3 算法

2.3.1 排序算法

排序算法之（9）–八种常用排序算法效率对比_hiudawn-CSDN博客_排序算法比较

2.4 操作系统

2.4.1 基础知识

（1）什么是操作系统？

操作系统是管理硬件和软件的一种应用程序。操作系统是运行在计算机上最重要的一种软件，它管理计算机的资源和进程以及所有的硬件和软件。它为计算机硬件和软件提供了一种中间层，使应用软件和硬件进行分离，让我们无需关注硬件的实现，把关注点更多放在软件应用上。通常情况下，计算机上会运行着许多应用程序，它们都需要对内存和 CPU 进行交互，操作系统的目的就是为了保证这些访问和交互能够准确无误的进行。

微信图片_20210728163635

（2）操作系统的主要功能

进程管理: 进程管理的主要作用就是任务调度，在单核处理器下，操作系统会为每个进程分配一个任务，进程管理的工作十分简单；而在多核处理器下，操作系统除了要为进程分配任务外，还要解决处理器的调度、分配和回收等问题
内存管理：内存管理主要是操作系统负责管理内存的分配、回收，在进程需要时分配内存以及在进程完成时回收内存，协调内存资源，通过合理的页面置换算法进行页面的换入换出
设备管理：根据确定的设备分配原则对设备进行分配，使设备与主机能够并行工作，为用户提供良好的设备使用界面。
文件管理：有效地管理文件的存储空间，合理地组织和管理文件系统，为文件访问和文件保护提供更有效的方法及手段。
提供用户接口：操作系统提供了访问应用程序和硬件的接口，使用户能够通过应用程序发起系统调用从而操纵硬件，实现想要的功能

（3）操作系统的作用

操作系统是一种软件，它的主要目的有三种

管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等。
提供一种图形界面，就像我们前面描述的那样，它提供了用户和计算机之间的桥梁。
为其他软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源。

（4）为什么Linux下的程序不能再Windows下运行？

主要包括两点：可执行程序文件格式不同；系统的API不同

（5）用户态和内核态

用户态和内核态是操作系统的两种运行状态。

内核态：处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。
用户态：处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

（6）为什么要区分用户态和内核态？

这个主要是访问能力的限制的考量，计算机中有一些比较危险的操作，比如设置时钟、内存清理，这些都需要在内核态下完成，如果随意进行这些操作，那你的系统得崩溃多少次。

（7）用户态和内核态如何切换？

通过系统调用进行切换

（8）什么是boot loader？

boot loader 又被称为引导加载程序，能够将计算机的操作系统放入内存中。在电源通电或者计算机重启时，BIOS 会执行一些初始测试，然后将控制权转移到引导加载程序所在的主引导记录(MBR)

（9）Linux系统的启动过程

BIOS开机自检、导入MBR分区、调入内核、

BIOS开机自检：计算机通电后，会进入BIOS开机自检阶段，对硬件进行检测和初始化，并按照BIOS设置的启动顺序来启动

导入MBR分区：BIOS默认启动设备的第一个分区，即MBR分区会被读取到内存的固定位置执行

调入内核：MBR分区包含一个512字节的程序，负责从磁盘中调入boot程序，boot程序负责读取磁盘文件根目录，调入操作系统内核，并转交控制权。

内核启动：由汇编语言编写，主要包括创建内核堆栈、识别CPU类型、计算内存、禁用中断、启动内存管理单元等，然后调用C语言的main函数执行操作系统部分

操作系统初始化：初始化系统中各设备并做相关配置工作

运行init：启动进程0，执行初始化、配置时钟、挂载文件系统等操作，并创建init进程（1号进程）和守护进程（2号进程），然后init进程会fork一个shell进程，运行系统初始化脚本来执行系统初始化工作

运行终端：最后，init会启动终端供用户登录

（10）什么是系统调用

凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

2.4.2 进程和线程

（1）时分共享技术和空分共享技术

时分共享（time sharing）是操作系统共享资源所使用的最基本的技术之一。通过允许资源由一个实体使用一小段时间，然后由另一个实体使用一小段时间，如此下去，所谓的资源（例如，CPU 或网络链接）可以被许多人共享。时分共享的自然对应技术是空分共享，资源在空间上被划分给希望使用它的人。例如，磁盘空间自然是一个空分共享资源，因为一旦将块分配给文件，在用户删除文件之前，不可能将它分配给其他文件。

（2）进程状态

一个进程的生命周期可以划分为一组状态，这些状态刻画了整个进程。进程状态即体现一个进程的生命状态

一般来说，进程有五种状态：

创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态
就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行
执行状态：进程处于就绪状态被调度后，进程进入执行状态
阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用
终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行

（3）父子进程、僵尸进程、孤儿进程

父子进程：在Linux里，除了进程0（即PID=0的进程）以外的所有进程都是由其他进程使用系统调用fork创建的，这里调用fork创建新进程的进程即为父进程，而相对应的为其创建出的进程则为子进程，因而除了进程0以外的进程都只有一个父进程，但一个进程可以有多个子进程。

僵尸进程：当一个子进程结束运行（一般是调用exit、运行时发生致命错误或收到终止信号所导致）时，子进程的退出状态（返回值）会回报给操作系统，系统则以SIGCHLD信号将子进程被结束的事件告知父进程，此时子进程的进程控制块（PCB）仍驻留在内存中。一般来说，收到SIGCHLD后，父进程会使用wait系统调用以获取子进程的退出状态，然后内核就可以从内存中释放已结束的子进程的PCB；而如若父进程没有这么做的话，子进程的PCB就会一直驻留在内存中，也即成为僵尸进程。僵尸进程也就会造成资源浪费，所以我们应该避免僵尸进程的产生。

孤儿进程：孤儿进程则是指当一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。孤儿进程由于有init进程循环的wait()回收资源，因此并没有什么危害。

（4）什么是进程、线程、协程？

进程：运行中的程序
线程：线程是程序的一条执行路径，又被称作轻量级的进程
协程：是一种比线程更加轻量级的存在，可以看作轻量级的线程。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。

（5）进程间的通信方式（Inter Process Communication，IPC）

竞态条件：即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。

临界区：不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢？或许一句话可以概括说明：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写。换句话说，我们需要一种 互斥(mutual exclusion) 条件，这也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）。

忙等互斥：当一个进程在对资源进行修改时，其他进程必须进行等待，进程之间要具有互斥性，我们讨论的解决方案其实都是基于忙等互斥提出的。

主要包括7种方式：

消息传递：消息传递是进程间实现通信和同步等待的机制，使用消息传递，进程间的交流不需要共享变量，直接就可以进行通信；消息传递分为发送方和接收方
先进先出队列：先进先出队列指的是两个不相关联进程间的通信，两个进程之间可以彼此相互进程通信，这是一种全双工通信方式
管道：管道用于两个相关进程之间的通信，这是一种半双工的通信方式，如果需要全双工，需要另外一个管道。
直接通信：在这种进程通信的方式中，进程与进程之间只存在一条链接，进程间要明确通信双方的命名。
间接通信：间接通信是通信双方不会直接建立连接，而是找到一个中介者，这个中介者可能是个对象等等，进程可以在其中放置消息，并且可以从中删除消息，以此达到进程间通信的目的。
消息队列：消息队列是内核中存储消息的链表，它由消息队列标识符进行标识，这种方式能够在不同的进程之间提供全双工的通信连接。
共享内存：共享内存是使用所有进程之间的内存来建立连接，这种类型需要同步进程访问来相互保护。

（6）进程的状态

微信图片_20210728172410

新建态：进程的新建态就是进程刚创建出来的时候
运行态：运行态指的就是进程实际占用 CPU 时间片运行时
就绪态：就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态
阻塞态：阻塞态又被称为睡眠态，它指的是进程不具备运行条件，正在等待被 CPU 调度。
终止态：进程的终止态就是指进程执行完毕，到达结束点，或者因为错误而不得不中止进程。

（7）进程的调度算法

先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
优先级调度 ：为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

2.4.3 内存管理

（1）内存管理机制

简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间，常见的如 块式管理 。同样地，非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理 和 段式管理。

块式管理 ：远古时代的计算机操系统的内存管理方式。将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
页式管理 ：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。
段式管理 ：页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义。段式管理把主存分为一段段的，每一段的空间又要比一页的空间小很多。但是，最重要的是段是有实际意义的，每个段定义了一组逻辑信息，例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。段式管理通过段表对应逻辑地址和物理地址。
段页式管理机制：段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。

（2）TLB和多级页表

快表

为了解决虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了快表来加速虚拟地址到物理地址的转换。我们可以把快表理解为一种特殊的高速缓冲存储器（Cache），其中的内容是页表的一部分或者全部内容。作为页表的 Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

使用快表之后的地址转换流程是这样的：

根据虚拟地址中的页号查快表；
如果该页在快表中，直接从快表中读取相应的物理地址；
如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

看完了之后你会发现快表和我们平时经常在我们开发的系统使用的缓存（比如 Redis）很像，的确是这样的，操作系统中的很多思想、很多经典的算法，你都可以在我们日常开发使用的各种工具或者框架中找到它们的影子。

多级页表

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景

（3）页面置换算法

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则。

OPT 页面置换算法（最佳页面置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。
FIFO（First In First Out）页面置换算法（先进先出页面置换算法） : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法） ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法） : 该置换算法选择在之前时期使用最少的页面作为淘汰页。

（4）空闲内存管理方式

使用位图管理
使用空闲列表

2.4.4 并发

（1）进程间的通信方式

管道/匿名管道(Pipes) ：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
有名管道(Names Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循**先进先出(first in first out)**。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
信号(Signal) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
消息队列(Message Queuing) ：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺。
信号量(Semaphores) ：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
共享内存(Shared memory) ：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

（2）进程间的同步方式

**互斥量(Mutex)**：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

2.4.5 死锁

（1）死锁的定义

定义：在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁

（2）产生死锁的必要条件

互斥条件：在一段时间内某资源仅为一个进程所占有。
不可剥夺条件：该资源只能由获得该资源的进程自己来释放。
占有并等待条件：进程在等待新资源的同时，继续占用已分配到的资源。
循环等待条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。

（3）死锁的处理

预防死锁：通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个
避免死锁：在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁的产生
检测死锁：允许系统在运行过程中发生死锁，但可检测死锁的发生，并采取适当措施加以清除
解除死锁：当检测出死锁后，采取措施将进程从死锁状态中解脱出来

（4）预防死锁

破坏互斥条件：采用虚拟分配技术排除非共享设备死锁的可能性。
破坏不可剥夺条件：
- 允许资源抢占
破坏占有并等待：
- 一次性资源分配方案
- 每个进程申请资源前，释放它所占有的资源
破坏循环等待条：静态资源分配、有序资源分配、修复死锁、重启系统。

（5）避免死锁

方法：

有序资源分配法：资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），必须以上升的次序申请资源。
银行家算法：系统给当前进程分配资源时，先检查是否安全，如果安全，允许分配资源，否则让进程进入等待状态。
- https://blog.csdn.net/wljliujuan/article/details/79651932/

技术：

加锁顺序：线程按照一定的顺序加锁，要求事先知道所有可能会用到的锁，并对这些锁做适当的排序，但总有些时候是无法预知的。
加锁时限：线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁。如果有非常多的线程同一时间去竞争同一批资源，就算有超时和回退机制，还是可能会导致这些线程重复地尝试但却始终得不到锁。
死锁检测：死锁检测是一个更好的死锁预防机制，它主要是针对那些不可能实现按序加锁并且锁超时也不可行的场景。

（6）检测死锁

（7）解除死锁

资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

三数据库

3.1 基础知识

3.1.1 数据库架构

（1）说说MySQL的基础架构

Mysql逻辑架构图主要分三层：

（1）第一层负责连接处理，授权认证，安全等等

（2）第二层负责编译并优化SQL

（3）第三层是存储引擎。

（2）一条SQL查询语句在MySQL中如何执行的？

先检查该语句是否有权限，如果没有权限，直接返回错误信息，如果有权限会先查询缓存(MySQL8.0 版本以前)。
如果没有缓存，分析器进行词法分析，提取 sql 语句中 select 等关键元素，然后判断 sql 语句是否有语法错误，比如关键词是否正确等等。
最后优化器确定执行方案进行权限校验，如果没有权限就直接返回错误信息，如果有权限就会调用数据库引擎接口，返回执行结果。

3.1.2 索引

（1）聚集索引与非聚集索引的区别

可以按以下四个维度回答：

一个表中只能拥有一个聚集索引，而非聚集索引一个表可以存在多个。
聚集索引，索引中键值的逻辑顺序决定了表中相应行的物理顺序；非聚集索引，索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。
索引是通过二叉树的数据结构来描述的，我们可以这么理解聚簇索引：索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块。
聚集索引：物理存储按照索引排序；非聚集索引：物理存储不按照索引排序；

（2）为什么用B+树而不用二叉搜索树

可以从几个维度去看这个问题，查询是否够快，效率是否稳定，存储数据多少，以及查找磁盘次数，为什么不是普通二叉树，为什么不是平衡二叉树，为什么不是B树，而偏偏是 B+ 树呢？

为什么不是普通二叉树？

如果二叉树特殊化为一个链表，相当于全表扫描。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。

为什么不是平衡二叉树呢？

我们知道，在内存比在磁盘的数据，查询效率快得多。如果树这种数据结构作为索引，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，但是平衡二叉树可是每个节点只存储一个键值和数据的，如果是B树，可以存储更多的节点数据，树的高度也会降低，因此读取磁盘的次数就降下来啦，查询效率就快啦。

为什么不是 B 树而是 B+ 树呢？

B+ 树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。innodb中页的默认大小是16KB，如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。

B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，链表连着的。那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。

（3）Hash 索引和 B+ 树索引区别是什么？你在设计索引是怎么抉择的？

B+ 树可以进行范围查询，Hash 索引不能。
B+ 树支持联合索引的最左侧原则，Hash 索引不支持。
B+ 树支持 order by 排序，Hash 索引不支持。
Hash 索引在等值查询上比 B+ 树效率更高。
B+ 树使用 like 进行模糊查询的时候，like 后面（比如%开头）的话可以起到优化的作用，Hash 索引根本无法进行模糊查询。

（4）什么是最左前缀原则？什么是最左匹配原则？

最左前缀原则，就是最左优先，在创建多列索引时，要根据业务需求，where 子句中使用最频繁的一列放在最左边。

当我们创建一个组合索引的时候，如 (a1,a2,a3)，相当于创建了（a1）、(a1,a2)和(a1,a2,a3)三个索引，这就是最左匹配原则。

（5）索引不适合哪些场景?

数据量少的不适合加索引
更新比较频繁的也不适合加索引 = 区分度低的字段不适合加索引（如性别）

（6）索引有哪些优缺点？

(1) 优点：

唯一索引可以保证数据库表中每一行的数据的唯一性
索引可以加快数据查询速度，减少查询时间

(2)缺点：

创建索引和维护索引要耗费时间
索引需要占物理空间，除了数据表占用数据空间之外，每一个索引还要占用一定的物理空间
以表中的数据进行增、删、改的时候，索引也要动态的维护。

3.1.3 锁

（1）悲观锁、乐观锁的区别？

悲观锁：

悲观锁她专一且缺乏安全感了，她的心只属于当前事务，每时每刻都担心着它心爱的数据可能被别的事务修改，所以一个事务拥有（获得）悲观锁后，其他任何事务都不能对数据进行修改啦，只能等待锁被释放才可以执行。

乐观锁：

乐观锁的“乐观情绪”体现在，它认为数据的变动不会太频繁。因此，它允许多个事务同时对数据进行变动。

实现方式：乐观锁一般会使用版本号机制或CAS算法实现。

（2）什么是MVCC？它的底层原理是什么？

MVCC (Multiversion Concurrency Control)，即多版本并发控制技术。

MVCC在MySQL InnoDB中的实现主要是为了提高数据库并发性能，用更好的方式去处理读-写冲突，做到即使有读写冲突时，也能做到不加锁，非阻塞并发读。

3.1.4 查询优化

（1）怎么优化SQL

优化表结构

尽量使用数字型字段

若只含数值信息的字段尽量不要设计为字符型，这会降低查询和连接的性能，并会增加存储开销。这是因为引擎在处理查询和连接时会逐个比较字符串中每一个字符，而对于数字型而言只需要比较一次就够了。

尽可能的使用 varchar 代替 char

变长字段存储空间小，可以节省存储空间。

当索引列大量重复数据时，可以把索引删除掉

比如有一列是性别，几乎只有男、女、未知，这样的索引是无效的。

优化查询

应尽量避免在 where 子句中使用!=或<>操作符
应尽量避免在 where 子句中使用 or 来连接条件
任何查询也不要出现select *
避免在 where 子句中对字段进行 null 值判断

索引优化

对作为查询条件和 order by的字段建立索引
避免建立过多的索引，多使用组合索引

（2）关心过业务系统里面的sql耗时吗？统计过慢查询吗？对慢查询都怎么优化过？

我们平时写Sql时，都要养成用explain分析的习惯。慢查询的统计，运维会定期统计给我们

优化慢查询思路：

分析语句，是否加载了不必要的字段/数据
分析 SQL 执行句话，是否命中索引等
如果 SQL 很复杂，优化 SQL 结构
如果表数据量太大，考虑分表

3.1.5 事务

（1）MySQL事务的四大特性以及实现原理

原子性：事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。
一致性：指在事务开始之前和事务结束以后，数据不会被破坏，假如A账户给B账户转10块钱，不管成功与否，A和B的总金额是不变的。
隔离性：多个事务并发访问时，事务之间是相互隔离的，即一个事务不影响其它事务运行效果。简言之，就是事务之间是进水不犯河水的。
持久性：表示事务完成以后，该事务对数据库所作的操作更改，将持久地保存在数据库之中。

（2）事务的隔离级别有哪些？MySQL的默认隔离级别是什么？

读未提交（Read Uncommitted）
读已提交（Read Committed）
可重复读（Repeatable Read）
串行化（Serializable）

Mysql默认的事务隔离级别是可重复读(Repeatable Read)

（3）什么是幻读，脏读，不可重复读呢？

事务A、B交替执行，事务A被事务B干扰到了，因为事务A读取到事务B未提交的数据，这就是脏读。

在一个事务范围内，两个相同的查询，读取同一条记录，却返回了不同的数据，这就是不可重复读。

事务A查询一个范围的结果集，另一个并发事务B往这个范围中插入/删除了数据，并静悄悄地提交，然后事务A再次查询相同的范围，两次读取得到的结果集不一样了，这就是幻读。

3.2 MYSQL

3.2.1 数据引擎

（1）MyISAM和InnoDB区别

MyISAM是MySQL的默认数据库引擎（5.5版之前）。虽然性能极佳，⽽且提供了⼤量的特性，包括全⽂索引、压缩、空间函数等，但MyISAM不⽀持事务和⾏级锁，⽽且最⼤的缺陷就是崩溃后⽆法安全恢复。不过，5.5版本之后，MySQL引⼊了InnoDB（事务性数据库引擎），MySQL 5.5版本后默认的存储引擎为InnoDB。

1.是否支持行级锁

MyISAM 只有表级锁(table-level locking)，而 InnoDB 支持行级锁(row-level locking)和表级锁,默认为行级锁。

也就说，MyISAM 一锁就是锁住了整张表，这在并发写的情况下是多么滴憨憨啊！这也是为什么 InnoDB 在并发写的时候，性能更牛皮了！

2.是否支持事务

MyISAM 不提供事务支持。

InnoDB 提供事务支持，具有提交(commit)和回滚(rollback)事务的能力。

3.是否支持外键

MyISAM 不支持，而 InnoDB 支持。

🌈 拓展一下：

一般我们也是不建议在数据库层面使用外键的，应用层面可以解决。不过，这样会对数据的一致性造成威胁。具体要不要使用外键还是要根据你的项目来决定。

4.是否支持数据库异常崩溃后的安全恢复

MyISAM 不支持，而 InnoDB 支持。

使用 InnoDB 的数据库在异常崩溃后，数据库重新启动的时候会保证数据库恢复到崩溃前的状态。这个恢复的过程依赖于 redo log 。

🌈 拓展一下：

MySQL InnoDB 引擎使用 redo log(重做日志) 保证事务的持久性，使用 undo log(回滚日志) 来保证事务的原子性。
MySQL InnoDB 引擎通过 锁机制、MVCC 等手段来保证事务的隔离性（默认支持的隔离级别是 REPEATABLE-READ ）。
保证了事务的持久性、原子性、隔离性之后，一致性才能得到保障。

5.是否支持 MVCC

MyISAM 不支持，而 InnoDB 支持。

讲真，这个对比有点废话，毕竟 MyISAM 连行级锁都不支持。

MVCC 可以看作是行级锁的一个升级，可以有效减少加锁操作，提供性能。

3.2.2 锁

表级锁： MySQL 中锁定 粒度最大 的一种锁，对当前操作的整张表加锁，实现简单，资源消耗也比较少，加锁快，不会出现死锁。其锁定粒度最大，触发锁冲突的概率最高，并发度最低，MyISAM 和 InnoDB 引擎都支持表级锁。
行级锁： MySQL 中锁定 粒度最小 的一种锁，只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，并发度高，但加锁的开销也最大，加锁慢，会出现死锁。

3.2.3 实战应用

（1）MySQL数据库cpu飙升的话，要怎么处理呢？

排查过程：

（1）使用top 命令观察，确定是mysqld导致还是其他原因。（2）如果是mysqld导致的，show processlist，查看session情况，确定是不是有消耗资源的sql在运行。（3）找出消耗高的 sql，看看执行计划是否准确，索引是否缺失，数据量是否太大。

处理：

（1）kill 掉这些线程(同时观察 cpu 使用率是否下降)，（2）进行相应的调整(比如说加索引、改 sql、改内存参数) （3）重新跑这些 SQL。

其他情况：

也有可能是每个 sql 消耗资源并不多，但是突然之间，有大量的 session 连进来导致 cpu 飙升，这种情况就需要跟应用一起来分析为何连接数会激增，再做出相应的调整，比如说限制连接数等

（2）MySQL的主从延迟，你怎么解决？

步骤一：主库的更新事件(update、insert、delete)被写到binlog
步骤二：从库发起连接，连接到主库。
步骤三：此时主库创建一个binlog dump thread，把binlog的内容发送到从库。
步骤四：从库启动之后，创建一个I/O线程，读取主库传过来的binlog内容并写入到relay log
步骤五：还会创建一个SQL线程，从relay log里面读取内容，从Exec_Master_Log_Pos位置开始执行读取到的更新事件，将更新内容写入到slave的db

主从同步延迟的原因

一个服务器开放Ｎ个链接给客户端来连接的，这样有会有大并发的更新操作, 但是从服务器的里面读取binlog的线程仅有一个，当某个SQL在从服务器上执行的时间稍长或者由于某个SQL要进行锁表就会导致，主服务器的SQL大量积压，未被同步到从服务器里。这就导致了主从不一致，也就是主从延迟。

主从同步延迟的解决办法

主服务器要负责更新操作，对安全性的要求比从服务器要高，所以有些设置参数可以修改，比如sync_binlog=1，innodb_flush_log_at_trx_commit = 1 之类的设置等。
选择更好的硬件设备作为slave。
把一台从服务器当度作为备份使用，而不提供查询，那边他的负载下来了，执行relay log 里面的SQL效率自然就高了。
增加从服务器喽，这个目的还是分散读的压力，从而降低服务器负载。

（3）如果让你做分库与分表的设计，简单说说你会怎么做？

分库分表方案:

水平分库：以字段为依据，按照一定策略（hash、range等），将一个库中的数据拆分到多个库中。
水平分表：以字段为依据，按照一定策略（hash、range等），将一个表中的数据拆分到多个表中。
垂直分库：以表为依据，按照业务归属不同，将不同的表拆分到不同的库中。
垂直分表：以字段为依据，按照字段的活跃性，将表中字段拆到不同的表（主表和扩展表）中。

常用的分库分表中间件：

sharding-jdbc
Mycat

分库分表可能遇到的问题

事务问题：需要用分布式事务啦
跨节点Join的问题：解决这一问题可以分两次查询实现
跨节点的count,order by,group by以及聚合函数问题：分别在各个节点上得到结果后在应用程序端进行合并。
数据迁移，容量规划，扩容等问题
ID问题：数据库被切分后，不能再依赖数据库自身的主键生成机制啦，最简单可以考虑UUID
跨分片的排序分页问题

3.3 Redis

3.3.1 Redis内存淘汰策略

彻底弄懂Redis的内存淘汰策略 - 知乎 (zhihu.com)

3.3.2 Redis的pipeline

(14条消息) 分布式缓存Redis之Pipeline（管道）_ZhangRui的博客-CSDN博客

四常用框架

4.1 Spring

4.1.1 基本概念

（1）什么是Spring

轻量级的JavaEE开发框架

Spring的两个重要特性

IOC：控制反转，将创建对象的过程交给Spring进行管理
AOP：面向切面，不修改源代码的情况加进行功能增强

4.1.2 控制反转（IOC）

https://mp.weixin.qq.com/s/0zRks2Cz36S8N70Uonb0OA

（1）什么是Spring IOC容器？

Spring IOC 负责创建对象，管理对象（通过依赖注入（DI）实现），装配对象，配置对象，并且管理这些对象的整个生命周期。

（2）什么是IOC？

控制反转：从主动创建对象变为被动接受对象（例如使用setter方式创建）

（3）使用IOC的好处

它将最小化应用程序中的代码量。
它将使您的应用程序易于测试，因为它不需要单元测试用例中的任何单例或 JNDI 查找机制。
它以最小的影响和最少的侵入机制促进松耦合。
它支持即时的实例化和延迟加载服务。

（4）关键概念

控制：资源的获取方式
- 主动式：使用new方式创建资源，复杂对象的创建过于繁琐、麻烦。
- 被动式：资源的创建过程由容器来创建和设置，我们直接使用资源即可。
容器：管理所有的组件（有功能的类）。
反转：将资源创建的过程交给Spring来做。
DI，Denpendency Injection：依赖注入，通过反射创建组件。

（5）Spring中有几种IOC容器？

BeanFactory ：粗暴简单，可以理解为就是个 HashMap，Key 是 BeanName，Value 是 Bean 实例。通常只提供注册（put），获取（get）这两个功能。我们可以称之为 “低级容器”。
ApplicationContext：可以称之为 “高级容器”。因为他比 BeanFactory 多了更多的功能。他继承了多个接口。因此具备了更多的功能。例如资源的获取，支持多种消息（例如 JSP tag 的支持），对 BeanFactory 多了工具级别的支持等待。所以你看他的名字，已经不是 BeanFactory 之类的工厂了，而是 “应用上下文”，代表着整个大容器的所有功能。该接口定义了一个 refresh 方法，此方法是所有阅读 Spring 源码的人的最熟悉的方法，用于刷新整个容器，即重新加载/刷新所有的 bean。

BeanFactory	ApplicationContext
它使用懒加载	它使用即时加载
它使用语法显式提供资源对象	它自己创建和管理资源对象
不支持国际化	支持国际化
不支持基于依赖的注解	支持基于依赖的注解

4.1.3 面向切面（AOP）

（1）什么是AOP？

AOP（Aspect Oriented Programming）：面向切面编程，指在程序运行期间，将某段代码动态的切入到**指定方法的指定位置**进行运行的编程方式。

（2）哪些场景下会使用到AOP？

场景：计算器运行计算方法的时候进行日志记录
- 直接编写在方法内部：耦合度太高，修改维护麻烦，不推荐
- 使用动态代理加入日志

（3）AOP的好处？

降低模块的耦合度、添加新的功能而不修改源代码

（4）AOP底层原理

使用动态代理：

有接口：使用JDK动态代理
无接口：使用CGLIB动态代理

4.1.4 进阶知识

（1）Spring用到了哪些设计模式？

工厂模式：Spring使用工厂模式可以通过 BeanFactory 或 ApplicationContext 创建 bean 对象。

单例模式：Spring 中 bean 的默认作用域就是 singleton(单例)的

代理模式：AOP(Aspect-Oriented Programming:面向切面编程)能够将那些与业务无关，却为业务模块所共同调用的逻辑或责任（例如事务处理、日志管理、权限控制等）封装起来，便于减少系统的重复代码，降低模块间的耦合度，并有利于未来的可拓展性和可维护性。

Spring AOP 就是基于动态代理的，如果要代理的对象，实现了某个接口，那么Spring AOP会使用JDK Proxy，去创建代理对象，而对于没有实现接口的对象，就无法使用 JDK Proxy 去进行代理了，这时候Spring AOP会使用Cglib ，这时候Spring AOP会使用 Cglib 生成一个被代理对象的子类来作为代理

观察者模式：观察者模式是一种对象行为型模式。它表示的是一种对象与对象之间具有依赖关系，当一个对象发生改变的时候，这个对象所依赖的对象也会做出反应。Spring 事件驱动模型就是观察者模式很经典的一个应用

适配器模式：

装饰者模式：

六微服务、分布式

高并发、高可用

Reference:

Tags: all

← Java SPI 机制 paper-summarizer →

Java知识点全面梳理(完善中)

一 Java基础+集合+多线程+JVM

1.1 Java基础

1.1.1 Java基础知识

（1）Java的特点？

（2） 面向过程和面向对象？

（3） JVM、JDK、JRE的区别和联系？

（4） Java和C++的区别和联系

（5）为什么说Java编译和解释并存？

（6）字符型常量和字符串常量的区别？

（7）重载和重写的区别？

（8）== 和 equals 的区别？⭐

（9）hashCode()与equals()⭐

（10）自动装箱和自动拆箱

（11）常量池

（12）深拷贝和浅拷贝

（13）StringBuffer和StringBuilder的区别和联系？

（14）String为什么是不可变的？

（15）一个char占用多少字节？

1.1.2 面向对象

（1）面向对象的三大特性：封装、继承、多态

（2）成员变量和局部变量的区别？

（3）对象相等和它们的引用相等

（4）final关键字

（5）一个空字符串占用多少字节

（6）String Pool的底层结构

1.1.3 异常

（1）异常的分类

（2）异常处理

1.1.4 Java IO

（1）IO流分类

（2）BIO、NIO、AIO地区别

1.1.5 程序、进程和线程

（1）程序、进程、线程的定义

1.1.6 String类和常量池

（1）String

（2）String s=new String(“xyz”)会创建几个对象

1.2 集合

1.2.1 常见容器的比较

（1）List、Set、Map的比较

（2）ArrayList和Vector的区别

（3）ArrayList和LinkedList区别

（4）HashMap和HashTable的区别

（5）HashSet、LinkedHashSet、TreeSet的异同

（6）无序性和不可重复性的含义是什么？

（7）Comparable和Comparator的区别

1.2.2 容器结构的底层实现

（1） List、Set、Map

（2）ArrayList的扩容机制

（3）HashMap的底层实现

（4）HashSet如何检查重复

（5）HashMap 的⻓度为什么是2的幂次⽅

1.2.3 ConcurrentHashmap

（1）ConcurrentHashMap 和 Hashtable 的区别

（2）ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

（3）ConcurrentHashMap读写过程（JDK1.7）

1.3 多线程

1.3.1 基本概念

（1）什么是进程

（2）什么是线程

（3）什么是协程

（4）进程和线程的关系

（5）线程的上下文切换

（6）并发和并行的区别

（7）为什么使用多线程？

（8）使用多线程带来的问题

（9） 内核线程实现

（10） 用户线程实现

（11）上下文切换

1.3.2 Java的多线程

（1）程序计数器为什么是私有的？

（2）虚拟机栈和本地方法栈为什么是私有的？

（3）堆和方法区

（4）线程的生命周期和状态

（5）sleep() 和 wait()

（6）start() 和 run()

1.3.3 synchronized

（1）synchronized关键字

（2）synchronized的三种使用方式

（3）synchronized底层原理

（2）面向过程和面向对象？

（13）`StringBuffer`和`StringBuilder`的区别和联系？

（14）`String`为什么是不可变的？

（9）内核线程实现

（10）用户线程实现

二计算机基础