事务学习笔记

Posted on 2018-11-07

java学习笔记-多线程

Posted on 2018-10-24 | Edited on 2018-11-07

目录：
一、创建及启动线程
二、线程状态切换
三、线程安全（volatile，reentrantLock，syncrhoized）
四、线程池
五、concurrent 包

一、创建及启动线程

1. 实现Runnable接口

1.定义Runnable接口的实现类，一样要重写run()方法，这个run（）方法和Thread中的run()方法一样是线程的执行体
2.创建Runnable实现类的实例，并用这个实例作为Thread的target来创建Thread对象，这个Thread对象才是真正的线程对象
3.通过调用线程对象的start()方法来启动线程

public  class Runner1 implements Runnable {
     public void run(){
       for(int i=0;i<100;i++)  {
           System.out.println("runner1: " +i);
       }
     }
}

public static void main(String args[]) {
    Runner1 r1 = new Runner1();
    //r1.run();此处视为方法调用，等run方法执行完毕后才进行main（）方法操作。
    Thread t = new Thread(r1);
    t.start();
    for (int i = 0; i < 10; i++) {
        System.out.println("main thread：" + i);
    }
}

此时新线程和主线程交替打印。

2. 继承thread类

1.定义Thread类的子类，并重写该类的run()方法，该方法的方法体就是线程需要完成的任务，run()方法也称为线程执行体。
2.创建Thread子类的实例，也就是创建了线程对象
3.调用线程的start()方法启动线程

public class Runner2 extends Thread {
    public void run(){
        for(int i=0;i<100;i++)  {
            System.out.println("runner2: " +i);
        }
    }
}

public static void main(String args[] ){

     Runner2 r2=new Runner2();
     r2.start();
     
     for (int i = 0; i < 10; i++) {
         System.out.println("main thread：" + i);
     }

 }

3. 实现callable接口

