在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（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 本身不需要修改；

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

潜意识还没养成的我在思考问题方面总会出点岔子，老是走一些弯路。虽说结果可能是一样的，过程却是复杂许多，这也是我为什么决定要好好刷一遍 leetcode 中的题目的原因。数学就在于简单之美，一些看似异常复杂的问题可以巧妙地通过分治从而完美解决，很能锻炼人的逻辑思维能力，这也是我想要的。

下面来看问题的描述：

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

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

问题看似很简单，查找字符串数组中每个元素的最长公共前缀。

确实简单，我这个莽夫的第一想法就是遍历暴力分析。两个循环能解决，问题是不大，但是很不优雅，看着就难受。

虽说“黑猫白猫，能抓老鼠的就是好猫”，但是两猫都能抓老鼠，那我当然还是喜欢高颜值猫了！

随后我就去官网找到了我要的答案：

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

/**
 * 官网解法
 * 
 * @param strs
 * @return
 */
public static String longestCommonPrefix1(String[] strs) {
    if (strs.length == 0)
        return "";
    String prefix = strs[0]; // 以第一个字符串为基准
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) { // 依次找到均满足的相同起始字符
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty())
                return "";
        }
    return prefix;
}

这一种是我觉得最好理解最满意的一种解法。

这里以第一个元素为基准值，挨个与其它元素进行比较。while 循环里面就是为了使基准值成为比较元素的起始字符串，故它不满足就每次截掉最后一位。若是全部截完了那就是无公共前缀了。

这完美体现了分而治之，将所有元素的比较变成了两个元素之间的比较，可以节省其运行时间同时也使得代码更好理解更加优雅。

学习了，牢记。

LeetCode 中有多道组合总和（Combination Sum）的题，这些题目都是比较经典的，面试很可能会问到。我这一想，还真是。今天就来简单总结下这一系列题目，总结很重要，还要时而回顾！

Combination Sum I

第一道题的描述如下：

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

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

注意点：

• candidates 中的数字可以无限制重复被选取。
• 解集不能包含重复的组合。

这时候头脑里很快就会产生一个思路：无限遍历该数组，直到其元素之和满足条件，然后塞入集合中。

这个想法没问题，不过在这过程中我们怎么才能满足解集不能包含重复的组合。这个条件呢？

对对对，那就是确定一个 index，我们要保证数组不往回找就是了。

解题代码如下：

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

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        recursive(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    /**
     * 
     * @param list
     *            总的输出 list
     * @param tempList
     *            存放的 list
     * @param nums
     *            数组
     * @param remain
     *            剩余值
     * @param index
     *            数组下标
     */
    private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int index) {

        if (remain < 0) // return 或者进行 add 操作后就开始执行弹出尾部元素 塞入下个元素
            return;
        else if (remain == 0)
            list.add(new ArrayList<>(tempList)); // 这里需要注意不能直接 list.add(tempList),最终 tempList 所指向的对象是空的,
                                                    // 所以需要 new 一个新对象，将值复制进去
        else {
            for (int i = index; i < nums.length; i++) {
                tempList.add(nums[i]); // 挨个塞入
                recursive(list, tempList, nums, remain - nums[i], i); // 由于元素可重复 所以是 i
                tempList.remove(tempList.size() - 1); // 挨个弹出
            }
        }
    }

我这注释什么的都有，理解起来不成问题吧。这里需要注意的就是两个点：list.add(new ArrayList<>(tempList)); 和 recursive(list, tempList, nums, remain - nums[i], i);。

这里先对数组进行排序可以使计算更快，当然你也可以不排序。

Combination Sum II

第二道对第一道稍微加工了一下，描述如下：

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

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

注意点：

• candidates 中的每个数字在每个组合中只能使用一次。
• 解集不能包含重复的组合。

是的，这里把条件改了，数组中的每个元素在每个组合中只能使用一次！

这就意味着每次递归操作时其下标都需要往后移一位了！

代码如下：

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

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        recursive(list, new ArrayList<>(), candidates, target, 0);
        return list;

    }

    /**
     * DFS 添加每个满足条件的集合
     * 
     * @param list
     *            最终返回集合
     * @param tempList
     *            每个满足条件的子集合
     * @param candidates
     *            数组
     * @param remain
     *            剩余值
     * @param index
     *            数组下标
     */
    private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] candidates, int remain, int index) {
        if (remain < 0)
            return;
        else if (remain == 0)
            list.add(new ArrayList<>(tempList));
        else {
            for (int i = index; i < candidates.length; i++) {
                if (i > index && candidates[i] == candidates[i - 1]) // 说明两个值相等且之前一个值已经返回
                    continue;
                tempList.add(candidates[i]);
                recursive(list, tempList, candidates, remain - candidates[i], i + 1); // 规定数组中每个数字在每个组合中只能使用一次
                tempList.remove(tempList.size() - 1);
            }
        }
    }

