拓扑排序的BFS与DFS实现

以Leetcode 210. 课程表 II 为例题大致讲解一下两种搜索算法的思路。

广度优先搜索,实际上就要结合入度表来进行拓扑排序,入度表需要遍历整张图来计算得到。

之后需要维护一个队列,队列中入度为0的节点,当这个节点出队的时候就要将这个点所指向的所有节点的入度都减1,如果某个指向的节点入度为0了,则将它加入队列中。

可以用计数器记录出队的节点数目,用来最终判断是不是可拓扑排序的,如果是可拓扑排序的,按照出队的顺序也可以构成拓扑序列。

DFS广度优先搜索来处理拓扑排序不是特别好理解。首先说说如何用DFS判断是否可以进行拓扑排序。如果有向图中存在环,则无法拓扑排序。关键是如何判定存在环,那么使用dfs需要维护节点的三种状态,一种是未访问,一种是正在访问,一种是访问结束。

如果访问结束的话,就可以将这个节点,加入到结果中,由于最先访问结束的节点肯定是最后的,所以要用一个栈的数据结构来维护拓扑排序序列。如果当前访问的节点存在某个邻接节点处于正在被访问的一个状态,那么就可以说明存在环。具体的实现过程可以用DFS函数的返回值来巧妙的构造不同情况的判别。

        public int[] findOrder(int numCourses, int[][] prerequisites) {
        //构建邻接表、状态数组( 0:未访问 1:正在访问 2:访问结束)和存储拓扑序列的栈
        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<> (numCourses);
        Deque <Integer> stack = new LinkedList<Integer> ();
        int [] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) hm.put(i, new ArrayList<Integer> ());
        for (int[] prerequsity : prerequisites) {
            int to = prerequsity[0];
            int from = prerequsity[1];
            hm.get(from).add(to);
        }

        //DFS过程,DFS返回值是false说明存在环,全部为true的话,结果都存在stack里面
        for(int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(hm, visited, stack, i)) return new int[0];
            }
        }
        //从栈中取出数据,为了省点空间直接塞到状态数据里面了
        int i = 0;
        while(stack.size() != 0){
            visited[i++] = stack.pollLast();
        }
        return visited;
    }

    public boolean dfs(HashMap<Integer, ArrayList<Integer>> hm, int [] visited, Deque<Integer> stack, int i) {
        //能进入这个函数的肯定是0状态(未访问)的节点,首先更新到1状态(正在访问)
        visited[i] = 1;
        for (int adj : hm.get(i)) {
            //邻接节点处于1状态则说明存在环
            if (visited[adj] == 1) return false;
            //邻接节点未访问,但是从该邻接节点开始的DFS搜索检测到环
            if (visited[adj] == 0 && !dfs(hm, visited, stack, adj)) return false;
            //邻接节点处于访问结束状态不处理
        }
        //顺利访问完成的结果入栈,更新结果状态,返回true
        stack.offerLast(i);
        visited[i] = 2;
        return true;
    }

Prim kruskal 最小生成树算法和并查集

prim算法的思路比较简单,是一种贪心策略,也有严格的数学证明,证明这种算法是正确的(反证和归纳)

思路:随机选一个点作为开始,每次选择权重最小的那条边和连接的节点加入最小生成树。

实现过程中需要可以利用优先队列这种数据结构来对动态添加的候选边进行临时存储以提高效率。

kruskal算法的思路也是贪心的,也有严格的数学证明。

思路:首先对所有的边按照权重进行排序,选择权重最小的那条边作为初始化的边集合。便利按照权重排序好的边,如果某条边的两个节点属于两个不同的联通分量,则将这条边加入最小生成树,并合并这两个连通分量。

具体的实现过程会用到并查集这种数据结构,也可以认为它是一颗二叉树,实际编码过程中可以用数组来存储这种并查集的结构,数组的值就代表父亲节点的索引。

并查集练习:Leetcode 990. 等式方程的可满足性

跟谁学 2020-0603 视频面试 java后台开发

解释变量的值传递和地址传递

static 修饰符有什么作用

jvm 堆栈结构有哪些,静态变量放在什么位置,虚拟机栈内部结构,基本数据类型变量值存放的具体位置

Hashmap底层数据结构、何时扩容,为什么用红黑树,数组长度为什么是2的幂次

Hashmap是线程安全的吗,成环的现象如何理解?ConcurrentHashmap的结构,JDK8中的改进是什么。

线程池有了解吗,线程池的参数都有哪些

