java基础知识(一)

1 java零碎知识点

juc

juc概念

在 Java 中，线程部分是一个重点，本篇文章说的 JUC 也是关于线程的。JUC 就是 java.util .concurrent 工具包的简称。这是一个处理线程的工具包，JDK  1.5 开始出现的。

进程（Process）

是计算机中的程序关于某数据集合上的一次运行活动，是系 统进行资源分配和调度的基本单位，是操作系统结构的基础。 在当代面向线程 设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的 描述，进程是程序的实体。是计算机中的程序关于某数据集合上的一次运行活 动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。程序是 指令、数据及其组织形式的描述，进程是程序的实体

线程（thread）

是操作系统能够进行运算调度的最小单位。它被包含在进程之 中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流， 一个进程中可以并发多个线程，每条线程并行执行不同的任务。

总结来说: 进程：指在系统中正在运行的一个应用程序；程序一旦运行就是进程；进程— —资源分配的最小单位。 线程：系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个 单元执行流。线程——程序执行的最小单位。

线程的状态 Thread.State

线程状态。线程可以处于以下状态之一：
NEW 尚未启动的线程处于此状态。
RUNNABLE 在 Java 虚拟机中执行的线程处于这种状态。
BLOCKED 阻塞等待监视器锁的线程处于此状态。
WAITING 无限期等待另一个线程执行特定操作的线程处于此状态。
TIMED_WAITING 等待另一个线程执行操作达指定等待时间的线程处于此状态。
TERMINATED 已退出的线程处于此状态。
一个线程在给定的时间点只能处于一种状态。这些状态是不反映任何操作系统线程状态的虚拟机状态。

wait/sleep 的区别

（1）sleep 是 Thread 的静态方法，wait 是 Object 的方法，任何对象实例都 能调用。 （2）sleep 不会释放锁，它也不需要占用锁。wait 会释放锁，但调用它的前提 是当前线程占有锁(即代码要在 synchronized 中)。 （3）它们都可以被 interrupted 方法中断。

串行模式

串行表示所有任务都一一按先后顺序进行。串行意味着必须先装完一车柴才能 运送这车柴，只有运送到了，才能卸下这车柴，并且只有完成了这整个三个步 骤，才能进行下一个步骤。

并行模式

并行意味着可以同时取得多个任务，并同时去执行所取得的这些任务。并行模 式相当于将长长的一条队列，划分成了多条短队列，所以并行缩短了任务队列 的长度。并行的效率从代码层次上强依赖于多进程/多线程代码，从硬件角度上 则依赖于多核 CPU。

并发

并发(concurrent)指的是多个程序可以同时运行的现象，更细化的是多进程可 以同时运行或者多指令可以同时运行。对于单核心 CPU 来说，同一时刻 只能运行一个线程。所以，这里的”同时运行”表示的不是真的同一时刻有多个 线程运行的现象，这是并行的概念，而是提供一种功能让用户看来多个程序同 时运行起来了，但实际上这些程序中的进程不是一直霸占 CPU 的，而是执行一 会停一会。 要解决大并发问题，通常是将大任务分解成多个小任务, 由于操作系统对进程的 调度是随机的，所以切分成多个小任务后，可能会从任一小任务处执行。这可 能会出现一些现象： • 可能出现一个小任务执行了多次，还没开始下个任务的情况。这时一般会采用 队列或类似的数据结构来存放各个小任务的成果 • 可能出现还没准备好第一步就执行第二步的可能。这时，一般采用多路复用或 异步的方式，比如只有准备好产生了事件通知才执行某个任务。 • 可以多进程/多线程的方式并行执行这些小任务。也可以单进程/单线程执行这 些小任务，这时很可能要配合多路复用才能达到较高的效率

并发：同一时刻多个线程在访问同一个资源，多个线程对一个点 例子：春运抢票 电商秒杀… 并行：多项工作一起执行，之后再汇总 例子：泡方便面，电水壶烧水，一边撕调料倒入桶中

管程

管程(monitor)是保证了同一时刻只有一个进程在管程内活动,即管程内定义的操作在同 一时刻只被一个进程调用(由编译器实现).但是这样并不能保证进程以设计的顺序执行 JVM 中同步是基于进入和退出管程(monitor)对象实现的，每个对象都会有一个管程 (monitor)对象，管程(monitor)会随着 java 对象一同创建和销毁 执行线程首先要持有管程对象，然后才能执行方法，当方法完成之后会释放管程，方 法在执行时候会持有管程，其他线程无法再获取同一个管程

用户线程和守护线程

用户线程:平时用到的普通线程,自定义线程 守护线程:运行在后台,是一种特殊的线程,比如垃圾回收 当主线程结束后,用户线程还在运行,JVM 存活 如果没有用户线程,都是守护线程,JVM 结束。aa.setDaemon(true) 设置为守护线程

Thread aa = new Thread(() -> {
    System.out.println(Thread.currentThread().getName() + "::" + Thread.currentThread().isDaemon());
    while (true) {
    }
}, "aa");
//设置守护线程
aa.setDaemon(true);
aa.start();

synchronized

synchronized 是 Java 中的关键字，是一种同步锁。它修饰的对象有以下几种：

1. 修饰一个代码块，被修饰的代码块称为同步语句块，其作用的范围是大括号{} 括起来的代码，作用的对象是调用这个代码块的对象；
2. 修饰一个方法，被修饰的方法称为同步方法，其作用的范围是整个方法，作用 的对象是调用这个方法的对象；
   虽然可以使用 synchronized 来定义方法，但 synchronized 并不属于方法定 义的一部分，因此，synchronized 关键字不能被继承。如果在父类中的某个方 法使用了 synchronized 关键字，而在子类中覆盖了这个方法，在子类中的这 个方法默认情况下并不是同步的，而必须显式地在子类的这个方法中加上 synchronized 关键字才可以。当然，还可以在子类方法中调用父类中相应的方 法，这样虽然子类中的方法不是同步的，但子类调用了父类的同步方法，因此， 子类的方法也就相当于同步了。
3. 修改一个静态的方法，其作用的范围是整个静态方法，作用的对象是这个类的 所有对象；
4. 修改一个类，其作用的范围是 synchronized 后面括号括起来的部分，作用主 的对象是这个类的所有对象。

被锁的只有在该线程执行结束或者异常退出，其他线程才能进入执行。

Lock 锁

实现提供了比使用同步方法和语句可以获得的更广泛的锁操作。它们允 许更灵活的结构，可能具有非常不同的属性，并且可能支持多个关联的条件对 象。Lock 提供了比 synchronized 更多的功能。

Lock 与的 Synchronized 区别

Lock 不是 Java 语言内置的，synchronized 是 Java 语言的关键字，因此是内 置特性。Lock 是一个类，通过这个类可以实现同步访问；

• Lock 和 synchronized 有一点非常大的不同，采用 synchronized 不需要用户 去手动释放锁，当 synchronized 方法或者 synchronized 代码块执行完之后， 系统会自动让线程释放对锁的占用；而 Lock 则必须要用户去手动释放锁，如 果没有主动释放锁，就有可能导致出现死锁现象。

public interface Lock {
void lock();
void lockInterruptibly() throws InterruptedException;
boolean tryLock();
boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
void unlock();
Condition newCondition();
}

lock锁的使用

lock()方法是平常使用得最多的一个方法，就是用来获取锁。如果锁已被其他 线程获取，则进行等待。 采用 Lock，必须主动去释放锁，并且在发生异常时，不会自动释放锁。因此一 般来说，使用 Lock 必须在 try{}catch{}块中进行，并且将释放锁的操作放在 finally 块中进行，以保证锁一定被被释放，防止死锁的发生。通常使用 Lock 来进行同步的话，是以下面这种形式去使用的：

Lock lock = ...;
lock.lock();
try{
//处理任务
}catch(Exception ex){
}finally{
lock.unlock(); //释放锁
}

