看标题不知是否让您想起了有向图中的最短路径，是有些许类似，不过该题比其更简单更加清晰、直观、好理解。相信您看完这个之后，脑回路肯定更加的明亮！

题目描述如下：

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

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

初看题目，上下有关联，有结束点，是个适合用递归的题目。以三角形的“行数”作为递归的结束判断，行数加上下标作为参数来回穿插。可行，可行！

于是大笔一挥：

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

int size = 0;
TreeSet<Integer> ts = new TreeSet<>();
List<List<Integer>> list;

/**
 * 超时
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {
    list = triangle;
    size = triangle.size();
    if (size == 0)
        return 0;

    helper(0, 0, 0);
    return ts.first();
}

/**
 * 
 * @param row
 *            行数
 * @param index
 *            在该行中下标
 * @param sum_length
 *            路径之和
 */
private void helper(int row, int index, int sum_length) {
    if (row >= size) {
        ts.add(sum_length);
        return;
    }
    sum_length += list.get(row).get(index);
    helper(row + 1, index, sum_length);
    helper(row + 1, index + 1, sum_length);
}

是的，代码没有问题，可是拿去跑的时候，数据较大的测试用例却给了一个大红色的 超出时间限制。这里将 TreeSet 换成一个 MIN_LENGTH 整型变量每次进行比较取较小值，结果一样，都是超时。

本来是满怀欣喜，豪气撸码，结果给撞了个豆腐墙。

墙不硬，问题不大。我们换个思路，再摸摸青青草地。

以往出现这种求最小值、最大值啊，需要数据之间相关联相加减乘除的啊，用的都是 DP 居多啊！

脑浆乍现，回路高速擦亮，越擦越亮，越擦越闪，终于“吡”得一身，为数不多的小草又飘下几根，成了！

我也不用额外的空间了，就在你身上肆虐！

再回头看下那个“三角形”：

1
2
3
4
5
6

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

既然是要一个最小值，那我就逐步缩减法，自下而上攻之。

根据题目要求我们知道如果上一行的元素下标为 i，那它只能跟它下一行的下标为 i 和 i+1 两元素相加。当然，我们只需要这两者的较小值。

即：

1
2
3
4
5
6
7
8
9
10
11
12
13

 [6,5,7]   // i 行
[4,1,8,3]  // j 行

以这两行为例 （条件：j = i + 1）

i 行中的 6 可以跟 j 行中的 4 或者 1 相加，由于我们结果取的是最小值，所以我们只留较小值
6 + 4 = 10, 6 + 1 = 7
因为 10 > 7，所以 i 行中的 6 我们就随之替换为 7

剩余元素同理，i 行最终便成了：
[7,6,10]

再由此，层层攻上。随着数量越来越少，最终顶上的那位佼佼者便是我们要取的首级！

武器献之：

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

