2020年5月 – 个人空间

2020年5月30日

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的吞吐量或者暂停时间的参数。

2020年5月30日

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

2020年5月29日

复习：深度底层理解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回收。

2020年5月28日

复习：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（服务端）两种

2020年5月28日2020年5月30日

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();
    }

}

2020年5月27日

百度消息件后台实习面试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如何部署，有没有分布式

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

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

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

2020年5月27日

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

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

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

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

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

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

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

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

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

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

数据库ACID是否有了解？

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

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

2020年5月26日

阿里健康java后台5-26电话面试

闲聊了下项目上的事情，项目难点，如何解决，有没有关注过底层的细节，是否比较能够实现同一个功能的两个库，以及这两个库各自的优缺点，好是操作的CPU、内存的情况，Hibernate二级缓存之类的东西

JAVA技术相关

线程的状态有那些

java1.8中Hashmap的改进有哪些

为什么用红黑树，你对红黑树的理解

jdk7 中Hashmap为什么会成环，尾插法为什么可以解决线程安全问题吗

spring框架的启动流程？记不太清了。

2020年5月25日2020年5月25日

网易有道后台JAVA研发实习面试 2020-05-25

编程题

求根号2的值要求小数点后10位精确的一个精确度（二分，进阶牛顿迭代）

实现LRU缓存算法，忘了

写一个链表，实现增删改查

面试：

项目相关的不提了

http https的区别，介绍http

是否接触过Redis

java8有那些新特性

java中集合和map简单介绍

hashmap冲突怎么办

jvm的双亲委派类加载

数据库主键和索引的工作原理

2020年5月23日

迭代、递归、动态规划的粗浅区别

简单说说个人对这三个概念的粗浅认识

递归可以说是最容易理解的一个概念，简单的说就是函数里面调用自己，问题转化为小问题，分而治之。

迭代的理解就是通过上一步的结果，通过一个函数，得到现在的结果；而现在的结果，用同样的函数，得到再下一步的结果；不断迭代，简单举一个累加过程的例子， \( sum_{new} = sum_ {old} + arr[i] \) 。

或者从数学中很有名的牛顿迭代法来理解，之所以叫做迭代就是由于牛顿迭代法求根的时候，有一个迭代公式：

\(x_{new} = x_{old} – \frac{f'(x_ {old} )}{f(x_ {old} )}\)

就是符合迭代的一个思想，就是用上一步的结果推下一步的结果，而且每一步都是相同的公式，不断迭代，直到逼近零点。

动态规划有点类似于迭代的方式，但是又不完全等同于迭代，因为动态规划是一种自底向上的一个算法，并且有自己的状态转移方程和最优子结构性质，转移方程有点类似于迭代法中的迭代公式。