1.创建Callable接口的实现类，并实现call()方法，然后创建该实现类的实例（从java8开始可以直接使用Lambda表达式创建Callable对象）。
2.使用FutureTask类来包装Callable对象，该FutureTask对象封装了Callable对象的call()方法的返回值
3.使用FutureTask对象作为Thread对象的target创建并启动线程（因为FutureTask实现了Runnable接口）
4.调用FutureTask对象的get()方法来获得子线程执行结束后的返回值

 public static void main(String[] args) {
        Runner3 td = new Runner3();
        FutureTask<Integer> result = new FutureTask<>(td);
        new Thread(result).start();
        try {
            Integer sum = result.get();  
//FutureTask 可用于 闭锁 类似于CountDownLatch的作用，在所有的线程没有执行完成之后这里是不会执行的
            System.out.println(sum);
            System.out.println("------------------------------------");
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
    }

public class Runner3 implements Callable<Integer> {

    @Override
    public Integer call() throws Exception {
        int sum = 0;

        for (int i = 0; i <= 100000; i++) {
            sum += i;
        }
        return sum;
    }

}

二、线程状态切换

1. sleep()

sleep()方法需要指定等待的时间,它可以让当前正在执行的线程在指定的时间内暂停执行，进入阻塞状态。可以让其他同优先级或者高优先级的线程得到执行的机会，也可以让低优先级的线程得到执行机会。但是sleep()方法不会释放“锁标志”，也就是说如果有synchronized同步块，其他线程仍然不能访问共享数据。

2.yield()

　yield()方法和sleep()方法类似，也不会释放“锁标志”，区别在于，它没有参数，即yield()方法只是使当前线程重新回到可执行状态，所以执行yield()的线程有可能在进入到可执行状态后马上又被执行，另外yield()方法只能使同优先级或者高优先级的线程得到执行机会，这也和sleep()方法不同。

3.join()

join()方法会使当前线程等待调用join()方法的线程结束后才能继续执行.

4.notify()&notifyALL()

先说两个概念：锁池和等待池
● 锁池:假设线程A已经拥有了某个对象(注意:不是类)的锁，而其它的线程想要调用这个对象的某个synchronized方法(或者synchronized块)，由于这些线程在进入对象的synchronized方法之前必须先获得该对象的锁的拥有权，但是该对象的锁目前正被线程A拥有，所以这些线程就进入了该对象的锁池中。
● 等待池:假设一个线程A调用了某个对象的wait()方法，线程A就会释放该对象的锁后，进入到了该对象的等待池中。
然后再来说notify和notifyAll的区别：
● 如果线程调用了对象的wait()方法，那么线程便会处于该对象的等待池中，等待池中的线程不会去竞争该对象的锁。
● 当有线程调用了对象的 notifyAll()方法（唤醒所有 wait 线程）或 notify()方法（只随机唤醒一个 wait 线程），被唤醒的的线程便会进入该对象的锁池中，锁池中的线程会去竞争该对象锁。也就是说，调用了notify后只要一个线程会由等待池进入锁池，而notifyAll会将该对象等待池内的所有线程移动到锁池中，等待锁竞争优先级高的线程竞争到对象锁的概率大，假若某线程没有竞争到该对象锁，它还会留在锁池中，唯有线程再次调用 wait()方法，它才会重新回到等待池中。而竞争到对象锁的线程则继续往下执行，直到执行完了 synchronized 代码块，它会释放掉该对象锁，这时锁池中的线程会继续竞争该对象锁。
综上，所谓唤醒线程，另一种解释可以说是将线程由等待池移动到锁池，notifyAll调用后，会将全部线程由等待池移到锁池，然后参与锁的竞争，竞争成功则继续执行，如果不成功则留在锁池等待锁被释放后再次参与竞争。而notify只会唤醒一个线程。有了这些理论基础，后面的notify可能会导致死锁，而notifyAll则不会的例子也就好解释了。

三、线程安全（volatile，reentrantLock，syncrhoized）

四、线程池

五、concurrent 包

jvm学习笔记-原理篇

Posted on 2018-10-24 | Edited on 2018-11-16 | In java

参考文档：
https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html
https://blog.csdn.net/hellozhxy/article/details/80649342

一、jvm内存结构

1. heap堆

堆是内存管理里最大的一块，是线程共享的数据。在jvm启动时创建。
目的是存放对象实例。java的引用传递依靠的就是堆内存，例如引用类型的变量是在栈区保存一个指向堆区的指针，通过这个指针可以找到实例在堆区对应的对象。同一块堆内存可以被不同的栈内存所指向。
堆内部细分为新生代和老年代。

新生代

新生代是用于存储新生对象，分为Eden，From survior，TO survior，hotspot虚拟机中默认比例是8:1:1，当新生代存储满是会发生MinorGC。

MinorGC

对象从Young generation区域消失的过程我们称之为MinorGC。

MinorGC的过程：MinorGC采用复制算法。首先，把Eden和ServivorFrom区域中存活的对象复制到ServicorTo区域（如果有对象的年龄以及达到了老年的标准，则赋值到老年代区），同时把这些对象的年龄+1（如果ServicorTo不够位置了就放到老年区）；然后，清空Eden和ServicorFrom中的对象；最后，ServicorTo和ServicorFrom互换，原ServicorTo成为下一次GC时的ServicorFrom区。

所有的 Minor GC 都会触发“全世界的暂停（stop-the-world）”，停止应用程序的线程。

老年代

主要存放应用程序中生命周期长的内存对象。

MajorGC

对象从old generation区域消失的过程我们称之为MajorGC。
老年代的对象比较稳定，所以MajorGC不会频繁执行。在进行MajorGC前一般都先进行了一次MinorGC，使得有新生代的对象晋身入老年代，导致空间不够用时才触发。当无法找到足够大的连续空间分配给新创建的较大对象时也会提前触发一次MajorGC进行垃圾回收腾出空间。

MajorGC采用标记—清除算法：首先扫描一次所有老年代，标记出存活的对象，然后回收没有标记的对象。MajorGC的耗时比较长，因为要扫描再回收。MajorGC会产生内存碎片，为了减少内存损耗，我们一般需要进行合并或者标记出来方便下次直接分配。

当老年代也满了装不下的时候，就会抛出OOM（Out of Memory）异常。
MajorGC也会触发STW，STW的时间取决于老年代垃圾收集器的种类。

FullGC

full gc清理整个堆空间

2. 方法区（永久代）

方法区逻辑上属于堆的一部分，但是为了与堆进行区分，通常又叫“非堆”。方法区又称为永久代，线程共享，目的是存放已被jvm加载的类信息，常量，静态变量，即时编译器编译后的代码等数据，垃圾回收在这个区域比较少，主要目的是对常量池的回收和类的卸载。

运行时常量池

运行时常量池是方法区的一部分，用于存储编译器产生的字面量和符号引用，这类内容类加载后被存储到方法区的rcp。
在JDK8中废弃了永久代，替换为Metaspace(本地内存中)

3. JVM Stack

JVM栈是线程私有的，它的生命周期与线程相同。JVM栈描述的是java方法执行的内存模型，每个方法在执行的同时都会创建一个栈帧，用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每个方法从调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。
局部变量表中存放了编译期可知的各种基本数据类型（boolean、byte、char、short、int、float、long、double）、对象的引用类型（reference类型，不等同于对象本身，根据不同的虚拟机实现，可能是一个指向对象起始地址的引用指针，也可能是一个代表对象的句柄或者其他与对象相关的位置）。局部变量表中需要的内存空间在编译期间完成分配，当进入一个方法时，这个方法需要在帧中分配多大的局部变量空间是完全确定的，在方法运行期间不会改变局部变量表的大小。

4. 本地方法栈

与VM Strack相似，VM Strack为JVM提供执行JAVA方法的服务，Native Method Stack则为JVM提供使用native 方法的服务。

5. 程序计数器

程序计数器是一块较小的内存区域，作用可以看做是当前线程执行的字节码的位置指示器。分支、循环、跳转、异常处理和线程恢复等基础功能都需要依赖这个计算器来完成

二、Java 类加载机制

加载
⬇️
验证➡️准备➡️解析
           ⬇️
           初始化
           ⬇️
           使用
           ⬇️
           卸载

类加载的过程包括了加载、验证、准备、解析、初始化五个阶段。

隐式加载
程序在运行过程中当碰到通过new 等方式生成对象时，隐式调用类装载器加载对应的类到jvm中
显式加载
通过class.forname()等方法，显式加载需要的类

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

类加载器

jvm通过类加载器把数据加载到内存

1.启动类加载器Bootstrp loader

Bootstrp加载器是用C++语言写的，它是在Java虚拟机启动后初始化的，它主要负责加载%JAVA_HOME%/jre/lib,-Xbootclasspath参数指定的路径以及%JAVA_HOME%/jre/classes中的类。

2.扩展类加载器ExtClassLoader

Bootstrp loader加载ExtClassLoader,并且将ExtClassLoader的父加载器设置为Bootstrp loader。
主要加载%JAVA_HOME%/jre/lib/ext，此路径下的所有classes目录以及java.ext.dirs系统变量指定的路径中类库。

3.应用程序类加载器AppClassLoader

Bootstrp loader加载完ExtClassLoader后，就会加载AppClassLoader,并且将AppClassLoader的父加载器指定为 ExtClassLoader。
ClassLoader中有个getSystemClassLoader方法,此方法返回的正是AppclassLoader.AppClassLoader主要负责加载classpath所指定的位置的类或者是jar文档，它也是Java程序默认的类加载器。

示例：

public class JVMTest {
    public static void main(String[] args) {
        ClassLoader  loader = JVMTest.class.getClassLoader();
        System.out.println(loader);
        ClassLoader loderp =loader.getParent();
        System.out.println(loderp);
        ClassLoader loaderpp =loderp.getParent();
        System.out.println(loaderpp);

    }
}

运行结果：

1
2
3

sun.misc.Launcher$AppClassLoader@135fbaa4
sun.misc.Launcher$ExtClassLoader@2503dbd3
null

由于Bootstrap Loader是用C++语言写的，并不存在类实体，所以打印为null。

类加载模型：双亲委派

这个模型要求除了Bootstrap ClassLoader外，其余的类加载器都要有自己的父加载器。子加载器通过组合来复用父加载器的代码，而不是使用继承。在某个类加载器加载class文件时，它首先委托父加载器去加载这个类，依次传递到顶层类加载器(Bootstrap)。如果顶层加载不了（它的搜索范围中找不到此类），子加载器才会尝试加载这个类。

双亲委派模型解决的问题：

每一个类都只会被加载一次，避免了重复加载
每一个类都会被尽可能的加载（从引导类加载器往下，每个加载器都可能会根据优先次序尝试加载它）
有效避免了某些恶意类的加载（比如自定义了Java。lang.Object类，一般而言在双亲委派模型下会加载系统的Object类而不是自定义的Object类）

三、方法执行过程

四、java大版本新特性

数据结构-栈

Posted on 2018-10-12

java学习笔记-synchronized

Posted on 2018-10-07 | Edited on 2018-10-29

杨晓峰老师《java核心技术36讲》15，16课&郑雨迪老师《深入拆解java虚拟机》14课学习总结

参考文章：https://www.cnblogs.com/charlesblc/p/5994162.html

synchronized的实现原理

在java程序中，我们利用synchronized关键字来对程序进行加锁，它可以申明一个synchronized代码块，也可以标记静态方法或者实例方法。

1.声明synchronized 代码块

是由一对 monitorenter/monitorexit指令实现的，monitor 对象是同步的基本实现单元。

例如：

public void foo(Object lock) {
  synchronized (lock) {
    lock.hashCode();
  }
}

这段代码编译的字节码会包括一个monitorenter指令和多个monitorexit，jvm需要确保所获得的锁在正常/异常执行路径都能够被解锁。

执行monitorenter时

如果目标锁的计数器为0，说明他没有被其他线程所持有，jvm会将锁对象的持有线程设置为当前线程，并将计数器加1.
如果目标锁的计数器不为0，如果锁对象的持有线程是当前线程，jvm可以将计数器加1，否则等待，直到持有线程释放该锁。

执行monitorexit时，jvm将锁对象的计数器减1，如果计数器为0，代表锁已经被释放。

2.用synchronized标记方法

例如：

1
2
3

public synchronized void foo(Object lock) {
  lock.hashCode();
}

这段代码编译的字节码中方法的访问有ACC_SYNCHRONIZED。但是没有monitorenter或者monitorexit。

因为方法级别的同步是隐式的，它实现在方法调用和返回操作之中。虚拟机可以从方法常量池中的方法表结构（method_info structure）中的 ACC_SYNCHRONIZED 访问标志区分一个方法是否是同步方法。

当调用方法时，调用指令将会检查方法的 ACC_SYNCHRONIZED 访问标志是否设置，如果设置了，执行线程先持有同步锁，然后执行方法，最后在方法完成时释放锁。

锁的升级降级

jvm 提供三种不同的Monitor实现，即偏斜锁，轻量锁，重量锁。
当jvm检测到不同的竞争状况时，会自动切换到适合的锁实现，这就是锁的升级降级。
当没有竞争出现时，默认使用偏斜锁。

其中，00代表轻量锁，01代表无锁（或者偏向锁），10代表重量锁，11则根垃圾回收算法的标记有关。

在所有的锁都启用的情况下线程进入临界区时会先去获取偏向锁，如果已经存在偏向锁了，则会尝试获取轻量级锁，如果以上两种都失败，则启用自旋锁，如果自旋也没有获取到锁，则使用重量级锁，没有获取到锁的线程阻塞挂起，直到持有锁的线程执行完同步块唤醒他们；

重量锁

重量锁会阻碍加锁失败的线程，并在目标锁被释放时唤醒这些线程。
为了避免昂贵的线程阻塞，唤醒的过程，jvm会在线程进入阻塞状态之前，以及被唤醒后竞争不到锁的情况下，进入自旋状态，在处理器上空跑并轮询锁是否释放，如果此时锁恰好被释放了，那线程便无须进入阻塞状态，直接获得这把锁。

轻量锁

轻量级锁是相对于重量级锁而言在获取锁和释放锁时更加高效，但轻量级锁并不能代替重量级锁。轻量级锁适用的场景是在线程交替获取某个锁执行同步代码块的场景，如果出现多个进程同时竞争同一个锁时，轻量级锁会膨胀成重量级锁。

轻量锁采用CAS操作，把锁对象的标记字段替换成一个指针，指向当前线程栈上的一块空间，存储这锁对象原本的标记字段。

偏向锁

偏向锁只会在第一次请求是采用CAS操作，在锁对象的标记字段中记录下当前线程的地址，在之后的运行过程中，持有该偏向锁的线程的加锁操作将直接返回。

锁	适用场景	优点	缺点
重量锁	多个线程同时进入临界区	线程竞争不使用自旋不消耗cpu，吞吐量高	线程阻塞，响应缓慢
轻量锁	多个线程交替进入临界区	竞争的线程不会阻塞，响应速度快	如果始终得不到锁竞争的线程使用自旋会消耗cpu
偏向锁	仅有一个线程进入临界区	加锁和解锁不需要额外的消耗	如果线程间存在锁竞争，会带来额外的锁撤销的消耗

ReentrantLock和synchronized的区别

1.用法比较

Lock使用起来比较灵活，但是必须有释放锁的配合动作
Lock必须手动获取与释放锁，而synchronized不需要手动释放和开启锁
Lock只适用于代码块锁，而synchronized可用于修饰方法、代码块等

2.特性比较

ReentrantLock的优势体现在：

具备尝试非阻塞地获取锁的特性：当前线程尝试获取锁，如果这一时刻锁没有被其他线程获取到，则成功获取并持有锁
能被中断地获取锁的特性：与synchronized不同，获取到锁的线程能够响应中断，当获取到锁的线程被中断时，中断异常将会被抛出，同时锁会被释放
超时获取锁的特性：在指定的时间范围内获取锁；如果截止时间到了仍然无法获取锁，则返回

3.注意事项

在使用ReentrantLock类的时，一定要注意三点：

在finally中释放锁，目的是保证在获取锁之后，最终能够被释放
不要将获取锁的过程写在try块内，因为如果在获取锁时发生了异常，异常抛出的同时，也会导致锁无故被释放。
ReentrantLock提供了一个newCondition的方法，以便用户在同一锁的情况下可以根据不同的情况执行等待或唤醒的动作。

数据结构-链表

Posted on 2018-10-06 | Edited on 2018-10-12

王争老师的《数据结构与算法之美》06-07课链表学习总结

一、什么是链表？

和数组一样，链表也是一种线性表。
从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

二、链表的特点

插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

三、常用链表：单链表、循环链表和双向链表

1. 单链表

private class Node {
    private Object data;        //数据
    private Node next = null;  //指针域

    public Node() {                         //无参数构造函数为了创建头结点服务
        data = null;
    }

    public Node(E data) {                //带数据的构造函数
        this.data = data;
    }
        
}

    private Node head;               //头引用（指针）
    private Node tail;                //尾引用（指针）
    private Node point;              //临时引用（指针）
    private int length;                 
    //链表长度

    public nodeList() {                  //链表构造函数，创建无数据的头结点
        head = new Node();
        tail = head;
        length = 0;
    }

    }

