力扣225. 用队列实现栈

力扣232.用栈实现队列

这里不自己造轮子，主要讲一下Java里这两个数据结构相关的实现类

Java Stack类

Java集合框架提供了一个Stack类，它模拟和实现了一个 Stack数据结构 该类是基于后进先出的基本原则。除了基本的push和pop操作外，该类还提供了empty、search和peek三种功能。该类也可以说是对Vector的扩展，并将该类作为一个具有上述五个功能的堆栈。该类也可以被称为Vector的子类。

下图显示了 Stack类的层次结构

该类支持一个默认的构造函数 Stack() ，用于创建一个空栈。

声明

1

public class Stack<E> extends Vector<E>

所有实现的接口 。

• 可序列化（Serializable）： 这是一个标记性的接口，如果类要被序列化和反序列化，就必须实现它。
• Cloneable: 这是Java中的一个接口，需要由一个类来实现，以使其对象可以被克隆。
• Iterable <E>：这个接口表示一个可迭代的对象集合，意思是可以迭代。
• Collection <E>:一个集合代表了一组被称为其元素的对象。在需要最大限度的通用性时，Collection接口被用来传递对象的集合。
• List <E>:List接口提供了一种存储有序集合的方法。它是Collection的一个子接口。
• RandomAccess： 这是一个标记接口，由List实现使用，表示它们支持快速（一般是恒定时间）的随机访问。

如何创建一个堆栈

为了创建一个堆栈，我们必须导入 java.util.stack 包并使用该类的Stack()构造函数。下面的例子创建了一个空的堆栈。

1

Stack<E> stack = new Stack<E>()

这里E是对象的类型。

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

// Java code for stack implementation
  
import java.io.*;
import java.util.*;
  
class Test
{   
    // Pushing element on the top of the stack
    static void stack_push(Stack<Integer> stack)
    {
        for(int i = 0; i < 5; i++)
        {
            stack.push(i);
        }
    }
      
    // Popping element from the top of the stack
    static void stack_pop(Stack<Integer> stack)
    {
        System.out.println("Pop Operation:");
  
        for(int i = 0; i < 5; i++)
        {
            Integer y = (Integer) stack.pop();
            System.out.println(y);
        }
    }
  
    // Displaying element on the top of the stack
    static void stack_peek(Stack<Integer> stack)
    {
        Integer element = (Integer) stack.peek();
        System.out.println("Element on stack top: " + element);
    }
      
    // Searching element in the stack
    static void stack_search(Stack<Integer> stack, int element)
    {
        Integer pos = (Integer) stack.search(element);
  
        if(pos == -1)
            System.out.println("Element not found");
        else
            System.out.println("Element is found at position: " + pos);
    }
  
  
    public static void main (String[] args)
    {
        Stack<Integer> stack = new Stack<Integer>();
  
        stack_push(stack);
        stack_pop(stack);
        stack_push(stack);
        stack_peek(stack);
        stack_search(stack, 2);
        stack_search(stack, 6);
    }
}

输出
Pop Operation:
4
3
2
1
0
Element on stack top: 4
Element is found at position: 3
Element not found

Stack类中的方法

Java Stack类

队列接口存在于java.util包中，并扩展了Collection接口，用于保存即将以FIFO（先进先出）顺序处理的元素。它是一个有序的对象列表，其用途仅限于在列表的末尾插入元素和从列表的开头删除元素，（即）它遵循 先进先出 的原则。

队列的特点： 以下是队列的特点。

• 队列用于在队列的末端插入元素，并从队列的开头删除。它遵循FIFO概念。
• Java队列支持集合接口的所有方法，包括插入、删除等。
• LinkedList、ArrayBlockingQueue和PriorityQueue是最常使用的实现方式。
• 如果对阻塞队列进行任何空操作，就会抛出NullPointerException。
• java.util包中的队列是无界队列。
• java.util.concurrent包中的队列是有界队列。
• 除了Deques之外，所有的队列都分别支持在队列的尾部和头部进行插入和删除。Deques支持两端的元素插入和删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

