单例模式

发表于2023-06-03更新于2023-09-08字数统计1.1k阅读时长6分

1.单例模式的基本概念

整个程序全局中只能有一个属于该对象的类，并且只提供单一入口供使用者调用该类。也就是说，使用了单例模式的对象不允许在程序中出现两个相同的对象。

特点：

单例模式全局只能有唯一实例
单例模式全局的唯一实例必须由其自己创建
单例模式必须提供其他调用方获取该实例的方法

2.单例模式的适用场景

生命周期短的对象

频繁访问io资源的对象，如数据库连接池，redis配置等

只需要调用该对象方法，对该对象没有任何修改动作且频繁使用的对象

3.单例模式示例

构建单例模式，一般需要三个语句

初始化静态私有成员变量
无参构造器
对外暴露能够得到这个对象的方法

3.1 饿汉模式

public class HungrySingleton {

    // 1. 初始化静态私有成员变量
    private static HungrySingleton hungrySingleton = new HungrySingleton();

    // 2. 无参构造器
    HungrySingleton(){}

    // 3. 对外暴露能够得到这个对象的方法
    public static HungrySingleton getHungrySingleton() {
        return hungrySingleton;
    }
}

优点：程序执行的时候就立刻初始化成员变量，在类被加载的时候就将初始化好的成员变量存放入内存中，在调用对象时运行速度会变快。

缺点：大量使用饿汉模式会占据一定的系统内存，导致系统运行速度变慢。

3.2 懒汉模式

// 1. 静态私有唯一对象
private static LazySingleton lazySingleton;

// 2. 空参构造器
LazySingleton(){}

// 3. 静态方法获取该类对象暴露(需要加锁，防止多个对象在单例模式中的创建)
public static LazySingleton getLazySingleton() {
    synchronized (LazySingleton.class) {
        if (lazySingleton == null) {
            lazySingleton = new LazySingleton();
        }
    }
    return lazySingleton;
}

优点：等到需要调用该类对象的时候才初始化对象，一定程度上节约了内存

缺点：因为防止重复创建对象加上的锁导致多人调用的时候可能运行时间会较长，接近于串行运行。

3.3 双检锁模式

// 1. 静态私有唯一对象
// 这里加volatile的原因是为了防止指令重排序而引发的返回一个没有初始化完全的单例对象
private static volatile DoubleCheckSingleton doubleCheckSingleton;

// 2. 空参构造器
DoubleCheckSingleton() {
}

// 3. 静态方法获取该类对象暴露(需要加锁，防止多个对象在单例模式中的创建)
// 再加一层判断，需要创建新对象的时候才用到锁
public static DoubleCheckSingleton getDoubleCheckSingleton() {
    if (doubleCheckSingleton == null) {
        synchronized (DoubleCheckSingleton.class) {
            if (doubleCheckSingleton == null) {
                doubleCheckSingleton = new DoubleCheckSingleton();
            }
        }
    }
    return doubleCheckSingleton;
}

volatile关键字：可以保证可见性和防止指令重排序，预防极端情况下因为指令重排序而引发的返回一个没有初始化完全的单例对象。
双检锁两层判断的意义：
1. 第一层，判断是否已经获得了单例对象，如果获得了，没必要增强，直接使用，为了提高效率
2. 第二层，锁内判断，防止获取两个单例对象，为了保证单例对象的唯一性

3.4 静态内部类模式

public class StaticClassSingleton {
    private static class innerStaticClassHolder {
        private static final StaticClassSingleton STATIC_CLASS_SINGLETON = new StaticClassSingleton();
    }

    StaticClassSingleton(){};

    public static StaticClassSingleton getStaticClassSingleton() {
        return innerStaticClassHolder.STATIC_CLASS_SINGLETON;
    }
}

静态内部类单例模式：基本和双检锁差不多，都是调用后才创建对象，也能保证对象的唯一性

但是只能运用在静态方法类中可保证线程安全(没有任何new的操作)，也能保证单例的唯一性，同时也延迟了单例的实例化。

3.5 枚举模式

/**
 * 枚举单例模式：防止反序列化造成的单例破坏
 */
public enum EnumSingleton {
    ENUM_SINGLETON;

    public static EnumSingleton getEnumSingleton() {
        return ENUM_SINGLETON;
    }

}

防止反序列化造成的单例破坏

推荐使用静态内部类模式，因为他不用new对象，不会产生多个对象的问题；

推荐使用枚举模式，因为他可以防止反序列化造成的单例破坏

JVM内存结构

发表于2023-06-03更新于2023-09-11字数统计2.6k阅读时长21分

JVM内存结构

内存结构基本示意图：

1. 程序计数器

1.1 定义

行号指示器，字节码解释器运行时通过改变计数器值来选取下一条需要执行的字节码指令。

1.2 特点

每条线程都需要有独立的程序计数器，线程私有

唯一一个不会出现OutOfMemoryError情况的内存区域

2. 栈

2.1 栈和栈帧

栈：线程运行所需要的内存空间
1. 线程生命周期和栈的生命周期相同
2. 栈的内存空间和线程数呈负相关
栈帧：每个方法运行时所需要的内存
1. 存储局部变量表，操作数栈，动态连接，方法出口等
2. 生命周期和方法相同，每个方法调用直到执行完毕，就对应着栈帧入栈到出栈的过程。

局部变量表：用于存储方法参数和局部变量等

2.2 栈的线程安全

！！！方法内的局部变量是否涉及线程安全：

线程安全：保证多个线程同时对某一对象或资源进行操作时不会出错

如果方法内局部变量没有逃离方法作用范围，那么他是**线程安全**的:

没有逃离方法的作用范围，局部变量无逃逸，无法被其他线程访问。

public static void m1() {
    StringBuilder sb = new StringBuilder();
    sb.append(1);
    sb.append(2);
    sb.append(3);
    System.out.println(sb.toString());
}

如果局部变量引用了对象，并逃离方法的作用范围，那么他是**不安全**的:

作为参数传参进入，可以会有被别的对象调用的风险。
1
2
3
4
5
6
public static void m2(StringBuilder sb) {
sb.append(1);
sb.append(2);
sb.append(3);
System.out.println(sb.toString());
}

存在返回值，有可能被他人调用：

public static StringBuilder m3() {
    StringBuilder sb = new StringBuilder();
    sb.append(1);
    sb.append(2);
    sb.append(3);
    return sb;
}

2.3 栈的有关异常

StackOverFlowError: 线程请求的栈深度大于虚拟机所允许的深度

一般出现原因为递归调用无设置终止条件或者终止条件无法达到

public class Demo1_2 {
    private static int count;

    public static void main(String[] args) {
        try {
            method1();
        } catch (Throwable e) {
            e.printStackTrace();
            System.out.println(count);
        }
    }

    private static void method1() {
        count++;
        method1(); //递归调用自己，但是没有设置终止条件
    }
}

OutOfMemoryError: 栈无法申请到足够多的内存空间时

与内存空间有关。

3. 本地方法栈

为本地方法运行提供空间的内存空间

public native int hashCode();

1
2
3

public boolean equals(Object obj) {
    return (this == obj);
}

含有**native关键字**修饰的方法
object: motify, add, hashcode….

4. 堆

4.1 定义

是被所有线程共享的一块区域，在虚拟机启动的时候自动创建，目的是存放对象实例(new)。

4.2 特点

线程共享，需要考虑线程安全的问题
在虚拟机启动的时候自动创建
有垃圾回收机制

4.3 堆内存溢出

java.lang.OutOfMemoryError: Java heap space：

public static void main(String[] args) {
    int i = 0;
    try {
        List<String> list = new ArrayList<>();
        String a = "hello";
        while (true) {
            list.add(a); // hello, hellohello, hellohellohellohello ...
            a = a + a;  // hellohellohellohello
            i++;
        }
    } catch (Throwable e) {
        e.printStackTrace();
        System.out.println(i);
    }
}

4.4 堆内存诊断

JPS：查看系统中有哪些java进程

直接在Terminal窗口输入jps中可得到下图结果。

//进程编号         //进程名称
11936              Jps
13664              Demo1_4
436              
9388              Launcher

Jmap：观测指定进程的内存情况

用 jmap -heap + 进程编号查看当前进程的运行情况

Configuration```：堆配置信息


```MaxHeapSize```： 最大堆空间



<img src="/source/images/jmap2.png" style="zoom:67%;" align="left"/>

```Heap Usage```： 堆使用情况

```used```： 已经使用

```free```： 未使用



- **Jconsole：图形化页面监测工具，可以实现动态的检测**

<img src="/source/images/jconsole.png" style="zoom:50%;" align="left" />



## 5. 方法区

### 5.1 作用

存储被虚拟机加载的类型信息，常量，静态变量，代码缓存等数据



### 5.2  JVM1.8和1.6不同的组成

![](/source/images/MethodArea.png)

主要变化：实现方式由永久代转变为了元空间，常量池中```StringTable```放到了堆内存中。

原因：永久代垃圾回收机制为```Full GC```，回收效率低，易导致临时变量占据空间过多，堆内存中垃圾回收机制较永久代灵活



### 5.3 方法区内存溢出



```java
    public static void main(String[] args) {
        int j = 0;
        try {
            Demo1_8 test = new Demo1_8();
            for (int i = 0; i < 10000; i++, j++) {
                // ClassWriter 作用是生成类的二进制字节码
                ClassWriter cw = new ClassWriter(0);
                // 版本号， public， 类名, 包名, 父类， 接口
                cw.visit(Opcodes.V1_8, Opcodes.ACC_PUBLIC, "Class" + i, null, "java/lang/Object", null);
                // 返回 byte[]
                byte[] code = cw.toByteArray();
                // 执行了类的加载
                test.defineClass("Class" + i, code, 0, code.length); // Class 对象
            }
        } finally {
            System.out.println(j);
        }
    }

1.8 元空间内存溢出

1 2	// java.lang.OutOfMemoryError: Metaspace // -XX:MaxMetaspaceSize=8m

1.6 永久代内存溢出

1 2	// java.lang.OutOfMemoryError: PermGen space // -XX:MaxPermSize=8m

6. 常量池

作用：用于存储信息，本身时二进制字节码对象，常量池中的信息，都会被加载到运行时常量池中，这时 a b ab 都是常量池中的符号，还没有变为 java 字符串对象

通过javap -v HelloWorld.class可以获得class二进制字节码文件的基本信息

  // 基本配置信息
  Last modified 2022-11-24; size 442 bytes
  MD5 checksum 103606e24ec918e862312533fda15bbc
  Compiled from "HelloWorld.java"
public class cn.itcast.jvm.t5.HelloWorld
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
      //常量池