单链表的插入

让p的后继结点改成s的后继结点，再把结点s变成p的后继结点

s->next=p->next; p->next=s;
具体实现如下:

public void insert(int position, E elem) {
    if (position >= 0 && position <= length) {
        point = movePoint(position);
        Node tmp = new Node(elem);
        tmp.next = point.next;
        point.next = tmp;
        length++;
    } else {
        System.out.println("没有指定位置，插入失败");
    }

}

每个节点只包含一个指针，即后继指针。
单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。
2. 循环链表
除了尾节点的后继指针指向首节点的地址外均与单链表一致。
适用于存储有循环特点的数据，比如约瑟夫问题。
3.双向链表
节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
首节点的前驱指针prev和尾节点的后继指针均指向空地址。
性能特点：和单链表相比，存储相同的数据，需要消耗更多的存储空间。

插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：

给定数据值删除对应节点。
给定节点地址删除节点。

对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。

对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表

首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

四、选择数组还是链表？

1. 插入、删除和随机访问的时间复杂度

数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。

链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2. 数组缺点

1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。

2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点

1）内存空间消耗更大，因为需要额外的空间存储指针信息。

2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

4.如何选择？

数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。

如果代码对内存的使用非常苛刻，那数组就更适合。

五、应用

1. 如何分别用链表和数组实现LRU缓冲淘汰策略？