new Condition

2.2.3 newCondition 关键字 synchronized 与 wait()/notify()这两个方法一起使用可以实现等待/通 知模式，

Lock 锁的 newContition()方法返回 Condition 对象，Condition 类 也可以实现等待/通知模式。 用 notify()通知时，JVM 会随机唤醒某个等待的线程， 使用 Condition 类可以 进行选择性通知，

Condition 比较常用的两个方法：

• await()会使当前线程等待,同时会释放锁,当其他线程调用 signal()时,线程会重 新获得锁并继续执行。

• signal()用于唤醒一个等待的线程。

注意：在调用 Condition 的 await()/signal()方法前，也需要线程持有相关 的 Lock 锁，调用 await()后线程会释放这个锁，在 singal()调用后会从当前 Condition 对象的等待队列中，唤醒 一个线程，唤醒的线程尝试获得锁， 一旦 获得锁成功就继续执行。

ReentrantLock

ReentrantLock，意思是“可重入锁”，关于可重入锁的概念将在后面讲述。 ReentrantLock 是唯一实现了 Lock 接口的类，并且 ReentrantLock 提供了更 多的方法。下面通过一些实例看具体看一下如何使用。

  public class Test {
            private ArrayList<Integer> arrayList = new ArrayList<Integer>();
            public static void main(String[] args) {
                final Test test = new Test();
                new Thread(){
                    public void run() {
                        test.insert(Thread.currentThread());
                    };
                }.start();
                new Thread(){
                    public void run() {
                        test.insert(Thread.currentThread());
                    };
                }.start();
            }
            public void insert(Thread thread) {
                Lock lock = new ReentrantLock(); //注意这个地方
                lock.lock();
                try {
                    System.out.println(thread.getName()+"得到了锁");
                    for(int i=0;i<5;i++) {
                        arrayList.add(i);
                    }
                } catch (Exception e) {
                    // TODO: handle exception
                }finally {
                    System.out.println(thread.getName()+"释放了锁");
                    lock.unlock();
                }
            }
        }

ReadWriteLock接口

ReadWriteLock接口 由 ReentrantReadWriteLock类实现。

ReadWriteLock 也是一个接口，在它里面只定义了两个方法。一个用来获取读锁，一个用来获取写锁。也就是说将文件的读写操作分开，分成 2 个锁来分配给线程，从而使得多个线程可以同时进行读操作。

下面的ReentrantReadWriteLock 实现了 ReadWriteLock 接口。
ReentrantReadWriteLock 里面提供了很多丰富的方法，不过最主要的有两个方法：readLock()和 writeLock()用来获取读锁和写锁。下面通过几个例子来看一下 ReentrantReadWriteLock 具体用法。

public interface ReadWriteLock {
/**
* Returns the lock used for reading.
*
* @return the lock used for reading.
*/
Lock readLock();
/**
* Returns the lock used for writing.
*
* @return the lock used for writing.
*/
Lock writeLock();
}

public class TestReentrantReadWriteLock {
    //读写锁
    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    public static void main(String[] args) {
        final TestReentrantReadWriteLock test = new TestReentrantReadWriteLock();
        new Thread() {
            public void run() {
                test.get(Thread.currentThread());
            }
        }.start();
        new Thread() {
            public void run() {
                test.get(Thread.currentThread());
            }
        }.start();
    }
    private synchronized void get(Thread thread) {
        long start = System.currentTimeMillis();
        int i =0;
        while (System.currentTimeMillis() - start <= 1) {
            System.out.println(thread.getName()+"正在进行读操作"+(i++));
        }
        System.out.println(thread.getName() + "读操作完毕");
    }
    private void readWriteLockGet(Thread thread){
        readWriteLock.readLock().lock();
        try {
            long start = System.currentTimeMillis();
            int i =0;
            while(System.currentTimeMillis() - start <= 1) {
                System.out.println(thread.getName()+"正在进行读操作"+(i++));
            }
            System.out.println(thread.getName()+"读操作完毕");
        }catch (Exception e){
        }finally {
            readWriteLock.readLock().unlock();
        }
    }
}

说明 thread1 和 thread2 在同时进行读操作。这样就大大提升了读操作的效率。
注意:
•如果有一个线程已经占用了读锁，则此时其他线程如果要申请写锁，则申请写
锁的线程会一直等待释放读锁。
•如果有一个线程已经占用了写锁，则此时其他线程如果申请写锁或者读锁，则
申请的线程会一直等待释放写锁

Lock 和 synchronized 有以下几点不同：

1. Lock 是一个接口，而 synchronized 是 Java 中的关键字，synchronized 是内
   置的语言实现；
2. synchronized 在发生异常时，会自动释放线程占有的锁，因此不会导致死锁现
   象发生；而 Lock 在发生异常时，如果没有主动通过 unLock()去释放锁，则很
   可能造成死锁现象，因此使用 Lock 时需要在 finally 块中释放锁；
3. Lock 可以让等待锁的线程响应中断，而 synchronized 却不行，使用
   synchronized 时，等待的线程会一直等待下去，不能够响应中断；
4. 通过 Lock 可以知道有没有成功获取锁，而 synchronized 却无法办到。
5. Lock 可以提高多个线程进行读操作的效率。
   在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源
   非常激烈时（即有大量线程同时竞争），此时 Lock 的性能要远远优于
   synchronized。

线程间通信

线程间通信的模型有两种：共享内存和消息传递，以下方式都是基本这两种模
型来实现的。

我们来基本一道面试常见的题目来分析场景

两个线程，一个线程对当前数值加 1，另一个线程对当前数值减 1,要求
用线程间通信

1. 使用synchronized 实现，通过wait()和notifyAll()进行线程间通信交替执行
2. 使用lock实现，lock.newCondition()，然后使用condition.await()和condition.signalAll()来进行线程间通信，来实现交替执行。

Condition

等待通知机制，在Java中主要有两种方式:

• 一是基于wait/notify方法结合synchronized关键字来实现
• 二是Condition结合Lock来实现

Condition的示例：
Condition接口定义了等待/通知两种类型的方法，在线程调用这些方法时，需要提前获取Condition对象关联的锁（在基于wait/notify方法实现的方案中需要获取的是对象锁）。