Constant pool:
   #1 = Methodref          #6.#15         // java/lang/Object."<init>":()V
   #2 = Fieldref           #16.#17        // java/lang/System.out:Ljava/io/PrintStream;
   #3 = String             #18            // hello world
   #4 = Methodref          #19.#20        // java/io/PrintStream.println:(Ljava/lang/String;)V
   #5 = Class              #21            // cn/itcast/jvm/t5/HelloWorld
   #6 = Class              #22            // java/lang/Object
   #7 = Utf8               <init>
   #8 = Utf8               ()V
   #9 = Utf8               Code
  #10 = Utf8               LineNumberTable
  #11 = Utf8               main
  #12 = Utf8               ([Ljava/lang/String;)V
  #13 = Utf8               SourceFile
  #14 = Utf8               HelloWorld.java
  #15 = NameAndType        #7:#8          // "<init>":()V
  #16 = Class              #23            // java/lang/System
  #17 = NameAndType        #24:#25        // out:Ljava/io/PrintStream;
  #18 = Utf8               hello world
  #19 = Class              #26            // java/io/PrintStream
  #20 = NameAndType        #27:#28        // println:(Ljava/lang/String;)V
  #21 = Utf8               cn/itcast/jvm/t5/HelloWorld
  #22 = Utf8               java/lang/Object
  #23 = Utf8               java/lang/System
  #24 = Utf8               out
  #25 = Utf8               Ljava/io/PrintStream;
  #26 = Utf8               java/io/PrintStream
  #27 = Utf8               println
  #28 = Utf8               (Ljava/lang/String;)V
                             
   // 类方法定义
{
  public cn.itcast.jvm.t5.HelloWorld();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 4: 0

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=1, args_size=1
         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: ldc           #3                  // String hello world
         5: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
         8: return
      LineNumberTable:
        line 6: 0
        line 7: 8
}

主要操作流程：根据指令后面编号去查找相应内容

7. StringTable

 public static void main(String[] args) {
        String s1 = "a";
        String s2 = "b";
        String s3 = "a" + "b"; // ab
        String s4 = s1 + s2;   // new String("ab")
        String s5 = "ab";
        String s6 = s4.intern();

// 问
        System.out.println(s3 == s4); // false
        System.out.println(s3 == s5); // true
        System.out.println(s3 == s6); // true

        String x2 = new String("c") + new String("d"); // new String("cd")
        x2.intern();
        String x1 = "cd";

// 问，如果调换了【最后两行代码】的位置呢，如果是jdk1.6呢
        System.out.println(x1 == x2);
    }

7.1 常量池与串池之间的关系

常量池中存储的信息只是作为一个符号，通过方法调用（String a = "a"）或引用的时候才能真正的成为一个对象，而这时候如果串池中没有该对象的时候，将对象放入串池

懒惰性：用到了才会在串池中创建，没有用到不会创建（延迟加载）

HashCode结构

7.2 字符串拼接

String s1 = "a";
String s2 = "b";
String s3 = s1 + s2;
String s4 = "ab";
// new StringBuilder().append("a").append("b").toString()-> new String("ab")
// toString()方法生成了一个新的String对象

return s3 == s4; //false

7.3 编译期优化

String s1 = "a";
String s2 = "b";
String s3 = "a" + "b"; //编译期的优化：两个常量之和是确定的
String s4 = "ab";
return s3 == s4 //true

7.4 intern()方法

将字符串对象放入串池，有则不会放入，无则放入后返回

public static void main(String[] args) {

   
    String s = new String("a") + new String("b");

    // 堆  new String("a")   new String("b") new String("ab")
    String s2 = s.intern(); // 将这个字符串对象尝试放入串池，如果有则并不会放入，如果没有则放入串池， 会把串池中的对象返回
 	String x = "ab";
    System.out.println( s2 == x); //true
    System.out.println( s == x ); //true
}

地址复制后放入串池（和原来的地址不相同）

public static void main(String[] args) {

String s = new String("a") + new String("b");

// 堆  new String("a")   new String("b") new String("ab")
String s2 = s.intern(); // 将这个字符串对象尝试放入串池，如果有则并不会放入，如果没有则放入串池， 会把串池中的对象返回
String x = "ab";
System.out.println( s2 == x); //true
System.out.println( s == x ); //false   因为s2是复制的，和原来地址并不一样

}

7.5 性能调优

调整-XX:StringTableSize=桶个数：桶个数多有利于提高效率

public static void main(String[] args) throws IOException {
    try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("linux.words"), "utf-8"))) {
        String line = null;
        long start = System.nanoTime();
        while (true) {
            line = reader.readLine();
            if (line == null) {
                break;
            }
            line.intern();
        }
        System.out.println("cost:" + (System.nanoTime() - start) / 1000000);
    }


}

考虑串是否入池：重复字符串入池有助于提高效率

public static void main(String[] args) throws IOException {

    List<String> address = new ArrayList<>();
    System.in.read();
    for (int i = 0; i < 10; i++) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("linux.words"), "utf-8"))) {
            String line = null;
            long start = System.nanoTime();
            while (true) {
                line = reader.readLine();
                if(line == null) {
                    break;
                }
                address.add(line.intern());
            }
            System.out.println("cost:" +(System.nanoTime()-start)/1000000);
        }
    }
    System.in.read();

8. 直接内存

8.1 作用

是一种操作系统的内存，可以通过NIO中的directBuffer对象来实现内存调用的效率提高

直接用buffer调用需要通过系统缓冲区和Java缓冲区，而directMomery可以直接访问

8.2 特点

分配回收成本高，读写性能高
和系统内存相关，和java本身堆大小无关

8.3 内存释放

通过unsafe对象对于directMomery对象的调用

工厂模式

发表于2023-06-02更新于2023-09-11字数统计796阅读时长4分

1.定义

该模式用来封装和管理类的创建，终极目的是为了解耦，实现创建者和调用者的分离。在工厂模式中，我们在创建对象时不会对客户端暴露创建逻辑，而是通过使用一个共同的接口来指向新创建的对象。这个接口可以留给子类自行选择用这个工厂生产什么类型的产品。

工厂模式的本质就是对获取对象过程的抽象。

2.适用范围

很多场景中都能够适用，比如spring中的beanFactory工厂。能生产多个具有一定相似度对象的都可以由工厂模式来进行处理。

3.实例

3.1 简单工厂模式

结构图

这是一个学生选课的系统，很符合工厂模式的供给。老师不可能自己凭空创造课程，而应该是学校教务创建好课程之后让老师去选择自己想要传授的课程。而工厂模式能给我们提供这样的选择，他通过ClassFactory类对外暴露了创建课程的接口，但具体的创建流程是完全封装起来的。能够保证安全性和实现解耦合。

其中在这个简单工厂模式中，我们需要实现三个内容：

工厂类（需要对外暴露生产产品的方法以及需要提供的参数，以及原材料提供，但是无需暴露生产逻辑）
抽象产品类
具体产品类

工厂类

public class ClassFactory {
    public Class createClass(String className) {
        switch (className) {
            case "computerNet":
                return new ComputerNet();
            case "DataStruct":
                return new DataStruct();
            case "OperatorSystem":
                return new OperatorSystem();
        }
        return null;
    }
}

我们会发现，这里还有很多的条件分支语句，这就是简单工厂模式的一个缺点，扩展性不强。后续需要工厂生产新产品的时候需要对源代码的逻辑产生修改，不符合开闭原则。我们可以用策略模式对其进行优化。

抽象课程类

public abstract class Class {

    public abstract String getName();

    public abstract String getTeacher();

    public abstract int getScore();

}

具体课程类

public class OperatorSystem extends Class{
    @Override
    public String getName() {
        return "操作系统";
    }

    @Override
    public String getTeacher() {
        return "我嫩爹";
    }

    @Override
    public int getScore() {
        return 4;
    }
}

3.2 工厂方法模式

定义一个抽象的接口，让子类决定实例化哪个类。

结构图

定义一个抽象方法工厂类，每一个具体的课程对象都有具体的工厂类进行创建，具体的实现交由子类进行处理，****工厂方法将对象的实例化推迟到了子类，便于后期的维护和扩展，之后如果需要新增课程的话，只需要再建立一个新的工厂对象去继承抽象工厂即可，对原来的代码没有影响。

3.3 抽象工厂模式

在抽象工厂类中新增创建该产品的抽象方法，然后在具体工厂子类中实现它即可。相当于工厂模式的一种拓展。

事务

发表于2023-05-31更新于2023-09-11字数统计1.6k阅读时长8分

事务的ACID的原则

一致性(Consistency)

一致性放在最前面因为其实ACID是有逻辑关系的。一致性是其他三个性质的结果，其他三个性质都是为了一致性服务。一致性指的事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。

隔离性(Isolation)

隔离性指的是事务和事务之间的关系。指的是每个事务之间都是独立的，可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。比如一个用户在执行对商品的购买的同时不会影响到其他用户对于商品的操作。

原子性(Atomacity)

原子性指的是一个事务内部之间的关系。原子性指的是该单位是不可分割的，要么全部执行成功，要么全部执行失败。也就是防止了因为意外情况数据库数据中止在中间状态。一旦执行到中间遇到意外事故，该条执行语句会选择回滚。

持久性(Durability)

持久性指的是数据库的语句一旦发生修改之后，该值就会持久的保留下来。

持久性是通过 redo log （重做日志）来保证的；
原子性是通过 undo log（回滚日志）来保证的；
隔离性是通过 MVCC（多版本并发控制）或锁机制来保证的；
一致性则是通过持久性+原子性+隔离性来保证；

并行事务引发的问题

脏读

脏读指的是一个事务读取到了另一个事务正在修改但还未提交的数据。如果事务A在操作数据库的时候，执行成功了还未提交，这时突然发生错误了，数据进行回滚，但是事务B读取到了修改一半的数据。这个数据就不应该存在，那么我们说此时出现了脏读的情况。事务B读取到了一个不存在的数据。

不可重复读

指的是同一个事务两次读取的数据是不一样的。这个产生的原因主要在于读取的中间可能突然有另一个事务对于数据进行修改，那么这时候事务A读取的数据就不是原子性的了，前后读取的不一样就被称为不可重复读了。

幻读

幻读指的是同一个事务两次读取的数据条目数是不同的。这个和不可重复读产生的原因类似，都是两次读取操作没有保持原子性。但区别是不可重复读主要是针对于数据的内容，而幻读主要是针对于数据的条目数量。

事务的隔离级别

读未提交（read uncommitted）

指一个事务还没提交时，它做的变更就能被其他事务看到；

读提交（read committed）

指一个事务提交之后，它做的变更才能被其他事务看到；

可重复读（repeatable read）

指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；

串行化（serializable ）

会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

Read View 在 MVCC 里如何工作的？

