2019年7月

我们用一个HashSet来保存所有的数字
然后遍历这个数组 当这个数不存在这个数-1(说明是连续递增的开头)则开始一直循环找这个连续递增的数列直到结束,每次外层循环只会循环连续递增的开头所以复杂度为O(n) 空间复杂度O(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Set<Integer> set = new HashSet();
        for(int num: nums){
           set.add(num);
        }
        int res = 0;
        for(int num: nums){
            //只有遇到开头才会开始循环
            if(!set.contains(num - 1)){
                int now = num;
                int nowCnt = 1;
                while(set.contains(now + 1)){
                    now++;
                    nowCnt++;
                }
                res = Math.max(res, nowCnt);
            }
        }
        return res;
    }
}

主服务器开启binlog
从库服务器通过IO线程读取binlog到relaylog 然后从库通过读取relaylog来从放

步骤:
配置主从参数
配置复制的数据库账号

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/
需要两种二分 一种二分之一是找到相同的值要尽量往左边找 一种是找到相同的值要尽量往右边找 循环结束条件是l == r 因为r最终肯定是正确结果 那么我们返回l 或者r都一样

class Solution {
    private int solve(int[] nums, int target, boolean left){
        int l = 0;
        int r = nums.length;
        //结束条件是l == r
        while(l < r){
            int mid = l + ((r - l) >> 1);
            //如果是往左边找的话则要加上=号 继续往左边找 否则往右边找
            if(nums[mid] > target || (left && nums[mid] == target)){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        int leftIdx  = solve(nums, target, true);
        if(leftIdx == nums.length || nums[leftIdx] != target){
            //找不到值就直接返回
            return res;
        }
        //否则就继续找
        res[0] = leftIdx;
        res[1] = solve(nums, target, false) - 1;
        return res;
    }
}

什么是进程和线程

  • 进程是程序的一次执行过程,系统运行程序的基本单位
  • 同一个进程的多个线程共享进程的堆和方法区资源,但是线程有自己独立的程序计数器,虚拟机栈,本地方法栈等。
    总结:线程是进程划分成的更小的运行单位,线程和进程最大的不同在于基本上各进程是独立的,而各线程不一定。线程执行开销极小,但不利于资源的管理行业保护,进程相反。

程序计数器为什么是私有的

  • 在多线程的情况下线程需要记录当前所执行到的代码位置,当线程被切出去又切回来之后可以从上次执行的代码位置继续执行。因为是多线程所以每个线程执行的位置是不一样的。

虚拟机栈和本地方法栈为什么是私有的

  • 虚拟机栈主要存放局部变量,操作数栈,常量引用池等信息,因为这些信息对外部不可见。

本地方法栈

  • 和虚拟机栈作用类似

堆和方法区

堆和方法区是所有线程的共享资源,其中堆是进程中最大的一块内存,主要用于存放新创建的对象(所有对象都在这里分配内存),方法区主要存放已被加载的类信息,常量,静态变量,即时编译器后的代码等数据。

并发与并行

  • 并发: 同一时间段,多个任务都在执行
  • 并行: 单位时间内,多个任务同时执行。

多线程的优势

  • 相比进程来说,线程的上下文开销小
  • 能够共享进程资源

多线程可能带来的问题

  • 内存泄漏
  • 上下文切换
  • 死锁

线程的生命周期和状态 6种

  • NEW 初始状态 还没调用START
  • RUNABLE 运行状态
  • BLOCKED 阻塞状态
  • WAITING 等待状态(通知和中断)
  • TIME_WAIT 超时等待(在指定时间自行返回)
  • TERMINATED 终止

线程运行过程

先调用start,等待cpu分配时间片,系统准备就绪,然后建立一个新线程调用run方法

什么是上下文切换

每个代码执行都会对堆栈,寄存器等相关信息有所影响,那么当CPU调度到别的进程的时候要把当前的现场(堆栈,寄存器等)相关信息存储起来以备下次调度回来的时候还原这个过程叫上下文切换。

线程死锁

多个线程互相等待对方释放资源
产生死锁的必须具备以下四个条件:

1. 互斥条件 该资源任意时刻只能被一个线程占用
2. 请求与保持条件 一个线程因请求资源而阻塞时,对已获得的资源不释放
3. 不剥夺条件 线程已获得的资源在未使用完之前不能被其他线程强行剥夺,只有自己使用完毕后才释放资源。
4. 循环等待条件 若干线程之间形成一种头尾相接的循环等待资源关系

想要避免死锁只需要破坏上述四个条件的其中一个条件即可。具体如下

1. 破坏请求与保持条件 一次性申请所有的资源
2. 破坏不剥夺条件 占用部分资源的线程进一步申请其他资源时,如果申请不到 可以主动释放它占有的资源
3. 破坏循环等待条件 按序申请资源预防,按某一顺序申请资源,释放资源则按反序释放

sleep和wait方法区别和共同点

  • 共同点 都可以让线程进行登台
  • 不同点 sleep方法没有释放锁,而wait释放了锁,wait用于线程间的交互/通信 sleep通常用于暂停执行 wait方法调用后不会自动苏醒,需要别的线程调用同一个对象上的notify或者notifyAll(), sleep会自动苏醒

能否直接调用线程的run

直接调用run相当于是在本线程执行代码并不是创建线程执行。

synchronized 关键字的了解

synchronized 解决了多个线程之间的访问资源的同步性,synchronized关键字可以保证被它修饰的方法或者代码块在任意时刻只能有一个线程执行。

在早期java中synchronized属于重量级锁,效率低下,具体是因为监视器锁(monitor)依赖于底层的操作系统的Mutex Lock来实现,Java的线程是映射到操作系统的原生线程上,如果挂起或唤醒一个线程都需要操作系统帮忙完成。而操作系统实现线程之间的切换需要从用户态转到内核态,这个转换时间成本相对较高。 在java6之后synchronized得到了较大的优化 主要把他细分成了以下锁级别:

锁的状态总共有四种,无锁状态、偏向锁、轻量级锁和重量级锁。随着锁的竞争,锁可以从偏向锁升级到轻量级锁,再升级的重量级锁,但是锁的升级是单向的,也就是说只能从低到高升级,不会出现锁的降级,关于重量级锁,前面我们已详细分析过,下面我们将介绍偏向锁和轻量级锁以及JVM的其他优化手段。

  • 偏向锁
    偏向锁是Java 6之后加入的新锁,它是一种针对加锁操作的优化手段,经过研究发现,在大多数情况下,锁不仅不存在多线程竞争,而且总是由同一线程多次获得,因此为了减少同一线程获取锁(会涉及到一些CAS操作,耗时)的代价而引入偏向锁。偏向锁的核心思想是,如果一个线程获得了锁,那么锁就进入偏向模式,此时Mark Word 的结构也变为偏向锁结构,当这个线程再次请求锁时,无需再做任何同步操作,即获取锁的过程,这样就省去了大量有关锁申请的操作,从而也就提供程序的性能。所以,对于没有锁竞争的场合,偏向锁有很好的优化效果,毕竟极有可能连续多次是同一个线程申请相同的锁。但是对于锁竞争比较激烈的场合,偏向锁就失效了,因为这样场合极有可能每次申请锁的线程都是不相同的,因此这种场合下不应该使用偏向锁,否则会得不偿失,需要注意的是,偏向锁失败后,并不会立即膨胀为重量级锁,而是先升级为轻量级锁。
  • 轻量级锁
    倘若偏向锁失败,虚拟机并不会立即升级为重量级锁,它还会尝试使用一种称为轻量级锁的优化手段(1.6之后加入的),此时Mark Word 的结构也变为轻量级锁的结构。轻量级锁能够提升程序性能的依据是“对绝大部分的锁,在整个同步周期内都不存在竞争”,注意这是经验数据。需要了解的是,轻量级锁所适应的场景是线程交替执行同步块的场合,如果存在同一时间访问同一锁的场合,就会导致轻量级锁膨胀为重量级锁。
  • 自旋锁
    轻量级锁失败后,虚拟机为了避免线程真实地在操作系统层面挂起,还会进行一项称为自旋锁的优化手段。这是基于在大多数情况下,线程持有锁的时间都不会太长,如果直接挂起操作系统层面的线程可能会得不偿失,毕竟操作系统实现线程之间的切换时需要从用户态转换到核心态,这个状态之间的转换需要相对比较长的时间,时间成本相对较高,因此自旋锁会假设在不久将来,当前的线程可以获得锁,因此虚拟机会让当前想要获取锁的线程做几个空循环(这也是称为自旋的原因),一般不会太久,可能是50个循环或100循环,在经过若干次循环后,如果得到锁,就顺利进入临界区。如果还不能获得锁,那就会将线程在操作系统层面挂起,这就是自旋锁的优化方式,这种方式确实也是可以提升效率的。最后没办法也就只能升级为重量级锁了。
  • 锁消除
    消除锁是虚拟机另外一种锁的优化,这种优化更彻底,Java虚拟机在JIT编译时(可以简单理解为当某段代码即将第一次被执行时进行编译,又称即时编译),通过对运行上下文的扫描,去除不可能存在共享资源竞争的锁,通过这种方式消除没有必要的锁,可以节省毫无意义的请求锁时间,如下StringBuffer的append是一个同步方法,但是在add方法中的StringBuffer属于一个局部变量,并且不会被其他线程所使用,因此StringBuffer不可能存在共享资源竞争的情景,JVM会自动将其锁消除。

双重检验锁实现对象单例

public class Singleton {
    private volatile static Singleton uniqueInstance;
    // 使用volatile 可以防止指令重排。
    private Singleton() {
    
    }
    
    public static Singleton getUniqueInstance(){
        if(uniqueInstance == null){
            synchronized(Singleton.class){
                if(uniqueInstance == null){
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

synchronized 的底层原理

  1. 当synchronized作用于语句块时 会自动转换为monitorenter和monitorexit指令,当执行mointorenter指令时会对锁对象的计数器+1当执行monitorexit时减1 当线程调用mointorenter时会检测计数器是否为0 不为0则等待。
  2. 当synchronized作用于方法时 会给方法标志一个ACC_SYNCHRONIZED访问标志,JVM通过该ACC_SYNCHRONIZED访问标志来判定是否为同步方法而执行相应的同步调用。

synchronized和ReentrantLock

  1. 两者都是可重入锁 线程可自己再次获取已获取到的锁而无需等待。
  2. synchronized依赖于JVM而ReentrantLock依赖于API
  3. ReentrantLock比synchronized增加了一些高级功能

    1. 等待可中断
    2. 可实现公平锁
    3. 可实现选择性通知(线程对象可以注册在指定的condition中,从而可以有选择性的进行线程通知。)
    4. ReentrantLock提供了一种能够中断等待锁的线程的机制
    5. ReentrantLock可以指定是公平锁才是非公平锁(通过构造函数 new ReentrantLock(boolean fair)),synchronized只能是非公平锁。

volatile关键字原理

JDK1.2之前 Java内存模型都是从主存读取变量 而在JDK1.2以后变成了可以把变量保存在本地上(如寄存器上)这就可能造成另一个线程在主存中修改了一个变量的值,而另一个线程还继续使用它在寄存器中的变量值得拷贝,造成了数据不一致。把变量声明为volatile之后,每次读取变量都会从主存处读取,还可以防止指令重排序。

synchronized关键字和volatile关键字的区别

  • volatile关键字是线程同步的轻量级实现,volatile性能比synchronized好
  • volatile只能修饰变量 而synchronized可以修饰方法以及代码块
  • 多线程访问volatile关键字不会发阻塞,而synchronized可能会
  • volatile用于解决变量在多个线程之间的可见性,而synchronized关键字解决的是多个线程之间访问资源的同步性。

ThreadLocal简介

  • 每一个线程都有一个自己的专属本地变量。
  • 实现原理 每个Thread都有一个单独的TheadLocalMap实现

ThreadLocal内存泄漏问题

  • ThreadLocalMap是弱引用,value是强引用,所以ThreadLocal没有被外部强引用的情况下,在垃圾回收的时候会key会被清理掉,而value不会被清理掉,就会导致key为null value不为null的Entry就会导致内存泄漏 ThreadLocalMap实现已考虑了这种情况,set get remove方法会清理掉key为null的记录。

强引用、弱引用、软引用、幻象引用

  • 强引用, 就是普通的new
  • 软引用 new SoftReference<Object>(obj); 当内存空间足够的时候,垃圾回收器不会回收它。 当内存空间不足时会回收它。
  • 弱引用 WeakReference<Object> wf = new WeakReference<Object>(obj); GC时候不管引用不引用都会回收它。
  • 幻象引用 PhantomReference<Object> pf = new PhantomReference<Object>(obj); 用来检测对象是否被回收。
  • 所有引用类型都是抽象类java.lang.ref.Reference的子类,子类里提供了get()方法。通过上面的分析中可以得知,除了幻象引用(因为get永远返回null),如果对象还没有被销毁,都可以通过get方法获取原有对象。其实有个非常关键的注意点,利用软引用和弱引用,我们可以将访问到的对象,重新指向强引用,也就是人为的改变了对象的可达性状态。所以对于软引用、弱引用之类,垃圾收集器可能会存在二次确认的问题,以确保处于弱引用状态的对象没有改变为强引用。
  • 但是有个问题,如果我们错误的保持了强引用(比如,赋值给了static变量),那么对象可能就没有机会变回类似弱引用的可达性状态了,就会产生内存泄露。所以,检查弱引用指向对象是否被垃圾收集,也是诊断是否有特定内存泄露的一个思路,我们的框架使用到弱引用又怀疑有内存泄露,就可以从这个角度检查。

为什么要用线程池

  • 降低资源消耗 通过重复利用已创建的资源 避免创建和销毁的消耗
  • 提高响应速度 当任务到达时,任务不需要等待线程创建就能立即执行。
  • 提高线程的可管理性 使用线程池可以进行统一的分配、调优和监控。

Runable 和 Callable接口的区别

  • Runable不会返回结果 而 Callable会返回结果。

执行excute方法和submit方法的区别是什么

  • excute用于提交不需要返回值得任务,无法判断任务是否被线程池执行成功与否
  • submit方法用于提交需要返回值得任务,线程池会返回一个Future对象,可以通过这个对象判断是否执行成功可以通过get方法来获取值,get()方法会阻塞当前线程直到任务完成。方法则会阻塞当前线程一段时间后立即返回,有可能未执行完

如何创建线程池

  • 通过ThreadPoolExecutor创建
  • 利用Executors返回线程池对象的弊端如下

    • FixedThreadPool和SingleThreadExecutor 允许请求的队列长度为Integer.MAX_VALUE 可能堆集大量的请求,从而导致OOM
    • CachedThreadPool和ScheduledThreadPool 允许创建的线程数量为Integer.MAX_VALUE 可能会创建大量线程,导致OOM

Atomic原子类

Atomic指一个操作是不可中断的,即使是在多个线程一起执行时,一个操作一旦开始,就不会被其他线程干扰。

JUC包中的原子类有哪四类?

  • AtomicInteger
  • AtomicLong
  • AtomicBoolean
  • AtomicIntegerArray
  • AtomicLongArray
  • AtmoicReferenceArray
  • AtmoicReference
  • AtmoicStampedReference
  • AtmoicMarkableReference
  • AtmoicIntegerFieldUpdater
  • AtmoicLongFieldUpdater
  • AtmoicStampedReference

Atmoic原理?

  • 利用CAS(Compare And Swap) + Volatile 和native方法 保证原子操作,从而避免synchronized的高开销,执行效率大为提升。

AQS

是一个用来构建锁和同步器的框架,使用AQS能简单且高效的构造出应用广泛的大量的同步器,ReentrantLock,Semaphore,ReentrantReadWriteLock,SynchronousQueue,FutureTask等都是基于AQS的。

AQS原理

  • 如果资源时空闲的话则将当前请求资源线程设置为有效的工作线程,且资源被设置为锁定状态,如果被请求的共享资源被占用,那么久需要一套线程阻塞等待以及被唤醒时锁分配的机制,这个机制AQS是利用CLH队列锁实现的。

AQS对资源的共享方法

  • Exclusiv 独占 只有一个线程能执行,又可分为公平锁和非公平锁。
  • Share共享 多个线程可同时执行

AQS组件总结

  • Semaphore 信号量 允许多个线程同时方法
  • CountDownLatch 倒计时器 可以让某一个线程等待直到倒计时结束,再开始执行
  • CycliBarrier 循环栅栏 让一组线程全部到达屏障后屏障才会开门。

https://leetcode-cn.com/problems/divide-two-integers/submissions/
不能用 乘法、除法、mod 直观的感觉就是暴力循环剪去被除数,但是常数太大,想想为什么会超时,是因为每次减得被除数太少了我们可以剪去他的倍数这样子就可以加速这个过程了,这里可以用位运算直接找出这个数的2^n次倍来试效率高。
最终得出
2^az+2^bz+2^cz=(2^a+2^b+2^c)z 则内容之和则是最终结果。

class Solution {
    public int divide(int dividend, int divisor) {
         if (dividend == 0) { //除0情况直接返回
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {//溢出情况 特判
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异 符号是否相同
        long t = Math.abs((long) dividend); //取绝对值
        long d= Math.abs((long) divisor); //取绝对值
        int result = 0;
        for (int i=31; i>=0;i--) {
            if ((t>>i)>=d) {//找出足够大的数2^n*divisor
                result+=1<<i;//将结果加上2^n
                t-=d<<i;//将被除数减去2^n*divisor
            }
        }
        return negative ? -result : result;//符号相异取反
    }
}