解释一下BIO和NIO的区别,如何理解阻塞

AOP是什么解释一下

Spring中的对象生命周期是怎么样的

vim中如何撤销操作

Mysql默认的隔离级别是什么

简单介绍一下索引

最左匹配原则是什么意思

TCP的三次握手,为什么不是两次握手?

手撕算法:不用额外空间的前提下,删除一个int数组中的值为target的所有元素,并把剩余元素全部整理到数组前端,后段空余的位置补零

JAVA复习:GC垃圾收集器

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

垃圾是什么?指运行程序中没有任何指针指向的对象

不清理垃圾有什么后果?垃圾对象占用内存空间,容易内存溢出。

内存溢出和内存泄露的区别,

  • 内存溢出很容易来理解, 内存不够用,是指在程序申请内存时,没有足够的内存提供就出现了内存溢出
  • 内存泄漏 但是程序在申请内存后,无法释放已申请的内存空间 如java的数据库连接或者网络连接没有及时close。
  • 当内存泄露越来越多的时候,最终会导致内存溢出

JAVA 的垃圾回收机制

自动内存管理,(分配和回收)开发人员就不同过多关注内存的分配和释放,降低了内存的泄露和溢出。

java堆是垃圾回收的重点。青年区->老年区->永久代 回收频率依次减少

垃圾回收的算法

垃圾标记阶段:引用计数算法和可达性分析算法

引用计数器算法,每个对象保存一个整形的应用计数器,记录对象自身被引用的次数。

优点:实现简单,垃圾对象容易识别,判定效率高,回收没有延迟

缺点:额外的空间,更新计数器额外的时间开销。无法处理循环引用的情况(内存泄露,致命的缺点,因此java没有采用)

可达性分析/根搜索/追踪性垃圾收集算法

对象的finalization机制

对象要被gc回收之前会执行finalize方法,定义在Object类中的方法。可以在里面重写一些资源释放的方法。

但是不要主动去调用这个方法。

对象的三种状态

清除阶段的三种算法:

  • 标记-清除算法
  • 复制算法
  • 标记-压缩算法

标记-清除算法

标记从Gc roots开始遍历,标记所有可达到的对象(在对象的Header中记录为可达对象)

对堆中所有对象进行遍历,清除没有标记的对象。

缺点:效率不高,在进行GC的时候,需要停止整个应用程序,影响用户体验(Stop the world),容易产生内存碎片。需要维护一个空闲列表。

清空就是将对象的地址记录到空闲列表上。

复制算法:

优点:没有标志和消除过程,高效,不会产生碎片问题

缺点:需要两倍内存空间,需要维护对象之间的引用关系,如果大部分对象都不是垃圾,移动对象的时间开销也会很大

标记-压缩(标记-整理)算法

复制算法高效性的前提是垃圾对象多,存活对象少。而这很符合年轻代中数据的特点。但是老年代就不一样了,老年代的数据大部分是存活数据。

优点:没有内存碎片,不需要维护空闲列表,比复制算法空间利用率高

缺点:效率低,要维护对象间的引用,需要STW,影响用户体验

对比

分代收集算法:具体问题具体分析

青年代用复制算法,同时设置伊甸园区和幸存者区缓解内存的浪费。

老年代用标记-清除和标记-整理混合的方法。

增量收集算法:

缺点:造成垃圾回收总体成本提高,系统吞吐量下降。因为切换线程和上下文转换有额外开销。

分区算法:

一些概念:

System.gc() /Runtime.getRuntion().gc(),可能触发Full GC,对老年代和青年代进行回收。但是无法保证立刻调用垃圾收集器,会在程序执行的某个不确定时间节点进行调用。

System.runFinalization(); 会强制调用失去引用对象的finalize方法。

内存溢出 OOM:没有空闲空间,并且垃圾回收之后还是不够。

内存泄露 Memory Leak:对象不会再被程序使用了,但是GC又无法回收了。通常是编码过程的疏忽,导致某些对象的生命周期过长。

内存泄露的两个例子。

STW stop the world 所有的垃圾收集器都会有这个情况。就是把所有用户进程停止,执行垃圾回收。

并发(concurrent)实际上就是同步,某个时刻只有一个程序在执行,只是CPU快速地切换,让我们感觉同时在执行。

并行(Parallel) 同一个时刻,多个程序在真正运行。

  • 垃圾回收的并行:多条垃圾回收线程并行执行。
  • 垃圾回收的串行:只有一个垃圾回收器线程执行。
  • 垃圾回收器的并发:用户线程和垃圾回收线程同时执行。