针对快照读（普通 select 语句），是通过 MVCC 方式解决了幻读，因为可重复读隔离级别下，事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，即使中途有其他事务插入了一条数据，是查询不出来这条数据的，所以就很好了避免幻读问题。
针对当前读（select … for update 等语句），是通过 next-key lock（记录锁+间隙锁）方式解决了幻读，因为当执行 select … for update 语句的时候，会加上 next-key lock，如果有其他事务在 next-key lock 锁范围内插入了一条记录，那么这个插入语句就会被阻塞，无法成功插入，所以就很好了避免幻读问题。

Read View 有四个重要的字段：

m_ids ：指的是在创建 Read View 时，当前数据库中「活跃事务」的事务 id 列表，注意是一个列表，“活跃事务”指的就是，启动了但还没提交的事务。
min_trx_id ：指的是在创建 Read View 时，当前数据库中「活跃事务」中事务 id 最小的事务，也就是 m_ids 的最小值。
max_trx_id ：这个并不是 m_ids 的最大值，而是创建 Read View 时当前数据库中应该给下一个事务的 id 值，也就是全局事务中最大的事务 id 值 + 1；
creator_trx_id ：指的是创建该 Read View 的事务的事务 id。

一个事务去访问记录的时候，除了自己的更新记录总是可见之外，还有这几种情况：

如果记录的 trx_id 值小于 Read View 中的 min_trx_id 值，表示这个版本的记录是在创建 Read View 前已经提交的事务生成的，所以该版本的记录对当前事务可见。
如果记录的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示这个版本的记录是在创建 Read View 后才启动的事务生成的，所以该版本的记录对当前事务不可见。
如果记录的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id 之间，需要判断 trx_id 是否在 m_ids 列表中：
- 如果记录的 trx_id 在 m_ids 列表中，表示生成该版本记录的活跃事务依然活跃着（还没提交事务），所以该版本的记录对当前事务不可见。
- 如果记录的 trx_id 不在 m_ids列表中，表示生成该版本记录的活跃事务已经被提交，所以该版本的记录对当前事务可见。

索引

发表于2023-05-29更新于2023-09-11字数统计3.3k阅读时长18分

索引在建表时候的形成

有规定主键索引的时候，采用主键索引。
没有规定主键索引时，采用第一列唯一非空列作为索引。
如果上述情况不存在，sql会自动生成一列隐性主键索引。

索引的分类

索引在数据结构中

主键索引的查找过程

首先从B+ Tree的根节点开始，找到属于其索引数据范围内的数据段对应的子节点，进入到下一个子节点。最后判断递归到叶子节点。
在叶子节点中，通过二分查找去寻找到对应的索引值相等的位置，或者大于小于的话可以通过B+ Tree独特的双向链表结构找到大于小于索引的值。
最后在主键索引中，B+ Tree的叶子节点存储的就是其对应的数据结构体的值。找到之后返回即可。

辅助索引的查找过程

基本等同与主键索引的查找过程，但是有一点要注意的是，在没有联合索引的情况下，辅助索引的叶子节点存储的是主键索引的索引值。所以，设置辅助索引的目的就是为了更方便的确定主键索引。这之后会有一次徽标的操作，也就是在遍历完一次辅助索引的B+ Tree之后再次遍历一次主键索引的B+ Tree。
那么在联合索引的情况下，辅助索引的叶子节点存储的就是联合索引的值了。之后再根据最左匹配原则来进行数据的查询。
优化辅助索引回表的关键在于：如果当需要的数据直接出现在叶子节点中（无论是主键索引还是辅助索引），那么sql语句解释器都会直接输出结果。那么我们就可以通过查询联合索引的方式来查询我们所需要查询的列。

例如：我们需要查询某个姓名的学生的姓名，语文成绩，数学成绩；那么我们就可以将（姓名，语文成绩，数学成绩作为联合索引）, select name, chinese, math from student where name = 'zhangsan'；那么这样就可以节约一次回表的操作了。

B+ Tree的优点

在查询效率和占用空间上来讲，其更加扁平化的结构相较于二叉搜索树来讲，在查询上结构更加高效，因为二叉搜索树只能最多有两个分支，而B+ Tree能有好多个分支。
相较于B Tree 来讲，其结构做的优化主要有两个点：
- 将所有具体的数据放在叶子节点，索引放在非叶子节点：这样相较于B Tree 中数据也放在非叶子节点可以提高查询的效率，因为我们只需要定位一个索引。
- 叶子节点以双向链表的形式进行连接，有效的方便了比较运算的查询。B Tree 中 where 条件有大于小于的需要一个个遍历，而在 B+ Tree 中只需要通过链表就可以了。

索引在物理结构中

主键索引（聚簇索引）

主键索引的 B+Tree 的叶子节点存放的是实际数据，所有完整的用户记录都存放在主键索引的 B+Tree 的叶子节点里；
一般主键索引都是采用递增的数字进行存储，因为这样的话对于索引的增删改查的操作的效率都能够有所提升。

普通索引（二级索引）

二级索引的 B+Tree 的叶子节点存放的是主键值，而不是实际数据。
可以通过查询联合索引的方式来查询我们所需要查询的列，以提高查询效率。

索引在字段特性中

从字段特性的角度来看，索引分为主键索引、唯一索引、普通索引、前缀索引。

索引在字段个数中

按照字段个数分的话，可以分为单列索引和联合索引。单列索引包括主键索引，普通索引，前面都有讲过。主要这个部分梳理联合索引的知识点。

联合索引的最左匹配原则

定义：在建立联合索引的时候，由于最左匹配原则的约束，字段的顺序不同是会产生不一样的结果的。主要体现在以最左边的字段作为第一个的排序。如果 where 条件构建的时候，没有以最左边第一个排序作为条件出现的话，那么联合索引就会失效。我们可以认为联合索引中的个体字段（除了最左字段）是全局无序，局部有序的。

比如，如果创建了一个 (a, b, c) 联合索引，如果查询条件是以下这几种，就可以匹配上联合索引：

where a=1；
where a=1 and b=2 and c=3；
where a=1 and b=2；

但是，如果查询条件是以下这几种，因为不符合最左匹配原则，所以就无法匹配上联合索引，联合索引就会失效:

where b=2；
where c=3；
where b=2 and c=3；

联合索引对于普通字段查询的优化

优化辅助索引回表的关键在于：如果当需要的数据直接出现在叶子节点中（无论是主键索引还是辅助索引），那么sql语句解释器都会直接输出结果。那么我们就可以通过查询联合索引的方式来查询我们所需要查询的列。

联合索引失效的情况

这里我们可以看到，对于a来讲，是有序的，但是对于b来讲，是无序的。而一个索引要使用的条件必须是有序的。

1	select * from t_table where a > 1 and b = 2

a字段可以通过索引进行查询，但是在a > 1 的条件下，b是无序的，所以无法通过索引进行查询。所以在这个where条件中，只有a的查询能够运用得上索引。

1	select * from t_table where a >= 1 and b = 2

a和b都运用到了联合索引进行排序，原因是 a 存在等于1的情况，那么在这个情况下，a固定下来，那么所有 a = 1的行中就会执行到以 b 为索引的查询，所以此时 b 能用得上索引。但是也是仅限于 a = 1 的情况下。a > 1仍然用不上索引。

1	SELECT * FROM t_table WHERE a BETWEEN 2 AND 8 AND b = 2

在mysql中，between and是大于等于，小于等于的关系，所以其实和上一个的道理是一样的。只要最左的联合索引元素有等于号出现，那么第二个元素就一定能够用得上索引。

SELECT * FROM t_user WHERE name like 'j%' and age = 22，联合索引（name, age）哪一个字段用到了联合索引的 B+Tree？

都用到了联合索引进行排序。

索引的缺点

会占用一定的数据内存空间，索引过多可能带来数据库内存负担的加重。
创建和维护索引需要时间，这个时间会随着数据量的增大而增大。
会降低修改删除索引的效率，因为每一次对于索引进行修改时，B+ Tree 都会对于索引进行动态维护

索引的适用范围

唯一的不重复的非空字段，最好还能够是新增的时候有序排列的字段。当索引唯一的时候查询效率是比不唯一的索引效率要高的。非空是因为查询的时候还需要加上空字段会导致查询效率的降低。
经常用于查询语句 where 的字段，对于经常用于查询语句的字段建立索引，有利于提升查询效率
经常需要用于排序 order by 的字段，因为索引本身是有序的，所以提前对于排序字段建立好索引有利于执行sql语句的时候效率的提升。

索引的不适用情况

不经常用于查询，排列的字段。因为索引主要就是用于能够更好的排列顺序，如果不用那也就意味着没有必要建立索引。
重复度高的情况下不建议使用索引，最好是唯一字段才使用索引。内部优化器有一个规则，当索引重复度高于一个标准的时候，那么将会替换成为全局搜索。比如只有男和女的性别，各占50%，所以没有必要建立索引。
要经常修改的字段，因为字段的更新意味着索引的重新排序，对于数据库性能上会有一定的消耗。
数据量太少，没有必要建立索引。

优化索引的方式

前缀索引优化

使用前缀索引是为了减小索引字段大小，可以增加一个索引页中存储的索引值，有效提高索引的查询速度。在一些大字符串的字段作为索引时，使用前缀索引可以帮助我们减小索引项的大小。

不过，前缀索引有一定的局限性，例如：

order by 就无法使用前缀索引；
无法把前缀索引用作覆盖索引；

覆盖索引优化

覆盖索引是指 SQL 中 query 的所有字段，在索引 B+Tree 的叶子节点上都能找得到的那些索引，从二级索引中查询得到记录，而不需要通过聚簇索引查询获得，可以避免回表的操作。

主键索引最好是自增的

如果我们使用了自增的主键，那么我们要插入一条数据的时候，做的事情是只需要在链表的末尾加入一个元素即可，时间复杂度不高。

但是如果我们使用了非自增的主键，那么我们首先要查询这个主键的大小相较于其他大小的位置，在进行插入，那么相比于尾插法明显效率是得到了提升的。而且非自增主键还会造成内存碎片的危害，浪费存储空间。

索引列最好设置为NOT NULL

索引列存在 NULL 就会导致优化器在做索引选择的时候更加复杂.

NULL 值是一个没意义的值，但是它会占用物理空间，所以会带来的存储空间的问题，因为 InnoDB 存储记录的时候，如果表中存在允许为 NULL 的字段，那么行格式中至少会用 1 字节空间存储 NULL 值列表。

索引失效的情况

