#
未命名
基于 SpringBoot 的在线 Java IDE
- 功能
- 在线的 Java IDE,可以远程运行客户端发来的 Java 代码的 main 方法
- 将程序的标准输出内容、运行时异常信息反馈给客户端
- 对客户端发来的程序的执行时间进行限制 (线程池,future.get(limitTime))
- 涉及Java 基础的知识
- Java 程序编译过程: (运行时编译) 内存-内存
- 运行的过程:自定义类加载器实现类的加载 & 热替换
- Java 类加载机制
- Java 类文件结构: 根据 Java 类文件结构修改类的字节码,可将客户端程序对 System 的调用替换为对 System的替代类 HackSystem 的调用
- Java 反射:通过反射实现 main 方法的运行
- 一个简单的并发问题:如何将一个非线程安全的类变为一个线程安全的类 : 解决多用户同时发送执行代码请求时的并发问题: 通过 ThreadLoacl 实现线程封闭,为每个请求创建一个输出流存储标准输出及标准错误结果;
项目架构
在线执行 Java 代码的实现流程,架构如下图所示:
##正常情况下Java 程序编译和运行的过程
简要分析
1. 编译 :.java 源代码 javac 编译成 .class / jar包(其中都是.class)
- 加载:然后通过类的加载 classLoader, 双亲委派模型, 在JVM的方法区中得到类class对象
- 使用: JVM通过方法区中的class对象,获取该类的各种信息,或者运行该类的方法
- 程序入口的:指定类的main()
- 执行:通过JIT 编译,将class字节码 –> native code 交给OS执行
详细分析
编译
在运行前,我们首先需要将 .java 源文件编译为 .class 文件。Java 编译一个类时,如果这个类所依赖的类还没有被编译,编译器就会先编译这个被依赖的类,然后引用,否则直接引用,如果 Java 编译器在指定目录下找不到该类所其依赖的类的 .class 文件或者 .java 源文件的话,编译器话报“cant find symbol”的 Error。
运行
Java 类运行的过程可分为两个过程:
- 类的加载
- 应用程序运行后,系统就会启动一个 JVM 进程,JVM 进程从 classpath 路径中找到名为 Test.class 的二进制文件(假设客户端发来的类名为 Test),将 Test 的类信息加载到运行时数据区的方法区内,这个过程叫做 Test 类的加载。
- 上一步过程主要通过 ClassLoader 完成,类加载器会将类的字节码文件加载为 Class 对象,存放在 Java 虚拟机的方法区中,之后 JVM 就可以通过这个 Class 对象获取该类的各种信息,或者运行该类的方法。
- 关于类加载器的详细讲解可见:虚拟机类加载机制。
- 类的执行
- JVM 找到 Test 的主函数入口,开始执行 main 函数。
- 本项目主要通过反射来完成这一过程,有关反射的详细讲解可见:Java 反射。
本项目内用户传进来的Java 程序编译和运行的过程
编译
说明
- JDK 1.6 后新加的动态编译实现
compiler 1
2
3
43. 进行一些修改 实现从内存(String)-内存(bytes[])编译 (硬盘(.java)-硬盘(.class)
1. 后到的请求覆盖之前的.class
2. 保存在硬盘 不安全
4. ```Boolean result = compiler.getTask(null, manager, collector, options, null, Arrays.asList(javaFileObject)).call(); // 执行编译最关键的六个参数解析
1 | JavaCompiler.CompilationTask getTask(Writer out, |
out
:编译器的一个额外的输出 Writer,为 null 的话就是 System.err;options
:编译器的配置;javac - -target 1.8 -d /…….classes
:需要被 annotation processing 处理的类的类名;nulldiagnosticListener
:诊断信息收集器;service传入;如果编译出错,编译模块返回字节码null,将错误信息返回前端compilationUnits
:要被编译的单元们,就是一堆 JavaFileObjectfileManager
:文件管理器, 用以new JavaFileObject 存储编译好的byteCode
- compiler 编译过程源码流程
执行流程说明:
- 调用 JavaFileObject 的 getCharContent 方法,得到源码的字符序,返回类型 CharSequence接口(String,StringBuilder,StringBuffer实现)
- disk-disk: File – CharSequence
- mem- mem 实现一个自己的javaFileObject extends SimpleJavaFileObject
- 声明 private String source; 用以存储用户传入的代码,通过构造函数传入
- 重写 getCharContent() ,在其中返回 source
- 输入就搞定了,继续追源码,下面一个问题 就是 如何输出字节码,对于disk-disk 也就是如何将字节码写入磁盘
- 两个步骤:
- 1.JavaFileManager的 getJavaFileForOutput()方法获得JavaFileObject 对象 ,将编译得到字节码,封装进一个 JavaFileObject 对象;compiler调用完就找不到了
- 2.JavaFileObject 方法的openOutputStream() 来创建输出流对象,在compiler执行的过程中(具体啥时候不清楚) 会用这个输出流 保存到disk;
- 对于我们的目标–mem-mem
- JavaFileObject
- 重写自定义JavaFileObject 方法的openOutputStream() ,把该方法创建的输出流设为自定义JavaFileObject 的私有域,保存字节码
- 编译模块最终得到的其实是byte[],这个自定义的类中还有一个方法负责将输出流转为byte[]
- JavaFileManager
- 其 getJavaFileForOutput()搞出来的JavaFileObject ,compiler调用完就找不到了,所以说在自定义的编译模块中放一个 编译模块类的map里,key的话是classname,(不问的话不必说:value就是JavaFileObject 编译模块非并发,一个考虑就是避免不同请求,类名key相同把value覆盖)
- 另一个是说: getJavaFileForOutput()搞出来的JavaFileObject要是我们自己定义的JavaFileObject,只有这样才能操作其输出流
- 整体来说 就是实现自己的JavaFileManager,重写 getJavaFileForOutput()方法:1. new自定义JavaFileObject 2. 存入map 3. 返回
代码
我们实现的 SimpleJavaFileObject 的子类如下:
1 | public static class TmpJavaFileObject extends SimpleJavaFileObject { |
JavaFileManager fileManager
对于 JavaFileManager,我们需要重写以下 2 个方法:
1 | public static class TmpJavaFileManager extends ForwardingJavaFileManager<JavaFileManager> { |
实现编译器模块
最后,我们的编译器实现如下,通过调用 StringSourceCompiler.compile(String source)
就可以得到字符串源代码 source 的编译结果。
1 | //StringSourceCompiler 的执行是 非并发的 |
加载:
注意点:
- 绝不可以通过系统可以提供给我们的应用程序类加载器来加载用户传进来的类
- 因为这个类加载器是独一份的,如果通过这个类加载器加载了我们的字节码,当客户端对源码进行了修改,再次提交运行时,应用程序类加载器会认为这个类已经加载过了,不会再次加载它
- 这样除非重启服务器,否则我们永远都无法执行客户端提交来的新代码
至于说 为什么 应用程序类加载器会认为这个类已经加载过了,就要提到双亲委派模型
详细的双亲委派模型 不多说,但是在系统类加载器 systemClassLoader 源码里 loadClass()方法里的双亲委派模型的逻辑是这样的
1 | public abstract class ClassLoader { |
之前的问题:为什么 应用程序类加载器会认为这个类已经加载过了
答案:双亲委派模型中的一步,类加载器会通过类的全限定名查找该类加载器已经加载过的类 查找方法findLoadedClass(name 类全限定名)
我们想要解决的问题就是:1. 有两个类全限定名一样的字节码 (全限定名) 2. 需要他们是不同的类class对象
类加载器会通过类的全限定名查找该类加载器已经加载过的类 —- 可以推出—–>两个类相同的条件
- 类的全限定名相同
- 被同一个类加载器加载
要解决我们的问题就可以 破坏第二个条件 :加载一个用户请求的类,就用一个新的类加载器,并且不遵守双亲委派模型
通过protected final Class<?> defineClass(String name, byte[] b, int off, int len)
来完成,
所以我们只要新写一个 loadByte 方法把 defineClass 方法开放出来,我们自己要使用 HotswapClassLoader 加载类时就显式调用 loadByte 方法
虚拟机使用 HotswapClassLoader 时会去调用 loadClass 方法 (虚拟机会使用自定义的类加载器吗? 会的 类加载的传递性原则)
类加载的传递性原则 程序在运行过程中,遇到了一个未知的类,它会选择哪个 ClassLoader 来加载它呢?
虚拟机的策略是使用调用者 Class 对象的 ClassLoader 来加载当前未知的类。何为调用者 Class 对象?就是在遇到这个未知的类时,虚拟机肯定正在运行一个方法调用(静态方法或者实例方法),这个方法挂在哪个类上面,那这个类就是调用者 Class 对象。前面我们提到每个 Class 对象里面都有一个 classLoader 属性记录了当前的类是由谁来加载的。
也就是在用户传入的类中,如果有一个未加载过的 非用户自定义的类,VM会使用我们自定义的类加载器的loadClass()方法加载,遵守双亲委派
HotswapClassLoader 具体实现如下:
1 | public class HotSwapClassLoader extends ClassLoader { |
然后使用我们新写的类加载器,我们就可以通过以下两行代码无数次的加载客户端要运行的类了!
1 | HotSwapClassLoader classLoader = new HotSwapClassLoader(); |
使用:
将类加载进虚拟机之后,我们就可以通过反射机制来运行运行用户类的 main 方法了。
1 | Method mainMethod = clazz.getMethod("main", new Class[] { String[].class }); |
用户的结果输出:
经过
1. 编译模块的运行时编译,
2. 在执行模块,对每个用户请求传入的类都是用一个自定义的类加载器加载,
3. 然后使用反射运行main方法
可以完成,用户请求代码的运行,但是有一点问题:用户的输出如何获得?
用户输出:一般通过 System.out, 那么如何获取其中的内容
方案一:System.out 是一个PrintStream 显然可以通过 System.out.toString()
获取其中内容 或者System.setOut()
重定向输出流,然后获取其中内容
方案一问题:1. 每个用户的请求的执行操作都是在一个线程里跑的,并发的,那么所有用户的请求的输出流都会混在一个System.out里面,显然不可取
想要的目标:每个线程的输出流都独立 –> 很自然达到这个需求 就是ThreadLocal –> 为了在输出流中使用ThreadLocal需要继承PrintStream 写一个线程封闭的输出流
实现线程封闭的PrintStream类
主要思路:
继承PrintStream,实现线程封闭的子类(PrintStream类不是final的可以继承)
找到PrintStream中存储 流 的成员,改为ThreadLocal的
PrintStream有一个继承自其父类的成员
OutputStream out
,输出基本依靠该成员PrintStream不抛出异常,而是使用
Boolean trouble
记录是否产生异常- 因此在自定义的PrintStream类中 将这两个变量实现为ThreadLocal的
查看System类中是否有使用到PrintStream 类型out的方法 (没有,也就是一般是System.out使用)
System类中没有使用到PrintStream 类型out的方法,也就是一般是System.out使用
但是PrintStream的无参构造函数肯定会用到 (初始化System 的out成员)
1
2
3> private ThreadLocal<ByteArrayOutputStream> out;
> private ThreadLocal<Boolean> trouble;
>
查找PrintStream类中的public 方法,改为线程封闭的
改造方法:将相关方法(out 和 trouble相关的方法) 由线程同步的Synchronized(this)的 改为 从ThreadLocal类型的out中 先get()再操作
改写的方法:ensureOpen ,close ,write |||||||| setError,checkError,clearError
ensureOpen 方法
PrintStream 中的实现:
1
2
3> private void ensureOpen() throws IOException {
> if (out == null) throw new IOException("Stream closed");}
>重写为:
1
2
3
4
5> private void ensureOpen() throws IOException {
> if (out.get() == null) { // 不是判断out是否为空,而是判断out.get()是否为空
> out.set(new ByteArrayOutputStream()); // 如果为空不再抛出异常,而是新建一个流给调用这个方法的线程
> }}
>close 方法
PrintStream 中的实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14> private boolean closing = false; /* To avoid recursive closing */
> public void close() {
> synchronized (this) {
> if (!closing) {
> closing = true;
> try {
> textOut.close();
> out.close();}
> catch (IOException x) {
> trouble = true; }
> textOut = null;
> charOut = null;
> out = null; } } }
>重写为:
1
2
3
4
5
6
7
8> public void close() {
> try {// 关闭当前线程的OutputStream
> out.get().close(); }
> catch (IOException x) {
> trouble.set(true);}
> out.remove(); // 将当前线程的OutputStream移除
> }
>write 方法
PrintStream 中的实现:
1
2
3
4
5
6
7
8
9
10
11
12> public void write(byte buf[], int off, int len) {
> try {
> synchronized (this) {
> ensureOpen();
> out.write(buf, off, len);
> if (autoFlush)
> out.flush();} }
> catch (InterruptedIOException x) {
> Thread.currentThread().interrupt(); }
> catch (IOException x) {
> trouble = true; }}
>重写为:
1
2
3
4
5
6
7
8
9
10> public void write(byte buf[], int off, int len) {
> try {
> ensureOpen();
> out.get().write(buf, off, len); // out.get()才是当前线程的OutputStream
> }
> catch (InterruptedIOException x) {
> Thread.currentThread().interrupt(); }
> catch (IOException x) {
> trouble.set(true); } }
>
修改System类
承接上段*有了自定义的PrintStream输出流就可以在执行模块执行前,使用System.setOut()将输出流重定向至线程独立的输出流*
但没有这么做
原因在于System类本身也有很多不安全的地方 比如 System.exit(0)
,用户调用该方法直接关掉整个服务—>需要修改System类,限制用户使用不安全的方法
将 System 替换为 HackSystem 的思路
那么如何将客户端程序中对 System 的调用替换为对 HackSystem 的调用呢?当然不能直接修改客户端发来的程序的源代码字符串了,这既不优雅,操作也十分的繁琐。我们采用了一种“高级”的方法,即直接在字节码中,把要执行的类对 System 的符号引用替换为我们准备的 HackSystem 的符号引用,因此我们需要一个字节码修改器,这个字节码修改器完成如下流程:
- 遍历字节码常量池中的所有符号引用,找到 “java/lang/System”;
- 将 “java/lang/System” 替换为 “…/HackSystem”。
要想完成以上 2 步操作,首先我们要了解类文件的结构,这样我们才能找到类对 System 的符号引用的位置,并且知道替换的方法;其次,我们还需要一个字节数组修改工具 ByteUtils 帮助我们修改存储字节码的字节数组。
类文件结构
这里,为了不影响阅读的流畅性,我们只简单介绍一下我们会用到的有关类文件结构的内容。
Class 文件是一组以 8 位字节为基础单位的二进制流,各个数据项目严格按照顺序紧凑地排列在 Class 文件中,中间没有任何分隔符。Java 虚拟机规范规定 Class 文件采用一种类似 C 语言结构体的伪结构来存储数据,这种伪结构中只有两种数据类型:无符号数和表,我们之后也主要对这两种类型的数据类型进行解析。
- 无符号数: 无符号数属于基本数据类型,以 u1、u2、u4、u8 分别代表 1 个字节、2 个字节、4 个字节和 8 个字节的无符号数,可以用它来描述数字、索引引用、数量值或 utf-8 编码的字符串值。
- 表: 表是由多个无符号数或其他表为数据项构成的复合数据类型,名称上都以
_info
结尾。
Class 文件的头 8 个字节
Class 文件的头 8 个字节是魔数和版本号,其中头 4 个字节是魔数,也就是 0xCAFEBABE
,它可以用来确定这个文件是否为一个能被虚拟机接受的 Class 文件(这通过扩展名来识别文件类型要安全,毕竟扩展名是可以随便修改的)。
后 4 个字节则是当前 Class 文件的版本号,其中第 5、6 个字节是次版本号,第 7、8 个字节是主版本号。
常量池
从第 9 个字节开始,就是常量池的入口,常量池是 Class 文件中:
- 与其他项目关联最多的的数据类型;
- 占用 Class 文件空间最大的数据项目;
- Class 文件中第一个出现的表类型数据项目。
常量池的开始的两个字节,也就是第 9、10 个字节,放置一个 u2 类型的数据,标识常量池中常量的数量 cpc (constant_pool_count),这个计数值有一个十分特殊的地方,就是它是从 1 开始而不是从 0 开始的,也就是说如果 cpc = 22,那么代表常量池中有 21 项常量,索引值为 1 ~ 21,第 0 项常量被空出来,为了满足后面某些指向常量池的索引值的数据在特定情况下需要表达“不引用任何一个常量池项目”时,将让这个索引值指向 0 即可。
常量池中记录的是代码出现过的所有 token(类名,成员变量名等,也是我们接下来要修改的地方)以及符号引用(方法引用,成员变量引用等),主要包括以下两大类常量:
- 字面量:接近于 Java 语言层面的常量概念,包括
- 文本字符串
- 声明为 final 的常量值
- 符号引用:以一组符号来描述所引用的目标,包括
- 类和接口的全限定名
- 字段的名称和描述符
- 方法的名称和描述符
常量池中的每一项常量都通过一个表来存储。目前一共有 14 种常量,不过麻烦的地方就在于,这 14 种常量类型每一种都有自己的结构,我们在这里只详细介绍两种:CONSTANT_Class_info 和 CONSTANT_Utf8_info。
CONSTANT_Class_info 的存储结构为:
1 | ... [ tag=7 ] [ name_index ] ... |
其中,tag 是标志位,用来区分常量类型的,tag = 7 就表示接下来的这个表是一个 CONSTANT_Class_info,name_index 是一个索引值,指向常量池中的一个 CONSTANT_Utf8_info 类型的常量所在的索引值,CONSTANT_Utf8_info 类型常量一般被用来描述类的全限定名、方法名和字段名。它的存储结构如下:
1 | ... [ tag=1 ] [ 当前常量的长度 len ] [ 常量的符号引用的字符串值 ] ... |
在本项目中,我们需要修改的就是值为 java/lang/System
的 CONSTANT_Utf8_info 的常量,因为在类加载的过程中,虚拟机会将常量池中的“符号引用”替换为“直接引用”,而 java/lang/System
就是用来寻找其方法的直接引用的关键所在,我们只要将 java/lang/System
修改为我们的类的全限定名,就可以在运行时将通过 System.xxx
运行的方法偷偷的替换为我们的方法。
因为我们需要修改的内容在常量池中,所以我们就介绍到常量池为止,不再介绍 Class 文件中后面的部分了,接下来我们将要介绍修改字节码常量池时会用到的一个处理字节数组的小工具:ByteUtils。
ByteUtils 工具
这个小工具主要有以下几个功能:
- byte to int
- int to byte
- byte to String
- String to byte
- 替换字节数组中的部分字节
具体实现详见:ByteUtils.java
实现字节码修改器
介绍完会用到的基础知识,接下来就是本篇的重头戏:实现字节码修改器。通过之前的说明,我们可以通过以下流程完成我们的字节码修改器:
- 取出常量池中的常量的个数 cpc;
- 遍历常量池中 cpc 个常量,检查 tag = 1 的 CONSTANT_Utf8_info 常量;
- 找到存储的常量值为 java/lang/System 的常量,把它替换为 org/olexec/execute/HackSystem;
- 因为只可能有一个值为 java/lang/System 的 CONSTANT_Utf8_info 常量,所以找到之后可以立即返回修改后的字节码。
具体实现详见:ClassModifier.java
并发相关
Async注解
https://blog.csdn.net/wudiyong22/article/details/80747084
SimpleAsyncTaskExecutor:不是真的线程池,这个类不重用线程,每次调用都会创建一个新的线程。
ThreadPoolTaskExecutor :
最常使用,推荐。 其实质是对java.util.concurrent.ThreadPoolExecutor的包装
配置线程池参数,注册为bean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
241、corePoolSize:核心线程数 CPU+1
* 核心线程会一直存活,及时没有任务需要执行
* 当线程数小于核心线程数时,即使有线程空闲,线程池也会优先创建新线程处理
* 设置allowCoreThreadTimeout=true(默认false)时,核心线程会超时关闭
2、queueCapacity:任务队列容量(阻塞队列)ArrayBlockingQueue(0)
* 当核心线程数达到最大时,新任务会放在队列中排队等待执行
3、maxPoolSize:最大线程数 CPU+1
* 当线程数>=corePoolSize,且任务队列已满时。线程池会创建新线程来处理任务
* 当线程数=maxPoolSize,且任务队列已满时,线程池会拒绝处理任务而抛出异常
4、keepAliveTime:线程空闲时间
* 当线程空闲时间达到keepAliveTime时,线程会退出,直到线程数量=corePoolSize
* 如果allowCoreThreadTimeout=true,则会直到线程数量=0
5、rejectedExecutionHandler:任务拒绝处理器
* 两种情况会拒绝处理任务:
- 当线程数已经达到maxPoolSize,切队列已满,会拒绝新任务
- 当线程池被调用shutdown()后,会等待线程池里的任务执行完毕,再shutdown。如果在调用shutdown()和线程池真正shutdown之间提交任务,会拒绝新任务
* 线程池会调用rejectedExecutionHandler来处理这个任务。如果没有设置默认是AbortPolicy,会抛出异常
* ThreadPoolExecutor类有几个内部实现类来处理这类情况:
- AbortPolicy 丢弃任务,抛运行时异常
- CallerRunsPolicy 执行任务
- DiscardPolicy 忽视,什么都不会发生
- DiscardOldestPolicy 从队列中踢出最先进入队列(最后一个执行)的任务
* 实现RejectedExecutionHandler接口,可自定义处理器
6、allowCoreThreadTimeout:允许核心线程超时Future.get() 实现超时限制
- 捕获异常 RejectedExecutionException/TimeoutException
限制客户端程序的运行时间
我们并不知道客户端发来的程序的实际运行时间,出于安全的角度考虑,我们需要对其运行时间进行限制。
在 ExecuteStringSourceService 中,我们通过使用 Callable + Future 的方式来限制程序的执行时间,并且对运行过程中可能出现的错误进行 catch,返回给客户端。
1 | ExecutorService pool = Executors.newSingleThreadExecutor(); |
未命名
新生代 老年代的垃圾回收算法:新生代 复制算法 老年代 标记整理算法 原因?
单纯从算法比较为什么标记整理慢呢,因为多了一次整理堆空间碎片的过程。但是两者用处不一样,抛开使用场景谈效率是不合适的。copy算法是在新生代执行的,因为新生代对象大多朝生夕灭,存活时间短,占内存小,所以一次gc后剩下的对象少而且小,直接从from survivor和eden区copy到to survivor就好了,这叫minor gc。标记整理是老年代常用的,因为老年代对象大而且生存时间长,不适合用copy算法,这叫major gc。minor gc非常频繁,所以用copy算法以较小的空间换时间是合理的。
你问mark过程如何判断对象活着,对象被gc掉同时需要满足两个条件,一个是gc roots不可达,另一个是没必要执行finalize方法。需要执行finalize方法的对象会加入到守护线程队列中执行finalize方法,一旦执行完毕依旧是gc roots不可达的话则也会被gc掉。
- 复制算法 速度快 只有copy的过程 新生代对象小 存活率低 需要复制的对象少 (若整理 需要整理的多)
- 整理算法 速度慢 mark —-整理 老年代对象大 存活率高 需要整理的对象少 (若复制 需要复制的多)
标记复制算法 为什么有三个区域?
避免hash的方法: 开放地址法;再哈希法(有多个hash函数,再次计算hash值);拉链法;建立公共溢出区
左连接 右连接 全连接 自连接
sql 聚集group by
spring boot 注解 怎么加载进来
网络协议 分层
DNS 哪一层
volatile 原理
原子性 是指什么?
Java 泛型 extend super 字节码?
路由器 交换机 集线器 (网段 冲突域)
HTTP 协议 和 TCP 协议 responce时 TCP 协议怎么知道 传输的是 HTTP协议
概率题 贝叶斯
未命名
选择排序
从数组中选择最小元素,将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换,它的运行时间与输入无关,这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
1 | public class Selection<T extends Comparable<T>> extends Sort<T> { |
冒泡排序
从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。
在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。
1 | public class Bubble<T extends Comparable<T>> extends Sort<T> { |
插入排序
每次都将当前元素插入到左侧已经排序的数组中,使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1},它具有以下逆序:(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1),插入排序每次只能交换相邻元素,令逆序数量减少 1,因此插入排序需要交换的次数为逆序数量。
插入排序的时间复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么逆序较少,需要的交换次数也就较少,时间复杂度较低。
- 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换;
- 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换,最坏的情况是数组是倒序的;
- 最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了。
1 | public class Insertion<T extends Comparable<T>> extends Sort<T> { |
希尔排序
对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素,每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性,它通过交换不相邻的元素,每次可以将逆序数量减少大于 1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h,最后令 h=1,就可以使得整个数组是有序的。
1 | public class Shell<T extends Comparable<T>> extends Sort<T> { |
希尔排序的运行时间达不到平方级别,使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
归并排序
归并排序的思想是将数组分成两部分,分别进行排序,然后归并起来。
归并方法将数组中两个已经排序的部分归并成一个。
1 | private static void merge(int[] arr,int left,int mid,int right,int[] temp){ |
1 | import java.util.Arrays; |
快速排序
https://www.cnblogs.com/chengxiao/p/6262208.html
1. 基本算法
- 归并排序将数组分为两个子数组分别排序,并将有序的子数组归并使得整个数组排序;
- 快速排序通过一个切分元素将数组分为两个子数组,左子数组小于等于切分元素,右子数组大于等于切分元素,将这两个子数组排序也就将整个数组排序了。
1 | public class QuickSort<T extends Comparable<T>> extends Sort<T> { |
2. 切分
取 a[l] 作为切分元素,然后从数组的左端向右扫描直到找到第一个大于等于它的元素,再从数组的右端向左扫描找到第一个小于它的元素,交换这两个元素。不断进行这个过程,就可以保证左指针 i 的左侧元素都不大于切分元素,右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时,将切分元素 a[l] 和 a[j] 交换位置。
1 | private int partition(T[] nums, int l, int h) { |
3. 性能分析
快速排序是原地排序,不需要辅助数组,但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分,这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N,复杂度为 O(NlogN)。
最坏的情况下,第一次从最小的元素切分,第二次从第二小的元素切分,如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的,在进行快速排序时需要随机打乱数组。
4. 算法改进
4.1 切换到插入排序
因为快速排序在小数组中也会递归调用自己,对于小数组,插入排序比快速排序的性能更好,因此在小数组中可以切换到插入排序。
4.2 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素,但是计算中位数的代价很高。一种折中方法是取 3 个元素,并将大小居中的元素作为切分元素。
https://www.cnblogs.com/chengxiao/p/6262208.html
1 | public class QuickSort { |
4.3 三向切分
对于有大量重复元素的数组,可以将数组切分为三部分,分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
1 | public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> { |
快速选择
快选 = 快排 + 二分查找
快速排序的 partition() 方法,会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j],且 a[j+1..h] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 个元素。
该算法是线性级别的,假设每次能将数组二分,那么比较的总次数为 (N+N/2+N/4+..),直到找到第 k 个元素,这个和显然小于 2N
Quick select
的average case时间复杂度为O(n)
,然而其worst case时间复杂度为O(n^2)
1 | public T select(T[] nums, int k) { |
堆排序
1. 堆
堆中某个节点的值总是大于等于其子节点的值,并且堆是一颗完全二叉树。
堆可以用数组来表示,这是因为堆是完全二叉树,而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2,而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置,是为了更清晰地描述节点的位置关系。
1 | public class Heap<T extends Comparable<T>> { |
2. 上浮和下沉
在堆中,当一个节点比父节点大,那么需要交换这个两个节点。交换后还可能比它新的父节点大,因此需要不断地进行比较和交换操作,把这种操作称为上浮。
1 | private void swim(int k) { |
类似地,当一个节点比子节点来得小,也需要不断地向下进行比较和交换操作,把这种操作称为下沉。一个节点如果有两个子节点,应当与两个子节点中最大那个节点进行交换。
1 | private void sink(int k) { |
3. 插入元素
将新元素放到数组末尾,然后上浮到合适的位置。
1 | public void insert(Comparable v) { |
4. 删除最大元素
从数组顶端删除最大的元素,并将数组的最后一个元素放到顶端,并让这个元素下沉到合适的位置。
1 | public T delMax() { |
5. 堆排序
把最大元素和当前堆中数组的最后一个元素交换位置,并且不删除它,那么就可以得到一个从尾到头的递减序列,从正向来看就是一个递增序列,这就是堆排序。
5.1 构建堆
无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作,如果一个节点的两个节点都已经是堆有序,那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作,可以忽略叶子节点的元素,因此只需要遍历一半的元素即可。
5.2 交换堆顶元素与最后一个元素
交换之后需要进行下沉操作维持堆的有序状态。
1 | public class HeapSort<T extends Comparable<T>> extends Sort<T> { |
6. 分析
一个堆的高度为 logN,因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序,由于要对 N 个节点进行下沉操作,因此复杂度为 NlogN。
堆排序是一种原地排序,没有利用额外的空间。
现代操作系统很少使用堆排序,因为它无法利用局部性原理进行缓存,也就是数组元素很少和相邻的元素进行比较和交换。
小结
1. 排序算法的比较
算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 备注 |
---|---|---|---|---|
选择排序 | × | N2 | 1 | |
冒泡排序 | √ | N ~ N2 | 1 | |
插入排序 | √ | N ~ N2 | 1 | 时间复杂度和初始顺序有关 |
希尔排序 | × | N1.3 | 1 | 改进版插入排序 |
快速排序 | × | NlogN~ N2 | logN | |
三向切分快速排序 | × | N ~ NlogN | logN | 适用于有大量重复主键 |
归并排序 | √ | NlogN | N | |
堆排序 | × | NlogN | 1 | 无法利用局部性原理 |
快速排序是最快的通用排序算法,它的内循环的指令很少,而且它还能利用缓存,因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN,这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序,实际应用中可能出现的某些分布的输入能够达到线性级别,而其它排序算法仍然需要线性对数时间。
2. Java 的排序算法实现
Java 主要排序方法为 java.util.Arrays.sort(),对于原始数据类型使用三向切分的快速排序,对于引用类型使用归并排序。
Top K 问题
https://xiaozhuanlan.com/topic/4176082593
快速选择解决
堆排序解决
使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素
寻找最大top k, 使用小顶堆,堆顶元素 是 当前第 k 大元素,是当前top k 的边界,可以用来判断下一个元素是否需要加入堆,那么 加入堆的操作非常少 时间复杂度 为 O(n)
若 寻找最大top k,使用大顶堆,堆顶元素不是边界,每一个元素都需加入堆,然后维护堆的大小,复杂度为O(logk * n)
时间复杂复分析
https://blog.csdn.net/so_geili/article/details/53444816#3
- 迭代法
- Master 定理
- 公式
- 比较大小
- 相等/ 大于 / 小于
刷题技巧
- 利用utils 暴力做
- 搜索leetcode
- 简单方法
- 复杂方法
- debug思路
- 边界
- 正负值
- 特殊情况
数据结构
二叉树
满二叉树
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树
完全二叉树
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
二叉查找树/二叉排序树
https://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html
二叉查找树的概念定义:(递归概念)
- 左子树上节点的值均 小于 根节点的值
- 右子树上节点的值均 大于 根节点的值
- 左右子树也是二叉查找树 (递归定义)
- 树中不存在键值相等的节点
查找操作:递归定义
查找时间复杂度:平衡 logN, 最差:树退化成list,N
插入操作:查找对应节点,若存在更新,不存在插入新节点
删除:调整
二叉查找树的最大值最小值:
最大值:最右节点
最小值:最左节点
平衡二叉树
其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树
AVL树
定义:
- 一棵空树或左个子树的高度差的绝对值不超过1
- 左右两个子树都是一棵平衡二叉树 (递归定义)
左旋 右旋
特点:
- 实现比较复杂
- 插入和删除性能差
- 在实际环境下的应用不如红黑树(接近平衡)
- 真正的平衡二叉树
- 在logN时间内做查找插入删除(logN的常量比红黑树的大)
红黑树
http://dandanlove.com/2018/03/18/red-black-tree/
https://juejin.im/post/5a27c6946fb9a04509096248#comment
5个特性(根节点,普通节点,叶子节点,路径红色,路径黑色),三种手段(变色,左旋,右旋),2个结果(接近平衡,logN),应用
本质:一种自平衡(接近平衡)的二叉查找树
动机: AVL树较为严格完全平衡,代价大,红黑树近似平衡,插入查找删除代价小;解决二叉查找树退化为线性的情况,只需要近似平衡就能取得较好的查找效果
规则:这些规则保持了红黑树的自平衡,插入删除元素时需要维持规则
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点。
- 每个红色节点的两个子节点都是黑色 / 从每个叶子到根的所有路径上不能有两个连续的红色节点
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
平衡性:
- 红黑树从根节点到叶子的最长路径不会超过最短路径的2倍
- 在 O(logn)时间内做查找,插入和删除
调整方式: 有三中方式,组合起来维护 红黑树的五个特点
- 变色
- 左旋
- 右旋
应用:
- Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等
- Java的TreeMap和TreeSet
- C++ STL的map、multimap、multiset
B树
https://yq.aliyun.com/articles/38345
https://blog.csdn.net/aqzwss/article/details/53074186
https://blog.csdn.net/bigtree_3721/article/details/73632405
核心思想:通过多路查找树 降低树高,降低查找复杂度
节点结构: 假设 M=3 也即最大路数为3
1 | Class Node{ |
B树的特点:
B树是一种多路搜索树
节点上 至多有M-1个关键字(1. 包含具体信息 2. 关键字数组index=0不使用)
每个父节点的孩子数在 [M/2,M] 之间;根节点的孩子数在[2,M] 之间
所有叶子结点位于同一层(因此插入元素时,当前叶子节点存不下后,进行分裂而不是向下增加一层) 自动层次控制
非叶子结点的关键字个数=指向儿子的指针个数-1
树高:$log_M (N+1)/2$ M路,N个关键字
其搜索性能等价于在关键字全集内做一次二分查找 (假设全部在内存中,用作文件)
推到过程:换底公式$log_a b = log_c b / log_c a$
$O(n) = log_M \frac{n-1}{2} · log_2 M$ 树高*节点内二分查找代价
$=\frac {log_2 \frac{n-1}{2}}{log_2 M} · log_2 M $
$= O(log_2 n)$
查找
查找过程:
- 顺序查找或者二分查找关键词
- 关键词是否等于带查找元素: 若是则找到
- 从磁盘中载入 关键词对应的子节点
- 递归查找
节点内对关键词列表 采用 顺序查找 或者 二分查找,时间复杂度为O(M)
节点外主要为磁盘IO时间,次数不超过树高$h=log_M (N-1)/2$ 时间复杂度为 O(h)
总的时间复杂度为$O(M·h)$
插入
- 插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束(不会向下添加新的叶子节点,增加一层,保持所有叶子节点都在一层这一性质)
- 然后在叶子结点中插入该新的元素
- 如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素
- 如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中
- 如果父结点空间满了,也同样需要“分裂”操作,向上传导,如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层
删除
首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,如果删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的第一个或者最后一个元素到父节点中,如果没有,直接删除。
B+树
核心:B+-tree是应文件系统所需而产生的一种B-tree的变形树,B树节点带有关键字以及关键字数据的指针,B+树非叶子节点只包含关键字本身在树高相等情况下,B+树所需要的磁盘IO数小于B树
特点:相比于B树
- 所有的叶子结点中包含了全部关键字(不包含数据本身,只是包含指向含有这些关键字记录的指针(而B 树的叶子节点并没有包括全部需要查找的信息)
- 叶子结点本身依关键字的大小自小而大的顺序链接
为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?
B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。
如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多
一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)
B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当
B+树方便扫库,对数据库全部遍历/ 支持区间查询
B+树1. 所有关键字都在叶子节点上 2. 叶子节点之间有指针相连接 3. 可以直接从叶子节点扫库 4. 查找区间首尾节点后,通过叶子节点的指针可以区间查询
B树 1. 叶子节点不包括所有的关键字 2. 叶子节点间没有指针 3 需要采用中序遍历的方式才能扫库 4. 区间查询不友好,需要中序遍历
B*树
B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),
B 树定义了非叶子结点关键字个数至少为(2/3)M,即块的最低使用率为2/3(代替B+树的1/2)
B* 树中非根和非叶子结点再增加指向兄弟的指针;
B*树分配新结点的概率比B+树要低,空间使用率更高
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分
数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字
(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之
间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据
复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父
结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
LSM树
https://www.cnblogs.com/yanghuahui/p/3483754.html
https://blog.csdn.net/dbanote/article/details/8897599
LSM树的设计思想非常朴素:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,不过读取的时候稍微麻烦,需要合并磁盘中历史数据和内存中最近修改操作,所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。极端的说,基于LSM树实现的HBase的写性能比Mysql高了一个数量级,读性能低了一个数量级。
霍夫曼树/霍夫曼编码
docker学习
Java 基础
一、数据类型
基本类型
- byte/8
- char/16
- short/16
- int/32
- float/32
- long/64
- double/64
- boolean/~
boolean 只有两个值:true、false,可以使用 1 bit 来存储,但是具体大小没有明确规定。JVM 会在编译时期将 boolean 类型的数据转换为 int,使用 1 来表示 true,0 表示 false。JVM 并不支持 boolean 数组,而是使用 byte 数组来表示 int 数组来表示。
包装类型
基本类型都有对应的包装类型,基本类型与其对应的包装类型之间的赋值使用自动装箱与拆箱完成。
1 | Integer x = 2; // 装箱 |
Java中的不可变类型 与 可变类型
概念:不可变对象(Immutable Objects)即对象一旦被创建它的状态(对象的数据,也即对象属性值)就不能改变,反之即为可变对象(Mutable Objects)
不可变对象的特点:如果一个类符合以下特点,那么immutable
- 类的成员变量 应该是 immutable的 // 比如 基本数据类型 或者 包装类型
- 类的成员变量不能被修改
- 都被final修饰
- 都是 private的,且 没有提供setter方法
- 类不能被继承:被继承之后 可以添加setter或者能够改变类成员的方法
- 类被final修饰
- 使用静态工厂方法并且声明构造器为private
- 如果成员变量是可变类型(尽管被final修饰,这仅仅意味引用不可变,但是该成员对象内的成员可变),必须在向外部调用者提供该对象时 进行保护性拷贝
具体见例子代码:
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
49import java.util.Date;
// Planet是一个不可变类,因为当它构造完成之后没有办法改变它的状态
public final class Planet {
//声明为final的基本类型数据总是不可变的
private final double fMass;
//声明为final的不可变数据总是不可变的
private final String fName;
//Date是 可变类型 尽管被final修饰,这仅仅意味引用不可变,但是该对象内的成员可变
private final Date fDateOfDiscovery;
public Planet(double aMass, String aName, Date aDateOfDiscovery) {
fMass = aMass;
fName = aName;
//创建aDateOfDiscovery的一个私有拷贝
//这是保持fDateOfDiscovery属性为private的唯一方式, 并且保护这个
//类不受调用者对于原始aDateOfDiscovery对象所做任何改变的影响
fDateOfDiscovery = new Date(aDateOfDiscovery.getTime());
}
// 返回不可变对象(基本类型,String,包装类型...),外部的改变无法影响内部
public double getMass() {
return fMass;
}
public String getName() {
return fName;
}
/**
* 返回一个可变对象 - 好的方式.
*
* 返回属性的一个保护性拷贝.调用者可以任意改变返回的Date对象,但是不会
* 影响类的内部.为什么? 因为它们没有fDate的一个引用. 更准确的说, 它们
* 使用的是和fDate有着相同数据的另一个Date对象
*/
public Date getDateOfDiscovery() {
//外部调用者 尽管不能将该对象替换成另一个对象,但能修改对象的内部成员,不可取
//return fDateOfDiscovery;
//应该对原对象进行拷贝,生成一个新对象,从而外界的改变无法影响内部
return new Date(fDateOfDiscovery.getTime());
}
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
Planet planet = new Planet(1.0D, "earth", new Date());
Date date = planet.getDateOfDiscovery();
date.setTime(111111111L);
System.out.println("the value of fDateOfDiscovery of internal class : " + planet.fDateOfDiscovery.getTime());
System.out.println("the value of date after change its value : " + date.getTime());
}
Java中常见的不可变类型:
- 基本类型 是 可变类型/ 被final修饰 或者 不提供setter等改变其值的private基本类型是 不可变
- 基本类型的包装类型:Long , Float ,Integer
- String
- BigInteger ,BigDecimal // BigDecimal 从技术上讲不是不可变的, 因为它没有声明为final
类应该是不可变的,除非有很好的理由让它是可变的….如果一个类不能设计为不可变的,也要尽可能的限制它的可变性 — Effective Java // 应该尽量让一个类 成为不可变的,因为开发人员潜意识里总认为 引用不变即等于类不变,不可变类型 能够有效降低出错概率