栈的数据结构
栈数据结构方面特点是数据具有先进后出的特点，下面是用数组简单实现了栈的基本方法
/**
* @author 数组实现
*/
public class ArrayStack<T>
{
// 定义一个一维数组用来存储数据
private Object[] stack ;
private int size;
// 初始化数组
public ArrayStack(int maxLength){
stack = new Object[maxLength];
size = 0;
}
// 判空方法
public boolean isEmpty(){
return size==0;
}
// 判断数组是否超过长度
public boolean isFull(){
return size == stack.length;
}
// 进栈
public boolean push(T t){
if(isFull()) return false;
stack[size++] = t;
return true;
}
// 出栈
public Object pop(){
if(isEmpty()) return null;
return stack[--size];
}
// 返回栈顶元素
public Object peek(){
if(isEmpty()) return null;
return stack[size-1];
}
public void display(){
for (int i = 0; i < size; i++)
{
System.out.println("栈的第"+(i+1)+"个元素是"+stack[i]);
}
}
// 测试
public static void main(String[] args)
{
ArrayStack<Integer> arrayStack = new ArrayStack(5);
for (int i = 1; i < 10 ; i++)
{
boolean pushResult = arrayStack.push(i);
if(!pushResult){
System.out.println("栈已满 i="+i);
break;
}
}
// 打印栈元素
arrayStack.display();
while(!arrayStack.isEmpty()){
System.out.println("栈顶元素是："+arrayStack.peek());
System.out.println("弹栈元素是："+arrayStack.pop());
}
}
}
概念
1.每个java线程都对应一个栈，其中的调用的每个一个方法称为一个栈帧，栈是线程私有的，不存在线程安全问题
2.栈保存着局部变量 （8种基本数据类型（byte short int long double float boolean char) 以及引用对
象（类，数组，接口）——的地址值），部分结果，方法的调用和返回
3.栈不属于垃圾回收机制回收的区域，但是也会出现栈溢出（StackOverflowError）个别情况或出现OOM
4.可以通过-Xss命令来规定HotSpot中每个栈的大小（默认大小是1m）
运行原理
1.每个线程都有自己的栈，栈中的数据都是以栈帧(Stack Frame)的格式存在
2.在这个线程上正在执行的每个方法都对应各自的一个栈帧
3.栈帧是一个内存区块，是一个数据集，维系着方法执行过程中的各种数据信息
4.JVM直接对java栈的操作只有两个，就是对栈帧的压栈和出栈，遵循先进后出/后进先出的和原则。
5.在一条活动线程中，一个时间点上，只会有一个活动的栈帧。即只有当前正在执行的方法的栈帧（栈顶栈帧）是有效的，
这个栈帧被称为当前栈帧(Current Frame),与当前栈帧对应的方法就是当前方法（Current Frame）
6.执行引擎运行的所有字节码指令只针对当前栈帧进行操作
7.如果在该方法中调用了其他方法，对应的新的栈帧会被创建出来，放在栈的顶端，成为新的当前栈帧。
8.不同线程中所包含的栈帧是不允许相互引用的，即不可能在另一个栈帧中引用另外一个线程的栈帧
9.如果当前方法调用了其他方法，方法返回之际，当前栈帧会传回此方法的执行结果给前一个栈帧，接着，虚拟机会丢弃
当前栈帧，使得前一个栈帧重新成为当前栈帧
10.Java方法有两种返回函数的方式，一种是正常的函数返回，使用return指令；另外一种是抛出异常。不管使用哪种方
式，都会导致栈帧被弹出。
问题：局部变量是否是线程安全的
/**
* 面试题：
* 方法中定义的局部变量是否线程安全？具体情况具体分析
*
* 何为线程安全？
* 如果只有一个线程可以操作此数据，则必定是线程安全的。
* 如果有多个线程操作此数据，则此数据是共享数据。如果不考虑同步机制的话，会存在线程安全问题
*
* 我们知道StringBuffer是线程安全的源码中实现synchronized，StringBuilder源码未实现synchronized,在多线程情况下是不安全的
* 二者均继承自AbstractStringBuilder
*
*/
public class StringBuilderTest {
//s1的声明方式是线程安全的，s1在方法method1内部消亡了
public static void method1(){
StringBuilder s1 = new StringBuilder();
s1.append("a");
s1.append("b");
}
//stringBuilder的操作过程：是不安全的，因为method2可以被多个线程调用
public static void method2(StringBuilder stringBuilder){
stringBuilder.append("a");
stringBuilder.append("b");
}
//s1的操作：是线程不安全的 有返回值，可能被其他线程共享
public static StringBuilder method3(){
StringBuilder s1 = new StringBuilder();
s1.append("a");
s1.append("b");
return s1;
}
//s1的操作：是线程安全的 ，StringBuilder的toString方法是创建了一个新的String，s1在内部消亡了
public static String method4(){
StringBuilder s1 = new StringBuilder();
s1.append("a");
s1.append("b");
return s1.toString();
}
public static void main(String[] args) {
StringBuilder s = new StringBuilder();
new Thread(()->{
s.append("a");
s.append("b");
}).start();
method2(s);
}
}
栈帧的元素
方法栈是由许多栈帧组成的，一个栈帧对应一个方法
public class StackTest
{
public static void main(String[] args)
{
method1();
}
private static void method1(){
int a = 1;
method2();
}
private static void method2()
{
int a = 1;
long b = 1L;
String c = "1";
int d = 2;
}
}
当方法运行到method2()的时候,栈结构如下
栈.jpg
栈帧的元素主要包括
1.局部变量表（LocalVariables）
2。操作数栈
3.动态链接
4.方法返回地址
5.附加信息
其中动态链接，方法返回地址，附加信息 又称为帧数据区
局部变量表
1.又称为局部变量数组，或者是本地变量表，包括基本数据类型，引用数据类型
2.局部变量表的大小是在编译期间就确定下来的
3.局部变量表和方法是一对一的，即和栈帧是一对一的，随着栈帧的销而销毁
4.局部变量占据了栈绝大部分内存，是栈优化的重点区域
5.局部变量表中的变量也是重要的垃圾回收根节点，只要被局部变量表中直接或间接引用的对象都不会被回收
如何看局部变量表，通过查看字节码文件的汇编指令
1.javap -v StackTest.class(需要配置环境变量,需要到StackTest.class所在文件夹，并且私有方法不会显示
出来)
2.idea开发工具添加jclasslib bytecode viewer插件 需要重启idea生效
我们以javap -v 查看上述图 method2()中指令如下
public static void method2(); --方法名
descriptor: ()V -- 返回值类型
flags: ACC_PUBLIC, ACC_STATIC
Code: --方法运行指令
stack=2, locals=5, args_size=0 -- 操作栈长度：2，局部变量表长度：5 ，参数长度：0
0: iconst_1
1: istore_0
2: lconst_1
3: lstore_1
4: ldc #4 // String 1
6: astore_3
7: iconst_2
8: istore 4
10: return
LineNumberTable: --代码行对应的指令行
line 24: 0
line 25: 2
line 26: 4
line 27: 7
line 28: 10
LocalVariableTable: -- 局部变量表
Start Length Slot Name Signature
2 9 0 a I
4 7 1 b J
7 4 3 c Ljava/lang/String;
10 1 4 d I
详解局部变量表
Start: 表示该变量的作用域 指令行起始位置,即创建位置
Length: 表示该变量的作用域指令长度,该方法指令集从0开始到10一共11行方法中定义局部变量在方法结束前
都有作用,所以起始位置加上作用域长度都等于这个方法的指令长度
Slot:
1.参数值的存放总是在局部变量数组的index0开始，到数组长度-1的索引结束
2.局部变量表，最基本的存储单元是Slot(变量槽)
3.局部变量表中存放编译期可知的各种基本数据类型（8种），引用类型（reference），returnAddress
类型的变量。
4.在局部变量表里，32位以内的类型只占用一个slot（包括 returnAddress类型），64位的类型（long
和double）占用两个slot。byte、short、char、float在存储前被转换为int， boolean也被转换
为int，0表示false，非0表示 true；long和double则占据两个slot,引用对象也只占一个slot
5.栈帧中的局部变量表中的槽位是可以重复利用的，如果一个局部变量过了其作用域，那么在其作用域之后
申明的新的局部变量就很有可能会复用过期局部变量的槽位，从而达到节省资源的目的
private void test2() {
int a = 0;
{
int b = 0;
b = a+1;
}
//变量c使用之前以及经销毁的变量b占据的slot位置
int c = a+1;
}
问:这个方法对应的栈帧对应的slot是几个
结果: 3个, 1:this 2:a 3:b 3:c (变量c使用之前以及经销毁的变量b占据的slot位置)
name: 变量名
Signature: 数据类型信息
需要主要的是,如果是非静态方法,每个局部变量表第一个变量都是this,args_size(参数长度也是这样)
操作数栈
操作数栈，主要用于保存计算过程的中间结果，同时作为计算过程中变量临时的存储空间。
操作数栈就是jvm执行引擎的一个工作区，当一个方法开始执行的时候，一个新的栈帧也会随之被创建出来，这个方法的操作数栈是空的
每一个操作数栈都会拥有一个明确的栈深度用于存储数值，其所需的最大深度在编译器就定义好了，保存在方法的code属性中，为max_stack的值。
栈中的任何一个元素都是可以任意的java数据类型
32bit的类型占用一个栈单位深度
64bit的类型占用两个栈深度单位
操作数栈并非采用访问索引的方式来进行数据访问的，而是只能通过标准的入栈push和出栈pop操作来完成一次数据访问
如果被调用的方法带有返回值的话，其返回值将会被压入当前栈帧的操作数栈中，并更新PC寄存器中下一条需要执行的字节码指令。
操作数栈中的元素的数据类型必须与字节码指令的序列严格匹配，这由编译器在编译期间进行验证，同时在类加载过程中的类验证阶段的数据流分析阶段要再次验证。
另外，我们说Java虚拟机的解释引擎是基于栈的执行引擎,其中的栈指的就是操作数栈。
总结一句:就是临时记录数据的结构,如下是一个方法的代码
int a = 1;
int b = 2;
int c = a+b;
每一次变量的复制都需要存入操作数栈,然后再存入到局部变量表,计算的时候需要将a和b都进入压入操作数栈,然后计算所以这个栈帧的操作数栈最大长度是2,同理a,b,c都是double或者long,那么该栈帧的操作数栈的的最大长度就是4
动态链接
讲动态链接之前需要先了解一下类的常量池
1.javap -v StackTest.class 命令查看汇编指令的时候,会看到如下信息
Constant pool:
#1 = Methodref #6.#29 // java/lang/Object."<init>":()V
#2 = Methodref #5.#30 // stack/StackTest.method1:()V
#3 = Methodref #5.#31 // stack/StackTest.method2:()V
#4 = String #32 // 1
#5 = Class #33 // stack/StackTest
#6 = Class #34 // java/lang/Object
#7 = Utf8 <init>
#8 = Utf8 ()V
#9 = Utf8 Code
...............
上述部分就是类的常量池,作用是:提供一些符号和常量，便于指令的识别,上述讲方法运行指令的时候有一行:
4: ldc #4 // String 1
后面的#4就是符号引用,需要指导常量池中#4对应的常量或者指令
2.在Java源文件被编译成字节码文件中时，所有的变量和方法引用都作为符号引用（symbolic Refenrence）保存
在class字节码文件（javap反编译查看）的常量池里。比如：描述一个方法调用了另外的其他方法时，就是通过常量
池中指向方法的符号引用来表示的，那么动态链接的作用就是为了将这些符号引用（#）最终转换为调用方法的直接引用。
方法的调用
在JVM中，将符号引用转换为调用方法的直接引用与方法的绑定机制相关
##静态链接
当一个 字节码文件被装载进JVM内部时，如果被调用的目标方法在编译期可知，且运行期保持不变时。这种情况下将调用方法的符号引用转换为直接引用的过程称之为静态链接。
##动态链接
1.如果被调用的方法在编译期无法被确定下来，也就是说，只能够在程序运行期将调用方法的符号引用转换为直接引用，由于这种引用转换过程具备动态性，因此也就被称之为动态链接。
2.对应的方法的绑定机制为：早起绑定（Early Binding）和晚期绑定（Late Bingding）。绑定是一个字段、方法或者类在符号引用被替换为直接引用的过程，这仅仅发生一次。
##早期绑定
早期绑定就是指被调用的目标方法如果在编译期可知，且运行期保持不变时，即可将这个方法与所属的类型进行绑定，这样一来，由于明确了被调用的目标方法究竟是哪一个，因此也就可以使用静态链接的方式将符号引用转换为直接引用。
##晚期绑定
如果被调用的方法在编译期无法被确定下来，只能够在程序运行期根据实际的类型绑定相关的方法，这种绑定方式也就被称之为晚期绑定。
随着高级语言的横空出世，类似于java一样的基于面向对象的编程语言如今越来越多，尽管这类编程语言在语法风格上存在一定的差别，但是它们彼此之间始终保持着一个共性，那就是都支持封装，集成和多态等面向对象特性，既然这一类的编程语言具备多态特性，那么自然也就具备早期绑定和晚期绑定两种绑定方式。
Java中任何一个普通的方法其实都具备虚函数的特征，它们相当于C++语言中的虚函数（C++中则需要使用关键字virtual来显式定义）。如果在Java程序中不希望某个方法拥有虚函数的特征时，则可以使用关键字final来标记这个方法。
##虚方法和非虚方法
子类对象的多态性使用前提：实际开发编写代码中用的接口，实际执行是导入的的三方jar包已经实现的功能`
①类的继承关系（父类的声明）②方法的重写（子类的实现）`
##非虚方法
1. 如果方法在编译器就确定了具体的调用版本，这个版本在运行时是不可变的。这样的方法称为非虚方法
2.静态方法、私有方法、final方法、实例构造器（实例已经确定，this()表示本类的构造器）、父类方法（super调用）都是非虚方法**
3.其他所有体现多态特性的方法称为虚方法
## 虚拟机中提供了以下几条方法调用指令
普通调用指令：
1.invokestatic：调用静态方法，解析阶段确定唯一方法版本；
2.invokespecial:调用<init>方法、私有及父类方法，解析阶段确定唯一方法版本；
3.invokevirtual调用所有虚方法；
4.invokeinterface：调用接口方法；
动态调用指令（Java7新增）：
5.invokedynamic：动态解析出需要调用的方法，然后执行 .
前四条指令固化在虚拟机内部，方法的调用执行不可人为干预，而invokedynamic指令则支持由用户确定方法版本。
**其中invokestatic指令和invokespecial指令调用的方法称为非虚方法**
**其中invokevirtual**（final修饰的除外，JVM会把final方法调用也归为**invokevirtual指令，但要注意****final方法调用不是虚方法******）**、****invokeinterface**指令调用的方法称**称为虚方法。
## 关于invokedynamic指令
* JVM字节码指令集一直比较稳定，一直到java7才增加了一个invokedynamic指令，这是Java为了实现【动态类型语言】支持而做的一种改进
* 但是java7中并没有提供直接生成invokedynamic指令的方法，需要借助ASM这种底层字节码工具来产生invokedynamic指令.直到Java8的Lambda表达式的出现，invokedynamic指令的生成，在java中才有了直接生成方式
* Java7中增加的动态语言类型支持的本质是对java虚拟机规范的修改，而不是对java语言规则的修改，这一块相对来讲比较复杂，增加了虚拟机中的方法调用，最直接的受益者就是运行在java平台的动态语言的编译器
## 动态类型语言和静态类型语言
* 动态类型语言和静态类型语言两者的却别就在于对类型的检查是在编译期还是在运行期，满足前者就是静态类型语言，反之则是动态类型语言。
* 直白来说 **静态语言是判断变量自身的类型信息；动态类型语言是判断变量值的类型信息，变量没有类型信息，变量值才有类型信息**,这是动态语言的一个重要特征
* Java是静态类型语言（尽管lambda表达式为其增加了动态特性），js，python是动态类型语言.
## 方法重写的本质
* 1 找到操作数栈的第一个元素所执行的对象的实际类型，记作C。
* 2.如果在类型C中找到与常量池中的描述符、简单名称都相符的方法，则进行访问权限校验，如果通过则返回这个方法的直接引用，查找过程结束；如果不通过，则返回java.lang.IllegalAccessError异常。
* 3.否则，按照继承关系从下往上依次对c的各个父类进行第二步的搜索和验证过程。
* 4.如果始终没有找到合适的方法，则抛出java.lang.AbstractMethodError异常。 **IllegalAccessError介绍** 程序视图访问或修改一个属性或调用一个方法，这个属性或方法，你没有权限访问。一般的，这个会引起编译器异常。这个错误如果发生在运行时，就说明一个类发生了不兼容的改变。
## 虚方法表
* 在面向对象编程中，会很频繁期使用到动态分派，如果在每次动态分派的过程中都要重新在累的方法元数据中搜索合适的目标的话就可能影响到执行效率。因此，为了提高性能，jvm采用在类的方法区建立一个虚方法表（virtual method table）（非虚方法不会出现在表中）来实现。使用索引表来代替查找。
* 每个类中都有一个虚方法表，表中存放着各个方法的实际入口。
* 那么虚方法表什么时候被创建？ 虚方法表会在类加载的链接阶段被创建 并开始初始化，类的变量初始值准备完成之后，jvm会把该类的虚方法表也初始化完毕。
# 方法返回地址（Return Address）
* 存放调用该方法的PC寄存器的值。
* 一个方法的结束，有两种方式：
正常执行完成
出现未处理的异常，非正常退出
* 无论通过哪种方式退出，在方法退出后都返回到该方法被调用的位置。方法正常退出时，调用者（方法的调用者可能也是一个方法）的pc计数器的值作为返回地址，即调用该方法的指令的下一条指令的地址。**而通过异常退出时，返回地址是要通过异常表来确定，栈帧中一般不会保存这部分信息。
* 本质上，方法的退出就是当前栈帧出栈的过程。此时，需要恢复上层方法的局部变量表、操作数栈、将返回值入调用者栈帧的操作数栈、设置PC寄存器值等，让调用者方法继续执行下去。
* 正常完成出口和异常完成出口的区别在于：通过异常完成出口退出的不会给他的上层调用者产生任何的返回值。**
## 当一个方法开始执行后，只有两种方式可以退出这个方法
1.执行引擎遇到任意一个方法返回的字节码指令（return），会有返回值传递给上层的方法调用者，简称正常完成出口；
* 一个方法在正常调用完成之后究竟需要使用哪一个返回指令还需要根据方法返回值的实际数据类型而定
* 在字节码指令中，返回指令包含ireturn（当返回值是boolena、byte、char、short和int类型时使用）、lreturn、freturn、dreturn以及areturn(引用类型的)
* 另外还有一个return指令供声明为void的方法、实例初始化方法、类和接口的初始化方法使用
2.在方法执行的过程中遇到了异常（Exception），并且这个异常没有在方法内进行处理，也就是只要在本方法的异常表中没有搜素到匹配的异常处理器，就会导致方法退出，简称**异常完成出口**
方法执行过程中抛出异常时的异常处理，存储在一个异常处理表，方便在发生异常的时候找到处理异常的代码。
# 栈帧当中的一些附加信息
栈帧中还允许携带与java虚拟机实现相关的一些附加信息。例如，对程序调试提供支持的信息。（很多资料都忽略了附加信息）