当我们使用了左模糊匹配或者左右模糊匹配的时候，比如 select * from db where name like %ming 或者 select * from db where name like %ming% 索引会失效。原因是其是按最左前缀原则进行匹配的，即使对于字段内部也是一样，从左到右进行匹配。
当对索引值进行计算或者函数运算的时候，索引会失效。因为索引是根据他本身存入的值进行排序，运算后就不是原有的值了。那么解决这个问题可以将该函数设为索引。
设置联合索引的时候没有遵循最左匹配原则。
查询条件中设置or条件语句只要有一部分没有遵循索引，那么其将会进行全表查询。道理也很简单，or是求两部分的交集，即使前面用了索引后面也要进行全表查询，所以直接全部使用全表查询。

count(1), count(*)和count(字段)哪个查询效率更高？

结论：count(1) = count(*) > count(主键字段) > count(其他字段)

count(1)如何查询

当只有主键索引没有二级索引的时候：

InnoDB 循环遍历聚簇索引（主键索引），将读取到的记录返回给 server 层，但是不会读取记录中的任何字段的值，因为 count 函数的参数是 1，不是字段，所以不需要读取记录中的字段值。参数 1 很明显并不是 NULL，因此 server 层每从 InnoDB 读取到一条记录，就将 count 变量加 1。

当存在二级索引的时候，循环遍历找值的对象就变成了二级索引了。

count(*)如何查询

count(*)在编译的时候会转换为count(0)。

count(字段)如何查询

对于这个查询来说，会采用全表扫描的方式来计数，所以它的执行效率是比较差的。因为他统计的是在表中该字段不为空的值的字段有几个。而count（常量）统计的是该表中有几条数据。

mysql基础知识

发表于2023-05-27更新于2023-09-08字数统计2.9k阅读时长15分

mysql的执行过程

连接器

首先需要先登录账号密码，使mysql服务器和客户端进行连接，一个服务器可以连接多个客户端，和HTTP一样，连接都需要经过三次握手，都有默认开启长连接以节约多次请求反复连接带来的性能损耗。

查询缓存

这是mysql5.7的功能，到mysql8.0被废弃了。原因是因为缓存的使用效率极低，在一个频繁需要更新的表中，每进行更新一次，缓存就会全部清除，不管更新的和你缓存中的字段的关系大不大。所以mysql中查询缓存的命中率极低。在mysql8.0被废除。

mysql5.7查询缓存的主要流程为先判断客户端发送的sql语句的第一个关键字段，如果是select才进行查询缓存的操作，若不是则进行接下来的后续操作。缓存会以(key, value)记录先前的查询的sql语句以及查询的结果，如果缓存命中了，则直接返回其value值。如果查询不到缓存，则查询后将查询结果加入缓存中。

解析器

词法解析
mysql会分析sql语句，将每一个字段构建成为语法树。方便后续获取表名称，字段名称，where查询条件等。
语法分析
根据词法分析的结果，语法解析器会根据语法规则，判断你输入的这个 SQL 语句是否满足 MySQL 语法。
如果我们输入的 SQL 语句语法不对，就会在解析器这个阶段报错。比如，我把 from 写成了 form，这时 MySQL 解析器就会给报错。
此时报错仅仅是sql关键字的鉴别报错，如果输入了不存在的表名或者字段名时，在此阶段不会报错

预处理器

判断语法树中的字段在表中字段中是否存在
将所有的* 解析为表中的所有字段

优化器

优化器主要负责将 SQL 查询语句的执行方案确定下来

这一部分主要是索引的优化，sql优化器会通过对比，选择出主键索引，联合索引，二级索引中执行效率最高的方式，并在后面执行器中执行。

执行器

主键索引查询
全表扫描
索引下推

通过遍历的方式进行执行(while循环)，先去逐条查询所有的语句，之后再与条件进行对比，如果匹配条件的话，则将其加入结果集中，如果不匹配条件的话，则进行下一条的筛选，直至表中的字段被筛选结束。

没有索引下推的时候，每查询到一条二级索引记录，都要进行回表操作，然后将记录返回给 Server，进行二次判断

存储引擎定位到二级索引后，先不执行回表操作，而是先判断一下该索引中包含的列（reward列）的条件（reward 是否等于 100000）是否成立。如果条件不成立，则直接跳过该二级索引。如果成立，则执行回表操作，将完成记录返回给 Server 层。

所以我们可以认为，索引下推使用到了联合索引的特性，将联合索引中另一个索引的值在存储引擎层就已经进行查询了。

mysql记录存储结构

mysql数据存储文件

一个表对应了三个文件对数据库进行存储：

1
2
3

db.opt  
t_order.frm  
t_order.ibd

.opt 文件是对于文件字符集和默认字符校验规则的规定
.frm文件是对于对表结构格式的存储，存储的是表结构的元数据，如列名，表名，存储引擎等基本数据结构。
.ibd文件是对于表数据的存储。

表空间文件结构

从小到大，依次为段(segment) > 区(entend) > 页(page) > 行(row)

行

其中，行为最小的存储结构，可以看作对应的是表中的每个对象，一个对象即为一行，一行的大小规定最大为65535个字节，初始化定义的时候超过该大小则会报错。

页

但是数据表的读取和写入不以行为单位，为了避免传输的时候资源的浪费，以页为单位进行读取和写入，一页的大小为16kb，页的类型有很多，常见的有数据页、undo 日志页、溢出页等等。数据表中的行记录是用「数据页」来管理的

区

在表中数据量大的时候，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照区（extent）为单位分配。每个区的大小为 1MB，对于 16KB 的页来说，连续的 64 个页会被划为一个区，这样就使得链表中相邻的页的物理位置也相邻，就能使用顺序 I/O 了。

段

索引段：存放 B + 树的非叶子节点的区的集合；
数据段：存放 B + 树的叶子节点的区的集合；
回滚段：存放的是回滚数据的区的集合，事务隔离 (opens new window)介绍到了 MVCC 利用了回滚段实现了多版本查询数据。

COMPACT行格式

记录的额外信息
- 变长字段列表
- Null值列表
- 记录头信息
记录的真实数据
- row_id
- trx_id
- roll_ptr

变长字段列表

char(n) 和 varchar(n) 的区别为前者为不可变长的字符串类型，后者为可变长的字符串类型，后者的n表示的是该字符串允许的最大字符数。如果不存在可变长的类型，那么该额外信息字段将会被取消。存储的时候，存储的是其字符串的字符长度，比如存储aaa到 varchar(256) 的字段中，那么变长字段长度列表就会存储一个 3 。注意当出现多个可变长字段列表的时候，在表中的顺序越靠近左边的，在变长字段长度列表中存储的位置是靠右边的。这是因为记录头信息中有一个指针由该行指向下一行，他的位置是记录头信息的末尾，也就是接近真实数据和额外数据的分界线。那么他读取的时候，会左右都读，往左边读的时候可以理解成从后往前，所以变长字段长度列表从后往前进行记录也是符合底层存储引擎读取的顺序，能一定程度上提高性能。Null值列表也是同理的。

注意这里的n指的是字符数而不是字节数。比如在ascii字符集中，一个字符占一个字节，而在UTF-8字符集中，一个字符占了三个字节。

Null值列表

同理的，Null值列表也不是一定要存在的，其只有在某个或者某些字段规定允许为空的时候出现。所以我们平时设计数据库表的时候能设置非空就设置非空可以一定程度上节约数据库存储的额外性能。那么非空字段存储是通过二进制位来进行表示的，其非空字段必须为8的整数倍，高位用0补齐。如只有三个非空字段且其均为空，那么该行的非空字段可以表示为 00000111，注意，其也是逆序排序的。一行就是一个字节甚至根据非空字段的大小可能更多，所以尽可能的少用空字段。

当一条记录有 9 个字段值都是 NULL，那么就会创建 2 字节空间的「NULL 值列表」，以此类推。

记录头信息

delete_mask ：标识此条数据是否被删除。从这里可以知道，我们执行 detele 删除记录的时候，并不会真正的删除记录，只是将这个记录的 delete_mask 标记为 1。
next_record：下一条记录的位置。从这里可以知道，记录与记录之间是通过链表组织的。在前面我也提到了，指向的是下一条记录的「记录头信息」和「真实数据」之间的位置，这样的好处是向左读就是记录头信息，向右读就是真实数据，比较方便。
record_type：表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录

记录的真实数据

row_id

如果我们建表的时候指定了主键或者唯一约束列，那么就没有 row_id 隐藏字段了。如果既没有指定主键，又没有唯一约束，那么 InnoDB 就会为记录添加 row_id 隐藏字段。row_id不是必需的，占用 6 个字节。

trx_id

事务id，表示这个数据是由哪个事务生成的。 trx_id是必需的，占用 6 个字节。

roll_pointer

这条记录上一个版本的指针。roll_pointer 是必需的，占用 7 个字节。

varchar(n) 取值最大为多少

结论：varchar(n)中n的最大值为65533

首先我们知道一行最大能承受的字节数为65535，那么n代表了字符数，我们以最小兑换比例1：1的ascii进行兑换，那么可以存储65535个字符，但是不是这样的，我们从上面 COMPACT行格式 中可以看出，字段中除了记录的真实数据，还有记录的额外信息，那么这些额外信息也需要占用一定的字节。我们在考虑可变长字符串的最大长度的时候就要将其考虑进去。那么可变长字符串有一个分界线为255字节，当其小于255时候，长度为1个字节，大于时长度为2字节。所以需要减去记录其长度的两个字节，那么就是65533了

如果当我们设置该字段为允许为空时，我们还需要考虑Null值列表。即使存储的数据字段不为空，那么也会存储0表示存储的是空值，以区分数据传输时候丢失和传入的值本来就为空。所以此时，需要加上一个字节。

当然，前面考虑的都是一行只有一个varchar(n)字段，当有多个字段的时候，能够存储的空间就更加小了。

记得有一道面试题，数据库一行能存储下一本小说吗？其实就是说的这个，短篇小说应该还是可以的，还得是英文小说，不然ascii字符集没有对应的中文就不好了。如果是中文小说，那么最多只能存储65533/3的字节长度，也就是最多2w多字了。

行溢出后mysql如何处理

当发生行溢出时，在记录的真实数据处只会保存该列的一部分数据，而把剩余的数据放在「溢出页」中，然后真实数据处用 20 字节存储指向溢出页的地址，从而可以找到剩余数据所在的页。大致如下图所示。

GC

发表于2023-05-27更新于2023-09-11字数统计6.8k阅读时长40分

1. 内存分配与回收原则

1.1 对象优先在Eden区进行分配

当 Eden 区没有足够空间进行分配时，虚拟机将发起一次 Minor GC。若无法存入survivor区，则通过分配担保机制把新生代的对象提前转移到老年代中去

空间分配担保是为了确保在 Minor GC 之前老年代本身还有容纳新生代所有对象的剩余空间。

1.2 大对象直接进入老年代

大对象就是需要大量连续内存空间的对象（比如：字符串、数组）。
大对象直接进入老年代主要是为了避免为大对象分配内存时由于分配担保机制带来的复制而降低效率。