相比较上一题的代码，这次只是加了一个条件判断以及递归中元素下标加了一。

这里就要对数组先进行排序操作了，新增的条件判断也是为了优化代码执行速度。

Combination Sum III

再来看第三道变形，描述如下：

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

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

这次不给出数组了，而是规定了数组中元素的取值范围。

双手一摊，这还不是一样吗，不给我就自己造就是了！

注意点：

• 解集不能包含重复的组合。

解题代码如下：

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 List<List<Integer>> combinationSum3(int k, int n) {
        int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), nums, k, n, 0);
        return list;

    }

    /**
     * 
     * @param list
     *            最终返回的 list
     * @param tempList
     *            作为寻求满足条件的暂存 list
     * @param nums
     *            数组
     * @param reNum
     *            剩余的元素个数
     * @param reSum
     *            剩余的总和
     * @param index
     *            数组下标
     */
    private void dfs(List<List<Integer>> list, List<Integer> tempList, int[] nums, int reNum, int reSum, int index) {
        if (reNum < 0 || reSum < 0) // 两者有其一小于 0 就是不满足条件
            return;
        if (reNum == 0 && reSum == 0) // 两者都为 0 时满足条件，塞入
            list.add(new ArrayList<>(tempList));
        else if (reNum == 0 || reSum == 0) // 两者中有且只有一者等于 0 就不满足条件
            return;
        else {
            for (int i = index; i < nums.length; i++) {
                tempList.add(nums[i]);
                dfs(list, tempList, nums, reNum - 1, reSum - nums[i], i + 1); // 不能重复元素 所以 i + 1
                tempList.remove(tempList.size() - 1);
            }
        }
    }

真不愧为机智小少年……

Combination Sum IV

第四道变形就复杂了一些了，描述如下：

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

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

这里数组的元素可以重复，且组合的元素也能相同，但是顺序要不同。

一开始当然就是无脑循环了，然后满足条件就加上一，结果就是超时……

说明这么暴力不行的……

后来一想，无脑循环就相当于每一次都从头进行循环算了一遍，很多都是重复的计算。

对了，DP 浮现在了脑中，在那飘啊飘。

代码如下：

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

