Java-栈和队列

力扣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类中的方法

方法 描述
empty() 如果堆栈的顶部没有任何东西,则返回true。否则,返回false。
peek() 返回堆栈顶部的元素,但不删除它。
pop() 删除并返回堆栈顶部的元素。如果我们在调用pop()时,调用的堆栈是空的,就会抛出一个’EmptyStackException’异常。
push(Object element) 将一个元素推到堆栈的顶部。
search(Object element) 它确定一个对象是否存在于堆栈中。如果找到该元素,它返回该元素在堆栈顶部的位置。否则,它返回-1。

Java Stack类

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

LinkedList继承了队列接口

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

  • 队列用于在队列的末端插入元素,并从队列的开头删除。它遵循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


JVM-字节码文件构成

字节码

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];
}
类型 名称 说明 长度 数量
u4 magic 魔数,识别类文件格式 4个字节 1
u2 minor_version 副版本号(小版本) 2个字节 1
u2 major_version 主版本号(大版本) 2个字节 1
u2 constant_pool_count 常量池计数器 2个字节 1
cp_info constant_pool 常量池表 n个字节 constant_pool_count-1
u2 access_flags 访问标识 2个字节 1
u2 this_class 类索引 2个字节 1
u2 super_class 父类索引 2个字节 1
u2 interfaces_count 接口计数 2个字节 1
u2 interfaces 接口索引集合 2个字节 interfaces_count
u2 fields_count 字段计数器 2个字节 1
field_info fields 字段表 n个字节 fields_count
u2 methods_count 方法计数器 2个字节 1
method_info methods 方法表 n个字节 methods_count
u2 attributes_count 属性计数器 2个字节 1
attribute_info attributes 属性表 n个字节 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
主版本(十进制) 副版本(十进制) 编译器版本
45 3 1.1
46 0 1.2
47 0 1.3
48 0 1.4
49 0 1.5
50 0 1.6
51 0 1.7
52 0 1.8
53 0 1.9
54 0 1.10
55 0 1.11

常量池

常量池中常量的数量是不固定的,所以在常量池的入口需要放置一项 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

常量类型和结构:

类型 标志(或标识) 描述
CONSTANT_utf8_info 1 UTF-8编码的字符串
CONSTANT_Integer_info 3 整型字面量
CONSTANT_Float_info 4 浮点型字面量
CONSTANT_Long_info 5 长整型字面量
CONSTANT_Double_info 6 双精度浮点型字面量
CONSTANT_Class_info 7 类或接口的符号引用
CONSTANT_String_info 8 字符串类型字面量
CONSTANT_Fieldref_info 9 字段的符号引用
CONSTANT_Methodref_info 10 类中方法的符号引用
CONSTANT_InterfaceMethodref_info 11 接口中方法的符号引用
CONSTANT_NameAndType_info 12 字段或方法的符号引用
CONSTANT_MethodHandle_info 15 表示方法句柄
CONSTANT_MethodType_info 16 标志方法类型
CONSTANT_InvokeDynamic_info 18 表示一个动态方法调用点

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

访问标识

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

  • 类的访问权限通常为 ACC_ 开头的常量
  • 每一种类型的表示都是通过设置访问标记的 32 位中的特定位来实现的,比如若是 public final 的类,则该标记为 ACC_PUBLIC | ACC_FINAL
  • 使用 ACC_SUPER 可以让类更准确地定位到父类的方法,确定类或接口里面的 invokespecial 指令使用的是哪一种执行语义,现代编译器都会设置并且使用这个标记
标志名称 标志值 含义
ACC_PUBLIC 0x0001 标志为 public 类型
ACC_FINAL 0x0010 标志被声明为 final,只有类可以设置
ACC_SUPER 0x0020 标志允许使用 invokespecial 字节码指令的新语义,JDK1.0.2之后编译出来的类的这个标志默认为真,使用增强的方法调用父类方法
ACC_INTERFACE 0x0200 标志这是一个接口
ACC_ABSTRACT 0x0400 是否为 abstract 类型,对于接口或者抽象类来说,次标志值为真,其他类型为假
ACC_SYNTHETIC 0x1000 标志此类并非由用户代码产生(由编译器产生的类,没有源码对应)
ACC_ANNOTATION 0x2000 标志这是一个注解
ACC_ENUM 0x4000 标志这是一个枚举

索引集合

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

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

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

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

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

字段表

字段 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 指令引用的引导方式限定符

JVM-对象标记

三色标记

标记算法

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

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

当 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:读屏障