1）什么是缓存？
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

2）为什么使用缓存？即缓存的特点
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。

3）什么是缓存淘汰策略？
指的是当缓存被用满时清理数据的优先顺序。

4）有哪些缓存淘汰策略？
常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

5）链表实现LRU缓存淘汰策略
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。

6）数组实现LRU缓存淘汰策略

方式一：首位置保存最新访问数据，末尾位置优先清理
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。

方式二：首位置优先清理，末尾位置保存最新访问数据
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如上海自来水来自海上）

1）前提：字符串以单个字符的形式存储在单链表中。

2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。

3）将链表中的字符倒序存储一份在另一个链表中。

4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。

六、设计思想

时空替换思想：“用空间换时间” 与 “用时间换空间”
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

七、写链表时的注意项

如果链表为空时，代码是否能正常工作？
如果链表只包含一个节点时，代码是否能正常工作？
如果链表只包含两个节点时，代码是否能正常工作？
代码逻辑在处理头尾节点时是否能正常工作？

leetcode刷题-树

Posted on 2018-10-06

简单题

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路：
先判空树，然后比较两树的结点值是否相同，再判断p左树空，q左树不空，q右树空，p右树不空的情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean flag = true;
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
            return true;
        if((p != null && q == null) || (p == null && q != null))
            return false;
 
        isSame(p,q);
        return flag;
    }
    
    public void isSame(TreeNode p, TreeNode q){
        if(p.val != q.val){
            flag = false;
        }
 
        if ((p.left == null && q.left != null) || (p.left != null && q.left == null))
            flag = false;
 
        if (p.left != null && q.left != null){
            isSame(p.left,q.left);
        }
 
        if ((p.right == null && q.right != null) || (p.right != null && q.right == null))
            flag = false;
 
        if (p.right != null && q.right != null){
            isSame(p.right,q.right);
        }
 
    }
}

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