package java.util;

public interface Queue<E> extends Collection<E> {
    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

参考：https://geek-docs.com/java/java-collection/g_queue-interface-java.html

字节码

https://zhuanlan.zhihu.com/p/563602651

跨平台性

Java 语言：跨平台的语言（write once ，run anywhere）

• 当 Java 源代码成功编译成字节码后，在不同的平台上面运行无须再次编译
• 让一个 Java 程序正确地运行在 JVM 中，Java 源码就必须要被编译为符合 JVM 规范的字节码

编译过程中的编译器：

• 前端编译器： Sun 的全量式编译器 javac、 Eclipse 的增量式编译器 ECJ，把源代码编译为字节码文件 .class

  • IntelliJ IDEA 使用 javac 编译器
  • Eclipse 中，当开发人员编写完代码后保存时，ECJ 编译器就会把未编译部分的源码逐行进行编译，而非每次都全量编译，因此 ECJ 的编译效率会比 javac 更加迅速和高效
  • 前端编译器并不会直接涉及编译优化等方面的技术，具体优化细节移交给 HotSpot 的 JIT 编译器负责

• 后端运行期编译器：HotSpot VM 的 C1、C2 编译器，也就是 JIT 编译器，Graal 编译器

  • JIT 编译器：执行引擎部分详解
  • Graal 编译器：JDK10 HotSpot 加入的一个全新的即时编译器，编译效果短短几年时间就追平了 C2

• 静态提前编译器：AOT (Ahead Of Time Compiler）编译器，直接把源代码编译成本地机器代码

  • JDK 9 引入，是与即时编译相对立的一个概念，即时编译指的是在程序的运行过程中将字节码转换为机器码，AOT 是程序运行之前便将字节码转换为机器码

  • 优点：JVM 加载已经预编译成二进制库，可以直接执行，不必等待即时编译器的预热，减少 Java 应用第一次运行慢的现象

  • 缺点：

    • 破坏了 Java 一次编译，到处运行，必须为每个不同硬件编译对应的发行包
    • 降低了 Java 链接过程的动态性，加载的代码在编译期就必须全部已知

语言发展

机器码：各种用二进制编码方式表示的指令，与 CPU 紧密相关，所以不同种类的 CPU 对应的机器指令不同

指令：指令就是把机器码中特定的 0 和 1 序列，简化成对应的指令，例如 mov，inc 等，可读性稍好，但是不同的硬件平台的同一种指令（比如 mov），对应的机器码也可能不同

指令集：不同的硬件平台支持的指令是有区别的，每个平台所支持的指令，称之为对应平台的指令集

• x86 指令集，对应的是 x86 架构的平台
• ARM 指令集，对应的是 ARM 架构的平台

汇编语言：用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址

• 在不同的硬件平台，汇编语言对应着不同的机器语言指令集，通过汇编过程转换成机器指令
• 计算机只认识指令码，汇编语言编写的程序也必须翻译成机器指令码，计算机才能识别和执行

高级语言：为了使计算机用户编程序更容易些，后来就出现了各种高级计算机语言

字节码：是一种中间状态（中间码）的二进制代码，比机器码更抽象，需要直译器转译后才能成为机器码

• 字节码为了实现特定软件运行和软件环境，与硬件环境无关
• 通过编译器和虚拟机器实现，编译器将源码编译成字节码，虚拟机器将字节码转译为可以直接执行的指令

类结构

文件结构

字节码是一种二进制的类文件，是编译之后供虚拟机解释执行的二进制字节码文件，一个 class 文件对应一个 public 类型的类或接口

字节码内容是 JVM 的字节码指令，不是机器码，C、C++ 经由编译器直接生成机器码，所以执行效率比 Java 高

JVM 官方文档：https://docs.oracle.com/javase/specs/jvms/se8/html/index.html

根据 JVM 规范，类文件结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ClassFile {
	u4 				magic;						
    u2 				minor_version;						
    u2 				major_version;						
    u2 				constant_pool_count;
    cp_info			constant_pool[constant_pool_count-1];
    u2	 			access_flags;
    u2 				this_class;
    u2 				super_class;
    u2 				interfaces_count;
    u2 				interfaces[interfaces_count];
    u2 				fields_count;
    field_info 		fields[fields_count];
    u2 				methods_count;
    method_info 	methods[methods_count];
    u2 				attributes_count;
    attribute_info 	attributes[attributes_count];
}

Class 文件格式采用一种类似于 C 语言结构体的方式进行数据存储，这种结构中只有两种数据类型：无符号数和表

• 无符号数属于基本的数据类型，以 u1、u2、u4、u8 来分别代表1个字节、2个字节、4个字节和8个字节的无符号数，无符号数可以用来描述数字、索引引用、数量值或者按照 UTF-8 编码构成字符串
• 表是由多个无符号数或者其他表作为数据项构成的复合数据类型，表都以 _info 结尾，用于描述有层次关系的数据，整个 Class 文件本质上就是一张表，由于表没有固定长度，所以通常会在其前面加上个数说明

获取方式：

• HelloWorld.java 执行 javac -parameters -d . HellowWorld.java指令
• 写入文件指令 javap -v xxx.class >xxx.txt
• IDEA 插件 jclasslib

魔数版本

魔数：每个 Class 文件开头的 4 个字节的无符号整数称为魔数（Magic Number），是 Class 文件的标识符，代表这是一个能被虚拟机接受的有效合法的 Class 文件，

• 魔数值固定为 0xCAFEBABE，不符合则会抛出错误

• 使用魔数而不是扩展名来进行识别主要是基于安全方面的考虑，因为文件扩展名可以随意地改动

版本：4 个 字节，5 6两个字节代表的是编译的副版本号 minor_version，而 7 8 两个字节是编译的主版本号 major_version

• 不同版本的 Java 编译器编译的 Class 文件对应的版本是不一样的，高版本的 Java 虚拟机可以执行由低版本编译器生成的 Class 文件，反之 JVM 会抛出异常 java.lang.UnsupportedClassVersionError

常量池

常量池中常量的数量是不固定的，所以在常量池的入口需要放置一项 u2 类型的无符号数，代表常量池计数器（constant_pool_count），这个容量计数是从 1 而不是 0 开始，是为了满足后面某些指向常量池的索引值的数据在特定情况下需要表达不引用任何一个常量池项目，这种情况可用索引值 0 来表示

constant_pool 是一种表结构，以1 ~ constant_pool_count - 1为索引，表明有多少个常量池表项。表项中存放编译时期生成的各种字面量和符号引用，这部分内容将在类加载后进入方法区的运行时常量池

• 字面量（Literal） ：基本数据类型、字符串类型常量、声明为 final 的常量值等

• 符号引用（Symbolic References）：类和接口的全限定名、字段的名称和描述符、方法的名称和描述符

  • 全限定名：com/test/Demo 这个就是类的全限定名，仅仅是把包名的 . 替换成 /，为了使连续的多个全限定名之间不产生混淆，在使用时最后一般会加入一个 ; 表示全限定名结束

  • 简单名称：指没有类型和参数修饰的方法或者字段名称，比如字段 x 的简单名称就是 x

  • 描述符：用来描述字段的数据类型、方法的参数列表（包括数量、类型以及顺序）和返回值

    标志符	含义
    B	基本数据类型 byte
    C	基本数据类型 char
    D	基本数据类型 double
    F	基本数据类型 float
    I	基本数据类型 int
    J	基本数据类型 long
    S	基本数据类型 short
    Z	基本数据类型 boolean
    V	代表 void 类型
    L	对象类型，比如：Ljava/lang/Object;，不同方法间用;隔开
    [	数组类型，代表一维数组。比如：double[][][] is [[[D

常量类型和结构：

18 种常量没有出现 byte、short、char，boolean 的原因：编译之后都可以理解为 Integer

访问标识

访问标识（access_flag），又叫访问标志、访问标记，该标识用两个字节表示，用于识别一些类或者接口层次的访问信息，包括这个 Class 是类还是接口，是否定义为 public类型，是否定义为 abstract类型等

• 类的访问权限通常为 ACC_ 开头的常量
• 每一种类型的表示都是通过设置访问标记的 32 位中的特定位来实现的，比如若是 public final 的类，则该标记为 ACC_PUBLIC | ACC_FINAL
• 使用 ACC_SUPER 可以让类更准确地定位到父类的方法，确定类或接口里面的 invokespecial 指令使用的是哪一种执行语义，现代编译器都会设置并且使用这个标记

索引集合

类索引、父类索引、接口索引集合

• 类索引用于确定这个类的全限定名

• 父类索引用于确定这个类的父类的全限定名，Java 语言不允许多重继承，所以父类索引只有一个，除了Object 之外，所有的 Java 类都有父类，因此除了 java.lang.Object 外，所有 Java 类的父类索引都不为0

• 接口索引集合就用来描述这个类实现了哪些接口

  • interfaces_count 项的值表示当前类或接口的直接超接口数量
  • interfaces[] 接口索引集合，被实现的接口将按 implements 语句后的接口顺序从左到右排列在接口索引集合中

字段表

字段 fields 用于描述接口或类中声明的变量，包括类变量以及实例变量，但不包括方法内部、代码块内部声明的局部变量以及从父类或父接口继承。字段叫什么名字、被定义为什么数据类型，都是无法固定的，只能引用常量池中的常量来描述

fields_count（字段计数器），表示当前 class 文件 fields 表的成员个数，用两个字节来表示

fields[]（字段表）：

• 表中的每个成员都是一个 fields_info 结构的数据项，用于表示当前类或接口中某个字段的完整描述

• 字段访问标识：

  标志名称	标志值	含义
  ACC_PUBLIC	0x0001	字段是否为public
  ACC_PRIVATE	0x0002	字段是否为private
  ACC_PROTECTED	0x0004	字段是否为protected
  ACC_STATIC	0x0008	字段是否为static
  ACC_FINAL	0x0010	字段是否为final
  ACC_VOLATILE	0x0040	字段是否为volatile
  ACC_TRANSTENT	0x0080	字段是否为transient
  ACC_SYNCHETIC	0x1000	字段是否为由编译器自动产生
  ACC_ENUM	0x4000	字段是否为enum

• 字段名索引：根据该值查询常量池中的指定索引项即可

• 描述符索引：用来描述字段的数据类型、方法的参数列表和返回值

  字符	类型	含义
  B	byte	有符号字节型树
  C	char	Unicode字符，UTF-16编码
  D	double	双精度浮点数
  F	float	单精度浮点数
  I	int	整型数
  J	long	长整数
  S	short	有符号短整数
  Z	boolean	布尔值true/false
  V	void	代表void类型
  L Classname	reference	一个名为Classname的实例
  [	reference	一个一维数组

• 属性表集合：属性个数存放在 attribute_count 中，属性具体内容存放在 attribute 数组中，一个字段还可能拥有一些属性，用于存储更多的额外信息，比如初始化值、一些注释信息等

  1 2 3 4 5

  ConstantValue_attribute{ u2 attribute_name_index; u4 attribute_length; u2 constantvalue_index; }

  对于常量属性而言，attribute_length 值恒为2

方法表

方法表是 methods 指向常量池索引集合，其中每一个 method_info 项都对应着一个类或者接口中的方法信息，完整描述了每个方法的签名

• 如果这个方法不是抽象的或者不是 native 的，字节码中就会体现出来
• methods 表只描述当前类或接口中声明的方法，不包括从父类或父接口继承的方法
• methods 表可能会出现由编译器自动添加的方法，比如初始化方法 和实例化方法

重载（Overload）一个方法，除了要与原方法具有相同的简单名称之外，还要求必须拥有一个与原方法不同的特征签名，特征签名就是一个方法中各个参数在常量池中的字段符号引用的集合，因为返回值不会包含在特征签名之中，因此 Java 语言里无法仅仅依靠返回值的不同来对一个已有方法进行重载。但在 Class 文件格式中，特征签名的范围更大一些，只要描述符不是完全一致的两个方法就可以共存

methods_count（方法计数器）：表示 class 文件 methods 表的成员个数，使用两个字节来表示

methods[]（方法表）：每个表项都是一个 method_info 结构，表示当前类或接口中某个方法的完整描述

• 方法表结构如下：

  类型	名称	含义	数量
  u2	access_flags	访问标志	1
  u2	name_index	字段名索引	1
  u2	descriptor_index	描述符索引	1
  u2	attrubutes_count	属性计数器	1
  attribute_info	attributes	属性集合	attributes_count

• 方法表访问标志：

  标志名称	标志值	含义
  ACC_PUBLIC	0x0001	字段是否为 public
  ACC_PRIVATE	0x0002	字段是否为 private
  ACC_PROTECTED	0x0004	字段是否为 protected
  ACC_STATIC	0x0008	字段是否为 static
  ACC_FINAL	0x0010	字段是否为 final
  ACC_VOLATILE	0x0040	字段是否为 volatile
  ACC_TRANSTENT	0x0080	字段是否为 transient
  ACC_SYNCHETIC	0x1000	字段是否为由编译器自动产生
  ACC_ENUM	0x4000	字段是否为 enum

属性表

属性表集合，指的是 Class 文件所携带的辅助信息，比如该 Class 文件的源文件的名称，以及任何带有 RetentionPolicy.CLASS 或者 RetentionPolicy.RUNTIME 的注解，这类信息通常被用于 Java 虚拟机的验证和运行，以及 Java 程序的调试。字段表、方法表都可以有自己的属性表，用于描述某些场景专有的信息

attributes_ count（属性计数器）：表示当前文件属性表的成员个数

attributes[]（属性表）：属性表的每个项的值必须是 attribute_info 结构

• 属性的通用格式：

  1 2 3 4 5

  ConstantValue_attribute{ u2 attribute_name_index; //属性名索引 u4 attribute_length; //属性长度 u2 attribute_info; //属性表 }

• 属性类型：

  属性名称	使用位置	含义
  Code	方法表	Java 代码编译成的字节码指令
  ConstantValue	字段表	final 关键字定义的常量池
  Deprecated	类、方法、字段表	被声明为 deprecated 的方法和字段
  Exceptions	方法表	方法抛出的异常
  EnclosingMethod	类文件	仅当一个类为局部类或者匿名类是才能拥有这个属性，这个属性用于标识这个类所在的外围方法
  InnerClass	类文件	内部类列表
  LineNumberTable	Code 属性	Java 源码的行号与字节码指令的对应关系
  LocalVariableTable	Code 属性	方法的局部变量描述
  StackMapTable	Code 属性	JDK1.6 中新增的属性，供新的类型检查检验器检查和处理目标方法的局部变量和操作数有所需要的类是否匹配
  Signature	类，方法表，字段表	用于支持泛型情况下的方法签名
  SourceFile	类文件	记录源文件名称
  SourceDebugExtension	类文件	用于存储额外的调试信息
  Syothetic	类，方法表，字段表	标志方法或字段为编泽器自动生成的
  LocalVariableTypeTable	类	使用特征签名代替描述符，是为了引入泛型语法之后能描述泛型参数化类型而添加
  RuntimeVisibleAnnotations	类，方法表，字段表	为动态注解提供支持
  RuntimelnvisibleAnnotations	类，方法表，字段表	用于指明哪些注解是运行时不可见的
  RuntimeVisibleParameterAnnotation	方法表	作用与 RuntimeVisibleAnnotations 属性类似，只不过作用对象为方法
  RuntirmelnvisibleParameterAnniotation	方法表	作用与 RuntimelnvisibleAnnotations 属性类似，作用对象哪个为方法参数
  AnnotationDefauit	方法表	用于记录注解类元素的默认值
  BootstrapMethods	类文件	用于保存 invokeddynanic 指令引用的引导方式限定符

三色标记

标记算法

三色标记法把遍历对象图过程中遇到的对象，标记成以下三种颜色：

• 白色：尚未访问过
• 灰色：本对象已访问过，但是本对象引用到的其他对象尚未全部访问
• 黑色：本对象已访问过，而且本对象引用到的其他对象也全部访问完成

当 Stop The World (STW) 时，对象间的引用是不会发生变化的，可以轻松完成标记，遍历访问过程为：

1. 初始时，所有对象都在白色集合
2. 将 GC Roots 直接引用到的对象挪到灰色集合
3. 从灰色集合中获取对象：
   • 将本对象引用到的其他对象全部挪到灰色集合中
   • 将本对象挪到黑色集合里面
4. 重复步骤 3，直至灰色集合为空时结束
5. 结束后，仍在白色集合的对象即为 GC Roots 不可达，可以进行回收

并发标记

并发标记时，对象间的引用可能发生变化，多标和漏标的情况就有可能发生

多标情况：当 E 变为灰色或黑色时，其他线程断开的 D 对 E 的引用，导致这部分对象仍会被标记为存活，本轮 GC 不会回收这部分内存，这部分本应该回收但是没有回收到的内存，被称之为浮动垃圾

• 针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，也算浮动垃圾
• 浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除

漏标情况：

• 条件一：灰色对象断开了对一个白色对象的引用（直接或间接），即灰色对象原成员变量的引用发生了变化
• 条件二：其他线程中修改了黑色对象，插入了一条或多条对该白色对象的新引用
• 结果：导致该白色对象当作垃圾被 GC，影响到了程序的正确性

代码角度解释漏标：

1
2
3

Object G = objE.fieldG; // 读
objE.fieldG = null;  	// 写
objD.fieldG = G;     	// 写

为了解决问题，可以操作上面三步，将对象 G 记录起来，然后作为灰色对象再进行遍历，比如放到一个特定的集合，等初始的 GC Roots 遍历完（并发标记），再遍历该集合（重新标记）

所以重新标记需要 STW，应用程序一直在运行，该集合可能会一直增加新的对象，导致永远都运行不完

解决方法：添加读写屏障，读屏障拦截第一步，写屏障拦截第二三步，在读写前后进行一些后置处理：

• 写屏障 + 增量更新：黑色对象新增引用，会将黑色对象变成灰色对象，最后对该节点重新扫描

  增量更新 (Incremental Update) 破坏了条件二，从而保证了不会漏标

  缺点：对黑色变灰的对象重新扫描所有引用，比较耗费时间

• 写屏障 (Store Barrier) + SATB：当原来成员变量的引用发生变化之前，记录下原来的引用对象

  保留 GC 开始时的对象图，即原始快照 SATB，当 GC Roots 确定后，对象图就已经确定，那后续的标记也应该是按照这个时刻的对象图走，如果期间对白色对象有了新的引用会记录下来，并且将白色对象变灰（说明可达了，并且原始快照中本来就应该是灰色对象），最后重新扫描该对象的引用关系

  SATB (Snapshot At The Beginning) 破坏了条件一，从而保证了不会漏标

• 读屏障 (Load Barrier)：破坏条件二，黑色对象引用白色对象的前提是获取到该对象，此时读屏障发挥作用

以 Java HotSpot VM 为例，其并发标记时对漏标的处理方案如下：

• CMS：写屏障 + 增量更新
• G1：写屏障 + SATB
• ZGC：读屏障