Condition对象是需要关联Lock对象的，调用Lock对象的newCondition()对象创建而来，也就是说Condition的使用是需要依赖Lock对象的。

    private Lock lock = new ReentrantLock();
    private Condition condition = lock.newCondition();
    public void conditionAwait() throws InterruptedException {
        lock.lock();
        try {
            condition.await();
        } finally {
            lock.unlock();
        }
    }
    public void conditionSignal() {
        lock.lock();
        try {
            condition.signal();//condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

常用的方法：
await()：当前线程进入等待状态直到被通知（signal）或中断；

当前线程进入运行状态并从await()方法返回的场景包括：
（1）其他线程调用相同Condition对象的signal/signalAll方法，并且当前线程被唤醒；
（2）其他线程调用interrupt方法中断当前线程；

signal():
唤醒一个等待在Condition上的线程，被唤醒的线程在方法返回前必须获得与Condition对象关联的锁

Condition-线程通信更高效的方式借助于Condition对象，RetrantLock可以实现类似于Object的wait和notify/notifyAll功能。使用它具有更好的灵活性。
在一个Lock对象里面可以创建多个Condition(对象监视器)实例，线程对象可以注册在指定的Condition对象中，从而可以有选择性的进行线程通知，实现多路通知功能，在调度线程上更加灵活。

Vector

Vector 是矢量队列，它是 JDK1.0 版本添加的类。继承于 AbstractList，实现了 List, RandomAccess, Cloneable 这些接口。 Vector 继承了 AbstractList，实现了 List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功能。 Vector 实现了 RandmoAccess 接口，即提供了随机访问功能。RandmoAccess 是 java 中用来被 List 实现，为 List 提供快速访问功能的。在Vector 中，我们即可以通过素的序号快速获取元素对象；这就是快速随机访问。 Vector 实现了 Cloneable 接口，即实现 clone()函数。它能被克隆。

和 ArrayList 不同，Vector 中的操作是线程安全的。但是效率低不建议使用

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

Collections

有方法可以保证集合类型的线程安全。 效率低不建议使用

List<String> integers = Collections.synchronizedList(new Vector<String>());

CopyOnWriteArrayList

首先我们对 CopyOnWriteArrayList 进行学习,其特点如下:它相当于线程安全的 ArrayList。和 ArrayList 一样，它是个可变数组；但是和ArrayList 不同的时，它具有以下特性：

1. 它最适合于具有以下特征的应用程序：List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove()等等）的开销很大。
4. 迭代器支持 hasNext(), next()等不可变操作，但不支持可变 remove()等操作。
5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
6. 独占锁效率低：采用读写分离思想解决
7. 写线程获取到锁，其他写线程阻塞
8. 复制思想：
   当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这时候会抛出来一个新的问题，也就是数据不一致的问题。如果写线程还没来得及写会内存，其他的线程就会读到了脏数据。

动态数组与线程安全
下面从“动态数组”和“线程安全”两个方面进一步对CopyOnWriteArrayList 的原理进行说明。
“动态数组”机制

• 它内部有个“volatile 数组”(array)来保持数据。在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile 数组”, 这就是它叫做 CopyOnWriteArrayList 的原因
• 由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList 效率很低；但是单单只是进行历查找的话，效率比较高。

“线程安全”机制

• 通过 volatile 和互斥锁来实现的。
• 通过“volatile 数组”来保存数据的。一个线程读取 volatile 数组时，总能看到其它线程对该 volatile 变量最后的写入；就这样，通过 volatile 提供了“读取到的数据总是最新的”这个机制的保证。
• 通过互斥锁来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile 数组”中，然后再“释放互斥锁”，就达到了保护数据的目的。
  目前我们学习了有两种创建线程的方法-一种是通过创建 Thread 类，另一种是
  通过使用 Runnable 创建线程。但是，Runnable 缺少的一项功能是，当线程
  终止时（即 run（）完成时），我们无法使线程返回结果。为了支持此功能，
  Java 中提供了 Callable 接口。
  现在我们学习的是创建线程的第三种方案—-Callable 接口
  Callable 接口的特点如下(重点)
  •
  为了实现 Runnable，需要实现不返回任何内容的 run（）方法，而对于
  Callable，需要实现在完成时返回结果的 call（）方法。
  •
  call（）方法可以引发异常，而 run（）则不能。
  •
  为实现 Callable 而必须重写 call 方法
  •
  不能直接替换 runnable,因为 Thread 类的构造方法根本没有 Callable
  继承Thread类然

  Callable 接口

  创建线程的三种方法

  public class ThreadTest extends Thread {
   @Override
   public void run() {
       try {
           TimeUnit.SECONDS.sleep(3);
       } catch (InterruptedException e) {
           e.printStackTrace();
       }
       System.out.println("通过继承Thread类创建线程"+System.currentTimeMillis());
   }
  }
  main：
       Thread thread = new Thread(new ThreadTest());
       Thread thread2 = new Thread(new ThreadTest());
       thread.start();
       thread2.start();

  
  实现Runnable接口

public class RunAbleTest implements Runnable {
    @Override
    public void run() {
        try {
            TimeUnit.SECONDS.sleep(3);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("实现Runnable里面的run方法来创建线程");
    }
}
main：
     Thread thread = new Thread(new RunAbleTest());
     thread.start();
     System.out.println("允许开始····");

实现Callable接口，并通过FutureTask对象调用

//创建线程方式：1.实现Callable类 2.重写call()方法 3.看main方法注释
public class TestCallable2 implements Callable {
    @Override
    public Integer call() throws Exception {
        System.out.println("实现Callable接口");
        return 100;
    }
    public static void main(String[] args) {
        TestCallable2 testCallable = new TestCallable2();
        //创建多个FutureTask对象，才能多次执行线程
        FutureTask futureTask = new FutureTask(testCallable);
        FutureTask futureTask2 = new FutureTask(testCallable);
        new Thread(futureTask).start();
        new Thread(futureTask2).start();
        try {
            System.out.println(futureTask.get());
            System.out.println(futureTask2.get());
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
}

Future 接口

• 当 call（）方法完成时，结果必须存储在主线程已知的对象中，以便主线程可以知道该线程返回的结果。为此，可以使用 Future 对象。
• 将 Future 视为保存结果的对象–它可能暂时不保存结果，但将来会保存（一旦Callable 返回）。Future 基本上是主线程可以跟踪进度以及其他线程的结果的一种方式。要实现此接口，必须重写 5 种方法，这里列出了重要的方法,如下:
  public boolean cancel（boolean mayInterrupt）：用于停止任务。==如果尚未启动，它将停止任务。如果已启动，则仅mayInterrupt 为 true时才会中断任务。

• public Object get（）抛出 InterruptedException，ExecutionException：
  用于获取任务的结果。
  在主线程中需要执行比较耗时的操作时，但又不想阻塞主线程时，可以把这些作业交给 Future 对象在后台完成当主线程将来需要时，就可以通过 Future 对象获得后台作业的计算结果或者执行状态
  一般 FutureTask 多用于耗时的计算，主线程可以在完成自己的任务后，再去获取结果。
  仅在计算完成时才能检索结果；如果计算尚未完成，则阻塞 get 方法一旦计算完成，就不能再重新开始或取消计算
  get 方法而获取结果只有在计算完成时获取，否则会一直阻塞直到任务转入完成状态，然后会返回结果或者抛出异常get 只计算一次,因此 get 方法放到最后。
  •
  public boolean isDone（）：如果任务完成，则返回 true，否则返回 false可以看到 Callable 和 Future 做两件事-Callable 与 Runnable 类似，因为它封装了要在另一个线程上运行的任务，而 Future 用于存储从另一个线程获得的结果。实际上，future 也可以与 Runnable 一起使用。要创建线程，需要 Runnable。为了获得结果，需要 future。
  CountDownLatch 类可以设置一个计数器，然后通过 countDown 方法来进行
  减 1 的操作，使用 await 方法等待计数器不大于 0，然后继续执行 await 方法
  之后的语句。
  •
  CountDownLatch 主要有两个方法，当一个或多个线程调用 await 方法时，这
  些线程会阻塞
  •
  其它线程调用 countDown 方法会将计数器减 1(调用 countDown 方法的线程
  不会阻塞)
  •
  当计数器的值变为 0 时，因 await 方法阻塞的线程会被唤醒，继续执行
  CyclicBarrier 看英文单词可以看出大概就是循环阻塞的意思，在使用中
  CyclicBarrier 的构造方法第一个参数是目标障碍数，每次执行 CyclicBarrier 一
  次障碍数会加一，如果达到了目标障碍数，才会执行 cyclicBarrier.await()之后
  的语句。可以将 CyclicBarrier 理解为加 1 操作
  信号灯 Semaphore
  Semaphore 的构造方法中传入的第一个参数是最大信号量（可以看成最大线
  程池），每个信号量初始化为一个最多只能分发一个许可证。使用 acquire 方
  法获得许可证，release 方法释放许可
  场景: 抢车位, 6 部汽车 3 个停车位
  现实中有这样一种场景：对共享资源有读和写的操作，且写操作没有读操作那
  么频繁。在没有写操作的时候，多个线程同时读一个资源没有任何问题，所以
  应该允许多个线程同时读取共享资源；但是如果一个线程想去写这些共享资源，
  就不应该允许其他线程对该资源进行读和写的操作了。
  针对这种场景，JAVA 的并发包提供了读写锁 ReentrantReadWriteLock，
  它表示两个锁，一个是读操作相关的锁，称为共享锁；一个是写相关的锁，称
  为排他锁

  FutureTask类

  减少计数 CountDownLatch

  循环栅栏 CyclicBarrier

  读写锁介绍

  1. 线程进入读锁的前提条件：
     •
     没有其他线程的写锁
     •
     没有写请求, 或者有写请求，但调用线程和持有锁的线程是同一个(可重入
     锁)。
  2. 线程进入写锁的前提条件：
     •
     没有其他线程的读锁
     •
     没有其他线程的写锁
     而读写锁有以下三个重要的特性：
     （1）公平选择性：支持非公平（默认）和公平的锁获取方式，吞吐量还是非公
     平优于公平。
     （2）重进入：读锁和写锁都支持线程重进入。
     （3）锁降级：遵循获取写锁、获取读锁再释放写锁的次序，写锁能够降级成为
     读锁。

     阻塞队列

     BlockingQueue 简介

     Concurrent 包中，BlockingQueue 很好的解决了多线程中，如何高效安全
     “传输”数据的问题。通过这些高效并且线程安全的队列类，为我们快速搭建
     高质量的多线程程序带来极大的便利。本文详细介绍了 BlockingQueue 家庭
     中的所有成员，包括他们各自的功能以及常见使用场景。
     阻塞队列，顾名思义，首先它是一个队列, 通过一个共享的队列，可以使得数据
     由队列的一端输入，从另外一端输出；

当队列是空的，从队列中获取元素的操作将会被阻塞
当队列是满的，从队列中添加元素的操作将会被阻塞
试图从空的队列中获取元素的线程将会被阻塞，直到其他线程往空的队列插入新的元素
试图向已满的队列中添加新元素的线程将会被阻塞，直到其他线程从队列中移除一个或多
个元素或者完全清空，使队列变得空闲起来并后续新增

常用的队列主要有以下两种：

先进先出（FIFO）：先插入的队列的元素也最先出队列，类似于排队的功能。
从某种程度上来说这种队列也体现了一种公平性
•
后进先出（LIFO）：后插入队列的元素最先出队列，这种队列优先处理最近发
生的事件(栈)
在多线程领域：所谓阻塞，在某些情况下会挂起线程（即阻塞），一旦条件满足，被挂起
的线程又会自动被唤起

为什么需要 BlockingQueue

好处是我们不需要关心什么时候需要阻塞线程，什么时候需要唤醒线程，因为这一切
BlockingQueue 都给你一手包办了
在 concurrent 包发布以前，在多线程环境下，我们每个程序员都必须去自己控制这些细
节，尤其还要兼顾效率和线程安全，而这会给我们的程序带来不小的复杂度。
多线程环境中，通过队列可以很容易实现数据共享，比如经典的“生产者”和
“消费者”模型中，通过队列可以很便利地实现两者之间的数据共享。假设我
们有若干生产者线程，另外又有若干个消费者线程。如果生产者线程需要把准
备好的数据共享给消费者线程，利用队列的方式来传递数据，就可以很方便地
解决他们之间的数据共享问题。但如果生产者和消费者在某个时间段内，万一
发生数据处理速度不匹配的情况呢？理想情况下，如果生产者产出数据的速度
大于消费者消费的速度，并且当生产出来的数据累积到一定程度的时候，那么
生产者必须暂停等待一下（阻塞生产者线程），以便等待消费者线程把累积的
数据处理完毕，反之亦然。
•
当队列中没有数据的情况下，消费者端的所有线程都会被自动阻塞（挂起），
直到有数据放入队列
•
当队列中填满数据的情况下，生产者端的所有线程都会被自动阻塞（挂起），
直到队列中有空的位置，线程被自动唤醒

BlockingQueue 核心方法

1.放入数据
•
offer(anObject):表示如果可能的话,将 anObject 加到 BlockingQueue 里,即
如果 BlockingQueue 可以容纳,则返回 true,否则返回 false.（本方法不阻塞当
前执行方法的线程）
•
offer(E o, long timeout, TimeUnit unit)：可以设定等待的时间，如果在指定
的时间内，还不能往队列中加入 BlockingQueue，则返回失败
•
put(anObject):把 anObject 加到 BlockingQueue 里,如果 BlockQueue 没有
空间,则调用此方法的线程被阻断直到 BlockingQueue 里面有空间再继续.
2.获取数据
•
poll(time): 取走 BlockingQueue 里排在首位的对象,若不能立即取出,则可以等
time 参数规定的时间,取不到时返回 null
•
poll(long timeout, TimeUnit unit)：从 BlockingQueue 取出一个队首的对象，
如果在指定时间内，队列一旦有数据可取，则立即返回队列中的数据。否则知
道时间超时还没有数据可取，返回失败。
•
take(): 取走 BlockingQueue 里排在首位的对象,若 BlockingQueue 为空,阻断
进入等待状态直到 BlockingQueue 有新的数据被加入;
•
drainTo(): 一次性从 BlockingQueue 获取所有可用的数据对象（还可以指定
获取数据的个数），通过该方法，可以提升获取数据效率；不需要多次分批加
锁或释放锁。

ArrayBlockingQueue(常用)

基于数组的阻塞队列实现，在 ArrayBlockingQueue 内部，维护了一个定长数
组，以便缓存队列中的数据对象，这是一个常用的阻塞队列，除了一个定长数
组外，ArrayBlockingQueue 内部还保存着两个整形变量，分别标识着队列的
头部和尾部在数组中的位置。
ArrayBlockingQueue 在生产者放入数据和消费者获取数据，都是共用同一个
锁对象，由此也意味着两者无法真正并行运行，这点尤其不同于
LinkedBlockingQueue；按照实现原理来分析，ArrayBlockingQueue 完全可
以采用分离锁，从而实现生产者和消费者操作的完全并行运行。Doug Lea 之
所以没这样去做，也许是因为 ArrayBlockingQueue 的数据写入和获取操作已
经足够轻巧，以至于引入独立的锁机制，除了给代码带来额外的复杂性外，其
在性能上完全占不到任何便宜。 ArrayBlockingQueue 和
LinkedBlockingQueue 间还有一个明显的不同之处在于，前者在插入或删除
元素时不会产生或销毁任何额外的对象实例，而后者则会生成一个额外的
Node 对象。这在长时间内需要高效并发地处理大批量数据的系统中，其对于
GC 的影响还是存在一定的区别。而在创建 ArrayBlockingQueue 时，我们还
可以控制对象的内部锁是否采用公平锁，默认采用非公平锁。
一句话总结: 由数组结构组成的有界阻塞队列。

LinkedBlockingQueue(常用)

基于链表的阻塞队列，同 ArrayListBlockingQueue 类似，其内部也维持着一
个数据缓冲队列（该队列由一个链表构成），当生产者往队列中放入一个数据
时，队列会从生产者手中获取数据，并缓存在队列内部，而生产者立即返回；
只有当队列缓冲区达到最大值缓存容量时（LinkedBlockingQueue 可以通过
构造函数指定该值），才会阻塞生产者队列，直到消费者从队列中消费掉一份
数据，生产者线程会被唤醒，反之对于消费者这端的处理也基于同样的原理。
而 LinkedBlockingQueue 之所以能够高效的处理并发数据，还因为其对于生
产者端和消费者端分别采用了独立的锁来控制数据同步，这也意味着在高并发
的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列
的并发性能。
ArrayBlockingQueue 和 LinkedBlockingQueue 是两个最普通也是最常用
的阻塞队列，一般情况下，在处理多线程间的生产者消费者问题，使用这两个
类足以。
一句话总结: 由链表结构组成的有界（但大小默认值为
integer.MAX_VALUE）阻塞队列。

DelayQueue延迟队列

DelayQueue 中的元素只有当其指定的延迟时间到了，才能够从队列中获取到
该元素。DelayQueue 是一个没有大小限制的队列，因此往队列中插入数据的
操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻
塞。
==一句话总结: 使用优先级队列实现的延迟无界阻塞队列。

public class DelayQueueTest implements Delayed{
    //延时时间 单位自定义
    private long delayTime;
    private String name;
    public long getDelayTime() {
        return delayTime;
    }
    public void setDelayTime(long delayTime) {
        this.delayTime = delayTime;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public DelayQueueTest(long delayTime, String name) {
        this.delayTime = delayTime * 1000 + System.currentTimeMillis();;
        this.name = name;
    }
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(
                (this.delayTime - System.currentTimeMillis()),
                TimeUnit.MILLISECONDS);
    }
    @Override
    public int compareTo(Delayed o) {
        return (int) (this.delayTime-((DelayQueueTest)o).delayTime);
    }
    public static void main(String[] args) throws InterruptedException {
        DelayQueue<DelayQueueTest> delayeds = new DelayQueue<>();
        DelayQueueTest delayQueueTest;
        long delayTime;
        for (int i = 0; i < 10; i++) {
            delayeds.put(new DelayQueueTest(i, "aaa"+i));
        }
        for (int i = 0; i < 10; i++) {
            System.out.println("name= "+delayeds.take().name);
        }
    }
}

PriorityBlockingQueue

基于优先级的阻塞队列（优先级的判断通过构造函数传入的 Compator 对象来
决定），但需要注意的是 PriorityBlockingQueue 并不会阻塞数据生产者，而
只会在没有可消费的数据时，阻塞数据的消费者。
因此使用的时候要特别注意，生产者生产数据的速度绝对不能快于消费者消费
数据的速度，否则时间一长，会最终耗尽所有的可用堆内存空间。
在实现 PriorityBlockingQueue 时，内部控制线程同步的锁采用的是公平锁。
一句话总结: 支持优先级排序的无界阻塞队列。

take()

检索并删除此队列的头，如有必要，等待元素可用。

offer(E e)
将指定的元素插入到此优先级队列中。
boolean offer(E e, long timeout, TimeUnit unit)
将指定的元素插入到此优先级队列中,并设置等待时间。

SynchronousQueue

一种无缓冲的等待队列，类似于无中介的直接交易，有点像原始社会中的生产
者和消费者，生产者拿着产品去集市销售给产品的最终消费者，而消费者必须
亲自去集市找到所要商品的直接生产者，如果一方没有找到合适的目标，那么
对不起，大家都在集市等待。相对于有缓冲的 BlockingQueue 来说，少了一
个中间经销商的环节（缓冲区），如果有经销商，生产者直接把产品批发给经
销商，而无需在意经销商最终会将这些产品卖给那些消费者，由于经销商可以
库存一部分商品，因此相对于直接交易模式，总体来说采用中间经销商的模式
会吞吐量高一些（可以批量买卖）；但另一方面，又因为经销商的引入，使得
产品从生产者到消费者中间增加了额外的交易环节，单个产品的及时响应性能
可能会降低。
声明一个 SynchronousQueue 有两种不同的方式，它们之间有着不太一样的
行为。
公平模式和非公平模式的区别:
•
公平模式：SynchronousQueue 会采用公平锁，并配合一个 FIFO 队列来阻塞
多余的生产者和消费者，从而体系整体的公平策略；
•
非公平模式（SynchronousQueue 默认）：SynchronousQueue 采用非公平
锁，同时配合一个 LIFO 队列来管理多余的生产者和消费者，而后一种模式，
如果生产者和消费者的处理速度有差距，则很容易出现饥渴的情况，即可能有
某些生产者或者是消费者的数据永远都得不到处理。
一句话总结: 不存储元素的阻塞队列，也即单个元素的队列。

LinkedTransferQueue

LinkedTransferQueue 是一个由链表结构组成的无界阻塞 TransferQueue 队
列。相对于其他阻塞队列，LinkedTransferQueue 多了 tryTransfer 和
transfer 方法。
LinkedTransferQueue 采用一种预占模式。意思就是消费者线程取元素时，如
果队列不为空，则直接取走数据，若队列为空，那就生成一个节点（节点元素
为 null）入队，然后消费者线程被等待在这个节点上，后面生产者线程入队时
发现有一个元素为 null 的节点，生产者线程就不入队了，直接就将元素填充到
该节点，并唤醒该节点等待的线程，被唤醒的消费者线程取走元素，从调用的
方法返回。
==一句话总结: 由链表组成的无界阻塞队列

LinkedBlockingDeque

LinkedBlockingDeque 是一个由链表结构组成的双向阻塞队列，即可以从队
列的两端插入和移除元素。
对于一些指定的操作，在插入或者获取队列元素时如果队列状态不允许该操作
可能会阻塞住该线程直到队列状态变更为允许操作，这里的阻塞一般有两种情
况
•
插入元素时: 如果当前队列已满将会进入阻塞状态，一直等到队列有空的位置时
再讲该元素插入，该操作可以通过设置超时参数，超时后返回 false 表示操作
失败，也可以不设置超时参数一直阻塞，中断后抛出 InterruptedException 异
常
•
读取元素时: 如果当前队列为空会阻塞住直到队列不为空然后返回元素，同样可
以通过设置超时参数
一句话总结: 由链表组成的双向阻塞队列

线程池简介

线程池（英语：thread pool）：一种线程使用模式。线程过多会带来调度开销，
进而影响缓存局部性和整体性能。而线程池维护着多个线程，等待着监督管理
者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代
价。线程池不仅能够保证内核的充分利用，还能防止过分调度。
例子： 10 年前单核 CPU 电脑，假的多线程，像马戏团小丑玩多个球，CPU 需
要来回切换。 现在是多核电脑，多个线程各自跑在独立的 CPU 上，不用切换
效率高。
线程池的优势： 线程池做的工作只要是控制运行的线程数量，处理过程中将任
务放入队列，然后在线程创建后启动这些任务，如果线程数量超过了最大数量，
超出数量的线程排队等候，等其他线程执行完毕，再从队列中取出任务来执行。
它的主要特点为：
•
降低资源消耗: 通过重复利用已创建的线程降低线程创建和销毁造成的销耗。
•
提高响应速度: 当任务到达时，任务可以不需要等待线程创建就能立即执行。
•
提高线程的可管理性: 线程是稀缺资源，如果无限制的创建，不仅会销耗系统资
源，还会降低系统的稳定性，使用线程池可以进行统一的分配，调优和监控。
•
Java 中的线程池是通过 Executor 框架实现的，该框架中用到了 Executor，Executors，
ExecutorService，ThreadPoolExecutor 这几个类

常用参数(重点)

•
corePoolSize 线程池的核心线程数
•
maximumPoolSize 能容纳的最大线程数
•
keepAliveTime 空闲线程存活时间
•
unit 存活的时间单位
•
workQueue 存放提交但未执行任务的队列
•
threadFactory 创建线程的工厂类
•
handler 等待队列满后的拒绝策略

线程池中，有三个重要的参数，决定影响了拒绝策略：corePoolSize - 核心线
程数，也即最小的线程数。workQueue - 阻塞队列 。 maximumPoolSize -
最大线程数
当提交任务数大于 corePoolSize 的时候，会优先将任务放到 workQueue 阻
塞队列中。当阻塞队列饱和后，会扩充线程池中线程数，直到达到
maximumPoolSize 最大线程数配置。此时，再多余的任务，则会触发线程池
的拒绝策略了。
总结起来，也就是一句话，当提交的任务数大于（workQueue.size() +
maximumPoolSize ），就会触发线程池的拒绝策略。

拒绝策略(重点)

CallerRunsPolicy: 当触发拒绝策略，只要线程池没有关闭的话，则使用调用
线程直接运行任务。一般并发比较小，性能要求不高，不允许失败。但是，由
于调用者自己运行任务，如果任务提交速度过快，可能导致程序阻塞，性能效
率上必然的损失较大
AbortPolicy: 丢弃任务，并抛出拒绝执行 RejectedExecutionException 异常
信息。线程池默认的拒绝策略。必须处理好抛出的异常，否则会打断当前的执
行流程，影响后续的任务执行。
DiscardPolicy: 直接丢弃，其他啥都没有
DiscardOldestPolicy: 当触发拒绝策略，只要线程池没有关闭的话，丢弃阻塞
队列 workQueue 中最老的一个任务，并将新任务加入

常见的线程池的创建方式

new CachedThreadPool(常用)

作用：创建一个可缓存线程池，如果线程池长度超过处理需要，可灵活回收空
闲线程，若无可回收，则新建线程.
特点:
•
线程池中数量没有固定，可达到最大值（Interger. MAX_VALUE）
•
线程池中的线程可进行缓存重复利用和回收（回收默认时间为 1 分钟）
•
当线程池中，没有可用线程，会重新创建一个线程

//new CachedThreadPool
public static ExecutorService newCachedThreadPool(){
    /**
     * corePoolSize 线程池的核心线程数
     * maximumPoolSize 能容纳的最大线程数
     * keepAliveTime 空闲线程存活时间
     * unit 存活的时间单位
     * workQueue 存放提交但未执行任务的队列
     * threadFactory 创建线程的工厂类:可以省略
     * handler 等待队列满后的拒绝策略:可以省略
     */
    return new ThreadPoolExecutor(
            0,
            Integer.MAX_VALUE,
            60L,
            TimeUnit.SECONDS,
            new SynchronousQueue<>(),
            Executors.defaultThreadFactory(),
            new ThreadPoolExecutor.AbortPolicy()
    );
    //适用于创建一个可无限扩大的线程池，服务器负载压力较轻，执行时间较
    //短，任务多的场景
}

newFixedThreadPool(常用)

作用：创建一个可重用固定线程数的线程池，以共享的无界队列方式来运行这
些线程。在任意点，在大多数线程会处于处理任务的活动状态。如果在所有线
程处于活动状态时提交附加任务，则在有可用线程之前，附加任务将在队列中
等待。如果在关闭前的执行期间由于失败而导致任何线程终止，那么一个新线
程将代替它执行后续的任务（如果需要）。在某个线程被显式地关闭之前，池
中的线程将一直存在。
特征：
•
线程池中的线程处于一定的量，可以很好的控制线程的并发量
•
线程可以重复被使用，在显示关闭之前，都将一直存在
•
超出一定量的线程被提交时候需在队列中等待

场景: 适用于可以预测线程数量的业务中，或者服务器负载较重，对线程数有严
格限制的场景

/**
 * 固定长度线程池
 *
 * @return
 */
public static ExecutorService newFixedThreadPool() {
    /**
    * corePoolSize 线程池的核心线程数
    * maximumPoolSize 能容纳的最大线程数
    * keepAliveTime 空闲线程存活时间
    * unit 存活的时间单位
    * workQueue 存放提交但未执行任务的队列
    * threadFactory 创建线程的工厂类:可以省略
    * handler 等待队列满后的拒绝策略:可以省略
     *
     * 适用于可以预测线程数量的业务中，或者服务器负载较重，对线程数有严
     * 格限制的场景
    */
    return new ThreadPoolExecutor(
            10,
            10,
           0l,
            TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(),
            Executors.defaultThreadFactory(),
            new ThreadPoolExecutor.AbortPolicy()
    );
}

newSingleThreadExecutor(常用)

作用：创建一个使用单个 worker 线程的 Executor，以无界队列方式来运行该
线程。（注意，如果因为在关闭前的执行期间出现失败而终止了此单个线程，
那么如果需要，一个新线程将代替它执行后续的任务）。可保证顺序地执行各
个任务，并且在任意给定的时间不会有多个线程是活动的。与其他等效的
newFixedThreadPool 不同，可保证无需重新配置此方法所返回的执行程序即
可使用其他的线程。
特征： 线程池中最多执行 1 个线程，之后提交的线程活动将会排在队列中以此
执行

public static ExecutorService newSingleThreadExecutor(){
    /**
     * corePoolSize 线程池的核心线程数
     * maximumPoolSize 能容纳的最大线程数
     * keepAliveTime 空闲线程存活时间
     * unit 存活的时间单位
     * workQueue 存放提交但未执行任务的队列
     * threadFactory 创建线程的工厂类:可以省略
     * handler 等待队列满后的拒绝策略:可以省略
     */
    return new ThreadPoolExecutor(
            1,
            1,
            0L,
            TimeUnit.SECONDS,
            new LinkedBlockingQueue(),
            Executors.defaultThreadFactory(),
            new ThreadPoolExecutor.AbortPolicy()
    );
}

newScheduleThreadPool

作用: 线程池支持定时以及周期性执行任务，创建一个 corePoolSize 为传入参
数，最大线程数为整形的最大数的线程池**
特征:
（1）线程池中具有指定数量的线程，即便是空线程也将保留 （2）可定时或者
延迟执行线程活动

场景: 适用于需要多个后台线程执行周期任务的场景

public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize,
                                                              ThreadFactory threadFactory){
    return new ScheduledThreadPoolExecutor(corePoolSize, threadFactory);
}

newWorkStealingPool

jdk1.8 提供的线程池，底层使用的是 ForkJoinPool 实现，创建一个拥有多个
任务队列的线程池，可以减少连接数，创建当前可用 cpu 核数的线程来并行执
行任务

public static ExecutorService newWorkStealingPool(int parallelism){
    /**
     * parallelism：并行级别，通常默认为 JVM 可用的处理器个数
     * factory：用于创建 ForkJoinPool 中使用的线程。
     * handler：用于处理工作线程未处理的异常，默认为 null
     * asyncMode：用于控制 WorkQueue 的工作模式:队列---反队列
     */
    return new ForkJoinPool(parallelism,
            ForkJoinPool.defaultForkJoinWorkerThreadFactory,
            null,
            true);
}

线程池底层工作原理(重要)

1. 在创建了线程池后，线程池中的线程数为零
2. 当调用 execute()方法添加一个请求任务时，线程池会做出如下判断： 2.1 如
   果正在运行的线程数量小于 corePoolSize，那么马上创建线程运行这个任务；
   2.2 如果正在运行的线程数量大于或等于 corePoolSize，那么将这个任务放入
   队列； 2.3 如果这个时候队列满了且正在运行的线程数量还小于
   maximumPoolSize，那么还是要创建非核心线程立刻运行这个任务； 2.4 如
   果队列满了且正在运行的线程数量大于或等于 maximumPoolSize，那么线程
   池会启动饱和拒绝策略来执行。
3. 当一个线程完成任务时，它会从队列中取下一个任务来执行
4. 当一个线程无事可做超过一定的时间（keepAliveTime）时，线程会判断：
   4.1 如果当前运行的线程数大于 corePoolSize，那么这个线程就被停掉。 4.2
   所以线程池的所有任务完成后，它最终会收缩到 corePoolSize 的大小。

2 算法和数据结构

快速排序

private static void quickSort(int[] arr, int start, int end) {
    int low = start;
    int height = end;
    int temp = arr[low];
    while (low < height) {
        while (low < height && arr[height] >= temp) {
            height--;
        }
        //找到右边比temp小的 就交换位置
        arr[low] = arr[height];
        while (low < height && arr[low] <= temp) {
            low++;
        }
        arr[height] = arr[low];
    }
    //退出循环时候 low == height
    arr[height] = temp;
    //小于low的都在左边 大于temp的都在右边
    //然后分别对左右部分进行递归调用
    if (start < low - 1) {
        quickSort(arr, start, low - 1);
    }
    if (low + 1 > end) {
        quickSort(arr, low + 1, end);
    }
}

寻找第k大元素 215

基于快速排序

//方法2 基于快排的优化
private static int myfindKthLargest2(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
//实现快速选择方法
private static int quickSelect(int[] nums, int start, int end, int index) {
    //找到基准pivot的位置返回
    int position = randomPatition(nums, start, end);
    //判断当前pivot是否为index
    if (position == index) {
        return nums[position];
    } else {
        return position > index ?
                quickSelect(nums, start, position - 1, index)
                : quickSelect(nums, position + 1, end, index);
    }
}
//随机选择 这个会提高选择效率
public static int randomPatition(int[] nums, int start, int end) {
    Random random = new Random();
    int randIndex = start + random.nextInt(end - start + 1);
    swap(nums, start, randIndex);
    return partition(nums, start, end);
}
//分区方法
public static int partition(int[] nums, int start, int end) {
    int temp = nums[start];
    int left = start;
    int right = end;
    while (left < right) {
        while (left < right && nums[right] >= temp) {
            right--;
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= temp) {
            left++;
        }
        nums[right] = nums[left];
    }
    //退出循环的时候 left索引位置的数等于right索引位置的数
    nums[left] = temp;
    //返回找到的索引位置
    return left;
}
// 定义一个交换元素的方法
public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

基于堆排序

//方法3 基于堆排序
private static int myfindKthLargest3(int[] nums, int k) {
    int n = nums.length;
    //保存堆的大小，初始就是n
    int heapSize = n;
    //构建大顶堆的操作
    buildMaxHeap(nums, heapSize);
    //执行k-1次删除堆顶元素操作
    //执行交换操作
    for (int i = n - 1; i > n - k; i--) {
        //将堆顶元素交换到当前堆的末尾
        swap(nums, 0, i);
        heapSize--;
        maxheapify(nums, 0, heapSize);
    }
    //返回当前堆顶元素 第k大
    return nums[0];
}
//实现一个构建大顶堆的方法
private static void buildMaxHeap(int[] nums, int heapSize) {
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
        maxheapify(nums, i, heapSize);
    }
}
//定义一个调整成大顶堆的操作
private static void maxheapify(int[] nums, int top, int heapSize) {
    // 定义左右子节点
    int left = top * 2 + 1;
    int right = top * 2 + 2;
    //保存当前最大元素的索引位置
    int largest = top;
    //比较左右子节点 记录最大元素索引位置
    if (right < heapSize && nums[right] > nums[largest]) {
        largest = right;
    }
    if (left < heapSize && nums[left] > nums[largest]) {
        largest = left;
    }
    //将最大元素换到堆顶
    if (largest != top) {
        swap(nums, top, largest);
        //递归调用 继续下沉
        maxheapify(nums, largest, heapSize);
    }
}

颜色分类 75

基于快速排序 双指针(最优)

//3 基于 双指针 快排排序
public static void sortColors3(int[] nums) {
    // 定义左右指针
    int left = 0, right = nums.length - 1;
    //定义一个遍历所有元素的指针
    int i = left;
    //循环判断 遍历元素
    while (left < right && i <= right) {
        // 如果是2换到末尾 右指针左移 while 防止换到相同 就继续换
        while (i <= right && nums[i] == 2) {
            swap(nums, i, right--);
        }
        //如果是0 换到头部左指针右移
        if (nums[i] == 0) {
            swap(nums, i, left++);
        }
        //继续遍历
        i++;
    }
}

基于计数排序

public static void sortColors2(int[] nums) {
    int count0 = 0, count1 = 0;
    //遍历数组 统计0 1 2的个数
    for (int num : nums) {
        if (num == 0) {
            count0++;
        } else if (num == 1) {
            count1++;
        }
    }
    //将0 1 2 按照个数一次填入nums数组
    for (int i = 0; i < nums.length; i++) {
        if (i < count0) {
            nums[i] = 0;
        } else if (i < count0 + count1) {
            nums[i] = 1;
        } else {
            nums[i] = 2;
        }
    }
}

基于选择排序

public static void sortColors(int[] nums) {
    //定义一个指针 指向当前应该填入元素的位置
    int curr = 0;
    //1 遍历数组 将所有的0 交换到数组头部
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            swap(nums, curr++, i);
        }
    }
    //遍历数组 将所有的1 交换到中间位置 接着之前curr继续
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            swap(nums, curr++, i);
        }
    }
}