递归法

class Solution {
     public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return checkNodes(root.left, root.right);
    }

    public boolean checkNodes(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        } else {
            return checkNodes(node1.left, node2.right) && checkNodes(node1.right, node2.left);
        }
    }


}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7],深度是3

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    } else {
      int left_height = maxDepth(root.left);
      int right_height = maxDepth(root.right);
      return java.lang.Math.max(left_height, right_height) + 1;
    }
  }

}

迭代

解题思路：
所以我们从包含根结点且相应深度为 1 的栈开始。然后我们继续迭代：将当前结点弹出栈并推入子结点。每一步都会更新深度。

import javafx.util.Pair;
import java.lang.Math;

class Solution {
  public int maxDepth(TreeNode root) {
    Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root != null) {
      stack.add(new Pair(root, 1));
    }

    int depth = 0;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      int current_depth = current.getValue();
      if (root != null) {
        depth = Math.max(depth, current_depth);
        stack.add(new Pair(root.left, current_depth + 1));
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return depth;
  }
};

107. 二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

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

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

public List<List<Integer>> levelOrderBottom(TreeNode root) {
      LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

      if (root == null) {
          return result;
      }
      Queue<TreeNode> queue = new LinkedList<TreeNode>();
      queue.add(root);
      int i = queue.size(); // 记录每层的结点个数
      TreeNode tempNode = null;
      List<Integer> singleLevel = new ArrayList<>();
      while (!queue.isEmpty()) {
          if (i == 0) {// 一层记录结束
              //
              result.addFirst(singleLevel);

              i = queue.size();
              singleLevel = new ArrayList<>();
          }
          tempNode = queue.poll();
          singleLevel.add(tempNode.val);

          --i;

          if (tempNode.left != null) {
              queue.add(tempNode.left);
          }
          if (tempNode.right != null) {
              queue.add(tempNode.right);
          }

      }
      result.addFirst(singleLevel);
      return result;
  }