/**
 * DP
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {

    // 从倒数第二行开始往上走
    for (int i = triangle.size() - 2; i >= 0; i--) {
        // 从每行的起始下标开始直到 i
        for (int j = 0; j <= i; j++) {
            // i 行 j 下标的值
            int self = triangle.get(i).get(j);
            // 将 i 行 j 下标的值赋为 ： i 行 j 下标的值 与 i+1 行 j 下标和 j+1 下标值之和的较小值
            triangle.get(i).set(j,
                    Math.min(triangle.get(i + 1).get(j) + self, triangle.get(i + 1).get(j + 1) + self));
        }
    }
    // 层层往上 顶层值便是路径最小值
    return triangle.get(0).get(0);
}

这道题容易理解，对 DP（动态规划） 会有一个较为清晰的认知，我认为还是很不错的，故特意整理之。

文笔不好，望见谅！ End.

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

概述

执行引擎是 Java 虚拟机最核心的组成部分之一。在不同的虚拟机实现里面，执行引擎在执行 Java 代码的时候可能会有解释执行（通过解释器执行）和编译执行（通过即时编译器产生本地代码执行）两种选择，也可能两者兼备，甚至还可能会包含几个不同级别的编译器执行引擎。

但从外观上看起来，所有的 Java 虚拟机的执行引擎都是一致的：输入的是字节码文件，处理过程是字节码解析的等效过程，输出的是执行结果。接下来将主要从 概念模型的角度来总结下虚拟机的 方法调用和 字节码执行。

运行时栈帧结构

栈帧是用于支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区中的虚拟机栈的栈元素。每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机栈里面从入栈到出栈的过程。

每一个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外的附加信息。在编译程序代码的时候，栈帧中需要多大的局部变量表，多深的操作数栈都已经完全确定了，并且写入到方法表的 Code 属性之中，因此，一个栈帧需要分配多少内存，不会受到程序运行期变量数据的影响，而仅仅取决于具体的虚拟机实现。

局部变量表

局部变量表是一组变量值存储空间，用于存放方法参数和方法内部定义的局部变量。它的容量以变量槽（Variable Slot，下称 Slot）为最小单位。

在方法执行时，虚拟机是使用局部变量表来完成参数值到参数变量列表的传递过程的，如果执行的是实例方法（非 static 的方法），那局部变量表中第 0 位索引的 Slot 默认是用于传递方法所属对象实例的引用，在方法中可以通过关键字 this 来访问到这个隐含的参数。其余参数则按照参数表顺序排列，占用从 1 开始的局部变量 Slot，参数表分配完毕后，再根据方法体内部定义的变量顺序和作用域分配其余的 Slot。

局部变量定义了但没有赋初始值，是不能使用的，切记！

操作数栈

操作数栈也常称为操作栈，它是一个后入先出栈。同局部变量表一样，它的最大深度也是在编译时就写入到 Code 属性的 max_stacks 数据项中。

当一个方法刚刚开始执行时，这个方法的操作数栈是空的，在方法的执行过程中，会有各种字节码指令往操作数栈中写入和提取内容，也就是出栈 / 入栈操作。如：在做算术运算的时候是通过操作数栈来进行的，又或者在调用其他方法的时候是通过操作数栈来进行参数传递的。

动态连接

每个栈帧都包含一个指向运行时常量池中该栈帧所属方法的引用，持有这个引用是为了支持方法调用过程中的动态连接。

字节码中的方法调用指令就以常量池中指向方法的符号引用作为参数。这些符号引用一部分会在类加载阶段或者第一次使用的时候就转化为直接引用，这种转化称为 静态解析。另外一部分将在每一次运行期间转化为直接引用，这部分称为 动态连接。

方法返回地址

当一个方法开始执行后，只有两种方式可以退出这个方法：

• 执行引擎遇到任意一个方法返回的字节码指令，这时候可能会有返回值传递给上层的方法调用者，是否有返回值和返回值的类型将根据遇到何种方法返回指令来决定，这种退出方法的方式称为正常完成出口。
• 在方法执行过程中遇到了异常，并且这个异常没有在方法体内得到处理，无论是 Java 虚拟机内部产生的异常还是代码中使用 athrow 字节码指令产生的异常，只要在本方法的异常表中没有搜索到匹配的异常处理器，就会导致方法退出，这种退出方法的方式称为异常完成出口。

一个方法使用异常完成出口的方式退出，是不会给它的上层调用者产生任何返回值的。

方法退出的过程实际上就等同于把当前栈帧出栈，因此退出时可能执行的操作有：恢复上层方法的局部变量表和操作数栈，把返回值（如果有的话）压入调用者栈帧的操作数栈中，调整 PC 计数器的值以指向方法调用指令后面的一条指令等。

附加信息

虚拟机规范允许具体的虚拟机实现增加一些规范中没有描述的信息到栈帧之中，例如与调试相关的信息，这部分信息完全取决于具体的虚拟机实现。

在实际开发中，一般会把动态连接、方法返回地址与其他附加信息全部归为一类，称为栈帧信息。

方法调用

方法调用并不等同于方法执行，方法调用阶段唯一的任务就是确定被调用方法的版本（即调用哪一个方法），暂时还不涉及方法内部的具体运行过程。

一切方法调用在 Class 文件里面存储的都只是符号引用，而不是方法在实际运行时内存布局中的入口地址（相当于之前说的直接引用）。

解析

调用目标在程序代码写好、编译器进行编译时就必须确定下来。这类方法的调用称为解析。

在 Java 虚拟机里面提供了 5 条方法调用字节码指令：

• invokestatic：调用静态方法
• invokespecial：调用实例构造器 <init> 方法、私有方法和父类方法
• invokevirtual：调用所有的虚方法
• invokeinterface：调用接口方法，会在运行时再确定一个实现此接口的对象
• invokedynamic：先在运行时动态解析出调用点限定符所引用的方法，然后再执行该方法，在此之前的 4 条调用指令，分派逻辑是固化在 Java 虚拟机内部的，而 invokedynamic 指令的分派逻辑是由用户所设定的引导方法决定的

只要能被 invokestatic 和 invokespecial 指令调用的方法，都可以在解析阶段中确定唯一的调用版本，符合这个条件的有静态方法、私有方法、实例构造器和父类方法 4 类。它们在类加载的时候就会把符号引用解析为该方法的直接引用，称为 非虚方法。其余的称为 虚方法。

final 方法是一种非虚方法。

分派

静态分派

Human man = new Man()

上面代码中的 Human 称为变量的静态类型，或是外观类型，Man 称为变量的实际类型。静态类型和实际类型在程序中都可以发生一些变化，但是静态类型的变化仅仅在使用时发生，变量本身的静态类型不会被改变，并且最终的静态类型是在编译期可知的；而实际类型变化的结果在运行期才可确定，编译器在编译程序时并不知道一个对象的实际类型是什么。

编译器在重载时是通过参数的静态类型而不是实际类型作为判断依据的，所以，两个静态类型相同但实际类型不同的变量，在编译阶段，Javac 编译器会根据参数的静态类型决定使用哪一个重载版本。

动态分派

我们先说说重写，重写与动态分派关系密切。invokevirtual 指令执行是在 运行期确定接收者的实际类型，所以调用中的 invokevirtual 指令把常量池中的类方法符号引用解析到了不同的直接引用上，这个过程就是 Java 语言中方法重写的本质。

我们把这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量，根据分派基于多少种宗量，可以将分派划分为单分派和多分派两种。

单分派是根据一个宗量对目标方法进行选择，多分派是根据多于一个宗量对目标方法进行选择。

基于栈的字节码解释执行引擎

探讨虚拟机是如何执行方法中的字节码指令的。

解释执行

Java 语言中，Javac 编译器完成了程序代码经过词法分析、语法分析到抽象语法树，再遍历语法树生成线性的字节码指令流的过程。因为这一部分动作是在 Java 虚拟机之外进行的，而解释器在虚拟机的内部，所以 Java 程序的编译就是半独立的实现。

基于栈的指令集与基于寄存器的指令集

基于栈的指令集主要优点就是可移植，还可把一些访问频繁的数据放到寄存器中获取尽量好的性能，代码会相对更加紧凑，编译器实现更加简单等。

栈架构指令集的主要缺点是执行速度相对来说会稍慢一些，完成相同功能所需的指令数量较寄存器架构多，频繁的栈访问导致频繁的内存访问。

End.

这个十一月为什么说忙碌呢，因为忙着抽纸巾擤鼻涕，感冒了；因为忙着买买买，剁手了；因为忙着来来回回，出差了。

• 感冒

怪我，都怪我，前一段时间温差变化大，我懒啊，没及时加被子，还没穿裤子就睡了，半夜那个冻的，知道冷但就是没爬起来加被子，然后，感冒了一周，鼻子都搞破皮了……

后来晚上还去夜跑，跑完当时感觉好点了，结果洗了个澡之后，鼻涕又来了，睡觉时候那个呼吸难受的啊，还好我床头纸管够……

• 买买买

最近买了不少东西，买了件大衣，结果稍稍大了点，不换了吧来来回回的，凑活穿。还买了几双鞋，什么耐克阿迪的，便宜的太丑，好看的太贵还没货，倒是对彪马越来越感兴趣，价格还行，款式也还行（不还是因为较之便宜嘛……）。

气的是有双鞋刚买了不到一个月就又看到大降价，差了一百来块呢，唉，安慰自己毕竟早穿上了这么多天呢不是……

平时感觉穿的也都有，但是人嘛，喜新厌旧，而且这个购物啊，确实是精神上不一样啊，单身狗的刺激手段之一了，避免一直陷在麻木的生活状态之中。偶尔还是需要精神刺激的，啊，好疼~

搞了套迪卡侬的运动装备，迪卡侬性价比真高，懊恼自己以前怎么不去了解，东西感觉都不错，大赞！以后运动装备就尽量选择迪卡侬了。

• 金链子

去年就跟老姐说过今年要给老妈买条大金链子的，身上什么首饰也没有，着实不好了点。故趁着发工资了，给老姐打过去 2000 块，“给老妈买条大金链子！其余的你补上！”哈哈，2000 肯定是不够买的，怪儿子出门在外没挣到什么钱，心意到了啊。回头给老爸搞双皮鞋，本来是去年买的，唉，加油加油！

说到金，家里爷爷还留给我一个纯金戒指来着。小时候我看着那戒指，心想，这纯金戒指，得值多少钱啊。现在知道了，也就值个千把块钱……还用来传家呢……看什么时候给它化了，弄成其他的，金戒指也忒俗气了些。

• 路上姑娘

今儿早又看到这姑娘了，所以我才把这提上来。

姑娘长发小脸，笑意浓浓，纤细身材，气质不凡。

我们往往是在五角场附近相遇的。我骑着车，她低着头。

虽然我看她时她没看过我，但我却看到她眼睛在笑，即使我那只是短短的一瞥，看得却异常清楚。有一种熟悉的感觉爬上了我的心头。可能是我接触异性少了，脑子出现了毛病……用我大学室友一句口头禅来说就是：这个不孬。

也正是这几个月来遇到了很多次，且位置都大差不差，我这才记住了，不知道她是否注意到我没……

人的一生会遇到许许多多的人。佛说，前世的五百次回眸，才换来今生的擦肩而过。

如果无缘，我只愿你一生安好，陌生人。

• 出差

出差了出差了，人生中的第一次出差啊。这次去杭州出差了一周，期间自然不是很顺利。项目上的就不多说了，这个晚上啊，因为还有一位同事一起的，所以我们就定的标间。

我那几天都是凌晨才慢慢睡去。为什么？旁边有位打呼跟电钻工装修一样的，要搁你，你能睡得着不……我还那会感冒没好全，身体素质是真不好，鼻血都流了好几回也不知道是不是擤鼻涕用力过猛了。

而且我这个头啊，右脑勺还真刺疼，公司体检卡发了，不过要下月才开始能预约，希望一切健康，买的保险用不上啊……

说到买的保险，买了个泰康的，送了个洗牙套餐，上月预约的都只能预约到一月份了，全家现在就我这口牙还行，最近好像也是开始出问题了，我得勤刷牙了，晚上不忘记能刷就刷。

拉回来说这个出差。由于我也没有经验，也没有什么准备，导致我根本就找不到可以冲账的发票，最后还是用的领导的燃油发票来报。看来，以后要多攒攒发票了，虽说出差少，备着吧。

• 余华

余华，当代著名作家，他的许多作品获过国内外奖项。

不知道，没关系。《活着》这部小说，总看过吧，没看过总听说过吧。没听说过？那我劝你现在就拿起手机打开 APP，订购一本，不要 998，也不要 198，它只要二十来块就能买到。

记得当时我是花了一个晚上把《活着》给看完的，情节太紧凑了根本不给我歇的机会，看了停不下来，等歇下来了，原来后面没了，翻到了最后一页。

最近我又在看他的另一本长篇小说《兄弟》。文人骚客，不骚就不叫文人了。不过里面骚的恰到好处，连接情节，更能吸引读者，引人入胜。

大体上，我看到现在，主色调还是悲的，也是在文革前后那段时间下描述的故事。极具讽刺意味。

只要能捱过来，那就都不是事。

• 蒋劲夫家暴

今天早上又刷到了这个新闻。家暴，我是不可能家暴的，真的很气愤也只会动动嘴皮子，大不了就出门透透气。个人认为，家暴确实是做不得，也不是男人该做的事。当然，会有些人有暴力倾向，更可怕的是有些女人还会十分享受被家暴的过程，这种人呢肯定是有的，而且可能还不少。

大家夫妻之间，情侣之间搞搞 SM 啊什么的我倒是觉得很正常，别动不动就搞出血还搞出命，不值当啊！所以，两人在一起，这些东西都是需要熟知的，要了解清楚，三观不合的怎么可能长久，那种一夜情的就没必要查户口了。

真快啊都要 2018 12 月份了，下次写个年终总结，好好借机回顾一下自己这一年来的成长。长肯定是有长的，长哪就不知道了。

哈哈，生死本无常，人应多思量。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

想必大家对二叉树也不陌生，被各种二叉树面试题支配的恐惧仍记忆犹新……

这篇就总结一下二叉树的各种遍历，包括前、中、后序遍历还有层次遍历。

让我们来想象，大脑是个无底洞，这个栈它没有深度，所以我们要时而把栈底那些强行挖上来，以防痴呆！你不想痴呆吧！go go go.

层次遍历

先来这个层次遍历，二叉树一层又一层，它有深度。既然是一层接着一层，那很清楚了，我们逐层遍历就行。

题目描述：

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

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

清晰得不能再清晰了。递归调用 + 循环节点。代码如下：

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

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<>();
        List<TreeNode> l = new ArrayList<>();
        l.add(root);
        helper(list, l);
        return list;

    }

    /**
     * 递归 层层遍历
     * 
     * @param list
     * @param treeList
     */
    private void helper(List<List<Integer>> list, List<TreeNode> treeList) {
        if (treeList.size() == 0)
            return;
        List<Integer> listInt = new ArrayList<>();
        List<TreeNode> treeL = new ArrayList<>();
        // 逐层添值
        for (TreeNode node : treeList) {
            if (node != null) {
                listInt.add(node.val);
                treeL.add(node.left);
                treeL.add(node.right);
            }
        }
        if (listInt.size() > 0)
            list.add(listInt);

        helper(list, treeL);
    }