private int[] dp;

    /**
     * DP
     * 
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target);
    }

    private int helper(int[] nums, int target) {
        if (dp[target] != -1) {
            return dp[target]; // 若是之前的已经计算过了 直接返回
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) { // 所有组合的种数相加
                res += helper(nums, target - nums[i]);
            }
        }
        dp[target] = res; // 计算后赋值用于之后的数字使用
        return res;
    }

用空间换取时间的操作，DP + 递归稍微费点脑。

还有一种解法：

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

/**
     * DP
     * 
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int i = 1; i < comb.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    comb[i] += comb[i - nums[j]];
                }
            }
        }
        return comb[target];
    }

好了，组合总和系列（Combination Sum）的题目总结完了。记住了回溯。

使用 ssh 反向隧道穿透 NAT 访问内网主机

前言

由于公司经常会有项目需要去业主那边搭建服务器，基本不需要什么流量所以就准备用 4G 网卡搭建。而该网卡无固定公网 ip，只有内网 ip，我们目的就是为了可以远程操控以避免有时因业务需要往业主那边跑，要是地方比较远来回一趟也得花个把星期，不划算。所以就研究了下 ssh 隧道穿透来满足我们的需求。

场景

现在我们有三台机子：

• A：公司内网电脑（Win 10）
• B：公司内网服务器（Linux，固定外网 ip：58.247.33.44，ssh 开放端口：8862）
• C：业主那边 4G 网卡搭建的服务器（Linux，无固定外网 ip，ssh 开放端口：22）

操作前：A 可以访问 B，C 能上网也能访问 B，但是 B 不能访问 C，A 不能访问 C
我们需要满足：A 可以访问 C

当然，很多远程桌面软件可以满足我们这个需求，但是由于太不方便和不稳定，还是考虑 ssh。（安装 ssh 可见底文的附加安装指令）

配置

配置 B 服务器

• 修改服务器上的 sshd 设置

vim /etc/ssh/shhd_config 建议使用 vim，vim 比 vi 更强大（安装 vim 可见底文的附加安装指令）

• 把 GatewayPorts 打开(去掉前面的 # 号注释，没有就直接在底下添加)

GatewayPorts yes 打开允许映射端口

• 存盘后退出，并重新启动 sshd (不知如何操作文件的自行上网查阅)

service ssh restart 这个具体得看你 service 的实际名字（Ubuntu 下 service --status-all 可以查看所有服务状态）

配置 C 服务器

可以进行映射操作了

ssh -NfR 1234:localhost:22 user@58.247.33.44 -p8862

N 参数，表示只连接远程主机，不打开远程shell。

f 参数，表示后台运行。

R 参数接受三个值，分别是”远程主机端口:目标主机:目标主机端口”。

p 参数，表示指定 ssh 对外开放的端口号。

user 是 B 服务器的用户。

这条命令的意思，就是让 B 服务器监听它自己的 1234 端口，然后将所有数据经由 B 服务器转发到 C 服务器的 22 端口。这就被称为”远程端口绑定”。

这里每次连接需要输入 B 服务器的密码，不太方便，待会再详细介绍。

映射操作后我们可以发现在 B 服务器上已经开启了 1234 端口的监听，已经可以通过 1234 端口进行 ssh 连接到 C 服务器了。

密钥验证，直接登录

接回上面说的每次需要输入密码的问题，我们可以用 ssh 密钥来实现自动登录。

在 C 服务器上生成公钥和私钥

ssh-keygen （一直 enter）

ls ~ /.ssh/ 查看是否生成，显示如下

id_rsa id_rsa.pub known_hosts

ssh-copy-id user@58.247.33.44 复制到 B 服务器中

好了，这样就不需要每次都输入 B 服务器密码了。

autossh 实现自动重连

由于上述的 ssh 反向连接十分不稳定，可能随时断开，一旦断开就无法进行访问了。所以我们需要 autossh，它可以实现自动重连。（安装 autossh 可见底文的附加安装指令）

autossh -M 5678 -NR 1234:localhost:22 user@58.247.33.44 -p8862

M 参数，指定了 autossh 的监听端口，监听是否断开然后进行重连操作

autossh 本身就是后台执行，所以就省去了 f 参数。

到这里就很完美了，可是还不够。要是 C 服务器宕机重启了怎么办，autossh 又不会自动执行。

实现开机自启

这里以 Ubuntu 18.04 为例。

ls /lib/systemd/system 执行该指令我们可以看到许多启动脚本，我们需要操作的就是 rc.local.service

打开脚本内容，我们在最后面加上一段：

1
2
3

[Install]  
WantedBy=multi-user.target  
Alias=rc-local.service

保存退出。

由于 ubuntu-18.04 默认是没有 /etc/rc.local 这个文件的，需要自己创建。

1
2

sudo touch /etc/rc.local
chmod 755 /etc/rc.local

这里千万别忘记给 rc.local 文件设置可执行权限，不然没用。

在 rc.local 中你就可以编写脚本了。注意开头 #!/bin/bash 不可少

例如我的是：

1
2
3
4

#!/bin/bash
LOG_TIME=`date "+%Y-%m-%d %H:%M:%S"`
echo '123456' | sudo -S autossh -M 5678 -NR 1234:localhost:2223 user@58.247.33.44 -p8862
echo "autossh restart:"$LOG_TIME >>/usr/local/autossh.log

这里我是用 root 权限执行，123456 是 C 服务器的用户密码。 >> 表示追加，不覆盖。同时打印了执行的时间。

最后一步，前面我们说 systemd 默认读取 /etc/systemd/system 下的配置文件, 所以还需要在 /etc/systemd/system 目录下创建软链接。

ln -s /lib/systemd/system/rc.local.service /etc/systemd/system/

可以了，重启系统查看脚本是否执行，日志中是否有内容。

参考博文

笔者参考了如下博文并进行了整理实验：

• 使用ssh隧道穿透NAT访问内网主机(超干货)
• SSH反向连接及Autossh
• ubuntu-18.04 设置开机启动脚本
• ubuntu 18.04 配置 rc.local

附加安装

• 更新源列表

sudo apt-get update

• 安装 ssh

sudo apt-get install openssh-client 安装客户端 （反向隧道需要）

sudo apt-get install openssh-server 安装服务端

• 安装 vim

1
2

sudo apt-get remove vim-common
sudo apt-get install vim

Ubuntu 18.04 中 vi 方向键有点问题，vim 很好用。

• 安装 autossh

sudo apt-get install autossh

• 安装 net-tools

当发现输入 ifconfig 不可用时

sudo apt install net-tools 装之