合并区间 75

public class merge {
    public static void main(String[] args) {
        int[][] intervals = {
                {1, 3},
                {2, 6},
                {8, 10},
                {15, 18}
        };
        merge(intervals);
    }
    //方法1 排序
    public static int[][] merge(int[][] intervals) {
        // 定义一个结果数组
        ArrayList<int[]> result = new ArrayList<>();
        // 将所有区间按照左边界排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //遍历排序后的区间逐个合并
        for (int[] interval : intervals) {
            //记录当前的左右边界
            int left = interval[0], right = interval[1];
            //获取结果数组长度
            int length = result.size();
            //如果left比最后一个区间的右边界大，不能合并 直接添加到结果
            if (length == 0 || left > result.get(length - 1)[1]) {
                result.add(interval);
            }else {
                //可以合并
                int mergedLeft = result.get(length - 1)[0];
                int mergedRight  = Math.max(result.get(length - 1)[1], right);
                result.set(length - 1, new int[]{mergedLeft, mergedRight});
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

二叉树

二叉树性质

• 若二叉树的层次从0开始，则在二叉树的第i层至多右2的i次方个节点(i>0)
• 高度为k的二叉树最多右2的（k+1）次方减1个节点（k>=-1）空树高度为-1
• 对于任何一个二叉树，如果其叶子节点为m，度为2的节点数为n,则m=n+1

满二叉树和完全二叉树

• 满二叉树：除了叶子节点外，每个节点都有两个子节点，每一层都被完全填充。
• 完全二叉树：除了最后一层外，每一层都被完全填充，并且最后一层所有节点保持向左对齐。

递归

递归实现的两个必要条件

1. 必须定义一个“基准条件”，也就是递归终止的条件。在这种情况下，可以直接返回结果，无需继续递归。
2. 在方法中通过调用自身，向着基准情况前进。

一个简单示例就是计算阶乘：0 的阶乘被特别地定义为 1; n的阶乘可以通过计算 n-1的阶乘再乘以n来求得的。

public class ReCurstion {
    //定义一个计算阶乘的方法
    public static int factorial(int n) {
        if (n == 0) return 1;
        return factorial(n - 1) * n;
    }
    //节约栈空间占用 尾递归
    public static int factorial2(int n,int acc) {
        if (n == 0) return acc;
        return factorial2(n - 1, acc * n);
    }
}

遍历二叉树

• 中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。随着递归的逐渐出栈，最终完成遍历
• 先序遍历：即根-左-右遍历
• 后序遍历：即左-右-根遍历
• 层序遍历：按照从上到下、从左到右的顺序，逐层遍历所有节点。

// 构建二叉树
//树的节点类 二叉树
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class TreePrinter {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        node4.right = node6;
        printTreePreOrder(node1);
        System.out.println();
        printTreeLevelOrder(node1);
    }
    //二叉树的遍历
    //1 先序遍历 先打印根 再遍历左右节点
    public static void printTreePreOrder(TreeNode root) {
        //处理基准情况 节点没有叶子节点就结束
        if (root == null) return;
        System.out.print(root.val + "\t");
        printTreePreOrder(root.left);//打印左子树
        printTreePreOrder(root.right);//打印右子树
    }
    //2 中序遍历 先打左子树 再打印根 再打印右子树
    public static void printTreeInOrder(TreeNode root) {
        //处理基准情况 节点没有叶子节点就结束
        if (root == null) return;
        printTreeInOrder(root.left);//先打印左子树
        System.out.print(root.val + "\t");//再打印根节点
        printTreeInOrder(root.right);//再打印右子树
    }
    //3 后序遍历 先打左子树  再打印右子树 再打印根
    public static void printTreePostOrder(TreeNode root) {
        //处理基准情况 节点没有叶子节点就结束
        if (root == null) return;
        printTreePostOrder(root.left);//先打印左子树
        printTreePostOrder(root.right);//再打印右子树
        System.out.print(root.val + "\t");//再打印根节点
    }
    //4 层序遍历 分层遍历
    public static void printTreeLevelOrder(TreeNode root) {
        //定义一个队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //先把根节点放入队列
        queue.offer(root);
        //只要队列不为空 就一直出队
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            System.out.print(curNode.val + "\t");
            //将子节点加入队列
            if (curNode.left != null) {
                queue.offer(curNode.left);
            }
            if (curNode.right != null) {
                queue.offer(curNode.right);
            }
        }
    }
}

二叉搜索树（Binary Search Tree）

二叉搜索树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下性质：

• 任意节点左子树如果不为空，则左子树中节点的值均小于根节点的值
• 任意节点右子树如果不为空，则右子树中节点的值均大于根节点的值
• 任意节点的左右子树，也分别是二叉搜索树
• 没有键值相等的节点

平衡二叉搜索树 AVL树

平衡二叉搜索树：简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。

它具有如下几个性质：

• l 可以是空树
• l 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1
  
  AVL树是带有平衡条件的二叉搜索树，它是严格的平衡二叉树，平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的。旋转的目的是为了降低树的高度，使其平衡。

使用场景

AVL树适合用于插入删除次数比较少，但查找多的情况。也在Windows进程地址空间管理中得到了使用。

红黑树

• 红黑树是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
• 性质：
• l 节点是红色或黑色
• l 根节点是黑色
• l 每个叶子节点都是黑色的空节点（NIL节点）。
• l 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
• l 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
  

在插入一个新节点时，默认将它涂为红色（这样可以不违背最后一条规则），然后进行旋转着色等操作，让新的树符合所有规则。

红黑树也是一种自平衡二叉查找树，可以认为是对AVL树的折中优化。

使用场景

• 红黑树多用于搜索,插入,删除操作多的情况下。红黑树应用比较广泛：
• l 广泛用在各种语言的内置数据结构中。比如C++的STL中，map和set都是用红黑树实现的。Java中的TreeSet，TreeMap也都是用红黑树实现的。
• l 著名的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块。
• l epoll在内核中的实现，用红黑树管理事件块
• l nginx中，用红黑树管理timer等

B树 B-Tree

B树(B-Tree)是一种自平衡的树，它是一种多路搜索树（并不是二叉的），能够保证数据有序。同时，B树还保证了在查找、插入、删除等操作时性能都能保持在O(logn)，为大块数据的读写操作做了优化，同时它也可以用来描述外部存储。

特点：

• l 定义任意非叶子结点最多只有M个儿子；且M>2
• l 根结点的儿子数为[2, M]
• l 除根结点以外的非叶子结点的儿子数为[M/2, M]
• l 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个key）
• l 非叶子结点的关键字个数 = 指向儿子的指针个数 – 1
• l 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
• l 非叶子结点的指针：P[1], P[2], …, P[M]，其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树
• l 所有叶子结点位于同一层

M = 3的B树

B+树

B+树是B-树的变体，也是一种多路搜索树。

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找。

B+的特性：

• l 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
• l 不可能在非叶子结点命中
• l 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
• l 更适合文件索引系统

B+ 树的优点：

• l 层级更低，IO 次数更少
• l 每次都需要查询到叶子节点，查询性能稳定
• l 叶子节点形成有序链表，范围查询方便。这使得B+树方便进行“扫库”，也是很多文件系统和数据库底层选用B+树的主要原因。

反转二叉树 226

public static void main(String[] args) {
    TreeNode node4 = new TreeNode(4);
    TreeNode node2 = new TreeNode(2);
    TreeNode node7 = new TreeNode(7);
    TreeNode node1 = new TreeNode(1);
    TreeNode node3 = new TreeNode(3);
    TreeNode node6 = new TreeNode(6);
    TreeNode node9 = new TreeNode(9);
    node4.left = node2;
    node4.right = node7;
    node2.left = node1;
    node2.right = node3;
    node7.left = node6;
    node7.right = node9;
    printTreeLevelOrder(node4);
    invertTree(node4);
    System.out.println();
    printTreeLevelOrder(node4);
}
//方法1 先序遍历
public static TreeNode invertTree(TreeNode root) {
    //处理基准情况
    if (root == null) return null;
    //先处理根节点 交换左右节点
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    //递归处理左右子树
    invertTree(root.left);
    invertTree(root.right);
    return root;
}
//方法2 后序遍历
public static TreeNode invertTree2(TreeNode root) {
    //处理基准情况
    if (root == null) return null;
    TreeNode left = invertTree2(root.left);
    TreeNode right = invertTree2(root.right);
    root.left = right;
    root.right = left;
    return root;
}
//4 层序遍历 分层遍历
public static void printTreeLevelOrder(TreeNode root) {
    //定义一个队列
    LinkedList<TreeNode> queue = new LinkedList<>();
    //先把根节点放入队列
    queue.offer(root);
    //只要队列不为空 就一直出队
    while (!queue.isEmpty()) {
        TreeNode curNode = queue.poll();
        System.out.print(curNode.val + "\t");
        //将子节点加入队列
        if (curNode.left != null) {
            queue.offer(curNode.left);
        }
        if (curNode.right != null) {
            queue.offer(curNode.right);
        }
    }
}

平衡二叉树 110

//是否是平衡二叉树 110
public class isBalanced {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        boolean balanced = isBalanced(node4);
        System.out.println(balanced);
    }
    // 方法1 自顶向下 先序遍历
    public static boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    //定义一个计算树高度的方法
    public static int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    // 方法2 自低向上
    public static boolean isBalanced2(TreeNode root) {
        return balancedHeight(root) > -1;
    }
    //定义一个直接判断当前树是否平衡的方法 也返回高度
    public static int balancedHeight(TreeNode root) {
        if (root == null) return 0;
        //递归计算左右子树高度
        int leftHeight = balancedHeight(root.left);
        int rightHeight = balancedHeight(root.right);
        //如果子树不平衡 直接返回-1
        if (leftHeight == -1 || rightHeight == -1 ||
                Math.abs(leftHeight - rightHeight) > 1
        ) {
            return -1;
        }
        // 如果平衡 返回当前高度
        return Math.max(leftHeight, height(root.right)) + 1;
    }
}

98. 验证二叉搜索树

//98. 验证二叉搜索树
public class isValidBST {
    public static void main(String[] args) {
        //true
        /*TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(7);
        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(8);*/
        //false
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        System.out.println(isValidBST(node1));
    }
    // 方法2 中序遍历 把数值放到一个数组 判断前一个元素都比后一个元素大
    public static boolean isValidBST2(TreeNode root) {
    //定义一个list列表
    ArrayList<Integer> inOrderArrays = new ArrayList<>();
        // 中序遍历 得到一个升序数组
        inOrder(root,inOrderArrays);
        //遍历数组 判断是否升序
        for (int i = 0; i < inOrderArrays.size(); i++) {
            if (i > 0 && inOrderArrays.get(i) <= inOrderArrays.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
    private static void inOrder(TreeNode root,ArrayList<Integer> inOrderArrays) {
        if(root==null)return;
        inOrder(root.left,inOrderArrays);
        inOrderArrays.add(root.val);
        inOrder(root.right,inOrderArrays);
    }
    // 方法1 先序遍历
    public static boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return validator(root.left, null, root.val)
                && validator(root.right, root.val, null);
    }
    //定义一个辅助校验器 用来传入上下界递归调用
    public static boolean validator(TreeNode root, Integer lowerBound, Integer upperBound) {
        if (root == null) return true;
        // 判断当前节点的值是否在上下界范围内 如果超出直接返回false
        if (lowerBound != null && root.val <= lowerBound) {
            return false;
        }
        if (upperBound != null && root.val >= upperBound) {
            return false;
        }
        //递归判断左右子树
        return validator(root.left, lowerBound, root.val) && validator(root.right, root.val, upperBound);
    }
}