或者是使用队列 + while 循环搞定：

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

/**
     * 使用队列 queue
     * 
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

        if (root == null)
            return wrapList;

        queue.offer(root);
        while (!queue.isEmpty()) {
            // 有值就塞入集合 同时将其左右子节点添加到队列中
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for (int i = 0; i < levelNum; i++) {
                if (queue.peek().left != null)
                    queue.offer(queue.peek().left);
                if (queue.peek().right != null)
                    queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(subList);
        }
        return wrapList;
    }

这个问题不大。

中序遍历

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

也就是根结点遍历位置在中间： 左 -> 根 -> 右

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

既然都说了递归算法很简单，确实也很简单，先上递归算法：

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

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 递归
     * 
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        helper(list, root);
        return list;
    }

    private void helper(List<Integer> list, TreeNode node) {
        if (node != null) {
            if (node.left != null)
                helper(list, node.left);
            list.add(node.val);
            if (node.right != null)
                helper(list, node.right);
        }
    }

这个递归算法在前、中、后序遍历都可以套用的，着实好用也好记。下面就不重复该代码了，无非就是结点的顺序换一换。

迭代算法，这里我们思考一下，我们需要先读其左结点，读完之后再读其根结点，左结点若是存在，那它不就是下一层的根结点吗？然后我们再一层层往上读。此时脑壳一抖，栈！

Stack 来解决：

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

/**
 * 栈 stack 来解决
 * 
 * @param root
 * @return
 */
public List<Integer> inorderTraversal1(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            // 将其左节点依次放入 因为先读左节点
            stack.push(curr);
            curr = curr.left;
        }
        // 将栈顶弹出
        curr = stack.pop();
        // 塞值
        res.add(curr.val);
        // 将右节点赋值给它 完美呈现了中序遍历 ： 左 -> 根 -> 右
        curr = curr.right;
    }
    return res;
}

代码也不长，该过程可以用大脑无底栈来走一遍。闭上眼睛，冥想。

前序遍历

前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

即根结点遍历位置在前面： 根 -> 左 -> 右

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归算法不说了，见上。

迭代这里用双向链表 LinkedList，数据量大时存取数据性能好点。

代码如下：

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

/**
 * 双向队列
 * 
 * @param root
 * @return
 */
public List<Integer> preorderTraversal1(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
        return output;
    }
    stack.add(root);
    while (!stack.isEmpty()) {
        // 弹出队列中最后一个
        TreeNode node = stack.pollLast();
        output.add(node.val);
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            // 该节点就是下一个要读的根节点
            stack.add(node.left);
        }
    }
    return output;
}

这里需要注意的就是 stack.add() 先添加右结点在添加左结点，因为 stack.pollLast() 取出的是最后一个数据，这样就是左结点先弹出，满足前序遍历的顺序。

后序遍历

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

即根结点遍历位置在前面： 左 -> 右 -> 根

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

同样，递归算法不重复，见上。

这里的迭代算法我是看了官网的解法。秒。利用双向链表每次在起始位置添加值，顺序为根 -> 右 -> 左，然后遍历完后整个顺序从前往后就是左 -> 右 -> 根，后序遍历。

双向链表 LinkedList + 栈 Stack，代码如下：

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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 根 -> 右 -> 左 存入，遍历完全后从前往后即是 左 -> 右 -> 根
 * 
 * @param root
 * @return
 */
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null)
        return ans;

    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        // 将值塞到最前面
        ans.addFirst(cur.val);
        // 先左结点入栈
        if (cur.left != null) {
            stack.push(cur.left);
        }
        // 再是右结点入栈
        if (cur.right != null) {
            stack.push(cur.right);
        }
    }
    return ans;
}

从后往前推，一气呵成。

其实，还是递归最好使……

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

概述

虚拟机把描述类的数据从 Class 文件加载到内存，并对数据进行校验、转换解析和初始化，最终形成可以被虚拟机直接使用的 Java 类型，这就是虚拟机的类加载机制。

与那些在编译时需要进行连接工作的语言不同，在 Java 语言里面，类型的加载、连接和初始化过程都是在程序运行期间完成的，Java 里天生可以动态扩展的语言特性就是依赖 运行期动态加载和 动态连接这个特点实现的。

类加载的时机

类从被加载到虚拟机内存中开始，到卸载出内存为止，它的整个生命周期包括：加载、验证、准备、解析、初始化、使用和卸载 7 个阶段。其中验证、准备、解析 3 个部分统称为连接。

加载、验证、准备、初始化和卸载这 5 个阶段的顺序是确定的，类的加载过程必须按照这种顺序按部就班地开始，而解析阶段则不一定：它在某些情况下可以在初始化阶段之后再开始，这是为了支持 Java 语言的运行时绑定（也称为动态绑定或晚期绑定）。

对于初始化阶段，虚拟机规范是严格规定了 有且只有 5 中情况必须对类进行“初始化”（而加载、验证、准备自然需要在此之前开始）：

• 遇到 new、getstatic、putstatic 或 invokestatic 这 4 条字节码指令时，如果类没有进行过初始化，则需要先触发其初始化
• 使用 java.lang.reflect 包的方法对类进行反射调用的时候，如果类没有进行过初始化，则需要先触发其初始化
• 当初始化一个类的时候，如果发现其父类还没有进行过初始化，则需要先触发其父类的初始化
• 当虚拟机启动时，用户需要指定一个要执行的主类（包含 main() 方法的那个类），虚拟机会先初始化这个主类
• 当使用 JDK 1.7 的动态语言支持时，如果一个 java.lang.invoke.MethodHandle 实例最后的解析结果 REF_getStatic、REF_putStatic、REF_invokeStatic 的方法句柄，并且这个方法句柄所对应的类没有进行过初始化，则需要先触发其初始化

这 5 中场景中的行为称为对一个类进行主动引用。除此之外，所有引用类的方式都不会触发初始化，称为被动引用。

被动引用举例：

• 通过子类引用父类的静态字段，不会导致子类初始化
• 通过数组定义来引用类，不会触发此类的初始化
• 常量在编译阶段存入常量池中，调用时不会触发定义常量的类的初始化