安全点:

安全区域:

引用(前提都是可达的对象引用)

强引用对象不会被gc回收,也是内存泄露的主要原因。

软引用,内存足够不会回收,内存不够时,在二次gc时被回收。

弱引用:被gc就回收

JDK更新可以从三个层面区关注:

  • 语法层面
  • API层面
  • 底层优化

垃圾回收器的分类:

  • 按线程数分:串行gc和并行gc
  • 按照工作模式:并发式和独占式
  • 按碎片分:压缩式和非压缩式
  • 按工作内存:年轻代gc和老年代gc

GC的性能评估指标

上面标红的三项是主要的,但也是互相制约的。

主要关注前两项

吞吐量与暂停时间的矛盾。

可以在JVM参数中设置Parallel GC的吞吐量或者暂停时间的参数。

JAVA中的数组、链表、队列、栈

首先说一下Java中的集合框架collection是一个接口,、

下面有两大类型的子接口,分别是List和Deque

List下有三大常见的实现类,ArrayList、LinkedList、Vector

其中 ArrayList、Vector 底层都是用数组来实现的, LinkedList底层是用链表实现的

ArrayList非线程安全,Vecotr虽然是线程安全的但是已经被弃用了。

Stack类是早期JAVA为了栈数据结构而设计的一个类,它是vector的子类,但是早期设计的时候考虑的不是特别的完美,因为父类vector是一个线程安全的,意味着效率比较低,同时Vector的上层接口List里面有一个add(index, Element)的方法,被调用会破坏stack的结构,就是在这栈的中间可以随意的插入元素。因此Stack这个类也被弃用了。

Deque 接口顾名思义就是为了实现队列而提供的接口。双端队列。

下面有很多有用的实现类,ArrayDeque、LinekList、PriorityQueue 里面也封装了很多有用的方法。

LinkedList即使List的实现类又是Deque的实现类(底层是链表)因此可以使用它来作为队列或者栈来进行使用。

虽然LinkedList的功能很强大,但是它也是List的实现类,避免不了被错误调用

破坏了栈只能在栈顶操作数据的原则

操作队列或者栈用的方法主要带有offer poll peek + First/Last,而最好不是用add/remove之类的方法或者push/pop之类的方法,容易搞混乱。

这篇文章讲得很好。

https://mp.weixin.qq.com/s/Ba8jrULf8NJbENK6WGrVWg

复习:深度底层理解Java的String

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

String的两种创建方式:

  • String s = “abc”; //字面量初始化
  • String s = new String(“abc”); //对象的形式初始化

String类是final的,不可继承

JDK8以及以前版本String的底层是用char[]来进行存储的

JDK9以及以后底层改变为了用byte[]数据进行存储

修改底层结构的字符:String在程序中很常用,并且字符中大部分是拉丁文,即用一个字节就能进行存储,而cahr类型是两个字节的,因此会造成内存空间的浪费。

char[]就改变成了byte[]和对应的编码类型

StringBuilder、StringBuffer、JVM底层处理String的方式自JDK9都做了相应的修改。

String代表不可变的字符序列。

字符串常量池中不会存储相同的字符串。

StringPool 实际是一个固定大小的Hashtable,不能动态修改,常量过多的话Hash冲突会增加。大小可以在JVM的参数上进行定制。

常量池就类似java系统级别的一个缓存,可以让运行速度更快、更节省内存。

JDK6 的时候 字符串常量池在永久代的常量池中,JDK7和JDK8之后都在堆中。

为什么调整?

  • 永久代默认空间比较小,容易溢出
  • 永久代的垃圾回收的频率比较低(或者不回收),字符串回收效率低,也容易溢出

进阶知识

String s = “a” + “b” + “c”;

String s = “abc”

这两句在编译之后是等价的,常量字符串拼接(包括final修饰的变量)是在编译时期进行优化的。即在生成的字节码文件里面是两个一样的字面量“abc”

如果字符串的拼接符号的前后出现了变量,相当于在堆中new了一个String对象。

  • String s1 = “ab”;
  • String s2 = “cd”;
  • String s3 = s1 + s2;
  • String s4 = “abcd”;
  • System.out.println(s3 == s4); // false
  • String s3 = s1 + s2;这一句代码查看底层的字节码可以解释为
    • String tmp = new String();
    • tmp.append(s1);
    • tmp.append(s2);
    • s3 = tmp.toString();