递归

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

    levelRecursion(root, result, 0);

    return result;
}

/**
 * 递归方法
 */
private void levelRecursion(TreeNode node,
        LinkedList<List<Integer>> result, int level) {
    if (node == null) {
        return;
    }
    if (result.size() < level + 1) {// 说明还需要添加一行
        result.addFirst(new ArrayList<Integer>());
    }
    result.get(result.size() - 1 - level).add(node.val);

    levelRecursion(node.left, result, level + 1);
    levelRecursion(node.right, result, level + 1);
}

基础回顾

树的遍历(DFS思想)

     A
    / \
   B   C
 /  \  / \
D   E  F  G   
\
H

中序遍历:左子树——》根节点——》右子树

public void infixOrder(Node current){
    if(current != null){
        infixOrder(current.leftChild);
        System.out.print(current.data+" ");
        infixOrder(current.rightChild);
    }
}

前序遍历:根节点——》左子树——》右子树

public void preOrder(Node current){
    if(current != null){
        System.out.print(current.data+" ");
        preOrder(current.leftChild);
        preOrder(current.rightChild);
    }
}

后序遍历:左子树——》右子树——》根节点

public void postOrder(Node current){
    if(current != null){
        postOrder(current.leftChild);
        postOrder(current.rightChild);
        System.out.print(current.data+" ");
    }
}

leetcode刷题-数组

Posted on 2018-09-27

简单题

1.给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0,1]。

暴力法

class Solution {
   public int[] twoSum(int[] nums, int target) {
       for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j] == target){
                return new int[] {i,j};
                
            }
        }
       }
      throw new IllegalArgumentException("No two sum solution");  
       
   }

}

两遍哈希表

在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i]nums[i] 本身！

class Solution {
   public int[] twoSum(int[] nums, int target) {
       Map<Integer,Integer> map = new HashMap<>();
       for(int i=0;i< nums.length;i++){
           map.put(nums[i],i);
       }
       for(int i=0;i<nums.length;i++){
          int complement = target - nums[i];
           if(map.containsKey(complement) && map.get(complement)!=i){
              return new int[]{ i,map.get(complement) }; 
           }
               
       }
           
     throw new IllegalArgumentException("No two sum solution");  
   }

}