接口的加载过程与类加载过程稍有一些不同，针对接口需要做一些特殊处理：接口也有初始化过程，虽然接口中不能使用 “static{}” 语句块，但编译器仍然会为接口生成 “<clinit>()” 类构造器，用于初始化接口中所定义的成员变量。

当一个类在初始化时，要求其父类全部都已经初始化过了，但是一个接口在初始化时，并不要求其父接口全部都完成了初始化，只有在真正使用到父接口的时候（如引用接口中定义的常量）才会初始化。

类加载的过程

类加载的全过程也就是加载、验证、准备、解析和初始化这 5 个阶段所执行的具体动作。

加载

“加载”是“类加载”过程的一个阶段，在加载阶段，虚拟机需要完成以下 3 件事情：

• 通过一个类的全限定名来获取定义此类的二进制字节流
• 将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构
• 在内存中生成一个代表这个类的 java.lang.Class 对象，作为方法区这个类的各种数据的访问入口

加载阶段完成后，虚拟机外部的二进制字节流就按照虚拟机所需的格式存储在方法区之中，方法区中的数据存储格式由虚拟机实现自行定义，虚拟机规范未规定此区域的具体数据结构。然后在内存中实例化一个 java.lang.Class 类的对象（并没有明确规定是在 Java 堆中，对于 HotSpot 虚拟机而言，Class 对象比较特殊，它虽然是对象，但是存放在方法区里面），这个对象将作为程序访问方法区中的这些类型数据的外部接口。

加载阶段与连接阶段的部分内容是交叉进行的，如一部分字节码文件格式验证动作。

验证

验证是连接阶段的第一步，这一阶段的目的是为了确保 Class 文件的字节流中包含的信息符合当前虚拟机的要求，并且不会危害虚拟机自身的安全。

从整体上看，验证阶段大致上会完成下面 4 个阶段的校验动作：

文件格式验证

第一阶段要验证字节流是否符合 Class 文件格式的规范，保证输入的字节流能正确地解析并存储于方法区之内，并且能被当前版本的虚拟机处理。

该阶段的验证是基于二进制字节流进行的，只有通过了这个阶段的验证后，字节流才会进入内存的方法区中进行存储。

元数据验证

第二阶段是对字节码描述的信息进行语义分析，对类的元数据信息进行语义校验，以保证其描述的信息符合 Java 语言规范的要求。

字节码验证

第三阶段是整个验证过程中最复杂的一个阶段，主要目的是通过数据流和控制流分析，确定程序语义是合法的、符合逻辑的。

如果一个类方法体的字节码没有通过字节码验证，那肯定是有问题的；但如果一个方法体通过了字节码验证，也不能说明其一定就是安全的。即使字节码验证之中进行了大量的检查，也不能保证这一点。即通过程序去校验程序逻辑是无法做到绝对准确的——不能通过程序准确地检查出程序是否能在有限的时间之内结束运行。

符号引用验证

最后一个阶段的校验发生在虚拟机将符号引用转化为直接引用的时候，这个转化动作将在连接的第三阶段——解析阶段中发生。符号引用验证可以看做是对类自身以外（常量池中的各种符号引用）的信息进行匹配性校验。

符号引用验证的目的是确保解析动作能正常执行。

对于虚拟机的类加载机制来说，验证阶段是一个非常重要的、但不是一定必要的阶段。

准备

准备阶段是正式为类变量分配内存并设置类变量初始值的阶段，这些变量所使用的内存都将在方法区中进行分配。

这时候进行内存分配的仅包括类变量（被 static 修饰的变量），而不包括实例变量，实例变量将会在对象实例化时随着对象一起分配在 Java 堆中。

public static int value = 123;

上述的 value 变量在准备阶段过后的初始值为 0 而不是 123，因为这时候尚未开始执行任何 Java 方法，而把 value 赋值为 123 的 putstatic 指令是程序被编译后，存放于类构造器 <clinit>() 方法之中，所以把 value 赋值为 123 的动作将在初始化阶段才会执行。

如果类字段的字段属性表中存在 ConstantValue 属性，那在准备阶段变量 value 就会被初始化为 ConstantValue 属性所指定的值，如：

public static final int value = 123;

编译时 Javac 将会为 value 生成 ConstantValue 属性，在准备阶段虚拟机就会根据 ConstantValue 的设置将 value 赋值为 123。

解析

解析阶段是虚拟机将常量池内的符号引用替换为直接引用的过程。

• 符号引用：符号引用以一组符号来描述所引用的目标，符号可以是任何形式的字面量，只要使用时能无歧义地定位到目标即可。
• 直接引用：直接引用可以是直接指向目标的指针、相对偏移量或是一个能间接定位到目标的句柄。

解析动作主要针对以下 7 类符号引用进行：

• 类或接口的解析
• 字段解析
• 类方法解析
• 接口方法解析
• 方法类型解析
• 方法句柄解析
• 调用点限定符解析

初始化

类初始化阶段是类加载过程的最后一步，前面的类加载过程中，除了在加载阶段用户应用程序可以通过自定义类加载器参与之外，其余动作完全由虚拟机主导和控制。到了初始化阶段，才真正开始执行类中定义的 Java 程序代码（或者说是字节码）。

初始化阶段是执行类构造器 <clinit>() 方法的过程，在这执行过程中一些可能会影响程序运行行为的特点和细节：

• <clinit>() 方法是由编译器自动收集类中所有类变量的赋值动作和静态语句块（static{} 块）中的语句合并产生的，编译器收集的顺序是由语句在源文件中出现的顺序所决定的，静态语句块中只能访问到定义在静态语句块之前的变量，定义在它之后的变量，在前面的静态语句块可以赋值，但是不能访问。
• <clinit>() 方法与类的构造函数（或者说实例构造器 <init>() 方法）不同，它不需要显式地调用父类构造器，虚拟机会保证在子类的 <clinit>() 方法执行之前，父类的 <clinit>() 方法已经执行完毕。因此在虚拟机中第一个被执行的 <clinit>() 方法的类肯定是 java.lang.Object。
• 由于父类的 <clinit>() 方法先执行，也就意味着父类中定义的静态语句块要优先于子类的变量赋值操作。
• <clinit>() 方法对于类或接口来说并不是必需的，如果一个类中没有静态语句块，也没有对变量的赋值操作，那么编译器可以不为这个类生成 <clinit>() 方法。
• 接口中不能使用静态语句块，但仍然有变量初始化的赋值操作，因此接口与类一样都会生成 <clinit>() 方法。但接口与类不同的是，执行接口的 <clinit>() 方法不需要先执行父接口的 <clinit>() 方法。只有当父接口中定义的变量使用时，父接口才会初始化。另外，接口的实现类在初始化时也一样不会执行接口的 <clinit>() 方法。
• 虚拟机会保证一个类的 <clinit>() 方法在多线程环境中被正确地加锁、同步，如果多个线程同时去初始化一个类，那么只会有一个线程去执行这个类的 <clinit>() 方法，其他线程都需要阻塞等待，直到活动线程执行 <clinit>() 方法完毕。如果在一个类的 <clinit>() 方法中有耗时很长的操作，就可能造成多个进程阻塞，在实际应用中这种阻塞往往是很隐蔽的。

类加载器

虚拟机设计团队把类加载器阶段中的“通过一个类的全限定名来获取描述此类的二进制字节流”这个动作放到 Java 虚拟机外部去实现，以便让应用程序自己决定如何去获取所需要的类。实现这个动作的代码模块称为“类加载器”。

类与类加载器

对于任意一个类，都需要由加载它的类加载器和这个类本身一同确立其在 Java 虚拟机中的唯一性，每一个类加载器，都拥有一个独立的类名称空间。

双亲委派模型

从 Java 虚拟机的角度来讲，只存在两种不同的类加载器：

• 启动类加载器，这个类加载器使用 C++ 语言实现，是虚拟机自身的一部分
• 所有其他的类加载器，这些类加载器都由 Java 语言实现，独立于虚拟机外部，并且全部都继承自抽象类 java.lang.ClassLoader

类加载器还可以划分得更细致一些，绝大部分 Java 程序都会使用到一下 3 种系统提供的类加载器：