1.3 长期存活的对象进入老年代

大部分情况，对象都会首先在 Eden 区域分配。如果对象在 Eden 出生并经过第一次 Minor GC 后仍然能够存活，并且能被 Survivor 容纳的话，将被移动到 Survivor 空间（s0 或者 s1）中，并将对象年龄设为 1(Eden 区->Survivor 区后对象的初始年龄变为 1)。
对象在 Survivor 中每熬过一次 MinorGC,年龄就增加 1 岁，当它的年龄增加到一定程度（默认为 15 岁），就会被晋升到老年代中。对象晋升到老年代的年龄阈值，可以通过参数 -XX:MaxTenuringThreshold 来设置。

1.4 GC的分类

针对 HotSpot VM 的实现，它里面的 GC 其实准确分类只有两大种：

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

2. 如何判断对象可以被回收(死亡对象的判断)

2.1 引用计数法

通过调用对象的次数计数，调用了一次+1，调用了两次+2；如果失去引用了，计数器-1；
弊端：循环引用可能导致计数次数无法归零，进而导致内存泄漏。

2.2 可达性分析算法

先确立一个根对象(GC Root)，看有没有对象和根对象直接或者间接的引用，如果有，那就是不能被垃圾回收的对象。
可作为GC Root对象的有：

虚拟机栈(栈帧中的本地变量表)中引用的对象
本地方法栈(Native 方法)中引用的对象
方法区中类静态属性引用的对象
方法区中常量引用的对象
所有被同步锁持有的对象

2.3 四种引用

2.3.1 强引用

沿着根对象能找到的A对象，那么A对象称为被强引用。仅当强引用与A对象断开时，可被回收。

2.3.2 软引用

SoftRenference<byte[]> ref = new SoftRenference<>(new byte[])
没有被强引用所引用，垃圾回收发生时都有可能被回收。
当发生过一次垃圾回收且内存仍然不够时，会回收被软引用引用的对象。
软引用一般适用于一些非必要的场景，比如说网页图片，没有必要一直占着内存空间，等到需要的时候再加载就可以了。

具体案例如下：

public static void soft() {
    // list --> SoftReference --> byte[]

    List<SoftReference<byte[]>> list = new ArrayList<>();
    for (int i = 0; i < 5; i++) {
        SoftReference<byte[]> ref = new SoftReference<>(new byte[_4MB]);
        System.out.println(ref.get());
        list.add(ref);
        System.out.println(list.size());

    }
    System.out.println("循环结束：" + list.size());
    for (SoftReference<byte[]> ref : list) {
        System.out.println(ref.get());
    }
}

输出结果：