一遍哈希表

在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

 class Solution {
   public int[] twoSum(int[] nums, int target) {
       Map<Integer,Integer> map = new HashMap<>();
       for(int i=0;i<nums.length;i++){
          int complement = target - nums[i];
           if(map.containsKey(complement)){
              return new int[]{ map.get(complement) ,i}; 
           }
            map.put(nums[i],i);
       }
           
     throw new IllegalArgumentException("No two sum solution");  
   }

}

leetcode刷题-链表

Posted on 2018-09-27 | Edited on 2018-10-03

简单题

21.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

eg:输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路：每次都取两个中较小的一个，直到其中一个遍历到链表结尾结束遍历。如果这个时候还是剩下的元素，肯定比之前的元素都大，直接添加到链表结尾。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)
        {
            return l2;
        }
        if(l2 ==null)
        {
            return l1;
        }
        ListNode merged =null;
        ListNode head =null;
        while(l1!=null &&l2!=null){
            if(head ==null){
                if(l1.val <l2.val){
                    merged =l1;
                    l1=l1.next;
                    
                }else{
                    merged =l2;
                    l2=l2.next;
                }
                head =merged;
                continue;
            }
            if(l1.val<l2.val){
                merged.next =l1;
                l1 =l1.next;
            }else{
                merged.next =l2;
                l2=l2.next;
            }
            merged =merged.next;
        }
        while(l1 !=null){
            merged.next =l1;
            l1=l1.next;
            merged=merged.next;
        }
        while(l2 !=null){
            merged.next =l2;
            l2=l2.next;
            merged=merged.next;
        }
        return head;
    }
}

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解题思路：如果是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current =head;
        while(current !=null&&current.next !=null ){
            if(current.val==current.next.val){
                current.next=current.next.next;}
            
                else{
                    current=current.next;
                }
}
           return head;    
        }
             
    }

141. 环形链表

给定一个链表，判断链表中是否有环。

hash法

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

双向链表

通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至O(1)O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

//查询是否有环（双向链表）
public boolean hasCycle1(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路：如果A和B是两个长度不同的链表，他们相交前的长度一定是不同的，计算链表长度差额n，让长的链表指针先开始移动n，两个指针再一起移动，指针相遇时就是链表结点的相交处

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA=calcListLength(headA);
        int lengthB=calcListLength(headB);
        int lenc=lengthA-lengthB;
     
        
        for(int i=0;i<Math.abs(lenc);i++){
            if(lenc>0)
            {
                headA=headA.next;
            }
            else{
                headB=headB.next;
            }
        }
        while( headA !=null && headB !=null){
            if(headA == headB){
                return headA;
            }
          
            headA=headA.next;
            headB=headB.next;
    
    }   
        return null;
    }
    
    public int calcListLength(ListNode Node){
        ListNode head=Node;
        int i=0;
        while(head !=null){
            head=head.next;
            i++;
        }
        return i;
    }
    
    
    
}

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

迭代法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) { //先考虑链表是否为空
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        p1.next = null;
        while (p2 != null) {
            ListNode temp = p2.next;
            //设置一个tmp指针指向后续
            p2.next = p1;
            //p2指针反转
            p1 = p2;
            //p1指针向前进
            p2 = temp;  
            //p2指针向前进
        }
        return p1;
    }
}

递归法

解题思路：
假设1->2->3->4->5->null
已经变成1->2<-3<-4<-5<-null

2是head.next

2的后继是head.next.next

我们希望2的后继指向head所以是head=head.next.next

再去除1->2的环head.next=null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode subListHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return subListHead;
    }
}

中等题

2. 两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

非递归解法

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
               ListNode dummyHead = new ListNode(0);
               ListNode p = l1, q = l2, curr = dummyHead;
               int carry = 0;
               while (p != null || q != null) {
                   int x = (p != null) ? p.val : 0;
                   int y = (q != null) ? q.val : 0;
                   int sum = carry + x + y;
                   carry = sum / 10;
                   curr.next = new ListNode(sum % 10);
                   curr = curr.next;
                   if (p != null) p = p.next;
                   if (q != null) q = q.next;
               }
               if (carry > 0) {
                   curr.next = new ListNode(carry);
               }
               return dummyHead.next;
           }

递归写法