• 启动类加载器（Bootstrap ClassLoader）：这个类加载器负责将存放在 <JAVA_HOME>\lib 目录中的，或者被 -Xbootclasspath 参数所指定的路径中的，并且是虚拟机识别的类库加载到虚拟机内存中。启动类加载器无法被 Java 程序直接引用，用户在编写自定义类加载器时，如果需要把加载请求委派给引导类加载器，那直接使用 null 代替即可。
• 扩展类加载器（Extension ClassLoader）：这个加载器由 sun.misc.Launcher$ExtClassLoader 实现，它负责加载 <JAVA_HOME>\lib\ext 目录中的，或者被 java.ext.dirs 系统变量所指定的路径中的所有类库，开发者可以直接使用扩展类加载器。
• 应用程序类加载器（Application ClassLoader）：这个类加载器由 sun.misc.Launcher$AppClassLoader 实现。由于这个类加载器是 ClassLoader 中的 getSystemClassLoader() 方法的返回值，所以一般也称它为系统类加载器。它负责加载用户类路径（ClassPath）上所指定的类库，开发者可以直接使用这个类加载器，如果应用程序中没有自定义过自己的类加载器，一般情况下这个就是程序中默认的类加载器。

我们的应用程序都是由这 3 种类加载器互相配合进行加载的，如果有必要，还可以加入自己定义的类加载器。

上图中展示的类加载器之间的这种层次关系，称为类加载器的双亲委派模型。

双亲委派模型的工作过程是：如果一个类加载器收到了类加载器的请求，它首先不会自己去尝试加载这个类，而是把这个请求委派给父类加载器去完成，每一个层次的类加载器都是如此，因此所有的加载请求最终都应该传送到顶层的启动类加载器中，只有当父加载器反馈自己无法完成这个加载请求（它的搜索范围中没有找到所需的类）时，子加载器才会尝试自己去加载。

End.这一篇由于篇幅过大，故手稿就不丢出来了。还是一些概念，类加载是经常会被面试问到的知识点，可见其重要性了。该啃还是要啃的，就点醋……

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

无关性的基石

实现语言无关性的基础是虚拟机和字节码存储格式。Java 虚拟机不和包括 Java 在内的任何语言绑定，它只与“Class 文件”这种特定的二进制文件格式所关联，Class 文件中包含了 Java 虚拟机指令集和符号表以及若干其他辅助信息。

基于安全方面的考虑，Java 虚拟机规范要求在 Class 文件中使用许多强制性的语法和结构化约束，但任一门功能性语言都可以表示为一个能被 Java 虚拟机所接受的有效的 Class 文件。

Java 语言的各种变量、关键字和运算符号的语义最终都是由多条字节码命令组合而成的。

Class 类文件的结构

Class 文件是一组以 8 位字节为基础单位的二进制流，各个数据项目严格按照顺序紧凑地排列在 Class 文件之中，中间没有添加任何分隔符，这使得整个 Class 文件中存储的内容几乎全是程序运行的必要数据，没有空隙存在。

根据 Java 虚拟机规范的规定，Class 文件格式采用一种类似于 C 语言结构体的伪结构来存储数据，这种伪结构中只有两种数据类型：无符号数和表。

• 无符号数：属于基本的数据类型，以 u1、u2、u4、u8 来分别代表 1 个字节、2 个字节、4 个字节和 8 个字节的无符号数，无符号数可以用来描述数字、索引引用、数量值或者按照 UTF-8 编码构成字符串值。
• 表：是由多个无符号数或者其他表作为数据项构成的复合数据类型，所有表都习惯性地以“_info”结尾。表用于描述有层次关系的复合结构的数据，整个 Class 文件本质上就是一张表。

（这里有关的详细介绍还是请看《深入理解 Java 虚拟机》中的第六章节）

魔数与 Class 文件的版本

每个 Class 文件的头 4 个字节称为魔数，它的唯一作用是 确定这个文件是否为一个能被虚拟机接受的 Class 文件。

Class 文件的魔数的获得很有“浪漫气息”，值为：0xCAFEBABE（咖啡宝贝……）

紧接着魔数的 4 个字节存储的是 Class 文件的版本号：第 5 和第 6 个字节是次版本号，第 7 和第 8 个字节是主版本号。

常量池

紧接着主次版本号之后的是常量池入口，常量池可以理解为 Class 文件之中的资源仓库，它是 Class 文件结构中与其他项目关联最多的数据类型，也是占用 Class 文件空间最大的数据项目之一，同时它还是在 Class 文件中第一个出现的表类型数据项目。

由于常量池中常量的数量是不固定的，所以在常量池的入口需要放置一项 u2 类型的数据，代表常量池容量计数值。与 Java 中语言习惯不一样的是，这个容量计数是从 1 开始而不是 0。

在 Class 文件格式规范制定之时，设计者将第 0 项常量空出来是为了满足后面某些指向常量池的索引值的数据在特定情况下需要表达“不引用任何一个常量池项目”的含义，这种情况就可以把索引值置为 0 来表示。

常量池主要存放两大类常量：字面量和符号引用。

字面量比较接近于 Java 语言层面的常量概念，比如文本字符串、声明为 final 的常量值等。

而符号引用则属于编译原理方面的概念，包括了下面三类常量：

• 类和接口的全限定名
• 字段的名称和描述符
• 方法的名称和描述符

在 Class 文件中不会保存各个方法、字段的最终内存布局信息，因此这些字段、方法的符号引用不经过运行期转换的话无法得到真正的内存入口地址，也就无法直接被虚拟机使用。

当虚拟机运行时，需要从常量池获得对应的符号引用，再在类创建时或运行时解析、翻译到具体的内存地址之中。

访问标志

在常量池结束之后，紧接着的两个字节代表访问标志，这个标志用于识别一些类或者接口层次的访问信息，包括：

• 这个 Class 是类还是接口
• 是否定义为 public 类型
• 是否定义为 abstract 类型
• 如果是类的话，是否被声明为 final
• …..

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

类索引和父类索引都是一个 u2 类型的数据，而接口索引集合是一组 u2 类型的数据的集合，Class 文件中由这三项数据来确定这个类的继承关系。

类索引用于确定这个类的全限定名，父类索引用于确定这个类的父类的全限定名。

由于 Java 语言不允许多重继承，所以父类索引只有一个，除了 java.lang.Object 之外，所有的 Java 类都有父类，因此除了 java.lang.Object 外，所有 Java 类的父类索引都不为 0。

接口索引集合就用来描述这个类实现了哪些接口，这些被实现的接口将按 implements 语句（如果这个类本身是一个接口，则应当是 extends 语句）后的接口顺序从左到右排列在接口索引集合中。

字段表集合

字段表用于描述接口或者类中声明的变量。

字段包括类级变量以及实例级变量，但不包括在方法内部声明的局部变量。

字段表集合中不会列出从超类或者父类接口中继承而来的字段，但有可能列出原本 Java 代码之中不存在的字段，譬如在内部类中为了保持对外部类的访问性，会自动添加指向外部类实例的字段。

另外，在 Java 语言中字段是无法重载的，两个字段的数据类型、修饰符不管是否相同，都必须使用不一样的名称，但是对于字节码来讲，如果两个字段的描述符不一致，那字段重名就是合法的。

方法表集合

方法表的结构如同字段表一样，依次包括了访问标志、名称索引、描述符索引、属性表集合几项。

方法里的 Java 代码，经过编译器编译成字节码指令后，存放在方法属性表集合中一个名为“Code”的属性里面。

与字段表集合相对应的，如果父类方法在子类中没有被重写，方法表集合中就不会出现来自父类的方法信息。但同样的，有可能会出现由编译器自动添加的方法，最典型的便是类的构造器“<clinit>”方法和实例构造器“<init>”方法。

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

属性表集合

在 Class 文件、字段表、方法表都可以携带自己的属性表集合，以用于描述某些场景专有的信息。

Code 属性

Code 属性是 Class 文件中最重要的一个属性，如果把一个 Java 程序中的信息分为代码和元数据两部分，那么在整个 Class 文件中，Code 属性用于描述代码，所有的其他数据项目都用于描述元数据。

在实例方法的局部变量表中至少会存在一个指向当前对象实例的局部变量，局部变量表中也会预留出第一个 Slot 位来存放对象实例的引用，方法参数值从 1 开始计算。