[B@330bedb4
1
[B@2503dbd3
2
[B@4b67cf4d
3
[GC (Allocation Failure) [PSYoungGen: 2162K->488K(6144K)] 14450K->13074K(19968K), 0.0019161 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
内存不足，进行一次垃圾回收。
[B@7ea987ac
4
[GC (Allocation Failure) –[PSYoungGen: 4696K->4696K(6144K)] 17282K->17290K(19968K), 0.0006865 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
[Full GC (Ergonomics) [PSYoungGen: 4696K->4535K(6144K)] [ParOldGen: 12594K->12545K(13824K)] 17290K->17080K(19968K), [Metaspace: 3373K->3373K(1056768K)], 0.> > 0045075 secs] [Times: user=0.00 sys=0.00, real=0.01 secs]
[GC (Allocation Failure) –[PSYoungGen: 4535K->4535K(6144K)] 17080K->17096K(19968K), 0.0006433 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]
[Full GC (Allocation Failure) [PSYoungGen: 4535K->0K(6144K)] [ParOldGen: 12561K->677K(8704K)] 17096K->677K(14848K), [Metaspace: 3373K->3373K(1056768K)], 0.> > 0059614 secs] [Times: user=0.01 sys=0.00, real=0.01 secs]
进行一次垃圾回收之后内存仍然不足，触发软引用机制，将软引用创建的对象所垃圾回收释放空间。
[B@12a3a380
5
循环结束：5
null
null
null
null
[B@12a3a380

2.3.3 引用队列

软弱引用无引用对象时，自动进入引用队列

private static final int _4MB = 4 * 1024 * 1024;

public static void main(String[] args) {
    List<SoftReference<byte[]>> list = new ArrayList<>();

    // 引用队列
    ReferenceQueue<byte[]> queue = new ReferenceQueue<>();

    for (int i = 0; i < 5; i++) {
        // 关联了引用队列， 当软引用所关联的 byte[]被回收时，软引用自己会加入到 queue 中去
        SoftReference<byte[]> ref = new SoftReference<>(new byte[_4MB], queue);
        System.out.println(ref.get());
        list.add(ref);
        System.out.println(list.size());
    }

    // 从队列中获取无用的 软引用对象，并移除
    Reference<? extends byte[]> poll = queue.poll();
    while( poll != null) {
        list.remove(poll);
        poll = queue.poll();
    }

    System.out.println("===========================");
    for (SoftReference<byte[]> reference : list) {
        System.out.println(reference.get());
    }

}

输出：

[B@4aa8f0b4 (最后结果)

2.3.4 弱引用

只要当发生了垃圾回收，被弱引用引用的对象会被回收。
不过，由于垃圾回收器是一个优先级很低的线程，因此不一定会很快发现那些只具有弱引用的对象。
类似于软引用。

2.3.5 虚引用

必须配合引用队列来使用。创建时即关联引用队列。缓存时会留下直接内存，当StringBuffer对象被回收时，他的直接内存没有被回收掉，此时虚引用对象进入引用队列，调用线程清理直接内存。
虚引用主要用来跟踪对象被垃圾回收的活动。起到触发器的作用，当虚引用的对象意识到自己快要被回收了，会做出一些相应的程序。

2.3.6 终结器引用

当finallize()将要被垃圾回收时，将终结器引用放入引用队列，由finallizeHandler去由终结器引用的对象去销毁对象
所以说当对象不可达的时候不会被立刻销毁，而要经历两次标记之后才确定要被销毁。
缺点：finallizeHandler优先级很低，且销毁流程漫长，需要两次GC才能销毁完成，易造成内存泄漏。

3. 三种垃圾收集算法

3.1 标记——清除算法(Mark-Clear)

流程：首先标记出需要垃圾回收的对象，标记完成后，统一回收被标记的对象。也可以相反。
缺点：
执行效率不稳定，随着对象增长降低效率不断变化；
内存空间碎片化，需要分配较大内存时无法找到足够连续内存不得不提前进行一次垃圾回收操作。

3.2 标记——复制算法(Mark-Copy)

流程：半区复制。 将可用内存按容量划分为大小相等的两块，每次只使用其中的一块，这一块的内存用完了，就将存活着的对象复制到另一块的上面，然后再把已使用的内存空间一次性清理掉。
优点：解决了碎片空间的问题，只需要移动栈顶指针，按顺序分配即可
缺点：内存缩小到原来的一半，造成空间浪费

拓展：APPel式回收
把新生代分为一块较大的Eden空间和两块较小的Survivor空间，每次分配内存只使用一块Eden和一块Survivor。发生垃圾收集时，将Eden和Survivor仍然存活的对象一次性复制到另一块Survivor中，直接清理掉原来的两块对象。

理论依据：HotSpot默认Eden和Survivor的大小比为8：1，即新生代内存空间占总内存空间的90%，相比于标记复制算法节约了巨大的内存空间，而“朝生夕灭”理论认为，新生代中有98%的对象熬不过第一轮收集，所以内存空间时绰绰有余的。

3.3 标记——整理算法(Mark-Compact)

流程：标记算法和前两者一样，而在回收的时候不同于前者，是先让所有存活的对象往内存空间的一侧进行移动，然后直接清理掉边界之外的内存。
缺点：移动更新对象任务量及其庞大，需要全程暂停用户应用程序才能进行。易形成Stop The World现象。
移动和不移动的利弊比较：
是否移动对象都存在弊端，移动则内存回收时会更复杂，不移动则内存分配时会更复杂；从垃圾收集的停顿时间来看，不移动对象停顿时间会更短，甚至可以不需要停顿，但是从整个程序的吞吐量来看，移动对象会更划算；即使不移动对象会使得收集器的效率提升一些，但因内存分配和访问相比垃圾收集频率要高得多，这部分的耗时增加，总吞吐量仍然是下降的

4. 垃圾分代回收

(面试题)原因：
因为将对象分代可以根据各个年代的特点选择合适的垃圾分配机制。
比如在新生代，大部分(约98%)的对象都会被回收，那么这时候就可以使用标记——复制算法，只需要复制少量的存活对象，节约内存成本。而在老年代对象存活较多的情况下，也没有足够多的空间为其进行分配担保，所以使用“标记——清除”或者“标记——整理”分类方法。

4.1 分代垃圾回收机制

对象首先分配在伊甸园区域
新生代空间不足时，触发 minor gc，伊甸园和 from 存活的对象使用 copy 复制到 to 中，存活的对象年龄加 1并且交换 from to。
minor gc 会引发 stop the world，暂停其它用户的线程，等垃圾回收结束，用户线程才恢复运行
当对象寿命超过阈值时，会晋升至老年代，最大寿命是15（4bit）。
当老年代空间不足，会先尝试触发 minor gc，如果之后空间仍不足，那么触发 full gc，STW的时间更长。
当新生代内存无法容纳对象大小，直接晋升为老年代
线程中出现OOM异常时，他占据的内存资源会全部释放掉，不会影响其他线程的运行

4.2 VM相关参数

5. 垃圾回收器

serial: 串行单线程,一个方法执行完下个方法才能够执行
parallel : 并行多线程,可以同时执行垃圾回收, 但其他无法方法运行 STW 相当于所有线程都归垃圾回收所有
concurrent : 并发多线程,其他方法和垃圾回收可以同时执行,但是只能逐个进行垃圾回收,相当于平等的线程分配给每一个方法

5.1 串行垃圾回收器(Serial/ Serial Old)

单线程。适用于堆内存较少的情况，适合个人电脑
-XX:+UseSerialGC = Serial + SerialOld

新生代用“标记——复制”算法，老年代用“标记——整理”算法

5.2 吞吐量优先(Parallel/ Parallel Old)

多线程，堆内存较大，多核CPU
单位时间内,完成STW次数越少(STW的时间占总用户时间)
关注吞吐量
XX:+UseparalellGC
-XX:ParallelGCThreads:n :允许同时允许的线程数量
-XX:+UseAdaptSizePolicy :自适应调整新生代的大小
-XX:GCTimeRadio:radio : 最多允许垃圾回收时间占总线程时间的1/(1+radio),希望堆大，关注的是吞吐量
-XX:MaxGCPauseMillis=is : default是200ms,表示最长垃圾回收时间,希望堆小,与上一个冲突，关注的是响应时间

5.2 响应时间优先(CMS Concurrent Marking Sweep)

多线程，堆内存较大，多核CPU
注重STW时间的长度(单独只考虑STW的时间)

初始标记: 需要STW，但仅标记与GC Root关联的对象,速度快
并发标记: 从GC Root直接关联对象开始遍历整个对象图, 耗时长,但并发运行
重新标记: 需要STW, 修正因并发导致的对象标记变动
并发清除: 清理标记对象
只有在初始标记和重新标记时候才会STW
三个缺点:
对CPU占用低,只占用了一部分进行GC, 但拖慢了用户进行的CPU量, 对吞吐量有影响.
并发过程中产生的浮动垃圾难以处理
使用“标记——清除”算法大量空间碎片的产生
-XX:+UseConcMarkSweepGC
-XX:ConcGCThreads=thread:运用于垃圾回收的线程,一般是总线程数的1/4
-XX:CMSInitiatingOccupancyFraction : percent :触发垃圾回收阈值
剩下内存空间留给其他进行的进程以及浮动垃圾; 阈值过高可能导致并发失败

6. G1

难点，一款很多知识点的垃圾回收器，牵涉到很多新概念

6.1 基础概念的了解

6.1.1 写屏障

可以看成是虚拟机层面对”引用类型字段赋值”这个动作的AOP切面, 在引用对象赋值的时候会形成一个环形,供程序执行额外的操作,而我们解决这种想要在编译场景中赋值的操作,就可以使用写屏障这种在机械码方面操作的手段,简单的来说,写屏障就是负责对在编译阶段中产生改变内容的处理的.

6.1.2 记忆集和卡表

这两者的出现是为了解决对象跨代引用所带来的问题的.跨代引用会导致老年代向新生代的引用难以通过只扫描新生代的对象去识别, 而如果要进行对老年代和新生代进行同时扫描的话, 那么STW的时间会变长, 性能较差.而记忆集是一种抽象的数据结构, 主要是用于记录非搜集区域指向搜集区域的指针集合的抽象数据结构.其在G1垃圾处理器中被安排在新生代中.而卡表是记忆集的一种具体实现.卡表主要运用在老年代, 当有一个老年代对象引用了新生代的时候, 卡表就会在对应的数组元素值标记为1, 表示这个元素为脏.之后通过写屏障在引用对象的行为发生时进行标记, 之后在新生代垃圾回收扫描时,这个对象就会被视为活对象了.

6.2 三色标记算法

6.2.1 基本概念

这是垃圾回收在新生代回收时根据GC Root的遍历所进行标记的一种算法.具体实现为将对象标为黑灰白三种对象, 其划分标准如下:

黑: 已经被垃圾回收器访问过, 其所有引用已经全部被扫描过了, 保证其是安全存活的, 且不会再进行扫描;
灰: 被垃圾回收器访问过, 但是他身上的至少一个引用还没有被垃圾回收器访问, 是扫描引用他的灰色对象之后形成的;
白: 没有被垃圾回收器访问过, 开始的时候所有对象都是白色的, 当垃圾回收扫描完成时, 还是白色的对象说明对象是不可达的.
扫描完成的标志: 没有灰色对象的存在

6.2.2 遍历过程

1.初始时，全部对象都是白色的
2.GC Roots直接引用的对象变成灰色
3.从灰色集合中获取元素：
3.1 将本对象直接引用的对象标记为灰色
3.2 将本对象标记为黑色
4.重复步骤3，直到灰色的对象集合变为空
5.结束后，仍然被标记为白色的对象就是不可达对象，视为垃圾对象

6.2.3 存在问题

标记算法存在的问题都是基于并发执行下产生的, 因为用户线程在进行的时候, 对象的调用总是会进行, 而同时进行对对象的操作有可能导致引用的错误.

漏删
把原本死亡的对象标记为存活, 会发生的情况为因为A到B的引用,B被标灰了,但之后引用就断开了, 此时B没有对象引用他, 但是他的标记是灰色, 不会被回收, 这种我们把它叫做浮动垃圾. 这种解决方案十分简单, 下次扫描的时候, 因为没有对象引用他, 他就会自动被删除的.
多删
原本是黑色的对象被标记为白色.具体造成原因为如下两点:

插入了一条或者多条黑色对象对白色对象的引用
删除了所有灰色对象对白色对象的直接或者间接引用
这种问题很大, 因为本来程序运行所需要的一个对象被销毁了, 会导致程序的异常, 那么垃圾回收器给出了我们两种如下解决方案.

6.2.4 解决方案

增量更新(Increment update)
破坏的是第一个条件, 他会将这个新插入的引用记录下来, 扫描结束之后会以黑色对象为根重新进行扫描,可以理解为这个技术可以使得产生的新引用的黑色节点变灰.其主要实现为写屏障; 主要用于CMS中
原始快照(SnapShot At The Beginning)
破坏的主要是第二个条件, 他会在断开连接时将断开连接前的一瞬间记录下来, 再将他放到一个独立的内存区域中, 扫描结束后, 重新以灰色节点为根重新进行扫描.

6.3 G1垃圾回收器的垃圾处理流程

6.3.1 以rigion为分区的回收范围改变

首先我们需要知道，G1相较于CMS包括之前的垃圾回收器做出了一个巨大的改变，就是垃圾回收区域的划分，以前分代收集理论是垃圾回收器的主流理论，而G1将其做了一个更新包装，其面向堆内任何部分来组成回收集(Cset)，每一个回收集被叫做region区域，每一个区域中也可扮演为Eden，Survivor空间，每次回收的最小单元是一个region，而对于不同的region区域采取不同的策略，对于垃圾回收产生了更为优秀的结果。G1收集器会自动的去评估每个region区域的回收价值大小，根据-XX:MaxGCPauseMillis参数来确定回收策略，我们叫这种模式为Mixed GC。相比于之前，有两个优点，一个是变得更加灵活了，有回收策略了；另一个是不再需要连续了，内存空间的分配也会更加合理。
那么在我们了解了这种化整为零的内存空间分配策略后，我们需要知道整个G1回收器的垃圾回收流程：

6.3.2 Young GC

程序在运行的时候，随着对象不断创建，许多内存进行Eden区，当Eden区被占满时，会自动触发一次Young GC，此时会引起STW，此时G1涉及的对象只有Eden区和Survivor区,回收的内存进入Cset中进行回收;运用了复制算法,将存活单位复制到新的survivor区域.

扫描根和rset, 此时会有一个小的短暂的STW;
运用写屏障更新rset,此时所有跨代引用对象不会被视为垃圾;
复制算法,实现Eden区和Survivor区的存活对象到新的Survivor区的转移
处理软弱虚引用.

6.3.3 Young GC + Concurrent Marking

首先进行一次young GC, 同时进行一次进行一次初始标记, 标记GC Root对象, 此时会发生STW;
并发标记, 沿着GC Root遍历对象, 同时将所有跨代引用的标记变脏,此时属于并发标记, 不会STW; 同时也会进行SATB, 对漏标的对象进行了处理;
再次标记, 处理原来SATB的对象;
独占清理, 对每一块内存区域进行排序, 为下阶段Mixed GC做准备;
清理本阶段内存.

6.3.4 Mixed GC

此时会根据-XX:MaxGCPauseMillis实现清理策略, 在这个阶段会做三件事:

新生代的垃圾回收: Eden区存活对象到survivor区; Survivor区存活对象到新的survivor区;
晋升: Survivor区达到晋升阈值的对象晋升到老年代
老年代的垃圾回收: 结合-XX:MaxGCPauseMillis和上一阶段的排序, 将部分老年代进行回收;
这个阶段也说明了Garbage First这个垃圾回收器名字的由来, 就是会在这个环节优先回收占用内存较多的区域.

-XX:MaxGCPauseMillis: 最大暂停时间过短, 回收速度小于产生速度, 触发单线程的Full GC; 正常情况, 回收速度大于产生速度, Concurrent mark;
-XX：G1MixedGCLiveThresholdPercent: 回收阈值,默认为65%; 达到之后才会触发回收, 过小意味着存活对象多,复制时间浪费多, STW时间长．

6.4 新增功能

6.4.1 字符串去重

优点：节省大量内存
缺点：略微多占用了 cpu 时间，新生代回收时间略微增加
-XX:+UseStringDeduplication
将所有新分配的字符串放入一个队列; 当新生代回收时，G1并发检查是否有字符串重复; 如果它们值一样，让它们引用同一个 char[]

注意: 与 String.intern() 不一样; String.intern() 关注的是字符串对象; 而字符串去重关注的是 char[]; 在 JVM 内部，使用了不同的字符串表

6.4.2 类卸载

所有对象都经过并发标记后，就能知道哪些类不再被使用，当一个类加载器的所有类都不再使用，则卸载它所加载的所有类
-XX:+ClassUnloadingWithConcurrentMark 默认启用

6.4.3 巨型对象管理

一个对象大于 region 的一半时，称之为巨型对象
G1 不会对巨型对象进行拷贝
回收时被优先考虑
G1 会跟踪老年代所有 incoming 引用，这样老年代 incoming 引用为0 的巨型对象就可以在新生代垃圾回收时处理掉

7. ZGC收集器

是一款低延迟垃圾收集器, 希望在对吞吐量影响不大的前提下, 把垃圾收集的停顿时间缩短在10ms以内。
其内存布局也是和G1一样划分为若干Region区，但其具有动态的容量大小和动态创建和销毁的特征，可以分为如下三种容量：

大：不固定可以动态变换，但是一定为2MB的整数倍，不会被重分配。
中：容量固定为32MB，用来存储256KB ~ 4MB的对象
小：容量固定为2MB，用来存储0 ~ 256KB的对象

7.1 ZGC的垃圾收集流程

7.1.1 并发标记(Concurrent Marking)

只会在开始标记GC Root的时候有小小的停顿，剩下的标记活动都是并发运行的。和G1需要STW进行三色算法不同，ZGC的标记位置是在指针上的，所以可以省略去遍历对象图的流程

7.1.2 并发预备重分配(Concurrent Perpare for Relocation)

通过并发标记得出的结论查询到底有哪些垃圾是需要回收的，然后将需要回收的Region区组成重分配集(Relocation Set)。因为ZGC不区分新生代老年代的特点，所以该阶段的扫描是针对全堆的，但同时相较于G1也省去了记忆集的维护成本。

ZGC的重分配集只是决定了里面的存活对象会被重新复制到其他的Region中，而不是说回收的行为针对这个集合里面的region进行。

7.1.3 并发重分配(Concurrent Relocation)

是ZGC垃圾回收的核心过程。他将重分配集中的存活对象转移到新的Region中，并在重分配集中建立一个转发表(Forward Table)，用来标记重分配区中旧的Region对象到新的Region对象的转发关系。当用户访问了重分配集中的对象，那么就会被预置的内存屏障所截获，根据转发表的记录转发到新的对象上，并将引用更改到新的对象上，使其指向新的对象。这种行为被称为指针的“自愈”行为。
一旦region的存活对象都被复制完毕，那么这个region就可以进行下一轮的内存分配。但是转发表却得等到所有重分配集中的region对象复制完毕才可删除。

7.1.4 并发重映射(Concurrent Remap)

重映射指的是修正整个堆中指向重分配集中的旧对象的所有引用。可以合并到下一次的并发标记的流程进行，节约一次遍历对象图的操作。

7.2 ZGC解决并发算法问题的关键——染色指针

将少量标识信息存储在指针上，实现可达性分析，相较于G1的遍历对象图节约了许多时间的成本。
三个优点：

染色指针可以使得一旦某个Region的存活对象被移走之后，这个Region立即就能被释放和重用。指针的自愈行为使得它拥有即时性，而复制算法则是需要STW进行1：1的复制后才能够实现重用。
染色指针可以大幅度减少在垃圾收集过程中内存屏障的使用数量，内存屏障的功能之一就是记录对象引用的变动情况，而染色指针可以接替这一工作。
可以作为一种可拓展的存储结构用来记录，重定位过程的相关数据，日后可以进一步提升性能。日后标志位可用的提升可以使得其更有扩展性。

JVM概述

发表于2023-05-24更新于2023-09-11字数统计184阅读时长1分

一.Java语言及JVM的概述

1. Java的优点

一次编译，到处运行。
内存管理访问机制相对安全，尽可能避免内存泄漏和数组指针越界等问题。
热点代码检测，编译优化

编译优化：String c = "a" + "b"; ==>String c = "ab";
第三方类库丰富，开源功能强大
多态

2.JVM

jvm ( Java visual machine )，java虚拟机，具有控制java内存的能力，可以让程序员在编写程序时享受自动内存管理的诸多优势，但是也需要警惕因为各种原因出现的内存泄露和溢出的问题。

下图为Java技术体系的三个概念的关系：

String

发表于2023-04-07更新于2023-09-11字数统计547阅读时长4分

1. 字符串基础知识

1.1 字符串对象的创建

new String() 方法会在堆中创建一个对象，之后会在方法区中的字符串常量池中判断，如果没有值相等的字符串，那么创建一个常量；如果有，那么直接调用。

1.2 方法

方法名	作用
char charAt(int index)	返回指定位置的字符
int compareTo(String anotherString)	比较两个字符串。相等返回0；前大后小返回1；前小后大返回-1
boolean contains(CharSequence s)	判断字符串是否包含s
boolean endsWith(String suffix)	判断字符串是否以suffix结尾
boolean equals(Object anObject)	判断两个串是否相等
boolean equalsIgnoreCase(String anotherString)	忽略大小写判断两个串是否相等
byte[] getBytes()	将字符串串变成字节数组返回
int indexOf(String str)	返回str在字符串第一次出现的位置
boolean isEmpty()	字符串是否为空
int length()	字符串长度
int lastIndexOf(String str)	返回str最后一次出现的位置
String replace(CharSequence target, CharSequence replacement)	用replacement替换字符串target的字符
String[] split(String regex)	将字符串以regex分割
boolean startsWith(String prefix)	判断字符串是否以prefix开始
String substring(int beginIndex)	从beginIndex开始截取字串
String substring(int beginIndex, int endIndex)	截取beginIndex到endIndex - 1的字符串
char[] toCharArray()	将字符串转换乘char数组
String toLowerCase()	字符串转小写
String toUpperCase()	字符串转大写
String trim()	去除字符串两边空格
静态方法
static String valueOf(int i)	将 i 转换成字符串

class Solution {
public int numDifferentIntegers(String word) {
Set set = new HashSet();
int p1 = 0;
int n = word.length();
int p2;
while (true) {
while (p1 < n && !Character.isDigit(word.charAt(p1))) {
p1++;
}
if (p1 == n) {
break;
}
p2 = p1;
while(p2 < n && Character.isDigit(word.charAt(p1))) {
p2++;
}
while(p2-p1 > 1 && word.charAt(p1) == ‘0’) {
p1++;
}
res.add(word.substring(p1,p2));
p1 = p2;
}

    return res.size();
}

}

Class Solution {
public int numDifferentIntegers(String word) {
Set set = new HashSet();
int n = word.length(), p1 = 0, p2;
while (true) {
while (p1 < n && !Character.isDigit(word.charAt(p1))) {
p1++;
}
if (p1 == n) {
break;
}
p2 = p1;
while (p2 < n && Character.isDigit(word.charAt(p2))) {
p2++;
}
while (p2 - p1 > 1 && word.charAt(p1) == ‘0’) { // 去除前导 0
p1++;
}
set.add(word.substring(p1, p2));
p1 = p2;
}
return set.size();
}

3-hashtable

发表于2023-03-25更新于2023-09-11字数统计5.5k阅读时长38分

1. 哈希表基本概念的入门

哈希表也叫散列表，是通过key & value来进行定位的数据结构，他把关键码值映射到表中一个位置来进行定位，这个映射函数叫做哈希函数；
元素在数组位置position可以表示为hash(key)，表面上只存放key，找到key就可以找到value。
主要思想是空间换时间，可以节约遍历的时间成本，但是代价是需要建立字典库存储映射结果。

数组+链表结构
数组查询方便，可以通过下标直接获得所对应的值，但是插入删除不方便，需要整体移动元素还需要扩容；
链表查询不方便，没有下标只能通过遍历的方式进行查询，增加插入方便，只需要找到需要插入的节点之后进行插入删除即可；
哈希表是两者的结合，获得了两者的优点。
哈希碰撞指经过哈希函数两个key都映射到了同一个数组位置上，那么这时候有两种解决方法。
拉链法：在同一个位置进行链表结构的扩充；
线性探索法：往数组的下一个位置进行扩充；
需要考虑到的是查询效率，当链表长度过长，那么使用线性探索法；当链表长度足够，使用拉链法。
哈希攻击指的是黑客运用一些会转换为相同存储位置的数据注入，最后使得哈希表退化成一个单链表，降低了查询效率，DOS(Denial of Service, 拒绝服务供给)攻击.

1.1 hashMap

1.1.1 map基本操作

hashMap的主要Api：

map.clear();
map.size();
map.isEmpty
map.containsKey(); //判断
map.containsValue();
map.get(key);
map.put(key,value);
map.putAll(otherMap);
map.remove(key);
map.getOrDefault(key,defaultValue);查找key的值,不存在则返回默认值。
map.entrySet();用来遍历每一对KV
for(Map.Entry<Integer，Integer> etntey : map.entrySet())

map遍历三种方式

// 第一种方式： keySet 取出map中所有键，封装为map集合
		Set<String> s1=buy.keySet();
		//开始根据键找值
		for (String key : s1) {
			Integer value=buy.get(key);
			System.out.println(key+"->>>>"+value);	
		}

// 第二种方式： 将所有键值对取出封装为entrySet集合
		Set<Map.Entry<String,Integer>> en=buy.entrySet();
		for (Map.Entry<String, Integer> entry : en) {
			String key=entry.getKey();
			Integer value=entry.getValue();
			System.out.println(key+"->>>"+value);
			
		}

// 第三种方式： Lambda表达式遍历
		buy.forEach(new BiConsumer<String, Integer>() {
			@Override
			public void accept(String t, Integer u) {
				System.out.println(t+"->>>"+u);
				
			}
		});

1.1.2 HashMap两个重要参数

初始容量大小：确定了哈希表底层数组的长度，必须是2的幂，默认初始值为16；
加载因子：决定什么时候进行扩容，默认为0.75f，当数组存储元素个数超过初始容量大小*加载因子，数组就会用refresh()方法进行扩容，将数组扩大到原来的两倍。
扩容十分耗费性能，因为会生成一个新的数组，而且原来元素都要重新计算hashcode存入新的数组。

1.1.3 put方法原理

将key通过本地方法public native int hashcode()，获取对应key的哈希码，这个哈希码和key的存储位置有关，一般计算规则是取模存入，假如数组的长度是16个字节，key的hashcode是3214968，那么3214968 mod 16 = 8, 那么key就会被存储在数组的第8个位置，如果该位置为空则直接存入，如果该位置有值，就将插入的key与已经存在的key逐一进行equals判断，如果true就替换values，否则就以链表或红黑树(当链表长度大于8时)形式接入。此时(key, value)被封装为Node节点一同进行put操作

红黑树是平衡二叉树，在查找的效率方面比链表高。

equals()和hashcode()关系
equals()方法对于基本数据类型，比较两个数的内容是否相等，而对于引用数据类型，则比较两个数的存储位置是否相等。
两个对象equals()了，那么他们的hashcode()一定相等；两个对象不equals()，他们的hashcode不一定不相等(经过算法可能计算出来相同的值，哈希碰撞的原理)
equals()重写了，hashcode()就一定要重写，否则可能两个对象equals，他们的hashcode仍然不相等，可能为后世使用埋下隐患;

1.1.4 get(key)方法原理

首先调用hashcode()方法获取key的hashcode；
之后取模定位到数组的索引位置，如果位置为空，返回null；
如果有值，逐一遍历将key进行equal判断，成功则放回对应Node中的values；匹配不到返回null。

1.1.5 hashMap 在Java1.7和1.8中的区别

1. 结构不同

1.7采用的是数组+链表的数据结构
1.8采用的是数组+链表+红黑树的数据结构(当链表长度大于8时，扩展为红黑树)

2. 节点不同

区别：
1.8中的hash作为一个常量，可以减少扩容时候再次计算哈希值造成的性能消耗。
1.8多了红黑树的节点。

3. hash函数区别

1.8相较于1.7只采用了一次位运算和一次与运算，而这次的目的是为了能够减少哈希碰撞，将高位和地位融合在一起，因为发现进行取模操作的时候对高位的影响是相对较小的。因为计算公式为(n-1) & hash，对高位基本上是没有什么影响的。

取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，hash % length == hash & (length - 1)的前提是length是2的n次方, 位运算特征，length是2的n次方，那么他减去1之后就是n个1，异或运算同0异1，这时候就能准确得出他在长度内的值是多少了。

4. 初始化方式

1.7：

table是直接赋值给了一个空数组，在第一次put元素时初始化和计算容量。
table是单独定义的inflateTable（）初始化方法创建的。
1.8：
table没有赋值，属于懒加载，构造方式时已经计算好了新的容量位置（大于等于给定容量的最小2的次幂）。
table是resize（）方法创建的。

5. 扩容方式

1.7：运用异或对哈希值进行重新计算，运用resize()方法负责扩容，inflateTable()负责创建表；
1.8：运用原来的哈希值加上扩容数组长度得到新的数组索引位置，节约了性能利用；表为空时候resize()创建表，表中有数值resize()扩容

6. 数据插入方式

1.7：头插法
1.8：尾插法，避免了在并发时出现逆序和循环链表的情况

1.1.6 线程问题

1.7 死循环，数据丢失，并发执行扩容阶段
1.8 解决死循环，数据丢失仍然没有解决，并发put的时候

整体储存流程如下：

1.2 Set

1.2.1 Set集合基本操作

list是有序的，元素可以重复的；set是无序的，不能重复的

主要Api：

boolean add(E object) //添加一个元素，添加成功返回true
void clear() //从Set集合中移除所有元素，该方法是从Collection集合继承过来的。
Object clone()
boolean contains(Object object) //判断集合内是否包含元素
boolean isEmpty() //判断是否为空集合
Iterator<E> iterator() //迭代器，遍历set集合用
boolean remove(Object object) //移除元素
int size() //数组长度

遍历方式

iterator遍历

Set<String> set = new HashSet<String>();  
Iterator<String> it = set.iterator();  
while (it.hasNext()) {  
  String str = it.next();  
  System.out.println(str);  
}

增强for遍历

1
2
3

for (String str : set) {  
      System.out.println(str);  
}

2. 数组相关题目

2.1 字母异位词

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

主要思想

这道题目要我们比较的是每个字符出现的次数，那么我们就有两个需要比较的量，一个是出现的字符是否相等，另一个是字符出现的次数是否相等，那么我们就可以想到，本题中的字符串由26个字母构成，是一个有限且可以连续的集合(将字符转换位ASCII码)，所以我们考虑用可存储连续集合的存储工具数组来进行存储，每个索引对应的值就是他出现的次数。那么每在s字符串出现一次，加上1；每在t字符串出现一次，减去1；因为异位词要求字母个数都相等，到最后只需要判断数组内的元素是否均为0即可。

注意点

本题可能有的会考虑用Map进行存储，key为字母字符，values为次数；是可以的，但是Map中key的特点是可以连续可以不连续，需要用一个哈希映射来存储相对应Map的值，而且也会新增很多空间，影响性能。而连续的集合用数组可以和Map达到一样的效果，但是空间成本小了。

代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        // 新建26位数组存储26个字母
        int[] temp = new int[26];
        // 加入记录
        for(int i = 0; i < s.length(); i++) {
            temp[s.charAt(i) - 'a'] ++;
        }
        // 移除记录
        for(int i = 0; i < t.length(); i++) {
            temp[t.charAt(i) - 'a'] --;
        }
        // 匹配是否还有记录
        for(int i = 0; i < 26; i++) {
            if(temp[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

2.2 赎金信

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

主要思想

和上道题的思路是一样的，找要求的重复字符以及其出现的次数。这个升级版主要体现在他不是完全匹配的了，那我们就要从中想出加上的是哪个，减去的是哪个。那么这里用大的数组加入，小的数组减去，如果都大于0，说明大的完全能包含小的；如果小于0，说明大的里面由小的没有的元素。

注意点

学一下字符串的两种遍历方法吧，for增强遍历for(char ch : str.toCharArray)和直接遍历for()... str.charAt(i)

代码实现

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

3. Set相关题目

3.1 两个数组的交集

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

题目中说到输出结果中的每个元素一定是唯一的，那么就无需去考虑每个元素出现的次数了。所以我们只需判断的是有没有出现过即可，那么这种单一元素的判断，而且数组内元素是离散的，用数组会造成很多空间的浪费，所以我们想到了无连续的离散的集合Set。创建两个集合，其中一个作为比对集，负责比较有没有重复，另一个作为结果集，记录符合条件元素。

注意点

集合转数组的写法：resset.stream().mapToInt(x -> x).toArray()

代码实现

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 计算的集合
        Set<Integer> tempset = new HashSet<>();
        // 结果输出的集合
        Set<Integer> resset = new HashSet<>();
        for(int i : nums1) {
            tempset.add(i);
        }
        for(int i : nums2) {
            if(tempset.contains(i)) {
                // 比对成功，加入结果集
                resset.add(i);
            }
        }
        return resset.stream().mapToInt(x -> x).toArray();
    }
}

3.2 快乐数

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

这道题明确声明了会有无限循环的情况出现，那么这道题得到的就两个结果，一个是我们确定是快乐数的条件：最后结果是1；另一个是无限循环，不是快乐数。所以我们可以直接在循环中设置退出条件一个是为1，另一个是无限循环。那么要判断是否无限循环就是判断字符是否出现过，重复出现的问题想到哈希表，又因为我们只需要记录内容，次数我们不关心，一个维度我们就用Set就可以了。

注意点

获取每位数字的方法：第一步是取10模，得到个位的数字；第二步是除以10，将十位的数字移到下一位个位，然后不断循环，中止的条件是没有可以移动的位了，说明这个数已经被我们操作完了，也就是n > 0。

代码实现

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> code = new HashSet<>();
        // 因为会无限循环，所以到了重复的时候就说明无需再进行下去了
        while(n != 1 && !code.contains(n)){
            code.add(n);
            n = getNextCount(n);
        }
            return n == 1;
}


        // 获取每位数字的平方和
        private int getNextCount(int n) {
            int res = 0;
            while(n > 0) {
                int temp = n % 10;
                res += temp * temp;
                n = n / 10;
            }
            return res;
        }
    
}

4. Map相关题目

4.1 两数之和

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

我们需要通过数组的每个元素值对其进行计算，然后输出的是他的下标，那么这时候我们会发现，其实我们需要操作的是两个值，又需要对元素进行比对匹配，所以选择用Map集合或者数组存储会比较好一些，那我们就看到底是不是连续的。因为最后要输出的是索引，所以我们会选择把索引存在Values中，而元素就只能存在key中了，因为元素的离散的，所以我们只能用Map集合了。

注意点

每次一定都要好好想想空值和特殊值有没有办法包含在你的逻辑中，没有的话要提前排除掉。数组的空值具体实现为：nums == null || nums.length == 0

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 结果集存储结果
        int[] res = new int[2];
        // 排除空数组
            if(nums == null || nums.length == 0){
        return res;
    }
        Map<Integer, Integer> map = new HashMap<>();
        // key为数组元素值，values为对应元素索引
        for(int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if(map.containsKey(nums[i])) {
                res[1] = i;
                res[0] = map.get(nums[i]);
                break;
            }
            map.put(temp, i);
        }
        return res;
    }
}

4.2 四数之和Ⅱ

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

主要思想

这里要求我们输出的是元组的个数，也就是我们不需要具体的去确认他的下标，只需要知道有这个东西存在就可以了。所以我们要关心的就是元素的值。那其实我们可以两两拆分，遍历数组集合求出两个数组的和，然后再与另外两个数组匹配，时间复杂度虽然是n^2^，但是相较于暴力算法直接缩短了一半。但是我们发现，可能一个数的和可以由多种表现形式，所以我们还需要关心的一个点就是组成该和的个数。所以其实我们要考虑到的是两个变量，所以我们会使用Map集合，key用来存储两个数组和的值，values用来存储这个和的组成出现的次数。之后在进行配对的时候也要把所有符合的次数加上，也就计数的时候不是+1，而是+values了。

注意点

存储更新个数的操作：包含：map.put(sum, map.get(sum) + 1);不包含：map.put(nums1[i] + nums2[j], 1);

代码实现

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 计数器记录满足条件元组个数
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        // 两两配对生成集合
        for(int i = 0; i < nums1.length; i++) {
            for(int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                if(map.containsKey(sum)) {
                    // 存储个数更新的操作
                    map.put(sum, map.get(sum) + 1);
                }else{
                    map.put(nums1[i] + nums2[j], 1);
                }
            }
        }
        for(int i = 0; i < nums3.length; i++) {
            for(int j = 0; j < nums4.length; j++) {
                int temp = 0 - (nums3[i] + nums4[j]);
                    if(map.containsKey(temp)) {
                        // 需要进行所有的配对
                        count += map.get(temp);
                    }
            }
        }
        return count;
    }
}

4.3 三数之和

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

主要思想

等于一个指定的值，那么就有大于小于等于三种情况，只有三者不断的中立，那么最后才能实现，那么我们就想到了其实可以用排序对他进行划分，那么排序就想到了双指针，但是这里有三个数怎么办呢，那么我们就固定一个，然后去走另外两个，等于是有两个变量的双指针就是O(a)级别的时间复杂度，有三个变量的双指针就是O(n)的时间复杂度，有n个变量的双指针就是O(n^n-2)的时间复杂度。

注意点

去重复的动作，因为题目明确告诉我们了一样的不算，那么我们怎么去重复呢，就对于固定指针而言，他前后不能一样，对于移动的双指针模型而言，他们两个不能同时一样即可。因为他们两组指针是相对运动的。而有个细节的点就是判断固定指针去重的时候如果这么写nums[i] == nums[i + 1]，就会引发一个只是重复元素但是被我们排除的情况，因为我们未曾比较过，而后移了，这个本来应该操作的可操作范围就变小了，应该写成和i-1进行比较，这样才能确保所有都是匹配过的，操作范围上一个一样的比你大，那肯定你能匹配到的范围也是他能够匹配到的。
去重不能只去除一次，而要去到满足这个条件为止，所以不能用if，而要用while
将集合装进集合：list.add(Arrays.asList(nums[index], nums[left], nums[right]));

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        // 对于第一项就大于0的有序数组，那么势必无法加起来等于0


        
        for(int index = 0; index < nums.length; index++){
                    if(nums[index] > 0) {
            return list;
        }
        // 对于index的去重
        if(index != 0 && nums[index] == nums[index - 1]) {
            continue;
        }
        int left = index + 1;
        int right = nums.length - 1;
        while(left < right){
            int sum = nums[index] + nums[left] + nums[right];
            if(sum > 0) {
                // 太大了，应该小一点，那么右边就缩小
                right --;
            } else if(sum < 0) {
                // 太小了，应该大一点，左边过来点
                left ++;
            } else if(sum == 0) {
                // 是我们的目标，装进集合里去！
            list.add(Arrays.asList(nums[index], nums[left], nums[right]));
            
            // 去重left
            while(left < right && nums[left] == nums[left + 1]) {
                left++;
            }
            // 去重right
            while(left < right && nums[right] == nums[right - 1]) {
                right--;
            }
            left++;
            right--;
            }
        }
        }
        return list;
    }
}

4.4 四数之和

复杂度

时间复杂度：O(n^3)
空间复杂度：O(n)

主要思想

比三数之和多了一层循环。

注意点

不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};