以上导致了对象引用和常量池引用的地址不一致问题。

        String s = "";
        for (int i = 0; i < 10000; i++) {
            s = s + i;
        }
        
        StringBuilder s1 = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            s1.append(i);
        }

上述代码展示的两种字符串拼接方案,效率千差万别

  • append的方式只有一个StringBuilder对象,而字符串拼接的方式每次拼接都会产生一个新的StringBuilder对象以及String对象
  • 其次 ,第一中方式内存中存在过多stringBuilder和String垃圾,如果进行gc需要花费额外的时间。

进一步提高,StringBuilder可以在初始化的时候指定char[]数组的容量,可以避免扩容过程中带来的性能损耗。即如果逻辑大致确定,可以指定一个capacity的上界,就不会扩容了。

intern函数,返回字符串是字符串常量池中的地址(有就直接返回,没有就“创建”,JDK版本有差别)

new String(“ab”); 这条语句会创造几个对象?

一个对象是new 关键字创建的,另一个对象是字符串常量池中的对象。

new String(“a”) + new String(“b); 呢?从字节码的角度看一共有5个对象

  • new StringBuilder()
  • new String()
  • 字符串常量池中的对象“a”
  • new String()
  • 字符串常量池中的对象”b”

StringBuilder的toString方法中 return new String(value, 0, count);分析对应的字节码,得知并没有在常量池中创建“ab”,

字符串常量池的HashTable中放到是什么?现在的理解存到的就是一个完整的String对象的引用,该对象引用和字面量引用是等价的。而new出来的对象是在堆中的。

面试题:

String s1 = new String("1");
s1.intern();
String s2 = "1";
System.out.println(s1 == s2);           //false

String s3 = new String("1") +  new String("1");
s3.intern();
String s4 = "11";
System.out.println(s3 == s4);       //jdk6:false   jdk7/8:ture

第1部分比较简单,就是s1在对空间中创建了一个字符串一的对象,同时字面量一也在字符串常量池里面创建了一个一的对象,而第2句s1.intern();就相当于什么都没做,第3句的S2通过字面量初始化,指向字符串常量池中的那个对象,所以两个地址是不一样。

第2题就比较难,因为它的输出结果和jdk的版本有关,执行intern语句之前,如果字符串常量池中已经有了,就没什么区别。当字符串不存在常量池中的时候,intern方法在1.6中会在永久代中复制一份String对象,并返回相应的地址。而在JDK7/8中,字符串常量池的位置调整到了堆中,调用intern方法的时候如果常量池中没有,则直接指向堆中已有的那个对象,节省空间。

String s = String.valueOf(123);
System.out.println(s == s.intern());    //jdk8 true
String s3 = new String("1") +  new String("1");
String s4 = "11"; 
s3.intern();
System.out.println(s3 == s4);       //jdk7/8:false
String s1 = new String("a") +  new String("b");
String s2 = s1.intern(); 
System.out.println(s1 == "ab");    //jdk6:false   //jdk7/8:true
 System.out.println(s2 == "ab");   //jdk6:true    //jdk7/8:true

在代码中何时的位置加上intern函数可以在一定程度上节省内存空间。因为字符串常量池中的数据可以复用,重复的String对象就可能被gc回收。

复习:Java虚拟机 JVM底层结构

学习内容来自尚硅谷宋红康老师的JVM教程

https://www.bilibili.com/video/BV1PJ411n7xZ/

类的加载过程

  • 加载
    • 通过一个类的全类名获取该类的字节流
    • 将字节流代表的静态结构转换为方法区的运行时数据结构
    • 在内存中生成一个Class对象,作为这个类的各种数据的访问入口
  • 链接阶段
    • 验证:验证字节流中的信息满足虚拟机要求,如cafebabe头
    • 准备:为类变量分配内存,类的赋值默认初始值(非final的静态变量)
    • 解析:将常量池中的符号引用转换为直接引用的过程
  • 初始化:执行类构造器方法clinit方法(如给静态变量进行显式初始化, 静态代码块执行),子类运行前需要先加载父类的clinit方法,该方法是同步的。

类的加载器

两种类型,引导类加载器(Bootstrap Classloader)和自定义类加载器(拓展类加载器,系统类加载器,用户自定义加载器)

  • 引导类加载器在代码中获取不到,使用c、c++实现的,嵌套在jvm内部,主要加载一些java的核心类库,也会加载拓展类加载器和系统加载器
  • 拓展类加载器加载,父类加载器就是引导类加载器,在ClassLoader继承体系下,加载jre/lib/ext下面的jar包
  • 应用程序类加载器(系统类加载器), 父类加载器就是引导类加载器 , 在ClassLoader继承体系下, 是默认的类加载器,我们在代码中写的类都是这个加载的。