ConstantValue 属性

ConstantValue 属性的作用是通知虚拟机自动为静态变量赋值。只有被 static 关键字修饰的变量（类变量）才可以使用这项属性。

对于非 static 类型的变量（也就是实例变量）的赋值是在实例构造器 <init> 方法中进行的；而对于类变量，则有两种方式可以选择：在类构造器 <clinit 方法中或者使用 ConstantValue 属性。

字节码指令简介

Java 虚拟机的指令由一个字节长度的、代表着某种特定操作含义的数字（称为操作码）以及跟随其后的零至多个代表此操作所需参数（称为操作数）而构成。

字节码与数据类型

对于大部分与数据类型相关的字节码指令，它们的操作码助记符中都有特殊的字符来表明专门为哪种数据类型服务：i 代表对 int 类型的数据操作，l 代表 long，s 代表 short，b 代表 byte，c 代表 char，f 代表 float，d 代表 double，a 代表 reference。

大部分的指令都没有支持整数类型 byte、char 和 short，甚至没有任何指令支持 boolean 类型。编译器会在编译期或运行期将 byte 和 short 类型的数据带符号扩展为相应的 int 类型数据，将 boolean 和 char 类型数据零位扩展为相应的 int 类型数据。与之类似，在处理 boolean、byte、short 和 char 类型的数据时，也会转换为使用对应的 int 类型的字节码指令来处理。因此，大多数对于 boolean、byte、short 和 char 类型数据的操作，实际上都是使用相应的 int 类型作为运算类型。

加载和存储指令

加载和存储指令用于将数据在栈帧中的局部变量表和操作数栈之间来回传输，这类指令包括如下内容：

• 将一个局部变量加载到操作栈
• 将一个数值从操作数栈存储到局部变量表
• 将一个变量加载到操作数栈
• 扩充局部变量表的访问索引的指令

运算指令

运算或算术指令用于对两个操作数栈上的值进行某种特定运算，并把结果重新存入到操作栈顶。

大体上算术指令可以分为两种：对整型数据进行运算的指令与对浮点型数据进行运算的指令。

Java 虚拟机要求在进行浮点数运算时，所有的运算结果都必须舍入到适当的精度，非精确的结果必须舍入为可被表示的最接近的精确值，如果有两种可表示的形式与该值一样接近，将优先选择最低有效位为零的。这种舍入模式称为向最接近数舍入模式。

在把浮点数转换为整数时，Java 虚拟机使用向零舍入模式，这种模式的舍入结果会导致数字被截断，所有小数部分的有效字节都会被丢弃掉。向零舍入模式将在目标数值类型中选择一个最接近但是不大于原值的数字来作为最精确的舍入结果。

End. 这一章节概念的东西比较多，讲了 Class 文件中的种种。

Java 与 C++ 之间有一堵由内存动态分配和垃圾收集技术所围成的“高墙”，墙外面的人想进去，墙里面的人却想出来。

对象死活

垃圾收集器在对堆进行回收前，第一件事就是要确认这些对象之中哪些还“存活”着，哪些已经“死去”（即不可能再被任何途径使用的对象）

引用计数法

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加 1；当引用失效时，计数器值就减 1；任何时刻计数器为 0 的对象就是不可能再被使用的。这就是引用计数法。

但是，主流的 Java 虚拟机里面没有选用引用计数算法来管理内存，其中最主要的原因是它很难解决对象之间相互循环引用的问题。

可达性分析算法

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

上图所示，对象 object 5、object 6、object 7 虽然互相有关联，但是它们到 GC Roots 是不可达的，所以它们将会判定为是可回收的对象。

在 Java 语言中，可作为 GC Roots 的对象包括下面几种：

• 虚拟机栈（栈帧中的本地变量表）中引用的对象。
• 方法区中类静态属性引用的对象。
• 方法区中常量引用的对象。
• 本地方法栈中 JNI（即一般说的 Native 方法）引用的对象。

引用

在 JDK 1.2 以前，Java 中的引用的定义很传统：如果 reference 类型的数据中存储的数值代表的是另外一块内存的起始地址，就称这块内存代表着一个引用。

在 JDK 1.2 之后，Java 对引用的概念进行了扩充，将引用分为强引用、软引用、弱引用、虚引用 4 种，这 4 种引用强度依次逐渐减弱。

• 强引用就是指在程序代码之中普遍存在的，类似“Object obj = new Object()”这类的引用，只要强引用还存在，垃圾收集器永远不会回收掉被引用的对象。
• 软引用是用来描述一些 还有用但并非必需的对象。对于软引用关联着的对象，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中 进行第二次回收。如果这次回收还没有足够的内存，才会抛出内存溢出异常。在 JDK 1.2 之后，提供了 SoftReference 类来实现软引用。
• 弱引用也是用来描述非必需对象的，但是它的强度比软引用更弱一些，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。在 JDK 1.2 之后，提供了 WeakReference 类来实现弱引用。
• 虚引用也称为幽灵引用或者幻影引用，它是最弱的一种引用关系。一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。在 JDK 1.2 之后，提供了 PhantomReference 类来实现虚引用。

生存 Or 死亡

即使在可达性分析算法中不可达的对象，也并非是“非死不可”的，这时候它们暂时处于“缓刑”阶段，要真正宣告一个对象死亡，至少要经历两次标记过程：

• 如果对象在进行可达性分析后发现没有与 GC Roots 相连接的引用链，那它将会被第一次标记并且进行一次筛选，筛选的条件是此对象是否有必要执行 finalize() 方法。当对象没有覆盖 finalize() 方法，或者 finalize() 方法已经被虚拟机调用过，虚拟机将这两种情况都视为“没有必要执行”。
• 如果这个对象被判定为有必要执行 finalize() 方法，那这个对象将会放置在一个叫做 F-Queue 的队列之中，并在稍后由一个由虚拟机自动建立的、低优先级的 Finalize 线程去执行它。

finalize() 方法是对象逃脱死亡命运的最后一次机会，GC 将会对 F-Queue 中的对象进行第二次小规模的标记，对象只要重新与引用链上的任何一个对象建立关联才能拯救自己。

注意：任何一个对象的 finalize() 方法都只会被系统自动调用一次。

回收方法区

永久代的垃圾收集主要回收两部分内容：废弃常量和无用的类。

类需要同时满足下面 3 个条件才能算是“无用的类”：

• 该类所有的实例都已经被回收，也就是 Java 堆中不存在该类的任何实例。
• 加载该类的 ClassLoader 已经被回收。
• 该类对应的 java.lang.Class 对象没有在任何地方被引用，无法在任何地方通过反射访问该类的方法。

垃圾收集算法

标记-清除算法

算法分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

它的不足有两个：一个是效率问题，标记和清除两个过程的效率都不高；另一个是空间问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

复制算法

为了解决效率问题，一种称为“复制”的收集算法出现了，它将可用的内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。

标记-整理算法

复制收集算法在对象存活率较高时就要进行较多的复制操作，效率将会变低。

根据老年代的特点，有人提出了这种算法，标记过程还是一样，后续则让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

HotSpot 的算法实现

枚举根节点

可达性分析从 GC Roots 节点找引用链这个操作，如果逐个检查这里面的引用必然会消耗很多时间，且此分析工作必须在一个能确保一致性的快照中进行，即不可以出现分析过程中对象引用关系还在不断变化的情况。所以 GC 进行时必须停顿所有 Java 执行线程。

在 HotSpot 的实现中使用一组称为 OopMap 的数据结构来得知哪些地方存放着对象引用。

安全点

HotSpot 没有为每条指令都生成 OopMap,只是在“特定的位置”记录了这些信息，这些位置称为安全点，即程序执行时并非在所有地方都能停顿下来开始 GC，只有在到达安全点时才能暂停。

安全区域

若是程序没有分配 CPU 时间，这时候线程就无法响应 JVM 的中断请求。如线程处于 Sleep 状态或者 Blocked 状态。这种情况下就需要安全区域来解决。

垃圾收集器

Serial 收集器

Serial 收集器是最基本、发展历史最悠久的收集器。它是一个单线程的收集器，进行垃圾收集时必须暂停其他所有的工作线程，直到它收集结束。

ParNew 收集器