class Solution {
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }
    int value = l1.val + l2.val;
    ListNode result = new ListNode(value % 10);
    //节点相加
    result.next = addTwoNumbers(l1.next, l2.next);
    //节点相加的结果和余数相加.
    if (value >= 10) {
        result.next = addTwoNumbers(new ListNode(value / 10),
                      result.next);
    }
    return result;
}
}

基础回顾

ListNode的类结构

public class ListNode
{
    int val;//定义val变量值，存储节点值
    ListNode next;//定义next指针，指向下一个节点，维持节点连接
    
    public ListNode(int x){
        val=x;
    }

注意注意val只代表当前指针的值，比如p->val表示p指针的指向的值；而p->next表示链表下一个节点，也是一个指针。
构造函数包含两个参数 _value 和 _next ，分别用来给节点赋值和指定下一节点

Hexo Quick Start

Posted on 2018-09-27 | Edited on 2018-10-07

1. 安装hexo

1	sudo npm install -g hexo

目录结构

node_modules：是依赖包
public：存放的是生成的页面
scaffolds：命令生成文章等的模板
source：用命令创建的各种文章
themes：主题
_config.yml：整个博客的配置
db.json：source解析所得到的
package.json：项目所需模块项目的配置信息

2. 初始化

1
2
3

hexo init
hexo install
hexo s

此时打开http://localhost:4000可以看到静态页

3. 关联github

gitbash连接

1
2
3

git config --global user.name "用户名"
git config --global user.email "邮箱"
ssh-keygen -t rsa -C"邮箱"

找到ssh key

1 2	cd ~/.ssh cat id_rsa.pub

将这段配置到github上后，检查一下是否配置成功

1	ssh -T git@github.com

创建项目名为：用户名.github.io
在/blog下配置

1	vim _config.yml

deploy:
  type: git
  repo: https://github.com/用户名/用户名.github.io
  branch: master

退出保存

1
2
3

hexo clean
hexo g
hexo d

hexo d时提示ERROR Deployer not found:git

解决方法：
npm install –save hexo-deployer-git

4. 配置主题

这边使用了yilia

安装

1	git clone https://github.com/litten/hexo-theme-yilia.git themes/yilia

配置

修改hexo根目录下的 _config.ymltheme: yilia
配置yilia文件下的_config.yml

配置头像时出现了头像不能展示的问题

解决方法：

layout/_partial/left-col.ejs将第六行修改成如下形式：
1
<img src="<%=theme.root%><%=theme.avatar%>" class="js-avatar">
将头像文件放在theme/source/img目录下，修改yilia的配置文件
avatar: img/myicon.jpg

一、创建及启动线程

1. 实现Runnable接口

2. 继承thread类

3. 实现callable接口

二、线程状态切换

1. sleep()

2.yield()

3.join()

4.notify()&notifyALL()

三、线程安全（volatile，reentrantLock，syncrhoized）

四、线程池

五、concurrent 包

一、jvm内存结构

1. heap堆

新生代

MinorGC

老年代

MajorGC

FullGC

2. 方法区（永久代）

运行时常量池

3. JVM Stack

4. 本地方法栈

5. 程序计数器

二、Java 类加载机制

类加载器

1.启动类加载器Bootstrp loader

2.扩展类加载器ExtClassLoader

3.应用程序类加载器AppClassLoader

示例：

类加载模型：双亲委派

双亲委派模型解决的问题：

三、方法执行过程

四、java大版本新特性

synchronized的实现原理

1.声明synchronized 代码块

2.用synchronized标记方法

锁的升级降级

重量锁

轻量锁

偏向锁

ReentrantLock和synchronized的区别

一、什么是链表？

二、链表的特点

三、常用链表：单链表、循环链表和双向链表

1. 单链表

单链表的插入

2. 循环链表

3.双向链表

4.双向循环链表

四、选择数组还是链表？

1. 插入、删除和随机访问的时间复杂度

2. 数组缺点

3.链表缺点

4.如何选择？

五、应用

1. 如何分别用链表和数组实现LRU缓冲淘汰策略？

2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如 上海自来水来自海上）

六、设计思想

七、写链表时的注意项

简单题

100. 相同的树

101. 对称二叉树

递归法

104. 二叉树的最大深度

递归

迭代

107. 二叉树的层次遍历 II

递归

基础回顾

树的遍历(DFS思想)

简单题

1.给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

暴力法

两遍哈希表

一遍哈希表

简单题

21.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

83. 删除排序链表中的重复元素

141. 环形链表

2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如上海自来水来自海上）