用户自定义类加载器在一些特殊情况下使用

双亲委派机制

  • 如果一个类加载器收到了类加载请求,它并不会自己先去加载,而是把这个请求委托给父类的加载器去执行
  • 如果父类的加载器还存在父类的加载器,则进一步加上委托依次递归请求最终达到顶层的启动类加载器,
  • 如果父类加载器可以完成内加载任务就成功返回,倘若腹内加载器都无法完成此任务,此类加载器才会自己尝试去加载,这就是双亲委派模型

反向委派,核心类库是接口,外部jar包是实现类。

优势:避免类的重复加载,保护程序安全,防止核心的API被修改

沙箱安全机制,就是双亲委派机制对核心源代码的保护,不能再核心类库包名下定义main方法。

运行时数据区

本地方法栈、虚拟机栈、程序计数器、堆区、元数据区(方法区/非堆空间)

线程有自己的程序计数器、虚拟机栈、本地方法栈

多个线程共享堆区和方法区(进程独占,生命周期同JVM)

一个JVM实例对应着一个Runtime类的对象。

程序计数器(PC寄存器)

主要用来存储指向下一条指令的地址,也就是即将执行的指令代码,由执行引擎读取下一条指令

线程私有的,生命周期和线程同步,占用内存很小,不会发生OOM错误而且没有GC。

PC寄存器存储地址有什么用呢?因为CPU会不停的切换各个线程,当切换为某个线程之后,就要知道程序从哪里继续执行。

虚拟机栈

JAVA指令是根据栈来设计的,这样的优点是可以跨平台,指令级比较小,编译器容易实现,但是缺点是和基于寄存器的指令性能实现了一定的下降,同样的功能也需要更多的指令。

栈是运行时单位,堆是存储的单位。

虚拟机栈里面存数的是很多的栈桢 stack frame,每一个栈桢对应着一个方法的 。栈顶的栈桢对应着当前方法。

栈是一种快速有效的分配存储方式;访问速度仅次于PC计数器;操作只有两个 ,入站、出站;栈不存在垃圾回收问题.

StackOverFlowError请求的容量超过了虚拟机占允许的最大容量(无限递归)

OutofmemoryError动态拓展虚拟机内存的时候无法申请到足够的内存

JVM栈可以在启动的时候制定大小。

栈中存什么,栈桢(一个内存区块),栈桢和方法是一一对应的关系

当前栈桢–当前方法–当前类

方法的结束方式有两种,第一种正常结束return;第二种方法中出现未捕获的异常,以抛出异常结束。因此有可能栈顶是异常结束,栈底正常结束,因为栈底处理了异常。

每个栈桢的结构有:局部变量表、操作数栈、动态链接、方法返回地址、一些附加信息

局部变量表是一个数字数组,存方法参数和方法体内的局部变量,包括基本数据类型、引用数据类型和返回值类型。不存在安全问题。局部变量表的大小是在编译时期确定的。

局部变量表中的slot(除了long 和double占用两个slot(32bit 一个 slot),其他类型的数据或者引用占用一个slot);成员方法的局部变量表中的第一个元素是this的引用。slot重复利用,作用域小的销毁后重复利用。

成员变量都有默认初始化的过程,而局部变量没有,所以局部变量必须显式地赋值。

操作数栈主要用于保存计算过程中的中间结果,同时作为计算过程中变量临时的存储空间,

在方法执行过程中,根据字节码指令往栈中写入数据或提取数据即入栈或出栈

说操作数栈实际底层肯定是要用具体的数据结构来实现的,然后可以用数组或者列表,这里用的数组。所以需要指定数组的大小,编译时候确定。

动态链接(指向运行时常量池(这个常量池是字节码文件内部的,最终也会放到常量池中)的方法引用)的作用就是将符号引用转换为调用方法的直接引用

为什么需要常量池?提供一些符号和引用便于指令识别,减小字节码文件的冗余,多个字节码文件可以共用方法区的常量池。

方法调用是怎么样的?方法调用也有静态链接和动态链接对应早期绑定和晚期绑定。就是多态。

Lambda表达式引入入让java这种静态类型语言具有了动态类型语言的一些特性以及底层是用invokeDynamic指令来实现的。用值判断变量的类型,而不是用变量类型来约束值的类型是动态类型语言的关键。