ParNew 收集器其实就是 Serial 收集器的多线程版本。

Parallel Scavenge 收集器

Parallel Scavenge 收集器的目的是达到一个可控制的吞吐量。吞吐量就是 CPU 用于运行用户代码的时间与 CPU 总消耗时间的比值，即吞吐量 = 运行用户代码时间 /（运行用户代码时间 + 垃圾收集时间）。

Serial Old 收集器

Serial Old 是 Serial 收集器的老年代版本，同样是一个单线程收集器。

Parallel Old 收集器

Parallel Old 是 Parallel Scavenge 收集器的老年代版本，使用多线程和“标记-整理”算法。

CMS 收集器

CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器。

CMS 收集器是基于“标记-清除”算法实现的，它的运作过程相对于前面几种收集器来说更复杂一些，整个过程分为 4 个步骤：

• 初始标记（CMS initial mark）
• 并发标记（CMS concurrent mark）
• 重新标记（CMS remark）
• 并发清除（CMS concurrent sweep）

CMS 有以下 3 个明显的缺点：

• CMS 收集器对 CPU 资源非常敏感。
• CMS 收集器无法处理浮动垃圾，可能出现“Concurrent Mode Failure”失败而导致另一次 Full GC 的产生。
• CMS 是基于“标记-清除”算法实现的，收集结束时会产生大量空间碎片。

G1 收集器

G1 是一款面向服务端应用的垃圾收集器。与其他 GC 收集器相比，特点如下：

• 并行与并发
• 分代收集
• 空间整合
• 可预测的停顿

G1 收集器的运作大致可划分为以下几个步骤：

• 初始标记（Initial Marking）
• 并发标记（Concurrent Marking）
• 最终标记（Final Marking）
• 筛选回收（Live Data Counting and Evacuation）

内存分配与回收策略

Java 技术体系中所提倡的自动内存管理最终可以归结为自动化地解决两个问题：给对象分配内存以及回收分配给对象的内存。

对象优先在 Eden 分配

大多数情况下，对象在新生代 Eden 区中分配。当 Eden 区没有足够空间进行分配时，虚拟机将发起一次 Minor GC。

大对象直接进入老年代

所谓的大对象是指，需要大量连续内存空间的 Java 对象，最典型的就是很长的字符串以及数组。

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

虚拟机给每个对象定义了一个对象年龄计数器。如果对象在 Eden 出生并经过第一次 Minor GC 后仍然存活，并且能被 Survivor 容纳的话，将被移动到 Survivor 空间中，并且对象年龄设为 1。对象在 Survivor 区中每“熬过”一次 Minor GC，年龄就增加 1 岁，当它的年龄增加到一定程序（默认为 15 岁），就将会被晋升到老年代中。

动态对象年龄判定

如果在 Survivor 空间中相同年龄所有对象大小的总和大于 Survivor 空间的一半，年龄大于或等于该年龄的对象就可以直接进入到老年代。

空间分配担保

新生代使用复制收集算法，为了内存利用率之使用其中一个 Survivor 空间来作为轮换备份，因此当出现大量对象在 Minor GC 后仍然存活的情况，就需要老年代进行分配担保，把 Survivor 无法容纳的对象直接进入老年代。

好困啊……2018-11-20 00:37:02

LeetCode 中有好几道题是求数字之和的，有 Sum 2、Sum 3 和 Sum 4 等。求和这种情况在我们实际开发中也是经常会遇到的，在这不妨拿出来我们把这归并到一起来说说。

无非就是数组中几个数字求和比较是否为目标值。且大多结果中是不能有重复的值。

大致我说下这个题意：

1
2
3
4
5
6
7
8
9
10
11
12

给定一个包含 m 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在 n 个元素，使得这 n 个元素相加的值与 target 相等？找出所有满足条件且不重复的组。

注意：
答案中不可以包含重复的组。

示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]， target = 0，n = 4

满足要求的四元组集合为：
[ [-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2] ]

两数之和好办，循环遍历去除重复结果。三数之和也类似。

那要是许多许多数之和呢，遍历就不好使了，那就要采用 BFS 或者 DFS。

答案中不可以包含重复的组从这我们知道，首先，我们需要将数组排个序。

由大化小的思想，我们可以采用 DFS + 回溯来解决这一系列问题。

苦恼不已，别挠头了，我们还是需要好好爱护自己的青青草地！

旨在锻炼逻辑思维，思想对了很重要，请上代码：

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

/**
 * 
 * @param nums
 *            排序后目标数组
 * @param target
 *            累加目标数值
 * @param k
 *            个数
 * @param index
 *            起始下标
 * @return
 */
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {

    ArrayList<List<Integer>> res = new ArrayList<>();

    if (index >= len)
        return res;
    if (k == 2) { // 两数取和
        int i = index, j = len - 1;
        while (i < j) {
            // 满足条件塞入集合
            if (target - nums[i] == nums[j]) {
                List<Integer> temp = new ArrayList<>();
                temp.add(nums[i]);
                temp.add(nums[j]);
                res.add(temp);
                while (i < j && nums[i] == nums[i + 1]) // 跳过重复数值
                    i++;
                while (i < j && nums[j] == nums[j - 1]) // 跳过重复数值
                    j--;
                i++;
                j--;
            } else if (target - nums[i] > nums[j])
                i++;
            else
                j--;
        }
    } else {
        for (int i = index; i < len - k + 1; i++) {
            // 调用递归 DFS
            ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
            // 若是有值返回则将该数塞入，无则不进行任何操作
            if (temp != null && temp.size() > 0) {
                for (List<Integer> list : temp) {
                    list.add(nums[i]); // 将满足条件数值塞入
                }
                res.addAll(temp);
            }
            while (i < len - 1 && nums[i] == nums[i + 1]) // 跳过重复数值
                i++;
        }
    }
    return res;
}

注意：这里 len 定义的是个全局变量，初始值为 0

若 n 为 4，那程序应该是这样的：

1
2
3
4
5
6
7

int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
        len = nums.length;
        Arrays.sort(nums); // 先排序
        return kSum(nums, target, 4, 0); // 递归调用

    }

这下只要满足 n > 1 条件的都可以套用这个方法了。

要注意栈的深度。时间换空间。

回文数想必大家都不陌生吧。什么？你居然不知道何谓“回文数”？

回文数：“回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数（palindrome number）。

OK，来看题：

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

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
  
示例 1:
输入: 121 输出: true
 
示例 2:
输入: -121 输出: false 
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10 输出: false  
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:
你能不将整数转为字符串来解决这个问题吗？

这道题看到第一眼就能想到字符串反转可以解决。

当然，StringBuilder 就可以实现，如下：

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

/**
 * 通过字符串反转判断
 * 
 * @param x
 * @return
 */
public static boolean isPalindrome(int x) {

    if (x == 0)
        return true;

    String s = String.valueOf(x);

    StringBuilder sb1 = new StringBuilder(s);
    sb1.reverse();

    return sb1.toString().equals(s) ? true : false;

}

代码很简短，功能也能实现。但是这并不是我们所追求的！来看进阶:你能不将整数转为字符串来解决这个问题吗？

不转成字符串来解决这个问题，挠一挠头。当然，这肯定难不倒聪明才智的你！

不就是反着来吗，问题不大，请看：

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

public static boolean isPalindrome1(int x) {

        if (x == 0 || (x > 0 && x < 10))
            return true;
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;

        int result = 0, num = x;

        while (num != 0) {
            int i = num % 10;
            result = result * 10 + i;
            num /= 10;
            System.out.println("num :" + num + " result :" + result);
        }

        return result == x ? true : false;

    }

取余，上个余数乘 10 再加上这个余数，数字每次除 10 取整。

1
2

if (x == 0 || (x > 0 && x < 10))
            return true;

当 x == 0 或者 x > 0 && x < 10 时，该数肯定是个回文数，这不用多说。

1
2

if (x < 0 || (x % 10 == 0 && x != 0))
            return false;

当 x < 0 时，该数肯定不是个回文数，这也不用多说。x % 10 == 0 && x != 0 这个条件的意思是 x 的末数是个 0，也就是它是个 10 的倍数，同时 x 不是 0。这也可以想象，满足这个条件的也肯定不是个回文数，因为 0 开头的只能是 0。