虚方法和非虚方法

虚方法如果每次都需要不断向上层父类找实现类,效率会比较低。为了提高性能,建立虚方法表。虚方法在类加载的链接阶段被创建(具体是在解析的阶段)

方法返回地址 调用者的pc计数器的值作为返回地址,即调用方法之后的下一条指令地址。

方法如果正常退出,则正常返回调用者的方法返回地址,如果是异常退出,调用者则根据异常表来定位接下来执行的位置。

一些附加信息 不重要

一些面试题:

栈溢出的情况:stackOverflowError

调整栈的大小,能保证不一出吗?否

垃圾回收设计JVM栈吗?否

分配栈的内存越大越好吗?否

自定义的局部变量是否线程安全?不一定

如果方法的形参是引用类型的变量或者返回值是引用参数类型,则可能是线程不安全的

本地方法接口和本地方法库—–非运行时区的模块

本地方法:Native Method就是一个Java调用非Java代码的接口。为什么要用本地方法?

  • Java应用需要与Java外界环境交互,效率考量
  • Java需要与操作系统的交互,调用c语言实现的接口

本地方法栈

类似于虚拟机栈的作用,就是管理本地方法的调用,也是线程私有的,内存溢出差不多,有StackOverflow和OutOfMemory,也可以设置栈的内存大小。

一个JVM实例只有一个堆内存,堆也是java内存管理的核心区域。Java堆积在juem启动的时候即被串件,其空间大小也就确定了,是JVM 管理最大的一块内存空间。所有的线程共享堆空间(但是堆中可能有线程的私有缓冲区TLAB)

几乎所有的对象实例和数组都在堆空间中,对象的引用在JVM栈中的某个栈帧的局部变量表中。方法运行结束的时候,堆中的对象不会马上被移除,仅仅在垃圾收集的时候才会被移除。

堆是垃圾回收的重点区域。

现在垃圾收集器大部分都基于分代收集理论设计

  • JDK7以及之前:新生区+养老区+永久区
  • JDK8以及之后:新生区+养老区+元空间
  • 永久区/元空间可以理解为方法区。主要先关注新生区和养老区

堆可以手动设置堆空间的大小,默认是电脑内存的1/64,最大的堆内存大小是电脑内存的1/4。建议初始和最大的设置成一样的。

OOM Error 堆中的对象所占的空间超过了堆的大小,则会导致堆空间的溢出。

年轻代和老年代(二者的内存比例可以分配,默认值是1:2)

年轻代有分为:伊甸园区、幸存者1区和幸存者2区(默认比例是8:1:1,但是需要显式指定)

几乎所有的java对象都是在Edan区创建的,大多数的数据都在青年代被销毁。

  • 创建对象的过程,创建的对象默认放在edan区,当edan区满的时候,触发gc,不是垃圾的全部到to区,from区的也会被gc检查,不是垃圾也到to区。
  • from区和to区的数据会维护一个年龄,每次gc之后年龄+1,超过阈值的时候移动到老年区。
  • from区或者to区满的时候不会触发gc,只有edan区满的时候会,当伊甸园区来的对象to区放不下的时候,可以直接放到老年区。
  • 如果老年区也放不下,在老年区执行一次GC,如果还是放不下就报错OOM。

YGC就是MinorGC,MajorGC是OGC/老年代的GC。

GC线程执行会导致用户进程的暂停,所以GC要尽可能少。

分代的原因就是通过统计数据优化垃圾收集器的性能。因为大部分的对象的生命周期都比较短。

TLAB Thread Local Allocation Buffer

堆是线程共享数据,但是存在线程安全问题,加锁会导致效率的下降,因此未每个线程在伊甸园区分配私有缓存区域。(通常这个空间比较小,为伊甸园区的1%。)

伊甸园区过大,会降低MinorGC的效率,过小会导致MinorGC触发的频率过高,影响用户线程,所以设置要平衡一下。

堆是分配对象存储的唯一选择吗?(”是“)

逃逸分析后,如果未逃逸,则可以将对象优化成被栈上分配。

如果new的对象可以在方法外被进行调用,则发生了逃逸。(就是一个作用域的问题)

  • 栈上分配可以在某种程度上来说,加快代码的执行效率,并减少垃圾回收执行的次数,增强用户线程的体验。
  • 同步消除,如果锁通过逃逸分析,仅仅在当前线程被使用,那么不存在同步安全问题,可以消除同步操作。
  • 标量替换,未逃逸的对象,可以从聚合量的形式被打散成标量(基本数据类型),直接在栈上进行分配就可以了。

但是逃逸分析本身也要消耗性能的,总体的提升是有风险的。该技术还不成熟

方法区

方法区是线程共享的,逻辑上是堆的一部分,但是在大部分JVM在实现过程中是和堆分开的。jdk7 叫做永久带,jdk8叫做元空间。

方法区和永久代不严格等价,在hotspotJVM上是等价的。

元空间的使用的内存是本地内存,永久代用的是虚拟机内存。

方法区主要存类型信息,常量,静态变量和JIT代码缓存

类信息:

  • 类的完整定义如类声明、继承、实现情况、修饰符等
  • 域信息(成员变量):名称、类型、权限修饰符、顺序
  • 方法信息:方法名称、返回值类型、参数个数类型、方法字节码、本地变量表、操作数栈、异常表……

全局变量和全局常量的区别,全局常量在编译阶段就赋值完成了(在字节码文件中有体现),而全局变量在类加载链接阶段的prepare阶段才默认初始化,在第三各初始化阶段才显示初始化。

运行时常量池:字节码文件中有常量池,方法区中有运行时常量池。

常量池包括了各种字面量和对类型、域和方法的符号引用。


为什么要改?

  • 永久代的空间是不好确定,容易产生OOM
  • 对永久代的调优的过程是比较困难的

为什么StringTable要调整?因为永久代回收的效率很低,在full gc 的时候会触发,这导致StringTable回收的效率不高,而日常开发中会有大量的字符串被创建,如果不及时回收,会导致永久代空间不足,放到堆里面,回收会比较即使。

区分好对象本身一直是在堆区的,而对象引用变量(存的对象地址)放的位置不同版本有区别。

方法区的垃圾回收主要是常量池中废弃的常量不再使用的类型

方法区中类的回收条件十分苛刻,费力不讨好。

创建对象的方式

  • new
  • Class.newInstance
  • Constructor.newInstance
  • clone(实现Cloneable接口以及浅复制)
  • 反序列化

创建对象的步骤:Object obj = new Object();

对应的字节码:

Code:
stack=2, locals=2, args_size=1
0: new #2 // class java/lang/Object
3: dup
4: invokespecial #1 // Method java/lang/Object.””:()V
7: astore_1
8: return

  • 判断对象对应的类是否加载、链接、初始化
  • 为对象分配内存,计算占用空间的大小(确定的)
    • 内存规整-指针碰撞(整块空间)
    • 内存不规整-空闲分配列表(碎片化的空间)
  • 处理并发问题
  • 初始化分配到的空间(赋默认初始化值)
  • 设置对象头(所属的类,对象的HashCode,对象的GC信息、锁信息)
  • init方法初始化

对象的内存布局:

  • 对象头Header
    • 运行时元数据:哈希值、GC分代年龄、锁状态等
    • 类型指针:指向类元数据
  • 实例数据:从祖宗到自己的各种类型的字段
  • 对齐填充

对象的访问定位:

  • 句柄访问:效率低(间接访问),需要额外内存维护句柄池,栈中的指针稳定,
  • 直接指针(HotSpot采用的方式):效率高,栈中的指针不稳定,节省内存

直接内存

Java Process Memory = Java heap + native memory (其他空间太小了)

执行引擎

解释器和JIT编译器->java是半编译半解释型语言(与javac编译无关)

解释器:效率比较低,但是响应时间快

为什么非要有字节码?不想C语言、C++一步到位?分层思想可以提高各个部分的效率,不用一步到位的考虑,就想OSI网络分层结构一样,应用层不用直接管物理链路层的东西。虽然分层做出了一定性能上的牺牲。

JIT(Just in time)编译器:响应时间慢,但是执行效率高

Java中的编译器:前端编译器、后段编译器

热点代码以及探测方式

JIT编译后的代码缓存在方法区

默认情况下JVM执行引擎是混合模式,可以通过参数制定只运行特定模式。

JIT编译器分为C1(客户端)和C2(服务端)两种

Leetcode 146 LRU(最近最少使用)缓存机制

最近最少使用的一个缓存机制是操作系统这门课程里面的一个概念

非常直观基本的一个思路就是HashMap+加双端链表

使用 HashMap 是为了提高查找的一个效率在O(1)

双端链表是为了提高增加或者交换元素位置时的开销O(1)

当然这么做是代价,是使用了一些额外的空间O(n)

下面的代码参考自官方文档的题解。