乍一看，这么写稳稳的，堪称完美。满意的端起键盘旁的红枣枸杞水，美滋滋嘬了一口。

其实上述代码还可以优化，运行时间能减少一半。滚烫的红枣枸杞水烫着了舌头，忙用口水润润。

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

/**
 * 反转一半数字进行比较 比上面方法速度快一倍
 * 
 * @param x
 * @return
 */
public static boolean isPalindrome2(int x) {
    // 特殊情况：
    // 如上所述，当 x < 0 时，x 不是回文数。
    // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
    // 则其第一位数字也应该是 0
    // 只有 0 满足这一属性
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }
    // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
    // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
    // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
    return x == revertedNumber || x == revertedNumber / 10;
}

妙哉妙哉，满意地捋着下巴小胡子，眯眼色道。

Java 与 C++ 之间有一堵由内存动态分配和垃圾收集技术所围成的“高墙”，墙外面的人想进去，墙里面的人却想出来。

运行时数据区域

Java 虚拟机在执行 Java 程序的过程中会把它所管理的内存划分为若干个不同的数据区域。根据《Java 虚拟机规范（Java SE 7 版）》的规定，包括如下几个运行时数据区域，如图：

程序计数器

程序计数器是一块较小的内存空间，它可以看作是当前线程所执行的字节码的行号指示器。

由于 Java 虚拟机的多线程是通过 线程轮流切换并分配处理器执行时间的方式来实现的，在任何一个确定的时刻，一个处理器（对于多核处理器来说是一个内核）都只会执行一条线程中的指令。因此，为了线程切换后能恢复到正确的执行位置，每条线程都需要有一个独立的程序计数器，各条线程之间计数器互不影响，独立存储，这类内存区域称为“线程私有”的内存。

• 线程正在执行的是一个 Java 方法，这个计数器记录的是正在执行的虚拟机字节码指令的地址；
• 线程正在执行的是一个 Native 方法，这个计数器值则为空（Undefined）。

此内存区域是唯一一个在 Java 虚拟机规范中没有规定任何 OutOfMemoryError 情况的区域。

Java 虚拟机栈

与程序计数器一样它也是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是 Java 方法执行的内存模型：每个方法在执行的同时都会创建一个栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。

在 Java 虚拟机规范中，对这个区域规定了两种异常状况：

• 如果线程请求的栈深度大于虚拟机所允许的深度，将抛出 StackOverflowError 异常；
• 如果虚拟机栈可以动态扩展，如果扩展时无法申请到足够的内存，就会抛出 OutOfMemoryError 异常。

本地方法栈

本地方法栈与虚拟机栈所发挥的作用是非常相似的，它们之间的区别不过是 虚拟机栈为虚拟机执行 Java 方法（也就是字节码）服务，而本地方法栈则为虚拟机使用到的 Native 方法服务。

Java 堆

Java 堆是被所有线程共享的一块内存区域，在虚拟机启动时创建。

此内存区域的唯一目的就是存放对象实例，几乎所有的对象实例都在这里分配内存。Java 虚拟机规范中的描述是：所有的对象实例以及数组都要在堆上分配。

但是随着 JIT 编译器的发展与逃逸分析技术逐渐成熟，栈上分配、标量替换优化技术将会导致一些微妙的变化发生，所有的对象都分配在堆上也渐渐变得不是那么“绝对”了。

Java 堆是垃圾收集器管理的主要区域，所以有时也称之为“GC 堆”。

• 内存回收角度看，它可以细分为新生代和老年代，细致一点可以分为 Eden 空间、From Survivor 空间、To Survivor 空间等。
• 内存分配角度看，它可能划分出多个线程私有的分配缓冲区。

方法区

方法区与 Java 堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。

Java 虚拟机规范对方法区的限制非常宽松，除了和 Java 堆一样不需要连续的内存和可以选择固定大小或者可扩展外，还可以选择不实现垃圾收集。

根据 Java 虚拟机规范的规定，当方法区无法满足内存分配需求时，将抛出 OutOfMemoryError 异常。

运行时常量池

运行时常量池是方法区的一部分。它相对于 Class 文件常量池的一个重要特征是 具备动态性，Java 语言并不要求常量一定只有编译期才能产生，也就是并非预置入 Class 文件中常量池的内容才能进入方法区运行时常量池，运行期间也可能将新的常量放入池中，这种特性被开发人员利用得比较多的便是 String 类的 intern() 方法。

当常量池无法再申请到内存时会抛出 OutOfMemoryError 异常。

直接内存

直接内存并不是虚拟机运行时数据区的一部分，也不是 Java 虚拟机规范中定义的内存区域。但是这部分内存也被频繁地使用，而且也可能导致 OutOfMemoryError 异常出现。

在 JDK 1.4 中新加入了 NIO（New Input/Output）类，引入了一种基于通道（Channel）与缓冲区（Buffer）的 I/O 方式，它可以使用 Native 函数库 直接分配堆外内存，然后通过一个存储在 Java 堆中的 DirectByteBuffer 对象作为这块内存的引用进行操作。这样能在一些场景中显著提高性能，因为避免了在 Java 堆和 Native 堆中来回复制数据。

HotSpot 虚拟机对象探秘

以常用的虚拟机 HotSpot 和常用的内存区域 Java 堆为例，博主也在此简短总结下 HotSpot 虚拟机在 Java 堆中对象分配、布局和访问的全过程。

对象的创建

虚拟机遇到一条 new 指令时，首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用，并且检查这个符号引用代表的类是否已被加载、解析和初始化过。如果没有，那必须先执行相应的类加载过程。（类加载过程之后的博文会有相关总结）

在类加载检查通过后，接下来虚拟机将为新生对象分配内存。内存分配有两种方式：

• 假设 Java 堆中内存是绝对规整的，所有用过的内存都放在一边，空闲的内存放在另一边，中间放着一个指针作为分界点的指示器，那所分配内存就仅仅是把那个指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”。
• 如果 Java 堆中内存并不是规整的，已使用的内存和空闲的内存相互交错，那就没有办法简单地进行指针碰撞了，虚拟机就必须维护一个 列表，记录上哪些内存块是可用的，在分配的时候从列表中找到一块足够大的空间划分给对象实例，并更新列表上的记录，这种分配方式称为“空闲列表”。

选择哪种分配方式由 Java 堆是否规整决定，而 Java 堆是否规整又由所采用的垃圾收集器是否带有 压缩整理功能决定。

对象的内存布局

在 HotSpot 虚拟机中，对象在内存中存储的布局可以分为 3 块区域：对象头、实例数据和对齐填充。

对象头包括两部分信息：

• 第一部分用于存储对象自身的运行时数据，如哈希码、GC 分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳等；
• 另一部分是类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。

并不是所有的虚拟机实现都必须在对象数据上保留类型指针，也就是说查找对象的元数据信息并不一定要经过对象本身。

如果对象是一个 Java 数组，那在对象头中还必须有一块用于记录数组长度的数据，因为虚拟机可以通过普通 Java 对象的元数据信息确定 Java 对象的大小，但是从数组的元数据中却无法确定数组的大小。

实例数据部分是对象真正存储的有效信息，也是在程序代码中所定义的各种类型的字段内容。

对其填充并不是必然存在的，也没有特别的含义，它仅仅起着占位符的作用。

对象的访问定位

对象访问方式取决于虚拟机实现而定的，目前主流的访问方式有 使用句柄和 直接指针两种。

• 如果使用句柄访问的话，那么 Java 堆中将会划分出一块内存来作为句柄池，reference 中存储的就是对象的句柄地址，而句柄中包含了对象实例数据与类型数据各自的具体地址信息。
• 如果使用直接指针访问，那么 Java 堆对象的布局中就必须考虑如何放置访问类型数据的相关信息，而 reference 中存储的直接就是对象地址。

这两种对象访问方式各有优势。

使用句柄来访问的最大好处就是 reference 中存储的是稳定的句柄地址，在对象被移动时只会改变句柄中的实例数据指针，而 reference 本身不需要修改；

使用直接指针访问方式的最大好处就是速度更快，它节省了一次指针定位的时间开销。