class LRUCache extends LinkedHashMap<Integer, Integer>{

    int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        int res = super.getOrDefault(key, -1);
        return res;
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

        return size() > capacity;
    }
}

值得注意的是Java语言内部实现了这个结构非常和我们需求很相符,

其中内部内置final private boolean assessOrder这个变量,如果这个变量值是true的话,每次get操作get到的那个元素/(或者put插入的元素)会插入到链表头的位置。是在初始化的时候默认值是false,所以我们要在构造函数显式给定

同时在put方法结束前的最后会调用remove all these entry这个方法,这个方法返回true,就会去掉最后一个元素,默认是返回一个false,所以我们要对这个方法进行重写,以满足我们的需求。

当然也可以手写一个双向链表和使用Hashmap的方式实现

class LRUCache{

    class Node {
        int val;
        int key;
        Node pre;
        Node next;
        public Node(int key, int val) {this.key = key; this.val = val;}
    }
    int capacity;
    Node dummyHead = new Node(0,0);
    Node dummyTail = new Node(0,0);
    HashMap<Integer, Node> hm = new HashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }
    
    public int get(int key) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            moveToHead(cur, true);
            return cur.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            cur.val = value;
            moveToHead(cur, true);
        } else {
            Node cur = new Node(key, value);
            hm.put(key, cur);
            moveToHead(cur, false);
            if (hm.size() > capacity)
                removeTail();
        }
    }

    private void moveToHead(Node cur, boolean removeFlag) {
        if (removeFlag) {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        cur.pre = dummyHead;
        cur.next = dummyHead.next;
        dummyHead.next.pre = cur;
        dummyHead.next = cur;
    }

    private void removeTail() {
        Node cur = dummyTail.pre;
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        cur.next = null;
        cur.pre = null;
        hm.remove(cur.key);
    }

    private void printList(){
        Node cur = dummyHead.next;
        while (cur != dummyTail) {
            System.out.print("" + cur.val + "->");
            cur = cur.next;
        }
        System.out.println();
    }

}

百度消息件后台实习面试20200527

计算机网络结构 TCP/IP 4层结构都有那些。

传输层协议简单介绍一下。

TCP的三次握手和四次挥手,为什么是三次握手,每次握手携带了那些关键信息,都达到了那些目的。

三次握手和四次握手的区别,相同点

http协议的状态码的分类

http 1.0 、1.1 、2.0 的区别

从浏览器输入www.baidu.com 到看到页面的整个流程

DNS解析的详细流程

cname和a记录域名是什么

Linux熟悉吗?通常是怎么杀死进程的

进程号怎么找到的,怎么通过进程名字找进程

说几个你常用的命令,查看cpu-磁盘-内存,top 如何查看具体进程的信息

linux网络相关的命令

操作系统,说说进程和线程

说说堆和栈的区别,进程里面的堆内存和栈内存的区别

Redis和缓存懂吗

索引中的B树和B+树有什么区别

InnoDB和MyiSAM有了解吗,区别是什么。

数据库事务的几个特性,分别介绍一下。

事务有几种隔离级别

InnoDB和Myisam里面锁有什么区别

项目中的Mysql如何部署,有没有分布式

项目介绍,有没有做压力测试,读写的数据量

怎么进行测试,有些测试用例,单元测试?自动化脚本?

项目中的困难点介绍,如何解决点。

腾讯视频 后端实习生面试 20200527

嗯,项目为了一个项目的大体的结构啊,具体的功能是什么的,然后你是负责什么职责团队有多大

你觉得项目中的比较难的一个点,你是如何解决的?

项目有一个导出功能是一个web项目,然后如何解决导出时间过长的一个问题。

数据库的一个权限的是怎么实现的? 用户、角色和权限的数据库模型是如何抽象出来的?

操作系统。进程和线程的一个区别。进程之间是如何进行通讯的?知道管道模型吗?

计算机网络,简单描述一下TCP/IP的5层网络,从浏览器访问服务端的一个数据结合这5层的一个结构,具体的流程是怎么样?

传输层tcp和udp的区别,Tcp的三次握手,细节中的停止等待、滑动窗口、流量控制、阻塞是否有了解呢?

物理层传输的是什么?路由算法有了解吗?

网络层Ip的一个种类,A、BCD类别的IP分别是什么

数据库ACID是否有了解?

数据库各方面的索引有哪些类型?有没有做过数据库查询相关的性能优化?如何判断索引是否命中了。

编程题:Leetcode 31. 下一个排列