面试笔记

面试笔记

总结Java后端相关的重要知识点

Java基础

基础

Java语言的特点

• 简单易学、有丰富的类库
• 面向对象
• 与平台无关性，主要是JVM虚拟机的支持
• 可靠安全
• 支持多线程

你说你用过python/C++这些语言，说一下和Java有什么区别，或者说一下Java有什么缺点

• Java是面向对象的，比较符合人的认知
• Java和C++都是面向对象的，都支持封装、继承和多态
• Java不是通过指针访问内存的，程序的内存自动通过垃圾回收算法回收
• Java单继承，C++支持多重继承，虽然Java不可以多继承，但是接口可以多继承

说一下Java的八种基本类型

讲一下int和Integer的区别

• int是基本数据类型，Integer是int的封装类，是引用类型。int默认值是0，而Integer默认值是null，所以Integer能区分出0和null的情况。一旦java看到null，就知道这个引用还没有指向某个对象，再任何引用使用前，必须为其指定一个对象，否则会报错。
• 基本数据类型在声明时系统会自动给它分配空间，而引用类型声明时只是分配了引用空间， 必须通过实例化开辟数据空间之后才可以赋值。数组对象也是一个引用对象，将一个数组赋值给另 一个数组时只是复制了一个引用，所以通过某一个数组所做的修改在另一个数组中也看的见。
• 虽然定义了boolean这种数据类型，但是只对它提供了非常有限的支持。在Java虚拟机中没有任何供boolean值专用的字节码指令，Java语言表达式所操作的boolean值，在编译之后都使用Java 虚拟机中的int数据类型来代替，而boolean数组将会被编码成Java虚拟机的byte数组，每个元素 boolean元素占8位。这样我们可以得出boolean类型占了单独使用是4个字节，在数组中又是1个字 节。使用int的原因是，对于当下32位的处理器（CPU）来说，一次处理数据是32位（这里不是指的 是32/64位系统，而是指CPU硬件层面），具有高效存取的特点。

集合

有了解过Java中ArrayList和LinkedList的区别

• Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。 Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有 数据, (因为删除数据以后, 需要把后面所有的数据前移)
• LinkList是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于 ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。

TreeMap

TreeMap底层基于红黑树实现，可以保证在log(n)的时间复杂度内完成containsKey、get、put、remove操作。同时因为其由红黑树构成，也就是说明了能够维持内部元素的有序性，关于⽀持内部元素有序性的集合还有LinkedHashMap。

部分细节：

1. 红黑树相比于AVL树，牺牲了部分平衡性，以换取删除/插⼊操作时少量的旋转次数，整体来说，性能优于AVL
   树，但是做了性能测试，发现优化了的AVL树和红黑树相比差不了太多。
2. AVL树为了维护严苛的平衡条件，在破坏了平衡之后（插⼊、删除），需要执⾏旋转操作。共分为四种：左单
   旋、先左后右旋、右单旋、先右后左旋。
3. TreeMap内部无扩容的概念，因为使⽤的是树的链式存储结构
4. ⽀持范围查找，查找最近的元素
5. 以为内部是按照key进⾏排序的，所以不⽀持key为null
6. 排序依据，根据存放的对象是否实现Comprable接⼝。若实现了，则依据其⾃定义的compareTo⽅法，否者
   需要⾃定义外部比较器（Comparator），若是都未实现，则报错。

PriorityQueue

优先队列，是0个或者多个元素构成的集合，集合中按照某种排序方式（元素⾃身的权重）进⾏排序，不保证内部
元素整体有序，但是每次弹出的元素的优先级最高/低。

内部的数据结构是堆，因为堆底层的结构是完全⼆叉树，对于树的存储包含有链式存储或者顺序存储，
PriorityQueue使用的是顺序存储，所以使用的是Object[]数组，然后利用完全⼆叉树的性质，解决⽗⼦节点关系问
题。

默认实现是小根堆

实现细节

1. 未指定初始化容量⼤小，默认为11，感觉对于底层使用数组实现的集合，默认⼤小的规定好要没有啥规律可
   循
2. 扩容比其他集合多了⼀步，在数组长度 < 64 时，扩容为原先的两倍+2，超过64时，扩容为原先的1.5倍，同
   时做了放溢出处理，⽀持最⼤元素个数Integer.MAX_VALUE;
3. 删除和插⼊操作均会破坏当前的堆结果，所以每次都需要调用siftUp、siftDown动态调整
4. 插⼊操作是插⼊当前堆的末尾，调用siftUp，⾃底向上调整
5. 删除操作弹出堆顶元素，然后将堆最后⼀个元素置于堆顶，调用siftDown，⾃顶向下调整
6. 同样具有fast-fail机制

HashMap

HashMap概述

1. HashMap 底层是⼀个数组

2. 数组中每个元素是⼀个单向链表（即，采用拉链法解决哈希冲突）

单链表的节点每个节点是 Node<K, V> 类型（⻅下源码）

3. 同⼀个单链表中所有 Node 的 hash值不⼀定⼀样，但是他们对应的数组下标⼀定⼀样

数组下标利用哈希函数/哈希算法根据 hash值计算得到的

4. HashMap 是数组和单链表的结合体

   • 数组查询效率⾼，但是增删元素效率较低
   • 单链表在随机增删元素方⾯效率较⾼，但是查询效率较低
   • HashMap 将⼆者结合起来，充分它们各⾃的优点

5. HashMap 特点

   • 无序、不可重复
   • 无序：因为不⼀定挂在那个单链表上了

6. 为什么不可重复？通过重写 equals 方法保证的

HashMap源码

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

• HashMap默认初始化容量：16

  • 必须是2的次幂，主要是为了能够通过位运算获取key的索引位置，提升计算的效率
  • 为了达到散列均匀，以便提高HashMap集合的存取效率

• HashMap默认加载因子：0.75f

  • 数组容量达到 $\frac{3}{4}$ 时，开始扩容

• 扩容操作

  • 扩容的哈希表将拥有两倍的原容量，因为计算元素落在哪个位置的时候是 (n-1)&hash，n为数组长度，这样计算更加高效

• JDK 8 之后，对 HashMap 底层数据结构（单链表）进行了改进

  • 如果单链表元素超过8个，则将单链表转变为红黑树，大前提是整个Node数组容量>64；
  • 如果红黑树节点数量小于6时，会将红黑树重新变为单链表

put()方法

1. 先将 key, value 封装到 Node 对象中

2. 底层会调用 key 的 hashCode() 方法得出 hash 值

   static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

3. 通过哈希函数/哈希算法，将 hash 值转换为数组的下标

• 如果下标位置上没有任何元素，就把 Node 添加到这个位置上；
• 如果下标位置上有但链表，此时会将当前 Node 中的 key 与链表上每⼀个节点中的 key 进行 equals 比
  较
  • 如果所有的 equals 方法返回都是 false，那么这个新节点 Node 将被添加到链表的末尾；
  • 如果其中有⼀个 equals 返回了 true，那么链表中对应的这个节点的 value 将会被新节点 Node 的
    value 覆盖。（保证了不可重复）

1. HashMap 中允许 key 和 value 为 null，但是只能有⼀个（不可重复）
2. HashTable 中 key 和 value 都不允许为 null

get()方法

1. 先调用 key 的 hashCode() 方法得出 hash 值
2. 通过哈希函数/哈希算法，将 hash 值转换为数组的下标
3. 通过数组下标快速定位到数组中的某个位置：

• 如果这个位置上什么也没有（没有链表），则返回 null；
• 如果这个位置上有单链表，此时会将当前 Node 中的 key 与链表上每⼀个节点中的 key 进⾏ equals 比
  较。
  • 如果所有的 equals 方法返回都是 false，那么 get 方法返回 null；
  • 如果其中有⼀个 equals 返回了 true，那么这个节点的 value 便是我们要找的 value，此时 get 方
    法最终返回这个要找的 value。

• 放在 HashMap 中 key 的元素（或者放在 HashSet 中的元素）需要同时重写 hashCode() 和 equals() 方
  法
• 重写 hashCode() 方法时要达到散列分布均匀
  • 如果 hashCode() 方法返回⼀个固定的值，那么 HashMap 底层则变成了⼀个单链表；
  • 如果 hashCode() 方法所有返回的值都不同，此时 HashMap 底层则变成了⼀个数组

多线程

基础知识

为什么使用并发编程

• 可以充分利用CPU的计算能力
• 方便业务拆分，提升应用性能

并发编程有什么缺点

• 内存泄露
• 上下文切换
• 线程安全
• 死锁

并发编程的三要素

• 原子性：指的是一个或多个操作要么执行成功，要么全部执行失败
• 可见性：一个线程对共享变量的修改，另一个线程能够立刻看到
• 有序性：线程执行的顺序按照代码的先后顺序执行(处理器为了实现指令流水线，可能会对一些执行进行重排序)

解决线程安全

• 原子性问题：分多线程之间通过synchronized或使用锁lock
• 缓存导致的可见性问题：synchronized、volatile、LCOK，可以解决可见性问题
• 编译优化的有序性问题：Happens-Before规则

并行和并发

• 并发：多个任务在同一个 CPU 核上，按细分的时间片轮流(交替)执行，从逻辑上来看那些任务是 同时执行。
• 并行：单位时间内，多个处理器或多核处理器同时处理多个任务，是真正意义上的“同时进行”。
• 串行：有n个任务，由一个线程按顺序执行。由于任务、方法都在一个线程执行所以不存在线程不 安全情况，也就不存在临界区的问题。

线程和进程区别

• 进程：一个在内存中运行的应用程序。 每个正在系统上运行的程序都是一个进程
• 线程：进程中的一个执行任务（控制单元）， 它负责在程序里独立执行。

进程与线程的区别

• 根本区别：进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位
• 资源开销：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。
• 包含关系：如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共 同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。
• 内存分配：同一进程的线程共享本进程的地址空间和资源，而进程与进程之间的地址空间和资源是相互独立的
• 影响关系：一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃有可能导致整个进程都死掉。所以多进程要比多线程健壮。
• 执行过程：每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行

线程安全

什么是线程安全？

当多个线程访问一个对象时，如果不用考虑这些线程在运行时环境下的调度和交替执行，也不需要进行额外的同步，或者在调用方进行任何其他的协调操作，调用这个对象的行为都可以获得正确的结果，那这个对象就是线程安全的。

如何实现线程安全？

• 第一种：互斥同步

  synchronized锁

  • 普通同步方法，锁是当前的实例对象
  • 静态同步方法，锁时当前类的Class对象
  • 同步方法块，锁是Synchronized括号里匹配的对象

  如何实现：

  synchronized锁

  • synchronized经过编译之后，会在同步块的前后生成monitorenter和monitorexit这两个字节码指令，这两个字节码指令之后有一个reference类型的参数来指明要锁定和解锁的对象。在执行monitorenter指令时，首先会尝试获取对象的锁，如果该对象没有被锁定，或者当前线程已经拥有了那个对象的锁，把锁的计数器加一。若获取对象失败，那当前线程就要阻塞等待，直到对象锁被另一个线程释放。
  • synchronized用的锁是存放在对象头里面的，在jdk1.6之后，锁一共有四种状态：
    • 无锁状态
    • 偏向锁状态（在对象头和栈帧中的锁记录存储偏向锁的线程id）
    • 轻量级锁状态（将对象头的markword复制到当前线程的栈帧的锁记录中，使用CAS操作将对象头中的markword指向栈帧的锁记录，如果成功，则线程就拥有了对象的锁。如果两个以上的线程争用一把锁的话，则膨胀为重量级说）
    • 重量级锁

• 第二种：JUC包的重入锁

  在使用synchronized的时候，只能有一个线程可以获取对象的锁，其他线程就会进入阻塞状态，阻塞状态就会引起线程的挂起和唤醒，会带来很大的性能问题，所以就出现了非阻塞同步的实现方法

  先进行操作，如果没有其他线程争用共享数据，那么操作就成功了，如果共享数据有争用，就采取补偿措施（不断地重试）。

  CAS是实现非阻塞同步的计算机指令，它有三个操作数：内存位置，旧的预期值，新值，在执行CAS操作时，当且仅当内存地址的值符合旧的预期值的时候，才会用新值来更新内存地址的值，否则就不执行更新。

  使用方法：使用JUC包下的整数原子类decompareAndSet()和getAndIncrement()方法

  缺点 ：ABA 问题 版本号来解决

  只能保证一个变量的原子操作，解决办法：使用AtomicReference类来保证对象之间的原子性。可以把多个变量放在一个对象里。

• 第三种：无同步方法

  线程本地存储：将共享数据的可见性范围限制在一个线程中。这样无需同步也能保证线程之间不出现数据争用问题

  使用ThreadLocal类

  常见的使用场景：

  • 解决数据库连接
  • Session管理等

什么是上下文切换

• 多线程编程中一般线程的个数都大于 CPU 核心的个数，而一个 CPU 核心在任意时刻只能被一个线程使用，为了让这些线程都能得到有效执行，CPU 采取的策略是为每个线程分配时间片并轮转的 形式。当一个线程的时间片用完的时候就会重新处于就绪状态让给其他线程使用，这个过程就属于 一次上下文切换。
• 概括来说就是：当前任务在执行完 CPU 时间片切换到另一个任务之前会先保存自己的状态，以便下次再切换回这个任务时，可以再加载这个任务的状态。任务从保存到再加载的过程就是一次上下文切换。
• 上下文切换通常是计算密集型的。也就是说，它需要相当可观的处理器时间，在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间。所以，上下文切换对系统来说意味着消耗大量的 CPU 时间，事实上，可能是操作系统中时间消耗最大的操作。
• Linux 相比与其他操作系统（包括其他类 Unix 系统）有很多的优点，其中有一项就是，其上下文切换和模式切换的时间消耗非常少。

死锁的四个必要条件

• 互斥条件：在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，就只能等 待，直至占有资源的进程用毕释放。
• 占有且等待条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进 程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
• 不可抢占条件：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过 来。
• 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。（比如一个进程集合，A在 等B，B在等C，C在等A）

线程的状态

CAS算法

CAS是CompareAndSwap的缩写，中文意思是比较并替换。

当要进行CAS操作时，先比较内存地址和原来预期的地址比较，如果相同，表示这块内存地址没有被修改，可以用新地址替换，否则说明该地址被修改了，取消替换操作。

• 它的作用是可以将比较和交换转换为原子操作，这个原子操作直接由CPU保证，CAS可以保证共享变量赋值时的原子操作
• 是一种非阻塞算法的实现，可以在不使用锁的情况下实现多线程安全，是一种无锁算法

缺点是：

• 循环时间长开销大（自旋）
  • 如果CAS失败，会一直进行尝试，如果CAS长时间一直不成功，可能给CPU带来很大的开销
  • 解决办法：破坏掉死循环，当超过一定时间或者一定次数时，退出
• 只能保证一个共享变量的原子操作
  • 当对一个共享变量操作时，可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性
  • 解决方法：
    • 用锁来保证原子性
    • 把多个共享变量合成一个共享变量来操作
    • 封装成对象（JDK1.5开始，提供了AtomicReference类来保证引用对象之前的原子性，可以把多个变量放到一个对象来进行CAS操作
• ABA问题
  • 如果在内存地址V初次读取的值是A，并且在准备赋值的期间可能曾经被改为B，然后又改为A，在赋值前检查到仍然是A，这样CAS就会误认为它从来没有被修改过，这就是ABA问题
  • 解决方法：
    • 可以使用带有标记的原子引用类AtomicStampedReference，可以通过控制变量值的版本来保证CAS的正确性，即在变量前面添加版本号，每次变量更新的时候把版本+1，这样变化过程A-B-A就变成1A-2B-3A
    • 增加时间戳

关于Java多线程的synchronized和ThreadLocal有了解过吗

ThreadLocal^[1]和Synchronized都是为了解决多线程中相同变量的访问冲突问题，只是二者处理问题的思路和角度不同。

ThreadLocal

ThreadLocal 提供了线程本地的实例。它与普通变量的区别在于，每个使用该变量的线程都会初始化一个完全独立的实例副本。ThreadLocal 变量通常被private static修饰。当一个线程结束时，它所使用的所有 ThreadLocal 相对的实例副本都可被回收。

ThreadLocal 适用于每个线程需要自己独立的实例且该实例需要在多个方法中被使用，也即变量在线程间隔离而在方法或类间共享的场景

简单的示例如下：两个线程分表获取了自己线程存放的变量，他们之间变量的获取并不会错乱

public class ThreadLocaDemo {

    private static ThreadLocal<String> localVar = new ThreadLocal<String>();

    static void print(String str) {
        //打印当前线程中本地内存中本地变量的值
        System.out.println(str + " :" + localVar.get());
        //清除本地内存中的本地变量
        localVar.remove();
    }
    public static void main(String[] args) throws InterruptedException {

        new Thread(new Runnable() {
            public void run() {
                ThreadLocaDemo.localVar.set("local_A");
                print("A");
                //打印本地变量
                System.out.println("after remove : " + localVar.get());

            }
        },"A").start();

        Thread.sleep(1000);

        new Thread(new Runnable() {
            public void run() {
                ThreadLocaDemo.localVar.set("local_B");
                print("B");
                System.out.println("after remove : " + localVar.get());
            }
        },"B").start();
    }
}

ThreadLocal源码

set()方法

• 首先获取当前线程thread，并获取thread线程中的ThreadLocalMap
• 如果当前线程的ThreadLocalMap不为空，直接更行value值，如果map为空，示例化ThreadLocalMap，并将value值初始化

/**
 * Sets the current thread's copy of this thread-local variable
 * to the specified value.  Most subclasses will have no need to
 * override this method, relying solely on the {@link #initialValue}
 * method to set the values of thread-locals.
 *
 * @param value the value to be stored in the current thread's copy of
 *        this thread-local.
 */
public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        map.set(this, value);
    } else {
        createMap(t, value);
    }
}

/**
* Get the map associated with a ThreadLocal. Overridden in
* InheritableThreadLocal.
*
* @param  t the current thread
* @return the map
*/
ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

上述代码的ThreadLocalMap是什么，CreateMap又是什么，直接点击查看找到以下代码：

可看出ThreadLocalMap是ThreadLocal的内部静态类，而它的构成主要是用Entry来保存数据 ，而且还是继承的弱引用。在Entry内部使用ThreadLocal作为key，使用我们设置的value作为value

createMap是直接调用ThreadLocal的构造方法，构造一个新的ThreadLocalMap

  static class ThreadLocalMap {
 
        /**
         * The entries in this hash map extend WeakReference, using
         * its main ref field as the key (which is always a
         * ThreadLocal object).  Note that null keys (i.e. entry.get()
         * == null) mean that the key is no longer referenced, so the
         * entry can be expunged from table.  Such entries are referred to
         * as "stale entries" in the code that follows.
         */
        static class Entry extends WeakReference<ThreadLocal<?>> {
            /** The value associated with this ThreadLocal. */
            Object value;
 
            Entry(ThreadLocal<?> k, Object v) {
                super(k);
                value = v;
            }
        }
    }

/**
* Create the map associated with a ThreadLocal. Overridden in
* InheritableThreadLocal.
*
* @param t the current thread
* @param firstValue value for the initial entry of the map
*/
void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

/**
* Construct a new map initially containing (firstKey, firstValue).
* ThreadLocalMaps are constructed lazily, so we only create
* one when we have at least one entry to put in it.
*/
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
    table = new Entry[INITIAL_CAPACITY];
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    table[i] = new Entry(firstKey, firstValue);
    size = 1;
    setThreshold(INITIAL_CAPACITY);
}

get()方法

• get方法同样和set方法一样，首先需要获取当前线程thread-t， 然后获取当前线程的threadlocals变量(ThreadLocalMap)
• 如果当前theadlocals变量不为空，将当前线程的引用this(ThreadLocal)作为键值获取value
• 如果当前threadlocals变量为空，需要对当前线程的threadlocals变量进行初始化，然后返回初始化值

/**
* Returns the value in the current thread's copy of this
* thread-local variable.  If the variable has no value for the
* current thread, it is first initialized to the value returned
* by an invocation of the {@link #initialValue} method.
*
* @return the current thread's value of this thread-local
*/
public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    return setInitialValue();
}

/**
* Variant of set() to establish initialValue. Used instead
* of set() in case user has overridden the set() method.
*
* @return the initial value
*/
private T setInitialValue() {
    T value = initialValue();
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        map.set(this, value);
    } else {
        createMap(t, value);
    }
    if (this instanceof TerminatingThreadLocal) {
        TerminatingThreadLocal.register((TerminatingThreadLocal<?>) this);
    }
    return value;
}

/**
* Get the entry associated with key.  This method
* itself handles only the fast path: a direct hit of existing
* key. It otherwise relays to getEntryAfterMiss.  This is
* designed to maximize performance for direct hits, in part
* by making this method readily inlinable.
*
* @param  key the thread local object
* @return the entry associated with key, or null if no such
*/
private Entry getEntry(ThreadLocal<?> key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if (e != null && e.get() == key)
        return e;
    else
        return getEntryAfterMiss(key, i, e);
}

remove方法

该方法就是将ThreadLocal对应的值从当前Thread中的ThreadLocalMap中删除

/**
* Removes the current thread's value for this thread-local
* variable.  If this thread-local variable is subsequently
* {@linkplain #get read} by the current thread, its value will be
* reinitialized by invoking its {@link #initialValue} method,
* unless its value is {@linkplain #set set} by the current thread
* in the interim.  This may result in multiple invocations of the
* {@code initialValue} method in the current thread.
*
* @since 1.5
*/
public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null) {
        m.remove(this);
    }
}

实际上 ThreadLocalMap 中使用的 key 为 ThreadLocal 的弱引用，弱引用的特点是，如果这个对象只存在弱引用，那么在下一次垃圾回收的时候必然会被清理掉

所以如果 ThreadLocal 没有被外部强引用的情况下，在垃圾回收的时候会被清理掉的，这样一来 ThreadLocalMap中使用这个 ThreadLocal 的 key 也会被清理掉。但是，value 是强引用，不会被清理，这样一来就会出现 key 为 null 的 value。

ThreadLocal其实是与线程绑定的一个变量，如此就会出现一个问题：如果没有将ThreadLocal内的变量删除（remove）或替换，它的生命周期将会与线程共存。通常线程池中对线程管理都是采用线程复用的方法，在线程池中线程很难结束甚至于永远不会结束，这将意味着线程持续的时间将不可预测，甚至与JVM的生命周期一致。举个例字，如果ThreadLocal中直接或间接包装了集合类或复杂对象，每次在同一个ThreadLocal中取出对象后，再对内容做操作，那么内部的集合类和复杂对象所占用的空间可能会开始持续膨胀。

ThreadLocal常见使用场景

• 每个线程需要有自己单独的实例
• 实例需要在多个方法中共享，但不希望被多线程共享

例如

• 存储用户Session

  private static final ThreadLocal threadSession = new ThreadLocal();
   
      public static Session getSession() throws InfrastructureException {
          Session s = (Session) threadSession.get();
          try {
              if (s == null) {
                  s = getSessionFactory().openSession();
                  threadSession.set(s);
              }
          } catch (HibernateException ex) {
              throw new InfrastructureException(ex);
          }
          return s;
      }

• 数据跨层传输

Synchronized

Java中的synchronized，通过使⽤内置锁，来实现对共享变量的同步操作，进⽽解决了对共享变量操作的原⼦性、
保证了其他线程对共享变量的可⻅性、有序性，从⽽确保了并发情况下的线程安全。 同时synchronized是可重⼊的锁，避免了同⼀个线程重复请求⾃身已经获取的锁时出现死锁问题（请求于保持、不可剥夺感觉都有体现）

Synchronized的三种用法

1 普通方法

public class SynchronizedTest {
    public synchronized void test(String name){
        System.out.println(name+"开始执行");
        try {
            Thread.sleep(2000);
        }catch (Exception e){
        }
        System.out.println(name+"执行完毕");
    }
    public static void main(String[] args) throws  Exception {
        SynchronizedTest t=new SynchronizedTest();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t.test("线程1");
            }
        }).start();
        SynchronizedTest t1=new SynchronizedTest();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t1.test("线程2");
            }
        }).start();
    }
}

上面这个代码我们new了两个不同的对象。打印结果如下。线程2并没有等线程1执行完成后才执行，说明对于普通方法，如果是不同的对象实例锁是不起作用的

线程1开始执行
线程2开始执行
线程2执行完毕
线程1执行完毕

将代码改为一个实例

public class SynchronizedTest {
    public synchronized void test(String name){
        System.out.println(name+"开始执行");
        try {
            Thread.sleep(2000);
        }catch (Exception e){
        }
        System.out.println(name+"执行完毕");
    }

    public static void main(String[] args) throws  Exception {
        SynchronizedTest t=new SynchronizedTest();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t.test("线程1");
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t.test("线程2");
            }
        }).start();
    }
}

线程1开始执行
线程1执行完毕
线程2开始执行
线程2执行完毕

可以看到同一个对象实例的时候，第二个线程只等第一个线程执行完成后才开始执行

2 静态同步方法

对于静态同步方法来说，锁的是当前类的Class对象

public class SynchronizedTest {
    public synchronized static void test(String name){
        System.out.println(name+"开始执行");
        try {
            Thread.sleep(2000);
        }catch (Exception e){
        }
        System.out.println(name+"执行完毕");
    }
    public static void main(String[] args) throws  Exception {
        new Thread(new Runnable() {
            @Override
            public void run() {
                SynchronizedTest.test("线程1");
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                SynchronizedTest.test("线程2");
            }
        }).start();
    }
}

线程1开始执行
线程1执行完毕
线程2开始执行
线程2执行完毕

只用第一个线程执行完成后才开始执行第二个线程

3 同步方法块

对于同步方法块来说，锁的是synchronized括号里配置的对象

public class SynchronizedTest {
    public  void test(String name){
       Object o=new Object();
        synchronized(o.getClass()){
            System.out.println(name+"开始执行");
            try {
                Thread.sleep(2000);
            }catch (InterruptedException e){
                e.printStackTrace();
            }

            System.out.println(name+"执行完毕");
        }

    }
    public static void main(String[] args) throws  Exception {
        SynchronizedTest t=new SynchronizedTest();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t.test("线程1");
            }
        }).start();
        SynchronizedTest t1=new SynchronizedTest();
        new Thread(new Runnable() {
            @Override
            public void run() {
                t1.test("线程2");
            }
        }).start();
    }
}

线程1开始执行
线程1执行完毕
线程2开始执行
线程2执行完毕

第一个线程执行完成后才开始执行第二个线程

Synchronized是一个重量级锁

Synchronized 是通过对象内部的一个叫做监视器锁（monitor）来实现的，监视器锁本质又是依赖于底层的操作系统的 Mutex Lock（互斥锁）来实现的。而操作系统实现线程之间的切换需要从用户态转换到核心态，这个成本非常高，状态之间的转换需要相对比较长的时间，这就是为什么 Synchronized 效率低的原因。因此，这种依赖于操作系统 Mutex Lock 所实现的锁我们称之为 “重量级锁”。

Synchronized底层实现原理

同步方法通过ACC_SYNCHRONIZED 关键字隐式的对方法进行加锁。当线程要执行的方法被标注上ACC_SYNCHRONIZED时，需要先获得锁才能执行该方法。

同步代码块通过monitorenter和monitorexit执行来进行加锁。当线程执行到monitorenter的时候要先获得锁，才能执行后面的方法。当线程执行到monitorexit的时候则要释放锁。每个对象自身维护着一个被加锁次数的计数器，当计数器不为0时，只有获得锁的线程才能再次获得锁

Synchronized锁存储位置

Synchronized用的锁是存在java的对象头里面的。一个对象在new出来之后再内存中主要分为4个部分：

Mark Word：存储了对象的hashCode、GC信息、锁信息三部分。这部分占8字节。

Class Pointer：存储了指向类对象信息的指针。在64位JVM上有一个压缩指针选项-ClassPointer指针：-XX:+UseCompressedClassPointers 为4字节 不开启为8字节。默认是开启的。

实例数据(instance data)：记录了对象里面的变量数据。引用类型：-XX:+UseCompressedOops 为4字节 不开启为8字节 Oops Ordinary Object Pointers

Padding：作为对齐使用，对象在64位服务版本中，规定对象内存必须要能被8字节整除，如果不能整除，那么久靠对齐来不。举个例子：new出了一个对象，内存只占用18字节，但是规定要能被8整除，所以padding=6

Synchronized锁的升级过程

Java SE 1.6 为了减少获得锁和释放锁带来的性能消耗，引入了 “偏向锁” 和 “轻量级锁”：锁一共有 4 种状态，级别从低到高依次是：无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态。锁可以升级但不能降级。

偏向锁：大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。当一个线程访问同步块并获取锁时，会在对象头和栈帧中记录存储锁偏向的线程ID，以后该线程在进入同步块时先判断对象头的Mark Word里是否存储着指向当前线程的偏向锁，如果存在就直接获取锁。

轻量级锁：当其他线程尝试竞争偏向锁时，锁升级为轻量级锁。线程在执行同步块之前，JVM会先在当前线程的栈帧中创建用于存储锁记录的空间，并将对象头中的MarkWord替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，标识其他线程竞争锁，当前线程便尝试使用自旋来获取锁。

重量级锁：锁在原地循环等待的时候，是会消耗CPU资源的。所以自旋必须要有一定的条件控制，否则如果一个线程执行同步代码块的时间很长，那么等待锁的线程会不断的循环反而会消耗CPU资源。默认情况下锁自旋的次数是10 次，可以使用-XX:PreBlockSpin参数来设置自旋锁等待的次数。10次后如果还没获取锁，则升级为重量级锁。

内置锁

在Java中，每个对象都有⼀把锁，放置于对象头中，⽤于记录当前对象被哪个线程所持有。
相对于实例数据，对象头属于额外开销，所以被设计的极⼩来提⾼效率（⼀个对象在堆中的分布：对象头、实例数
据、对⻬填充）。
对象头中的markword更加体现了这⼀点。markword⾮结构化的，这样在不同的锁状态下，能够复⽤相同的bit
位。markword中就有存储锁的信息的部分。

Synchronized是Java保留关键字，通过线程等待，牺牲时间来解决访问冲突。依靠JVM的锁机制来实现临界区的函数或者变量的访问中的原子性。在同步机制中，通过对象的锁机制保证同一时间只有一个线程的访问变量，此时被用作锁机制的变量被多个线程共享。

public class SqlConnectionUtil {
    private static SqlPool instance=null;
    public static synchronized SqlConnection getInstance(){
        if(instance==null)
            instance=new SqlPool();
        return instance.getSqlConnection();
    }

ThreadLocal和Synchronized的区别

ThreadLocal其实是与线程绑定的一个变量。ThreadLocal和Synchonized都用于解决多线程并发访问。

但是ThreadLocal与synchronized有本质的区别：

1、Synchronized用于线程间的数据共享，而ThreadLocal则用于线程间的数据隔离。

2、Synchronized是利用锁的机制，使变量或代码块在某一时该只能被一个线程访问。而ThreadLocal为每一个线程都提供了变量的副本，使得每个线程在某一时间访问到的并不是同一个对象，这样就隔离了多个线程对数据的数据共享。

而ThreadLoal却正好相反，它用于在多个线程间通信时能够获得数据共享。

一句话理解ThreadLocal，threadlocl是作为当前线程中属性ThreadLocalMap集合中的某一个Entry的key值Entry（threadlocl,value），虽然不同的线程之间threadlocal这个key值是一样，但是不同的线程所拥有的ThreadLocalMap是独一无二的，也就是不同的线程间同一个ThreadLocal（key）对应存储的值(value)不一样，从而到达了线程间变量隔离的目的，但是在同一个线程中这个value变量地址是一样的。

可重入锁(ReentrantLock)

ReentrantLock支持两种获取锁的方式，一种是公平模型，一种是非公平模型

公平锁

可重入锁：就是一个线程在获取了锁之后，再次去获取同一个锁，这时候仅仅是把状态值进行累加

如果线程释放了一次锁，状态值减1。只有线程完全释放锁，状态值减到0，其他线程才有机会获取锁。

• 状态：volatile int state
• 获取锁线程：Thread
• 排队队列：Node双向队列

非公平锁

非公平锁时要唤醒阻塞的线程时，其他的线程抢占锁，阻塞的线程只能继续休眠

线程池

线程池优点

Java中的线程池是运用场景最多的并发框架，几乎所有需要异步或并发执行任务的程序都可以使用线程池。在开发过程中，合理地使用线程池能够带来许多好处。

• 降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
• 提高响应速度。当任务到达时，任务可以不需要等到线程创建就能立即执行。
• 提高线程的可管理性。线程是稀缺资源，如果无限制地创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配、调优和监控。但是，要做到合理利用‘

线程池的创建

ThreadPoolExecutor其实也是JAVA的一个类，我们一般通过Executors工厂类的方法，通过传入 不同的参数，就可以构造出适用于不同应用场景下的ThreadPoolExecutor（线程池）

/**
* Creates a new {@code ThreadPoolExecutor} with the given initial
* parameters and default thread factory and rejected execution handler.
* It may be more convenient to use one of the {@link Executors} factory
* methods instead of this general purpose constructor.
*
* @param corePoolSize the number of threads to keep in the pool, even
*        if they are idle, unless {@code allowCoreThreadTimeOut} is set
* @param maximumPoolSize the maximum number of threads to allow in the
*        pool
* @param keepAliveTime when the number of threads is greater than
*        the core, this is the maximum time that excess idle threads
*        will wait for new tasks before terminating.
* @param unit the time unit for the {@code keepAliveTime} argument
* @param workQueue the queue to use for holding tasks before they are
*        executed.  This queue will hold only the {@code Runnable}
*        tasks submitted by the {@code execute} method.
* @throws IllegalArgumentException if one of the following holds:<br>
*         {@code corePoolSize < 0}<br>
*         {@code keepAliveTime < 0}<br>
*         {@code maximumPoolSize <= 0}<br>
*         {@code maximumPoolSize < corePoolSize}
* @throws NullPointerException if {@code workQueue} is null
*/
public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue) {
    this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,
         Executors.defaultThreadFactory(), defaultHandler);
}

相关参数的说明

• corePoolSize 核心线程数量
• maximumPoolSize 最大线程数量
• keepAliveTime 线程保持时间，N个时间单位 unit 时间单位（比如秒，分）
• workQueue 阻塞队列
• threadFactory 线程工厂
• handler 线程池拒绝策略

线程池的实现原理

提交一个任务到线程池中，线程池的处理流程如下：

• 判断线程池里的核心线程是否都在执行任务，如果不是（核心线程空闲或者还有核心线程没有被创建）则创建一个新的工作线程来执行任务。如果核心线程都在执行任务，则进入下个流程。
• 线程池判断工作队列是否已满，如果工作队列没有满，则将新提交的任务存储在这个工作队列里。如果工作队列满了，则进入下个流程。
• 判断线程池里的线程是否都处于工作状态，如果没有，则创建一个新的工作线程来执行任务。如果已经满了，则交给饱和策略来处理这个任务。

线程池源码

execute方法

public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    //由它可以获取到当前有效的线程数和线程池的状态
    int c = ctl.get();
    // 1.获取当前正在运行线程数是否小于核心线程池，是则新创建一个线程执行任务，否则将任务放到任务队列中
    if (workerCountOf(c) < corePoolSize) { // 标识行 <------
        if (addWorker(command, true)) //在addWorker中创建工作线程执行任务
            return;
        c = ctl.get();
    }
    // 2.当前核心线程池中全部线程都在运行workerCountOf(c) >= corePoolSize，所以此时将线程放到任务队列中
    if (isRunning(c) && workQueue.offer(command)) {
    		//线程池是否处于运行状态，且是否任务插入任务队列成功
        int recheck = ctl.get();
        if (! isRunning(recheck) && remove(command))
            //线程池是否处于运行状态，如果不是则使刚刚的任务出队
            reject(command); //抛出RejectedExceptionException异常
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false);
    }
    else if (!addWorker(command, false))
    // 3.插入队列不成功，且当前线程数数量小于最大线程池数量，此时则创建新线程执行任务，创建失败抛出异常
        reject(command);//抛出RejectedExceptionException异常
}

addWorker方法

private boolean addWorker(Runnable firstTask, boolean core) {
/*首先会再次检查线程池是否处于运行状态，核心线程池中是否还有空闲线程，都满足条件过后则会调用compareAndIncrementWorkerCount先将正在运行的线程数+1，数量自增成功则跳出循环，自增失败则继续从头继续循环*/
　　...
　　if (compareAndIncrementWorkerCount(c))
　　　　break retry;
　　...
/*正在运行的线程数自增成功后则将线程封装成工作线程Worker*/
　　boolean workerStarted = false;
　　boolean workerAdded = false;
　　Worker w = null;
　　try {
　　　　final ReentrantLock mainLock = this.mainLock;        //全局锁
　　　　w = new Woker(firstTask);        //将线程封装为Worker工作线程
　　　　final Thread t = w.thread;
　　　　if (t != null) {
　　　　　　mainLock.lock();    //获取全局锁
/*当持有了全局锁的时候，还需要再次检查线程池的运行状态等*/
　　　　　　try {
　　　　　　　　int c = clt.get();
　　　　　　　　int rs = runStateOf(c);        //线程池运行状态
　　　　　　　　if (rs < SHUTDOWN || (rs == SHUTDOWN && firstTask == null)){        //线程池处于运行状态，或者线程池关闭且任务线程为空
　　　　　　　　　　if (t.isAlive())    //线程处于活跃状态，即线程已经开始执行或者还未死亡，正确的应线程在这里应该是还未开始执行的
　　　　　　　　　　　　throw new IllegalThreadStateException();
　　　　　　　　　　workers.add(w);    //private final HashSet<Worker> wokers = new HashSet<Worker>();包含线程池中所有的工作线程，只有在获取了全局的时候才能访问它。将新构造的工作线程加入到工作线程集合中
　　　　　　　　　　int s = worker.size();    //工作线程数量
　　　　　　　　　　if (s > largestPoolSize)
　　　　　　　　　　　　largestPoolSize = s;
　　　　　　　　　　workerAdded = true;    //新构造的工作线程加入成功
　　　　　　　　}
　　　　　　} finally {
　　　　　　　　mainLock.unlock();
　　　　　　}
　　 　　　　if (workerAdded) {
　　　　　　　　t.start();    //在被构造为Worker工作线程，且被加入到工作线程集合中后，执行线程任务，注意这里的start实际上执行Worker中run方法，所以接下来分析Worker的run方法
　　　　　　　　workerStarted = true;
　　　　　　}
　　　　}
　　} finally {
　　　　if (!workerStarted)    //未能成功创建执行工作线程
　　　　　　addWorkerFailed(w);    //在启动工作线程失败后，将工作线程从集合中移除
　　}
　　return workerStarted;
}

Worker

//ThreadPoolExecutor$Worker，它继承了AQS，同时实现了Runnable，所以它具备了这两者的所有特性
private final class Worker extends AbstractQueuedSynchronizer implements Runnable {
　　final Thread thread;
　　Runnable firstTask;
　　public Worker(Runnable firstTask) {
　　　　setState(-1);    
　　　　//设置AQS的同步状态为-1，禁止中断，直到调用runWorker
　　　　this.firstTask = firstTask;
　　　　this.thread = getThreadFactory().newThread(this);   
　　　　 //通过线程工厂来创建一个线程，将自身作为Runnable传递传递
　　}
　　public void run() {
　　　　runWorker(this);    //运行工作线程
　　}
}

worker在执行完任务后，还会通过getTask方法循环获取工作队里的任务来执行

线程池案例

创建线程

import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class ThreadPoolExample implements Runnable{
    @Override
    public void run() {
        try {
            Thread.sleep(200);
        }catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        LinkedBlockingDeque<Runnable> queue = new LinkedBlockingDeque<>(5);
        ThreadPoolExecutor threadPool = new ThreadPoolExecutor(
                5,
                10,
                60,
                TimeUnit.SECONDS,
                queue
        );
        for (int i = 0; i < 16; i++) {
            threadPool.execute(new Thread(new ThreadPoolExample(), "Thread" + i));
            System.out.println("线程中活跃的线程数：" + threadPool.getPoolSize());
            if (queue.size() > 0) {
                System.out.println("----->队伍中阻塞的线程数：" + queue.size());
            }
        }
        threadPool.shutdown();
    }
}

运行的结果是

线程中活跃的线程数：1
线程中活跃的线程数：2
线程中活跃的线程数：3
线程中活跃的线程数：4
线程中活跃的线程数：5
线程中活跃的线程数：5
----->队伍中阻塞的线程数：1
线程中活跃的线程数：5
----->队伍中阻塞的线程数：2
线程中活跃的线程数：5
----->队伍中阻塞的线程数：3
线程中活跃的线程数：5
----->队伍中阻塞的线程数：4
线程中活跃的线程数：5
----->队伍中阻塞的线程数：5
线程中活跃的线程数：6
----->队伍中阻塞的线程数：5
线程中活跃的线程数：7
----->队伍中阻塞的线程数：5
线程中活跃的线程数：8
----->队伍中阻塞的线程数：5
线程中活跃的线程数：9
----->队伍中阻塞的线程数：5
线程中活跃的线程数：10
----->队伍中阻塞的线程数：5
Exception in thread "main" java.util.concurrent.RejectedExecutionException: Task Thread[Thread15,5,main] rejected from java.util.concurrent.ThreadPoolExecutor@5cad8086[Running, pool size = 10, active threads = 10, queued tasks = 5, completed tasks = 0]
	at java.util.concurrent.ThreadPoolExecutor$AbortPolicy.rejectedExecution(ThreadPoolExecutor.java:2063)
	at java.util.concurrent.ThreadPoolExecutor.reject(ThreadPoolExecutor.java:830)
	at java.util.concurrent.ThreadPoolExecutor.execute(ThreadPoolExecutor.java:1379)
	at com.madao33.ThreadPoolExample.main(ThreadPoolExample.java:27)

从结果可以观察出：

• 创建的线程池具体配置为：核心线程数量为5个；全部线程数量为10个；工作队列的长度为5。
• 我们通过queue.size()的方法来获取工作队列中的任务数。
• 刚开始都是在创建新的线程，达到核心线程数量5个后，新的任务进来后不再创建新的线程，而是将任务加入工作队列，任务队列到达上线5个后，新的任务又会创建新的普通线程，直到达到线程池最大的线程数量10个，后面的任务则根据配置的饱和策略来处理。我们这里没有具体配置，使用的是默认的配置AbortPolicy:直接抛出异常。

当然，为了达到需要的效果，上述线程处理的任务都是利用休眠导致线程没有释放

饱和策略

当队列和线程池都满了，说明线程池处于饱和状态，那么必须对新提交的任务采用一种特殊的策略来进行处理。这个策略默认配置是AbortPolicy，表示无法处理新的任务而抛出异常。JAVA提供了4中策略：

• AbortPolicy：直接抛出异常
• CallerRunsPolicy：只用调用所在的线程运行任务
• DiscardOldestPolicy：丢弃队列里最近的一个任务，并执行当前任务。
• DiscardPolicy：不处理，丢弃掉。

我们现在用第四种策略来处理上面的程序：

import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.RejectedExecutionHandler;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class ThreadPoolExample implements Runnable{
    @Override
    public void run() {
        try {
            Thread.sleep(200);
        }catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        LinkedBlockingDeque<Runnable> queue = new LinkedBlockingDeque<>(5);
        RejectedExecutionHandler handler = new ThreadPoolExecutor.DiscardOldestPolicy();
        ThreadPoolExecutor threadPool = new ThreadPoolExecutor(
                5,
                10,
                60,
                TimeUnit.SECONDS,
                queue,
                handler
        );
        for (int i = 0; i < 16; i++) {
            threadPool.execute(new Thread(new ThreadPoolExample(), "Thread" + i));
            System.out.println("线程中活跃的线程数：" + threadPool.getPoolSize());
            if (queue.size() > 0) {
                System.out.println("----->队伍中阻塞的线程数：" + queue.size());
            }
        }
        threadPool.shutdown();
    }
}

这里采用了丢弃策略后，就没有再抛出异常，而是直接丢弃。在某些重要的场景下，可以采用记录日志或者存储到数据库中，而不应该直接丢弃。

线程中活跃的线程数：1
线程中活跃的线程数：2
线程中活跃的线程数：3
线程中活跃的线程数：4
线程中活跃的线程数：5
线程中活跃的线程数：5
----->队伍中阻塞的线程数：1
线程中活跃的线程数：5
----->队伍中阻塞的线程数：2
线程中活跃的线程数：5
----->队伍中阻塞的线程数：3
线程中活跃的线程数：5
----->队伍中阻塞的线程数：4
线程中活跃的线程数：5
----->队伍中阻塞的线程数：5
线程中活跃的线程数：6
----->队伍中阻塞的线程数：5
线程中活跃的线程数：7
----->队伍中阻塞的线程数：5
线程中活跃的线程数：8
----->队伍中阻塞的线程数：5
线程中活跃的线程数：9
----->队伍中阻塞的线程数：5
线程中活跃的线程数：10
----->队伍中阻塞的线程数：5
线程中活跃的线程数：10
----->队伍中阻塞的线程数：5

Process finished with exit code 0

Callable、Future、FutureTash

Callable与Future是在JAVA的后续版本中引入进来的，Callable类似于Runnable接口，实现Callable接口的类与实现Runnable的类都是可以被线程执行的任务

• Callable是Runnable封装的异步运算任务。
• Future用来保存Callable异步运算的结果
• FutureTask封装Future的实体类

Callable与Runnbale的区别：

• Callable定义的方法是call，而Runnable定义的方法是run。
• call方法有返回值，而run方法是没有返回值的。
• call方法可以抛出异常，而run方法不能抛出异常。

Future

future表示异步计算的结果，提供了以下方法，主要是判断任务是否完成，中断任务，获取任务执行结果

public interface Future<V> {

    boolean cancel(boolean mayInterruptIfRunning);

    boolean isCancelled();

    boolean isDone();

    V get() throws InterruptedException, ExecutionException;

    V get(long timeout, TimeUnit unit)
        throws InterruptedException, ExecutionException, TimeoutException;
}

FutureTask

可取消的异步计算，此类提供了对Future的基本实现，仅在计算完成时才能获取结果，如果计算尚未完成，则阻塞get方法。

public class FutureTask<V> implements RunnableFuture<V>
public interface RunnableFuture<V> extends Runnable, Future<V>

FutureTask不仅实现了Future接口，还实现了Runnable接口，所以不仅可以将FutureTask当成一个任务交给Executor来执行，还可以通过Thread来创建一个线程。

Callable与FutureTask案例

import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.FutureTask;

public class MyCallableTask implements Callable<Integer> {


    @Override
    public Integer call() throws Exception {
        System.out.println("callable do something");
        Thread.sleep(5000);
        return new Random().nextInt(100);
    }

    public static void main(String[] args) throws Exception {
        Callable<Integer> callable = new MyCallableTask();
        FutureTask<Integer> future = new FutureTask<Integer>(callable);
        Thread thread = new Thread(future);
        thread.start();
        Thread.sleep(100);
        //尝试取消对此任务的执行
        future.cancel(true);
        //判断是否在任务正常完成前取消
        System.out.println("future is cancel:" + future.isCancelled());
        if(!future.isCancelled())
        {
            System.out.println("future is cancelled");
        }
        //判断任务是否已完成
        System.out.println("future is done:" + future.isDone());
        if(!future.isDone())
        {
            System.out.println("future get=" + future.get());
        }
        else
        {
            //任务已完成
            System.out.println("task is done");
        }
    }
}

运行结果

callable do something
future is cancel:true
future is done:true
task is done

Callable与Future

import java.util.concurrent.*;

public class CallableThread implements Callable<String> {

    @Override
    public String call() throws Exception {
        System.out.println("进入call方法，开始休眠，休眠时间为： " + System.currentTimeMillis());
        Thread.sleep(10000);
        return "今天停电";
    }

    public static void main(String[] args) throws Exception{
        ExecutorService es = Executors.newSingleThreadExecutor();
        Callable<String> call = new CallableThread();
        Future<String> fu = es.submit(call);
        es.shutdown();
        Thread.sleep(5000);
        System.out.println("主线程休眠5秒，当前时间" + System.currentTimeMillis());
        String str = fu.get();
        System.out.println("Future已拿到数据，str=" + str + ";当前时间为：" + System.currentTimeMillis());
    }
}

运行的结果是

进入call方法，开始休眠，休眠时间为： 1664097924448
主线程休眠5秒，当前时间1664097929462
Future已拿到数据，str=今天停电;当前时间为：1664097934459

这里的future是直接扔到线程池里面去执行的。由于要打印任务的执行结果，所以从执行结果来看，主线程虽然休眠了5s，但是从Call方法执行到拿到任务的结果，这中间的时间差正好是10s，说明get方法会阻塞当前线程直到任务完成。

通过FutureTask也可以达到同样的结果

public static void main(String[] args) throws Exception {
      ExecutorService es = Executors.newSingleThreadExecutor();
      Callable<String> call = new CallableThread();
      FutureTask<String> task = new FutureTask<String>(call);
      es.submit(task);
      es.shutdown();
      Thread.sleep(5000);
      System.out.println("主线程等待5秒，当前时间为：" + System.currentTimeMillis());
      String str = task.get();
      System.out.println("Future已拿到数据，str=" + str + ";当前时间为：" + System.currentTimeMillis());
}

可以通过以上代码的组合，得到这样一个应用场景

如有一种场景中，方法A返回一个数据需要10s,A方法后面的代码运行需要20s，但是这20s的执行过程中，只有后面10s依赖于方法A执行的结果。如果与以往一样采用同步的方式，势必会有10s的时间被浪费，如果采用前面两种组合，则效率会提高：

• 先把A方法的内容放到Callable实现类的call()方法中
• 在主线程中通过线程池执行A任务
• 执行后面方法中10秒不依赖方法A运行结果的代码
• 获取方法A的运行结果，执行后面方法中10秒依赖方法A运行结果的代码

这样代码执行效率一下子就提高了，程序不必卡在A方法处。

JVM

说一下你对Java虚拟机的理解

Java内存结构

方法区和堆是所有线程共享的内存区域；而java栈、本地方法栈和程序员计数器是运行是线程私有的内存区域。

• Java堆（Heap），是Java虚拟机所管理的内存中最大的一块。Java堆是被所有线程共享的一块内存区域，在虚拟机启动时创建。此内存区域的唯一目的就是存放对象实例，几乎所有的对象实例都在这里分配内存。
• 方法区（Method Area），方法区（Method Area）与Java堆一样，是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。
• 程序计数器（Program Counter Register）,程序计数器（Program Counter Register）是一块较小的内存空间，它的作用可以看做是当前线程所执行的字节码的行号指示器。
• JVM栈（JVM Stacks）,与程序计数器一样，Java虚拟机栈（Java Virtual Machine Stacks）也是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是Java方法执行的内存模型：每个方法被执行的时候都会同时创建一个栈帧（Stack Frame）用于链接、方法出口等信息。每一个方法被调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。
• 本地方法栈（Native Method Stacks）,本地方法栈（Native Method Stacks）与虚拟机栈所发挥的作用是非常相似的，其区别不过是虚拟机栈为虚拟机执行Java方法（也就是字节码）服务，而本地方法栈则是为虚拟机使用到的Native方法服务。

类加载机制

JVM中类的装载是由类加载器（ClassLoader）和它的子类来实现的，Java中的类加载器是一个重要的Java运行时系统组件，它负责在运行时查找和装入类文件中的类。 由于Java的跨平台性，经过编译的Java源程序并不是一个可执行程序，而是一个或多个类文件。当Java程序需要使用某个类时，JVM会确保这个类已经被加载、连接（验证、准备和解析）和初始化。

• 类的加载是指把类的.class文件中的数据读入到内存中，通常是创建一个字节数组读入.class文件，然后产生与所加载类对应的Class对象。
• 加载完成后，Class对象还不完整，所以此时的类还不可用。当类被加载后就进入连接阶段，这一阶段包括验证、准备（为静态变量分配内存并设置默认的初始值）和解析（将符号引用替换为直接引用）三个步骤。
• 最后JVM对类进行初始化，包括：1)如果类存在直接的父类并且这个类还没有被初始化，那么就先初始化父类；2)如果类中存在初始化语句，就依次执行这些初始化语句。

类的加载是由类加载器完成的，类加载器包括：根加载器（BootStrap）、扩展加载器（Extension）、系统加载器（System）和用户自定义类加载器（java.lang.ClassLoader的子类）。从Java 2（JDK 1.2）开始，类加载过程采取了父亲委托机制（PDM）。PDM更好的保证了Java平台的安全性，在该机制中，JVM自带的Bootstrap是根加载器，其他的加载器都有且仅有一个父类加载器。类的加载首先请求父类加载器加载，父类加载器无能为力时才由其子类加载器自行加载。JVM不会向Java程序提供对Bootstrap的引用。下面是关于几个类加载器的说明：

• Bootstrap：一般用本地代码实现，负责加载JVM基础核心类库（rt.jar）；
• Extension：从java.ext.dirs系统属性所指定的目录中加载类库，它的父加载器是Bootstrap；
• System：又叫应用类加载器，其父类是Extension。它是应用最广泛的类加载器。它从环境变量classpath或者系统属性java.class.path所指定的目录中记载类，是用户自定义加载器的默认父加载器。

垃圾回收算法

如果说垃圾收集算法是内存回收的方法论，那么垃圾收集器就是内存回收的具体实现。下图展示了7种作用于不同分代的收集器，其中用于回收新生代的收集器包括Serial、PraNew、ParallelScavenge，回收老年代的收集器包括Serial Old、Parallel Old、CMS，还有用于回收整个Java堆的G1收集器。不同收集器之间的连线表示它们可以搭配使用。

• Serial收集器（复制算法): 新生代单线程收集器，标记和清理都是单线程，优点是简单高效；
• ParNew收集器 (复制算法): 新生代收并行集器，实际上是Serial收集器的多线程版本，在多核CPU环境下有着比Serial更好的表现；
• Parallel Scavenge收集器 (复制算法): 新生代并行收集器，追求高吞吐量，高效利用 CPU。吞吐量 = 用户线程时间/(用户线程时间+GC线程时间)，高吞吐量可以高效率的利用CPU时间，尽快完成程序的运算任务，适合后台应用等对交互相应要求不高的场景；
• Serial Old收集器 (标记-整理算法): 老年代单线程收集器，Serial收集器的老年代版本；
• Parallel Old收集器 (标记-整理算法)： 老年代并行收集器，吞吐量优先，Parallel Scavenge收集器的老年代版本；
• CMS(Concurrent Mark Sweep)收集器（标记-清除算法）： 老年代并行收集器，以获取最短回收停顿时间为目标的收集器，具有高并发、低停顿的特点，追求最短GC回收停顿时间。
• G1(Garbage First)收集器 (标记-整理算法)： Java堆并行收集器，G1收集器是JDK1.7提供的一个新收集器，G1收集器基于“标记-整理”算法实现，也就是说不会产生内存碎片。此外，G1收集器不同于之前的收集器的一个重要特点是：G1回收的范围是整个Java堆(包括新生代，老年代)，而前六种收集器回收的范围仅限于新生代或老年代。
• ZGC（Z Garbage Collector）是一款由Oracle公司研发的，以低延迟为首要目标的一款垃圾收集器。它是基于动态Region内存布局，（暂时）不设年龄分代，使用了读屏障、染色指针和内存多重映射等技术来实现可并发的标记-整理算法的收集器。在JDK 11新加入，还在实验阶段，主要特点是：回收TB级内存（最大4T），停顿时间不超过10ms。
  • 优点：低停顿，高吞吐量，ZGC收集过程中额外耗费的内存小。
  • 缺点：浮动垃圾目前使用的非常少，真正普及还是需要写时间的。

新生代收集器：Serial、ParNew、Parallel Scavenge

老年代收集器：CMS、Serial Old、Parallel Old

整堆收集器：G1，ZGC(因为不涉年代不在图中)。

垃圾回收器

Serial收集器

是最基础的收集器，在JDK1.3.1之前是HotSpot虚拟机新生代收集器的唯一选择。他是一个单线程工作的收集器，其单线程的意义不是说它只会使用一个处理器或者一条收集线程去完成垃圾手机工作，更重要的腔调它在进行垃圾收集的时候，必须暂停其他所有工作线程，直到它收集结束。

• 在客户端模式下的默认新生代收集器，简单高效
• 在内存有限的情况下，是所有收集器里额外内存消耗最小的
• 单核处理器中或者处理器核心数较少的环境中，没有线程交互的开销

Stop The World：垃圾回收算法在进行垃圾回收的时候暂停用户线程，导致的卡顿，感觉就像世界停止了一样

ParNew收集器

ParNew收集器实质上是Serial收集器的多线程并行版本，除了同时使用多条线程进行垃圾收集之外，其余的行为包括Serial收集器可用的所有控制参数（例如：-XX：SurvivorRatio、-XX：PretenureSizeThreshold、-XX：HandlePromotionFailure等）、收集算法、Stop The World、对象分配规则、回收策略等都与Serial收集器完全一致，在实现上这两种收集器也共用了相当多的代码。

除了支持新生代多线程并行收集外，和Serial收集器没有太多创新之处，但是是不少运行在服务端的HotSpot虚拟机，尤其是JDK7之前首选的新生代收集器

同时，ParNew也可以和CMS收集器配合工作，CMS是一个老年代收集器，CMS激活后默认的新生代收集器就是ParNew收集器

Parallel Scavenge收集器

Parallel Scavenge收集器也是一款新生代收集器，它同样是基于标记-复制算法实现的收集器，也是能够并行收集的多线程收集器，它的目标是达到一个可控制的吞吐量（Throughtput)，所谓的吞吐量就是处理器用于运行用户代码的时间与处理器总消耗时间的比值
$$
吞吐量=\frac{运行用户代码时间}{运行用户代码时间+运行垃圾收集时间}
$$
Parallel Scavenge收集器提供了两个参数用于精确控制吞吐量，分别是

• 控制最大垃圾收集停顿时间的-XX：MaxGCPauseMillis参数
• 设置吞吐量大小的-XX：GCTimeRatio参数

Serial Old收集器

Serial Old是Serial收集器的老年代版本，它同样是一个单线程收集器，使用标记-整理算法

Parallel Old收集器

Parallel Old是Parallel Scavenge收集器的老年代版本，支持多线程并发收集，基于标记-整理算法实现

配合新生代Parallel Scavenge收集器使用，在注重吞吐量或者处理器资源较为稀缺的组合，可以优先考虑Parallel Scavenge

CMS垃圾回收器

CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器，它是基于标记-清除算法实现的，只会回收老年代和永久代，整个过程包含四个步骤：

• 初始标记
• 并发标记
• 重新标记
• 并发清除

其中初始标记、重新标记这两个步骤仍然需要“Stop The World”。

• 初始标记仅仅只是标记一下GCRoots能直接关联到的对象，速度很快；
• 并发标记阶段就是从GC Roots的直接关联对象开始遍历整个对象图的过程，这个过程耗时较长但是不需要停顿用户线程，可以与垃圾收集线程一起并发运行；
• 而重新标记阶段则是为了修正并发标记期间，因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的停顿时间通常会比初始标记阶段稍长一些，但也远比并发标记阶段的时间短；
• 最后是并发清除阶段，清理删除掉标记阶段判断的已经死亡的对象，由于不需要移动存活对象，所以这个阶段也是可以与用户线程同时并发的。

由于在整个过程中耗时最长的并发标记和并发清除阶段中，垃圾收集器线程都可以与用户线程一起工作，所以从总体上来说，CMS收集器的内存回收过程是与用户线程一起并发执行的

虽说CMS有：并发收集、低停顿的优点，但是还是有一些缺点：

• 首先，CMS收集器对处理器资源非常敏感。事实上，面向并发设计的程序都对处理器资源比较敏感。在并发阶段，它虽然不会导致用户线程停顿，但却会因为占用了一部分线程（或者说处理器的计算能力）而导致应用程序变慢，降低总吞吐量。CMS默认启动的回收线程数是（处理器核心数量+3）/4，也就是说，如果处理器核心数在四个或以上，并发回收时垃圾收集线程只占用不超过25%的处理器运算资源，并且会随着处理器核心数量的增加而下降。但是当处理器核心数量不足四个时，CMS对用户程序的影响就可能变得很大。
• 然后，由于CMS收集器无法处理“浮动垃圾”（Floating Garbage），有可能出现“Con-current ModeFailure”失败进而导致另一次完全“Stop The World”的Full GC的产生。在CMS的并发标记和并发清理阶段，用户线程是还在继续运行的，程序在运行自然就还会伴随有新的垃圾对象不断产生，但这一部分垃圾对象是出现在标记过程结束以后，CMS无法在当次收集中处理掉它们，只好留待下一次垃圾收集时再清理掉。这一部分垃圾就称为“浮动垃圾”。
• 因为是基于标记-清除算法实现的收集器，所以收集结束会有大量空间碎片产生。空间碎片过多时，将会给大对象分配带来很大麻烦，往往会出现老年代还有很多剩余空间，但就是无法找到足够大的连续空间来分配当前对象，而不得不提前触发一次Full GC。

G1垃圾回收器

Garbage First（简称G1）收集器是垃圾收集器技术发展历史上的里程碑式的成果，它开创了收集器面向局部收集的设计思路和基于Region的内存布局形式

G1是一款主要面向服务端应用的垃圾收集器。

G1开创的基于Region的堆内存布局，G1不再坚持固定大小以及固定数量的分代区域划分，而是把连续的Java堆划分为多个大小相等的独立区域（Region），每一个Region都可以根据需要，扮演新生代的Eden空间、Survivor空间，或者老年代空间。收集器能够对扮演不同角色的Region采用不同的策略去处理，这样无论是新创建的对象还是已经存活了一段时间、熬过多次收集的旧对象都能获取很好的收集效果。

Region中还有一类特殊的Humongous区域，专门用来存储大对象。G1认为只要大小超过了一个Region容量一半的对象即可判定为大对象。

Region的大小可以通过参数-XX：G1HeapRegionSize设定，取值范围为1MB～32MB，且应为2的N次幂

超过了整个Region容量的超级大对象，将会被存放在N个连续的Humongous Region之中，G1的大多数行为都把Humongous Region作为老年代的一部分来进行看待

具体的处理思路是让G1收集器去跟踪各个Region里面的垃圾堆积的“价值”大小，价值即回收所获得的空间大小以及回收所需时间的经验值，然后在后台维护一个优先级列表，每次根据用户设定允许的收集停顿时间（使用参数-XX：MaxGCPauseMillis指定，默认值是200毫秒），优先处理回收价值收益最大的那些Region，这也就是“Garbage First”名字的由来。这种使用Region划分内存空间，以及具有优先级的区域回收方式，保证了G1收集器在有限的时间内获取尽可能高的收集效率。

• 初始标记（Initial Marking）：仅仅只是标记一下GC Roots能直接关联到的对象，并且修改TAMS指针的值，让下一阶段用户线程并发运行时，能正确地在可用的Region中分配新对象。这个阶段需要停顿线程，但耗时很短，而且是借用进行Minor GC的时候同步完成的，所以G1收集器在这个阶段实际并没有额外的停顿。
• 并发标记（Concurrent Marking）：从GC Root开始对堆中对象进行可达性分析，递归扫描整个堆里的对象图，找出要回收的对象，这阶段耗时较长，但可与用户程序并发执行。当对象图扫描完成以后，还要重新处理SATB记录下的在并发时有引用变动的对象。
• 最终标记（Final Marking）：对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的SATB记录。
• 筛选回收（Live Data Counting and Evacuation）：负责更新Region的统计数据，对各个Region的回收价值和成本进行排序，根据用户所期望的停顿时间来制定回收计划，可以自由选择任意多个Region构成回收集，然后把决定回收的那一部分Region的存活对象复制到空的Region中，再清理掉整个旧Region的全部空间。这里的操作涉及存活对象的移动，是必须暂停用户线程，由多条收集器线程并行完成的。

• G1收集器除了并发标记外，其余阶段也是要完全暂停用户线程的，它的目标是在延迟可控的情况下获得尽可能高的吞吐量
• 在小内存应用上CMS的表现大概率仍然要会优于G1，而在大内存应用上G1则大多能发挥其优势，这个优劣势的Java堆容量平衡点通常在6GB至8GB之间

ZGC垃圾回收器

ZGC的核心是一个并发垃圾回收器，其设计的目标是：

1. 停顿时间不超过10ms；
2. 停顿时间不会随着堆的大小，或者活跃对象的大小而增加；
3. 支持堆范围为8MB~4TB级别（未来支持16TB）。

总之， ZGC的目的就是在减少暂停时间的同时，仍然能压缩堆

ZGC内存管理

ZGC中管理物理内存的基本单位是segment。segment默认与small page size一样，都是2MB。引入segment是为了避免频繁的申请和释放内存的系统调用，一次申请2MB，当segment空闲时，将加入空闲列表，等待之后重复使用。

ZGC为了能高效、灵活地管理内存，实现了两级内存管理：虚拟内存和物理内存，并且实现了物理内存和虚拟内存的映射关系。这和操作系统中虚拟地址和物理地址设计思路基本一致。

当应用程序创建对象时，首先在堆空间申请一个虚拟地址，ZGC同时会为该对象在Marked0、Marked1和Remapped三个视图空间分别申请一个虚拟地址，且这三个虚拟地址对应同一个物理地址。

在ZGC中这三个空间在同一时间点有且仅有一个空间有效

为什么这么设计呢

这就是ZGC的高明之处，利用虚拟空间换时间

这三个空间的切换是由垃圾回收的不同阶段触发的，通过限定三个空间在同一时间点有且仅有一个空间有效高效的完成GC过程的并发操作，这个和ZGC并发处理算法有关系。ZGC并发处理算法利用全局空间视图的切换和对象地址视图的切换，结合SATB算法实现了高效的并发。

染色指针

我们都知道，之前的垃圾收集器都是把GC信息（标记信息、GC分代年龄..）存在对象头的Mark Word里。

而ZGC是这样做的：

如果某个对象是垃圾对象。就在这对象的信息里面标注这个对象是个垃圾。以后不管这个对象在哪儿使用，都知道他是个垃圾对象。

ZGC将对象信息存储在指针中，这种技术叫做——染色指针（Colored Pointer）。

在64位的机器中，对象指针是64位的。

ZGC使用64位地址空间的第0~43位存储对象地址，2^44 = 16TB，所以ZGC最大支持16TB的堆。

而第44~47位作为颜色标志位，Marked0、Marked1和Remapped代表三个视图标志位，Finalizable表示这个对象只能通过finalizer才能访问。

第48~63位固定为0没有利用。

读屏障

读屏障是JVM向应用代码插入一小段代码的技术。当应用线程从堆中读取对象引用时，就会执行这段代码。不要把这个读屏障和Java内存模型里面的读屏障搞混了，两者根本不是同一个东西，ZGC中的读屏障更像是一种AOP技术，在字节码层面或者编译代码层面给读操作增加一个额外的处理。

ZGC作为一款优秀垃圾收集器了，其借鉴了Pauseless GC，但在G1都没有普及的今天，谈论ZGC似乎为时过早。但也许我们探讨的不是ZGC，而是ZGC背后的设计思路。

数据结构

排序算法了解过吗，可以详细介绍一下吗

了解过一点，例如冒泡排序和选择排序

• 冒泡排序：每一轮循环都是和相邻的元素比较，然后一步步的将最小的元素或者最大的元素排在前面，时间复杂度是 $O(n^2)$

• 选择排序：每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。每一趟通过不断地比较交换来使得首元素为当前最小，交换是一个比较耗时间的操作，我们可以通过设置一个值来记录较小元素的下标，循环结束后存储的就是当前最小元素的下标，这时再进行交换就可以了。

  

  void Swap(int[] arr, int a, int b)
  {
  	int tmp = arr[a];
  	arr[a] = arr[b];
  	arr[b] = tmp;
  }
   
  void SimpleSelectSort(int[] arr)
  {
  	int min, len = arr.length;
  	for (int i = 0;i < len - 1;i++)
  	{
  		min = i;
  		for (int j = i + 1;j < len;j++)
  		{
  			if (arr[min] > arr[j])
  			{
  				min = j;
  			}
  		}
  		if (min != i)
  		{
  			Swap(arr,min,i);
  		}
  	}
  }

写一下反转链表的代码，伪代码即可

了解的链表反转有两种方法：

• 第一种是递归，递归的写法是需要明确两个条件：边界条件和递推关系
  • 先说一下递推关系：假设递归的顺序是先调整后面的结点，当前结点的后续结点都已经反转了，只需要反转当前结点和其后继结点的关系，这时候只需要将当前结点的后继结点的后继指向当前结点，即cur.next.next = cur，然后将当前结点的后继变为null，防止循环链表的出现，然后返回反转之后的头结点
  • 边界条件则是递归到最后一个节点，同时加上判断链表头结点是否为空的判断
• 另一种就是双指针，双指针比起递归来说要更好理解一些
  • 首先设置两个指针pre, cur，分别表示前一个结点和当前结点
  • 先设置一个临时变量保存当前结点的后继Node temp = cur.next，然后将当前结点的后继指向前一个结点cur.next = pre，这样实现了后继关系的反转，然后判断下一个，这时候的pre = cur; cur = temp
  • 反转结束之后返回pre为反转后链表的头结点

具体的代码如下所示：

public class BaiduInterview {
    /**
     * 递归实现链表反转
     * @param root 链表头结点
     * @return 返回反转后链表的头结点
     */
    public static Node reverseLinkedList(Node root) {
        if (root.next == null || root == null)
            return root;
        Node newroot = reverseLinkedList(root.next);
        root.next.next = root;
        root.next = null;
        return newroot;
    }

    public static Node reverseLinkedList2(Node root) {
        if (root.next == null || root == null)
            return root;
        Node pre = null, cur = root;
        while (cur != null) {
            Node temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 通过数组构建链表
     * @param nums 数组
     * @return head 链表头结点
     */
    public static Node constructLinkedList(int[] nums) {
        Node head = new Node();
        Node cur = head;
        for (int num : nums) {
            Node temp = new Node(num);
            temp.next = null;
            cur.next = temp;
            cur = temp;
        }
        return head.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        Node root = constructLinkedList(nums);
//        Node reversed2 = reverseLinkedList(root);
        Node reversed3 = reverseLinkedList2(root);
    }
}

/**
 * 定义链表结点
 */
class Node{
    public int val;
    public Node next;
    public Node(){};
    public Node(int val) {
        this.val = val;
    }
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}

红黑树

红黑树^[5]，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

1. 每个节点都有红色或黑色
2. 树的根始终是黑色的 (黑土地孕育黑树根， )
3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）
4. 从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

一棵典型的红黑树如下图所示

关于红黑树的左旋右旋操作过多，后续再来详细记载，可以先查看这篇文章

红黑树详解_晓之木初的博客-CSDN博客_红黑树

设计模式

有了解过Java的设计模式吗，手写一个单例模式

了解过一些，设计模式（Design Pattern）是前辈们对代码开发经验的总结，是解决特定问题的一系列套路。它
不是语法规定，而是一套用来提高代码可复用性、可维护性、可读性、稳健性以及安全性的解决方案。

单例模式、代理模式、模板方法模式、装饰器模式、工厂模式、责任链模式、观察者模式、原型模
式。

单例模式是一种常用的软件设计模式，在应用这个模式时，单例对象的类必须保证只有一个实例存在，整个系统只能使用一个对象实例。
优点：不会频繁地创建和销毁对象，浪费系统资源。

单例模式有很多种的写法^[2]：

• 饿汉式单例模式的写法：线程安全

  饿汉式在类加载时已经创建好该对象，在程序调用时直接返回该单例对象即可，即我们在编码时就已经指明了要马上创建这个对象，不需要等到被调用时再去创建。

  关于类加载，涉及到JVM的内容，我们目前可以简单认为在程序启动时，这个单例对象就已经创建好了。

  

  public class Singleton{
      
      private static final Singleton singleton = new Singleton();
      
      private Singleton(){}
      
      public static Singleton getInstance() {
          return singleton;
      }
  }

• 懒汉式单例模式的写法：非线程安全

  懒汉式创建对象的方法是在程序使用对象前，先判断该对象是否已经实例化（判空），若已实例化直接返回该类对象，否则则先执行实例化操作。

  

  public class Singleton {
      
      private static Singleton singleton;
      
      private Singleton(){}
      
      public static Singleton getInstance() {
          if (singleton == null) {
              singleton = new Singleton();
          }
          return singleton;
      }
      
  }

  这个单例模式是较为简单的写法，写完之后，面试官问如果在多线程的任务下，很多线程请求，可能会出现线程不安全的情况，都到达if(singleton == null)，可能会有复数个线程创建了不同的实例

  

  如何解决这个问题，这个时候需要考虑加锁，也就是下面这个方式

• 双检锁单例模式的写法：线程安全

  一般在懒汉单例非线程的代码上进行修改有两种简便的方式：一种是给对象加锁，一种是给方法加锁

  • 对象上锁

    public static Singleton getInstance() {
        synchronized(Singleton.class){
            if (singleton == null) {
                singleton = new Singleton();
            }
        }
        return singleton;
    }

  • 方法加锁

    public static synchronized Singleton getInstance() {
        if (singleton == null) {
            singleton = new Singleton();
        }
        return singleton;
    }

  • 这样就规避了两个线程同时创建Singleton对象的风险，但是引来另外一个问题：每次去获取对象都需要先获取锁，并发性能非常地差，极端情况下，可能会出现卡顿现象。
  • 接下来要做的就是优化性能，目标是：如果没有实例化对象则加锁创建，如果已经实例化了，则不需要加锁，直接获取实例

  直接在方法上加锁的方式被废除掉了，这种方式无论如何都需要先获取锁，所以在对象加锁代码的基础上进行优化

  优化的代码如下：

  public static Singleton getInstance() {
      if (singleton == null) {  // 线程A和线程B同时看到singleton = null，如果不为null，则直接返回singleton
          synchronized(Singleton.class) { // 线程A或线程B获得该锁进行初始化
              if (singleton == null) { // 其中一个线程进入该分支，另外一个线程则不会进入该分支
                  singleton = new Singleton();
              }
          }
      }
      return singleton;
  }

  上面的代码已经完美地解决了并发安全+性能低效问题：

  • 第2行代码，如果singleton不为空，则直接返回对象，不需要获取锁；而如果多个线程发现singleton为空，则进入分支；
  • 第3行代码，多个线程尝试争抢同一个锁，只有一个线程争抢成功，第一个获取到锁的线程会再次判断singleton是否为空，因为singleton有可能已经被之前的线程实例化
  • 其它之后获取到锁的线程在执行到第4行校验代码，发现singleton已经不为空了，则不会再new一个对象，直接返回对象即可
  • 之后所有进入该方法的线程都不会去获取锁，在第一次判断singleton对象时已经不为空了

  上面这段代码已经近似完美了，但是还存在最后一个问题：指令重排，这个时候可以使用volatile防止指令重排

  创建一个对象，在JVM中会经过三步：

  • 为singleton分配内存空间

  • 初始化singleton对象

  • 将singleton指向分配好的内存空间

  指令重排序是指：JVM在保证最终结果正确的情况下，可以不按照程序编码的顺序执行语句，尽可能提高程序的性能

  在这三步中，第2、3步有可能会发生指令重排现象，创建对象的顺序变为1-3-2，会导致多个线程获取对象时，有可能线程A创建对象的过程中，执行了1、3步骤，线程B判断singleton已经不为空，获取到未初始化的singleton对象，就会报NPE异常。文字较为晦涩，可以看流程图：

  

  使用volatile关键字可以防止指令重排序，可以这样理解：使用volatile关键字修饰的变量，可以保证其指令执行的顺序与程序指明的顺序一致，不会发生顺序变换，这样在多线程环境下就不会发生NPE异常了

  volatile还有第二个作用：使用volatile关键字修饰的变量，可以保证其内存可见性，即每一时刻线程读取到该变量的值都是内存中最新的那个值，线程每次操作该变量都需要先读取该变量。

  最终的代码如下

  public class Singleton {
      
      private static volatile Singleton singleton;
      
      private Singleton(){}
      
      public static Singleton getInstance() {
          if (singleton == null) {  // 线程A和线程B同时看到singleton = null，如果不为null，则直接返回singleton
              synchronized(Singleton.class) { // 线程A或线程B获得该锁进行初始化
                  if (singleton == null) { // 其中一个线程进入该分支，另外一个线程则不会进入该分支
                      singleton = new Singleton();
                  }
              }
          }
          return singleton;
      }
  }

拓展的方式，枚举实现

public enum Singleton {
    INSTANCE;
    
    public void doSomething() {
        System.out.println("这是枚举类型的单例模式！");
    }
}

枚举实现的优点：

• 对比饿汉和懒汉式来说，更加简洁
• 不需要做任何额外的操作去保证对象单一性与线程安全性
• 使用枚举可以防止调用者使用反射、序列化和反序列化机制强制生成多个单例对象，以此破坏单例模式

• 单例模式常见的写法有两种：懒汉式、饿汉式
• 懒汉式：在需要用到对象时才实例化对象，正确的实现方式是：Double Check + Lock，解决了并发安全和性能低下问题
• 饿汉式：在类加载时已经创建好该单例对象，在获取单例对象时直接返回对象即可，不会存在并发安全和性能问题。
• 在开发中如果对内存要求非常高，那么使用懒汉式写法，可以在特定时候才创建该对象；
• 如果对内存要求不高使用饿汉式写法，因为简单不易出错，且没有任何并发安全和性能问题
• 为了防止多线程环境下，因为指令重排序导致变量报NPE，需要在单例对象上添加volatile关键字防止指令重排序
• 最优雅的实现方式是使用枚举，其代码精简，没有线程安全问题，且 Enum 类内部防止反射和反序列化时破坏单例。

有在项目中用到过这种设计模式吗

在个人网站的开发过程中，每一个页面设置了一个head-img，使用的是枚举的单例模式实现的，在每一篇文章和每一个页面加载的时候创建图片的实例，并获取实例，为了加速访问数据，还将对应图片的路径/链接保存在redis数据库中

计算机网络

网络协议层次

• 应用层：HTTP，DNS(域名解析协议)，FTP(文件传输协议)
• 传输层：UDP,TCP
• 网络层：IP(网际协议)，ICMP(互联网控制报文协议），IGMP（互联网组管理协议），RIP

子网掩码

知网掩码又叫网络掩码、地址掩码、子网络遮罩，是一个应用于TCP/IP网络的32位二进制值。它可以屏蔽IP地址中的一部分，从而分离出IP地址中的网络部分与主机部分，基于子网掩码，管理员可以将网络进一步划分为若干子网。它必须结合IP地址一起使用。

如何通过子网掩码得到网络和主机地址

• 网络地址：二进制形式的IP地址与子网掩码的二进制做与运算，将结果转换为十进制就是网络地址
• 主机地址：将取反的子网掩码与IP地址做与，将结果转换为十进制得到主机地址

例如：

ip地址：192.168.0.1 子网掩码：255.255.255.0

ip二进制： 11000000.10101000.00000000.00000001

子网二进制：11111111.11111111.11111111.00000000

网络地址： 11000000.10101000.00000000.00000000 192.168.0.0

主机地址： 00000000.00000000.00000000.00000001 0.0.0.1

http和https的区别

HTTP^[3]：超文本传输协议（HTTP，HyperText Transfer Protocol）是互联网上应用最为广泛的一种网络协议。设计 HTTP 最初的目的是为了提供一种发布和接收 HTML 页面的方法。它可以使浏览器更加高效。HTTP 协议是以明文方式发送信息的，如果黑客截取了 Web 浏览器和服务器之间的传输报文，就可以直接获得其中的信息。

HTTPS：是以安全为目标的 HTTP 通道，是 HTTP 的安全版。HTTPS 的安全基础是 SSL。SSL 协议位于 TCP/IP 协议与各种应用层协议之间，为数据通讯提供安全支持。SSL 协议可分为两层：SSL 记录协议（SSL Record Protocol），它建立在可靠的传输协议（如TCP）之上，为高层协议提供数据封装、压缩、加密等基本功能的支持。SSL 握手协议（SSL Handshake Protocol），它建立在 SSL 记录协议之上，用于在实际的数据传输开始前，通讯双方进行身份认证、协商加密算法、交换加密密钥等。

简要概括一下两者的区别就是：

1、HTTPS 协议需要到 CA （Certificate Authority，证书颁发机构）申请证书，一般免费证书较少，因而需要一定费用。(以前的网易官网是http，而网易邮箱是 https 。)

2、HTTP 是超文本传输协议，信息是明文传输，HTTPS 则是具有安全性的 SSL 加密传输协议。

3、HTTP 和 HTTPS 使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。

4、HTTP 的连接很简单，是无状态的。HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，比 HTTP 协议安全。(无状态的意思是其数据包的发送、传输和接收都是相互独立的。无连接的意思是指通信双方都不长久的维持对方的任何信息。)

说一下加密算法，即https如何实现加密传输的

加密方法：SSL采用一种叫作公开秘钥加密的加密处理方式，近代的加密方法中加密算法是公开的，而秘钥是保密的，通过这种方式可以保持加密方法的安全性。

共享秘钥加密：加密和解密使用同一个秘钥的方式，在加密时必须要将秘钥也发给对方，在互联网转发秘钥时，如果通信被监听那么秘钥就可能会落入攻击者之手，同时也失去了加密的意义。

使用两把秘钥的公开秘钥加密：公开秘钥加密使用一堆非对称的秘钥，一把叫做私有秘钥，另一把叫做公开秘钥；发送密文的一方使用对方的公开密钥进行加密处理，对方收到被加密的信息后，再使用自己的私有秘钥进行解密，利用这种方式，不需要发送用来解密的私有秘钥，也不必担心秘钥被攻击者窃听而盗走；但是他的处理速度相对共享秘钥来说很慢。

HTTPS采用混合加密方式：利用两种加密方式的优点，组合起来进行通信；在交换秘钥环节使用公开密钥加密方式，之后的建立通信交换报文阶段则使用共享加密方式。

https采用对称加密与非对称加密的混合加密方式

混合加密方式原理：

1. 用户在浏览器发起HTTPS请求( 如https://www.mogu.com )，默认使用服务端的443端口进行连接；
2. HTTPS需要使用一套CA数字证书，证书内会附带一个公钥Pub，而与之对应的私钥Private保留在服务端不公开；
3. 服务端收到请求，返回配置好的包含公钥Pub的证书给客户端；
4. 客户端收到证书，校验合法性，主要包括是否在有效期内、证书的域名与请求的域名是否匹配，上一级证书是否有效（递归判断，直到判断到系统内置或浏览器配置好的根证书），如果不通过，则显示HTTPS警告信息，如果通过则继续；
5. 客户端生成一个用于对称加密的随机Key，并用证书内的公钥Pub进行加密，发送给服务端；
6. 服务端收到随机Key的密文，使用与公钥Pub配对的私钥Private进行解密，得到客户端真正想发送的随机Key；
7. 服务端使用客户端发送过来的随机Key对要传输的HTTP数据进行对称加密，将密文返回客户端；
8. 客户端使用随机Key对称解密密文，得到HTTP数据明文；
9. 后续HTTPS请求使用之前交换好的随机Key进行对称加解密。

HTTP状态码

HTTP状态码由三个十进制数字组成，第一个十进制数字定义了状态码的类型，后两个数字没有分类的作用

HTTP状态码分类

• 1xx 信息，服务器收到请求，需要请求者继续执行操作
• 2xx 成功，操作被成功接收并处理
• 3xx 重定向，需要进一步的操作以完成请求
• 4xx 客户端错误，请求包含语法错误或无法完成请求
• 5xx 服务器错误，服务器在处理请求的过程中发生了错误

数据库

数据库的隔离级别

数据库有四个隔离级别：

• 读未提交（Read uncommitted)

  这种隔离级别下，可以读取还未提交的数据，并发最高，但是可能导致脏读

• 读已提交（Read committed）

  可以读取已经提交的数据，可以避免脏读，但是仍然存在不可重复读和幻读的现象

• 可重复读（Repeated read)

  MySQL默认隔离级别，可以避免脏读，不可重复读的现象，但是仍然存在幻读的想想

• 串行化（Serializable)

  可以避免幻读、不可重复读、幻读的发生

• 脏读：一个事务在处理数据的过程中，读取到另一个未提交事务的数据
• 不可重复读：对于数据库中的某个数据，一个事务范围内的多次查询却返回了不同的结果，这是由于在查询过程中，数据被另一个事务修改并提交了，针对的是行级别的数据修改
• 幻读：对于同一查询，两次返回的数据统计不一致，针对的是表级别的新增数据，重点在于新增或者删除

有用过数据库吗，例如MySQL，可以讲一下MySQL的索引和他的索引引擎吗

官方介绍索引是帮助MySQL高效获取数据的数据结构。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中，也可能和数据一起存储在数据文件中）。我们通常所说的索引，包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等，没有特别说明，默认都是使用B+树结构组织（多路搜索树，并不一定是二叉的）的索引^[4]。

索引类型

• 主键索引：索引列中的值必须是唯一的，不允许有空值

• 普通索引：MySQL中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值。

• 唯一索引：索引列中的值必须是唯一的，但是允许为空值。

• 全文索引：只能在文本类型CHAR,VARCHAR,TEXT类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行like模糊查询时效率比较低，这时可以创建全文索引。 MyISAM和InnoDB中都可以使用全文索引。

• 空间索引：MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。

• 前缀索引：在文本类型如CHAR,VARCHAR,TEXT类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

• 其他（按照索引列数量分类）

  • 单列索引

  • 组合索引

    组合索引的使用，需要遵循最左前缀匹配原则（最左匹配原则）。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。

索引的数据结构

Hash表

Hash表，在Java中的HashMap，TreeMap就是Hash表结构，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

二叉查找树

每个节点最多有2个分叉，左子树和右子树数据顺序左小右大。

这个特点就是为了保证每次查找都可以这折半而减少IO次数，但是二叉树就很考验第一个根节点的取值，因为很容易在这个特点下出现我们并发想发生的情况“树不分叉了”，这就很难受很不稳定。

平衡二叉树

平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。

就这个特点来看，可能各位会觉得这就很好，可以达到二叉树的理想的情况了。然而依然存在一些问题：

时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）

平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B树：改造二叉树

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。

为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。

这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：

1. B树的节点中存储着多个元素，每个内节点有多个分叉。
2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
3. 父节点当中的元素不会出现在子节点中。
4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

在B树中查询数据的例子：

假如我们查询值等于10的数据。查询路径磁盘块1->磁盘块2->磁盘块5。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，10<15，走左路，到磁盘寻址磁盘块2。

第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<10，到磁盘中寻址定位到磁盘块5。

第三次磁盘IO：将磁盘块5加载到内存中，在内存中从头遍历比较，10=10，找到10，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。

相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。

虽然B树看来已经很理想了，但是仍然存在许多可以优化的地方：

• B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
• 如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树：改造B树

B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题

• B树：非叶子节点和叶子节点都会存储数据。
• B+树：只有叶子节点才会存储数据，非叶子节点至存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

B+树的最底层叶子节点包含了所有的索引项。从图上可以看到，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，所以放索引的磁盘块锁存放的索引数量是会跟着增加的，所以相对于B树来说，B+树的树高理论上情况下是比B树要矮的。也存在索引覆盖查询的情况，在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点

等值查询
假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。

• 第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走左路，到磁盘寻址磁盘块2。
• 第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，到磁盘中寻址定位到磁盘块6。
• 第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。（这里需要区分的是在InnoDB中Data存储的为行数据，而MyIsam中存储的是磁盘地址。）

范围查询

假如我们想要查找9和26之间的数据。查找路径是磁盘块1->磁盘块2->磁盘块6->磁盘块7。

• 首先查找值等于9的数据，将值等于9的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘IO。
• 查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块6，键值9开始向后遍历筛选所有符合筛选条件的数据。
• 第四次磁盘IO：根据磁盘6后继指针到磁盘中寻址定位到磁盘块7，将磁盘7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将data缓存到结果集。
• 主键具备唯一性（后面不会有<=26的数据），不需再向后查找，查询终止。将结果集返回给用户。

可以看到B+树可以保证等值和范围查询的快速查找，MySQL的索引就采用了B+树的数据结构

索引实现

MyIsam索引

以一个简单的user表为例。user表存在两个索引，id列为主键索引，age列为普通索引

CREATE TABLE `user`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = MyISAM
  AUTO_INCREMENT = 1
  DEFAULT CHARSET = utf8;

MyISAM的数据文件和索引文件是分开存储的。MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。

主键索引的B+树如下图所示：

表user的索引存储在索引文件user.MYI中，数据文件存储在数据文件 user.MYD中

主键等值索引

select * from user where id = 28;

• 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
• 将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
• 检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于30的索引项。（1次磁盘IO）
• 从索引项中获取磁盘地址，然后到数据文件user.MYD中获取对应整行记录。（1次磁盘IO）
• 将记录返给客户端。

磁盘IO次数：3次索引检索+记录数据检索。

主键返回查询数据

select * from user where id between 28 and 47;

• 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
• 将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
• 检索到叶节点，将节点加载到内存中遍历比较16<28，18<28，28=28<47。查找到值等于28的索引项。
• 根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）
• 我们的查询语句时范围查找，需要向后遍历底层叶子链表，直至到达最后一个不满足筛选条件。
• 向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）
• 最后得到两条符合筛选条件，将查询结果集返给客户端。

磁盘IO次数：4次索引检索+记录数据检索

在 MyISAM 中,辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。

InnoDB索引

每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：

• 在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。
• 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
• 如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。

这里以user_innodb为例，user_innodb的id列为主键，age列为普通索引。

CREATE TABLE `user_innodb`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = InnoDB;

InnoDB主键索引

查询等值数据

select * from user_innodb where id = 28;

• 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）
• 将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）
• 检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项，直接可以获取整行数据。将改记录返回给客户端。（1次磁盘IO）

辅助索引

除聚簇索引之外的所有索引都称为辅助索引，InnoDB的辅助索引只会存储主键值而非磁盘地址。

以表user_innodb的age列为例，age索引的索引结果如下图

底层叶子节点的按照（age，id）的顺序排序，先按照age列从小到大排序，age列相同时按照id列从小到大排序。

使用辅助索引需要检索两遍索引：首先检索辅助索引获得主键，然后使用主键到主索引中检索获得记录。

辅助索引等值查询的情况

select * from t_user_innodb where age=19;

根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。

磁盘IO数：辅助索引3次+获取记录回表3次

组合索引

还是以自己创建的一个表为例：表 abc_innodb，id为主键索引，创建了一个联合索引idx_abc(a,b,c)。

CREATE TABLE `abc_innodb`
(
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `a`  int(11)     DEFAULT NULL,
  `b`  int(11)     DEFAULT NULL,
  `c`  varchar(10) DEFAULT NULL,
  `d`  varchar(10) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_abc` (`a`, `b`, `c`)
) ENGINE = InnoDB;

组合索引的数据结构

组合索引的查询过程

select * from abc_innodb where a = 13 and b = 16 and c = 4;

最左匹配原则

最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。

在组合索引树中，最底层的叶子节点按照第一列a列从左到右递增排列，但是b列和c列是无序的，b列只有在a列值相等的情况下小范围内递增有序，而c列只能在a，b两列相等的情况下小范围内递增有序。

就像上面的查询，B+树会先比较a列来确定下一步应该搜索的方向，往左还是往右。如果a列相同再比较b列。但是如果查询条件没有a列，B+树就不知道第一步应该从哪个节点查起。

可以说创建的idx_abc(a,b,c)索引，相当于创建了(a)、（a,b）（a,b,c）三个索引。、

组合索引的最左前缀匹配原则：使用组合索引查询时，mysql会一直向右匹配直至遇到范围查询(>、<、between、like)就停止匹配

覆盖索引

覆盖索引并不是说是索引结构，覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候，我们只可以拿到主键值，相当于获取数据还需要再根据主键查询主键索引再获取到数据。但是试想下这么一种情况，在上面abc_innodb表中的组合索引查询时，如果我只需要abc字段的，那是不是意味着我们查询到组合索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是覆盖索引。

可以讲一下如何优化数据库查询吗

避免回表

在InnoDB的存储引擎中，使用辅助索引查询的时候，因为辅助索引叶子节点保存的数据不是当前记录的数据而是当前记录的主键索引，索引如果需要获取当前记录完整数据就必然需要根据主键值从主键索引继续查询。这个过程我们成位回表。想想回表必然是会消耗性能影响性能。那如何避免呢？

使用索引覆盖，举个例子：现有User表（id(PK),name(key),sex,address,hobby…）

如果在一个场景下，select id,name,sex from user where name ='zhangsan';这个语句在业务上频繁使用到，而user表的其他字段使用频率远低于它，在这种情况下，如果我们在建立 name 字段的索引的时候，不是使用单一索引，而是使用联合索引（name，sex）这样的话再执行这个查询语句是不是根据辅助索引查询到的结果就可以获取当前语句的完整数据。这样就可以有效地避免了回表再获取sex的数据。

这里就是一个典型的使用覆盖索引的优化策略减少回表的情况。

联合索引

联合索引，在建立索引的时候，尽量在多个单列索引上判断下是否可以使用联合索引。联合索引的使用不仅可以节省空间，还可以更容易的使用到索引覆盖。试想一下，索引的字段越多，是不是更容易满足查询需要返回的数据呢。比如联合索引（a_b_c），是不是等于有了索引：a，a_b，a_b_c三个索引，这样是不是节省了空间，当然节省的空间并不是三倍于（a，a_b，a_b_c）三个索引，因为索引树的数据没变，但是索引data字段的数据确实真实的节省了。

联合索引的创建原则，在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面，频繁使用代表索引利用率高，区分度高代表筛选粒度大，这些都是在索引创建的需要考虑到的优化场景，也可以在常需要作为查询返回的字段上增加到联合索引中，如果在联合索引上增加一个字段而使用到了覆盖索引，那我建议这种情况下使用联合索引。

联合索引的使用

考虑当前是否已经存在多个可以合并的单列索引，如果有，那么将当前多个单列索引创建为一个联合索引。
当前索引存在频繁使用作为返回字段的列，这个时候就可以考虑当前列是否可以加入到当前已经存在索引上，使其查询语句可以使用到覆盖索引。

数据库中的锁

锁的分类

MySQL大致可归纳为以下3种锁：

• 表级锁：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高，并发度最低。
• 行级锁：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。
• 页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般

MyIsam锁

在使用MyIsam时，我们只可以使用表级锁，而MySQL的表级锁有两种模式：

表共享锁（Table Read Lock）和表独占写锁（Table Write Lock），他们在工作时表现如下：

• 对某一个表的读操作，不会阻塞其他用户对同一表请求，但会阻塞对同一表的写请求；
• 对MyISAM的写操作，则会阻塞其他用户对同一表的读和写操作；
• MyISAM表的读操作和写操作之间，以及写操作之间是串行的。

当一个线程获得对一个表的写锁后，只有持有锁的线程可以对表进行更新操作。其他线程的读、写操作都会等待，直到锁被释放为止。

MyISAM在执行查询语句（SELECT）前，会自动给涉及的所有表加读锁，在执行更新操作（UPDATE、DELETE、INSERT等）前，会自动给涉及的表加写锁，这个过程并不需要用户干预

InnoDB

InnoDB与MyISAM的最大不同有两点：一是支持事务（TRANSACTION）；二是采用了行级锁。

行级锁和表级锁本来就有许多不同之处，另外，事务的引入也带来了一些新问题。

事务（Transaction）及其ACID属性

事务是由一组SQL语句组成的逻辑处理单元，事务具有4属性，通常称为事务的ACID属性。

• 原子性（Actomicity）：事务是一个原子操作单元，其对数据的修改，要么全都执行，要么全都不执行。
• 一致性（Consistent）：在事务开始和完成时，数据都必须保持一致状态。这意味着所有相关的数据规则都必须应用于事务的修改，以操持完整性；事务结束时，所有的内部数据结构（如B树索引或双向链表）也都必须是正确的。
• 隔离性（Isolation）：数据库系统提供一定的隔离机制，保证事务在不受外部并发操作影响的“独立”环境执行。这意味着事务处理过程中的中间状态对外部是不可见的，反之亦然。
• 持久性（Durable）：事务完成之后，它对于数据的修改是永久性的，即使出现系统故障也能够保持。

并发事务带来的问题

相对于串行处理来说，并发事务处理能大大增加数据库资源的利用率，提高数据库系统的事务吞吐量，从而可以支持可以支持更多的用户。但并发事务处理也会带来一些问题，主要包括以下几种情况。

• 更新丢失（Lost Update）：当两个或多个事务选择同一行，然后基于最初选定的值更新该行时，由于每个事务都不知道其他事务的存在，就会发生丢失更新问题——最后的更新覆盖了其他事务所做的更新。例如，两个编辑人员制作了同一文档的电子副本。每个编辑人员独立地更改其副本，然后保存更改后的副本，这样就覆盖了原始文档。最后保存其更改保存其更改副本的编辑人员覆盖另一个编辑人员所做的修改。如果在一个编辑人员完成并提交事务之前，另一个编辑人员不能访问同一文件，则可避免此问题

• 脏读（Dirty Reads）：一个事务正在对一条记录做修改，在这个事务并提交前，这条记录的数据就处于不一致状态；这时，另一个事务也来读取同一条记录，如果不加控制，第二个事务读取了这些“脏”的数据，并据此做进一步的处理，就会产生未提交的数据依赖关系。这种现象被形象地叫做“脏读”。

• 不可重复读（Non-Repeatable Reads）：一个事务在读取某些数据已经发生了改变、或某些记录已经被删除了！这种现象叫做“不可重复读”。

• 幻读

  （Phantom Reads）：一个事务按相同的查询条件重新读取以前检索过的数据，却发现其他事务插入了满足其查询条件的新数据，这种现象就称为“幻读”。

  • 产生幻读的原因是，行锁只能锁住行，但是新插入记录这个动作，要更新的是记录之间的“间隙”。因此，为了解决幻读问题，InnoDB只好引入新的锁，也就是间隙锁(Gap Lock)

InnoDB都有哪些锁

1. 行锁
   1. 共享锁（lock in share mode）
   2. 排他锁（for update）
2. 意向锁（表级别）
   1. 意向共享锁
   2. 意向排他锁
3. 间隙锁
4. Next-key lock：行锁（排他锁）+间隙锁

InnoDB的行锁模式及加锁方法

InnoDB实现了以下两种类型的行锁。

• 共享锁（s）：允许一个事务去读一行，阻止其他事务获得相同数据集的排他锁。xxx lock in share mode
• 排他锁（Ｘ）：允许获取排他锁的事务更新数据，阻止其他事务取得相同的数据集共享读锁和排他写锁。xxx for update

另外，为了允许行锁和表锁共存，实现多粒度锁机制，InnoDB还有两种内部使用的意向锁（Intention Locks），这两种意向锁都是表锁。

意向共享锁（IS）：事务打算给数据行共享锁，事务在给一个数据行加共享锁前必须先取得该表的IS锁。

意向排他锁（IX）：事务打算给数据行加排他锁，事务在给一个数据行加排他锁前必须先取得该表的IX锁。

InnoDB行锁实现方式

InnoDB行锁是通过索引上的索引项来实现的，这一点ＭySQL与Oracle不同，后者是通过在数据中对相应数据行加锁来实现的。InnoDB这种行锁实现特点意味者：只有通过索引条件检索数据，InnoDB才会使用行级锁，否则，InnoDB将使用表锁（如果是RR / Serializable 级别，将在主键上使用Next-Key Locks（行锁+间隙锁）来实现锁表的操作）

在InnoDB事务中，行锁是在需要的时候才加上的，但并不是不需要了就立刻释放，而是要等到事务结束时才释放。这个就是两阶段锁协议。

间隙锁

当我们用范围条件而不是相等条件检索数据，并请求共享或排他锁时，InnoDB（可重复读、串行化级别下才有效）会给符合条件的已有数据的索引项加锁；对于键值在条件范围内但并不存在的记录，叫做“间隙(GAP)”，InnoDB也会对这个“间隙”加锁，这种锁机制就是所谓的间隙锁它通常是一个开区间（xx, xx）。

InnoDB使用间隙锁的目的，一方面是为了防止幻读，以满足相关隔离级别的要求

很显然，在使用范围条件检索并锁定记录时，InnoDB这种加锁机制会阻塞符合条件范围内键值的并发插入，这往往会造成严重的锁等待。因此，在实际开发中，尤其是并发插入比较多的应用，我们要尽量优化业务逻辑，尽量使用相等条件来访问更新数据，避免使用范围条件。

Next-Key锁

next-key lock是InnoDB加锁的基本单位，它是一个前开后闭的区间，即行锁+间隙锁

InnoDB加锁规则

两个“原则”、两个“优化”和一个“bug”：

• 原则1：加锁的基本单位是next-key lock。next-key lock是前开后闭区间。
• 原则2：查找过程中访问到的对象才会加锁。
• 优化1：索引上的等值查询，给唯一索引加锁的时候，next-key lock退化为行锁。
• 优化2：索引上的等值查询，向右遍历时且最后一个值不满足等值条件的时候，next-key lock退化为间隙锁。
• 一个bug：唯一索引上的范围查询会访问到不满足条件的第一个值为止。

什么时候使用表锁

对于InnoDB表，在绝大部分情况下都应该使用行级锁，因为事务和行锁往往是我们之所以选择InnoDB表的理由。但在个别特殊事务中，也可以考虑使用表级锁。

• 第一种情况是：事务需要更新大部分或全部数据，表又比较大，如果使用默认的行锁，不仅这个事务执行效率低，而且可能造成其他事务长时间锁等待和锁冲突，这种情况下可以考虑使用表锁来提高该事务的执行速度。
• 第二种情况是：事务涉及多个表，比较复杂，很可能引起死锁，造成大量事务回滚。这种情况也可以考虑一次性锁定事务涉及的表，从而避免死锁、减少数据库因事务回滚带来的开销。

InnoDB加锁方法

• 意向锁是 InnoDB 自动加的， 不需用户干预。

• 对于 UPDATE、 DELETE 和 INSERT 语句， InnoDB会自动给涉及数据集加排他锁（X)；

• 对于普通 SELECT 语句，InnoDB 不会加任何锁；
  事务可以通过以下语句显式给记录集加共享锁或排他锁：

• • 共享锁（S）：SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE。 其他 session 仍然可以查询记录，并也可以对该记录加 share mode 的共享锁。但是如果当前事务需要对该记录进行更新操作，则很有可能造成死锁。
  • 排他锁（X)：SELECT * FROM table_name WHERE ... FOR UPDATE。其他 session 可以查询该记录，但是不能对该记录加共享锁或排他锁，而是等待获得锁

for update 和 lock in share mode 的区别：

前一个上的是排他锁（X 锁），一旦一个事务获取了这个锁，其他的事务是没法在这些数据上执行 for update ；后一个是共享锁，多个事务可以同时的对相同数据执行 lock in share mode

MySQL乐观锁的实现

悲观锁：从字面理解就是很悲观，每次去拿数据的时候都认为别人会修改，所以在每次拿的时候对数据上锁，这样就保证了数据的准确性。比如mysql中的表锁，行锁。

乐观锁：在每次去拿数据的时候认为别人不会修改，不对数据上锁，但是在提交更新的时候会判断在此期间数据是否被更改，如果被更改则提交失败。

乐观锁的实现：使用版本控制字段，再使用行锁的特性实现乐观锁

如果执行一次，那么版本号就增加一次

update order set price = 1, version = version + 1 where id = 1 and version = 0;

死锁的处理

数据库使用乐观锁导致产生死锁

假设在两个事务中有以上两个操作，同时修改order表中两条数据

事务A在执行完第一条update的时候，刚好事务B也执行完第一条update

此时， 事务A中order表中的id = 1的行被锁住， 事务B中order表中id = 2的行被锁住，两个事务继续往下执行

事务A中第二条update执行需要order表中id = 2的行数据，而事务B中第二条update执行需要id = 1的行数据， 两条update往下执行的条件都需要对方事务中已经被锁住的行，于是陷入无限等待，形成死锁。

解决死锁的方法

指定锁的执行顺序，比如把以上两事务稍作修改

事务A执行第一条update时，id = 2 的行被锁住，此时，事务B想修改id = 2的行，只能等待事务A执行完成，当事务A执行完成时，事务B再执行， 这样就不会产生死锁了。

Redis

为什么Redis这么快

1. Redis是纯内存数据库。
2. Redis是单线程数据库。利用队列技术将并发访问变为串行访问。
3. Redis采用了多路复用IO技术：“多路”指多个网络连接；”复用”指复用一个线程；多路复用IO技术可以让单线程高效的处理多个连接请求。

Redis常用的数据结构

• 字符串 String
• 列表 list
• 有序集合 zset
• 哈希表 hash
• 集合 set

其他的一些高级数据结构

• HyperLogLog：通常用于基数统计，使用少量固定大小的内存，来统计集合中唯一元素的数据
• Geo：可以将用户给定的地理位置信息存储起来，并进行操作
• BitMap：位图
• Stream：主要用于消息队列，类似于Kafka。提供了消息的持久化和主从复制功能，可以让任何客户端访问任何时刻的数据，并且能记住每一个客户端的访问位置，还能保证信息不丢失

Redis应用场景

• 缓存
• 分布式锁
• 排行榜 zset
• 计数 incrby
• 消息队列 stream
• 地理位置 geo
• 访客统计 hyperloglog

Redis做异步队列

一般使用list结构作为队列，rpush生产信息，lpop消费消息

缺点：在消费者下线的情况下，生产的消息会丢失，得使用专业的消息队列如rabbitmq等

使用pub/sub主题订阅者模式，可以实现1:N的消息队列

Redis和数据库一致性问题

更新策略：

• 采用正确的更新策略，先更新数据库，再删除缓存
• 因为可能存在删除缓存失败的问题，提供一个消息队列作为补偿措施

采用延时双删策略：

• 先淘汰缓存
• 再写数据库
• 休眠一会，再次淘汰缓存

如果对数据有强一致性要求，不能放缓存

Redis持久化

由于Redis是一种内存型数据库，即服务器在运行时，系统为其分配了一部分内存存储数据，一旦服务器挂了或宕机了，那么数据库里面的数据将会丢失，为了使服务器即使突然关机也能保存数据，必须通过持久化的方式将数据从内存保存到磁盘中。

持久化就是把内存的数据写到磁盘中，防止服务器宕机了，导致内存数据待久。

Redis提供两种持久化机制，分别是RDB和AOF。Redis服务器默认开启RDB，关闭AOF；

RDB持久化

RDB(Redis DataBase)：快照。按照一定的时间将内存的数据以快照的形式保存到硬盘中，对应产生的数据文件为dump.rdb。通过配置文件中的save参数来定义快照的周期。

优点：RDB文件紧凑，体积小，网络传输快，适合全量复制；恢复速度比AOF快。与AOF相比，RDB最重要的优点之一是对性能的影响相对较小。

缺点：RDB文件的致命缺点在于其数据快照的持久化方式决定了必然做不到实时持久化，而在数据越来越重要的今天，数据的大量丢失很多时候是无法接受的，因此AOF持久化成为主流。此外，RDB文件需要满足特定格式，兼容性差（如老版本的Redis不兼容新版本的RDB文件）。

AOF持久化

AOF(Append Only File)：将Redis执行的每次写命令记录到单独的日志文件中，当重启Redis会重新将持久化的日志志中文件恢复数据。

与RDB持久化相对应，AOF的优点在于支持秒级持久化、兼容性好，缺点是文件大、恢复速度慢、对性能影响大。

持久化策略选择

• 如果Redis中的数据完全丢弃也没有关系，那么无论是单机，还是主从架构，都可以不进行任何持久化。
• 在单机环境下，如果可以接受十几分钟或更多的数据丢失，选择RDB对Redis的性能更加有利；如果只能接受秒级别的数据丢失，应该选择AOF。
• 但在多数情况下，我们都会配置主从环境，slave的存在既可以实现数据的热备，也可以进行读写分离分担Redis读请求，以及在master宕掉后继续提供服务。

Redis的淘汰策略

当Redis的内存（maxmemory参数配置）已满时，它会根据淘汰策略（maxmemory-policy参数配置）进行相应的操作。

• 不删除策略（no-eviction）
  no-eviction：不删除策略。Redis默认策略。达到最大内存限制时，若需要更多内存，直接返回错误信息。

• 最近最少使用策略（lru）

  • allkeys-lru：所有key通用；优先删除最近最少使用的key
  • volatile-lru：只限于设置了 expire 过期时间的部分；优先删除最近最少使用的key

• 随机策略（random）：

  • allkeys-random：所有key通用；随机删除一部分key。
  • volatile-random：只限于设置 expire 的部分；随机删除一部分key。

• 剩余时间短策略（ttl）：

  volatile-ttl：只限于设置 expire 的部分；优先删除剩余时间短的key。

• 最不经常使用策略（lfu）:

  volatile-lfu：只限于设置 expire 的部分；优先删除最不经常使用的key。

• allkeys-lfu：所有key通用；优先删除最不经常使用的key。

• volatile-：从已过期时间的数据集中淘汰key。
• allkeys-：所有key。

Redis线程模型

Redis基于 Reactor 模式开发了自己网络事件处理器，它由四部分组成，分别是

• 套接字
• IO多路复用程序
• 文件事件分派器
• 事件处理器

因为文件事件分派器队列的消费是单线程的，所以Redis才叫单线程模型。

IO多路复用技术

IO多路复用：”多路”是指多个TCP连接；”复用”是指复用一个或多个线程；可以让单线程高效的处理多个连接请求。

IO多路复用使用两个系统调用(select/poll/epoll和recvfrom)，阻塞IO只调用了recvfrom；

select/poll/epoll 核心是可以同时处理多个连接，而不是更快，所以连接数不高的话，性能不一定比多线程+阻塞IO好，多路复用模型中，每一个socket，设置为non-blocking，阻塞是被select这个函数阻塞的，而不是被socket阻塞的。

select机制

原理：客户端操作服务器时会三种文件描述符(简称fd)：writefds(写)、readfds(读)、exceptfds(异常)。select会阻塞监视3类文件描述符，等有数据、可读、可写、出异常或超时，就会返回；返回后通过遍历fdset整个数组来找到就绪的描述符fd，然后进行对应的IO操作。

优点：所有平台都支持，跨平台性好。
缺点：

• 由于是采用轮询方式全盘扫描，会随着文件描述符fd数量增多而性能下降。
• 每次调用 select()，需要把 fd 集合从用户态拷贝到内核态，并进行遍历(消息传递都是从内核到用户空间)
• 默认单个进程打开的fd有限制是1024个，可修改宏定义，但是效率仍然慢。

poll机制

原理：基本原理与select一致，也是轮询+遍历；唯一的区别就是poll没有最大文件描述符限制（使用链表的方式存储fd）。

epoll机制

原理：epoll也没有fd个数限制，用户态拷贝到内核态只需要一次，使用时间通知机制来触发。通过epoll_ctl注册fd，一旦fd就绪就会通过callback回调机制来激活对应fd，进行相关的io操作。

优点：

• 没有fd限制，所支持的fd上限是操作系统的最大文件句柄数，1G内存大概支持10万个句柄
• 效率提高，使用回调通知而不是轮询的方式，不会随着FD数目的增加效率下降
• 内核和用户空间mmap同一块内存实现(mmap是一种内存映射文件的方法，即将一个文件或者其它对象映射到进程的地址空间)

Redis异常问题

缓存雪崩

同一时间内大量键过期（失效），导致所有请求瞬间都落在了数据库中导致连接异常而崩掉。

如何解决缓存雪崩

• 给缓存数据的过期时间设置随机机，防止同一时间大量数据过期。
• 给每一个缓存数据增加相应的缓存标记，记录缓存是否失效，若标记失效，则更新缓存数据。
• 并发量不大时，可以使用加锁排队。

对于”Redis挂掉了，请求全部走数据库”这种情况，我们可以有以下的思路：

• 事发前：实现Redis的高可用（主从架构+Sentinel或者Redis集群），尽量避免Redis挂掉
• 事发中：设置本地缓存(ehcache)+限流(hystrix)，尽量避免数据挂掉，保证服务能正常工作
• 事发后：redis持久化，重启后自动从磁盘上加载数据，快速恢复缓存数据

缓存穿透

恶意请求缓存中不存在的数据，导致所有请求都落在数据库，造成短时间承受大量请求而崩掉

采用布隆过滤器，将所有可能存在的数据哈希到一个bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免对底层存储系统的查询压力。

缓存击穿

缓存击穿是指缓存中没有但数据库中有的数据。同时读缓存数据没有读到，导致所有请求都落在数据库，造成过大压力。

缓存雪崩与缓存击穿的区别

与缓存雪崩不同的是，缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期，很多数据都查不到从而查数据库。

如何解决缓存击穿

1. 设置热点数据永不过期。
2. 利用互斥锁：在缓存失效的时，先获取锁，得到锁后再去请求数据库。没有得到锁，则休眠一段时间在重试。

缓存预热

缓存预热指系统上线后，将相关的缓存数据直接加载到Redis中，这样就可以避免在用户请求时，先查询数据库，然后再将数据缓存的问题。

1. 直接写个缓存刷新页面，系统上线时手动将缓存数据加载；
2. 定时刷新缓存；

缓存降级

当访问量剧增、服务出现问题（如响应时间慢或不响应）或非核心服务影响到核心流程的性能时，仍然需要保证服务还是可用的，即使是有损服务。系统可以根据一些关键数据进行自动降级，也可以配置开关实现人工降级。

缓存降级的最终目的是保证核心服务可用，即使是有损的。而且有些服务是无法降级的（如加入购物车、结算）。

在进行降级之前要对系统进行梳理，看看系统是不是可以丢卒保帅；从而梳理出哪些必须誓死保护，哪些可降级；比如可以参考日志级别设置预案：

• 一般：比如有些服务偶尔因为网络抖动或者服务正在上线而超时，可以自动降级；
• 警告：有些服务在一段时间内成功率有波动（如在95~100%之间），可以自动降级或人工降级，并发送告警；
• 错误：比如可用率低于90%，或者数据库连接池被打爆了，或者访问量突然猛增到系统能承受的最大阀值，此时可以根据情况自动降级或者人工降级；
• 严重错误：比如因为特殊原因数据错误了，此时需要紧急人工降级。

服务降级的目的，是为了防止Redis服务故障，导致数据库跟着一起发生雪崩问题。因此，对于不重要的缓存数据，可以采取服务降级策略，例如一个比较常见的做法就是，Redis出现问题，不去数据库查询，而是直接返回默认值给用户。

Redis事务

事务间相互独立：事务中的所有命令都会序列化，按顺序执行。事务在执行过程中，不会被其他客户端请求的命令中断。

事务中的命令要么都执行，要么都不执行

Redis事务相关命令

Redis事务功能是通过MULTI、EXEC、DISCARD、WATCH命令实现的。通过MULTI开启事务，然后将请求的命令入队，最后通过EXEC命令依次执行队列中所有的命令。

Redis会将一个事务所有的命令序列化，然后按顺序执行。

• Redis不支持回滚。Redis在事务失败时不进行回滚，而是继续执行剩下的命令。
• 若在一个事务中的命令出现错误，那么所有命令都不会执行。
• 若在一个事务中出现运行错误，那么正确的命令会被执行。

WATCH命令：是一个乐观锁，可以为Redis提供CAS操作。可以监控一个或多个键，一旦其中有一个键被修改或删除，之后的事务就不执行，监控一直持续到EXEC命令。

MULTI命令：用于开启事务。MULTI执行后，Client可以继续向服务器发送任意多条命令，这些命令会存放到一个队列中，当EXEC命令调用后，所有队列中的命令才会被执行。

EXEC命令：执行所有事务块的命令，可以理解为提交事务。按命令的执行顺序，返回事务中所有命令的返回值。当操作被打断时，返回空值（nil）。

DISCARD命令：用于清空事务队列，并放弃执行事务。Client从事务状态中退出。

UNWATCH命令：用于取消WATCH命令对所有key的监控。

事务执行过程中，若服务器收到有EXEC、DISCARD、WATCH、MULTI之外的请求，将会把请求放入队列中

Redis事务的特性

就是数据库的ACID特性

• 原子性（Atomicity）
• 一致性（Consistency）
• 隔离性（Isolation）
• 持久性（Durability）

Redis分布式问题

Redis的分布式锁

Redis是单进程模式，队列技术将并发访问变为串行访问，且多个客户端对Redis的连接并不存在竞争关系，Redis可以使用setnx命令实现分布式锁。

获取锁时调用setnx（setnx若设置值成功，返回1；设置失败，返回0）。锁的value值会随机生成一个UUID，在释放锁时，会通过UUID进行判断是否为对应的锁，若是该锁，则释放该锁；可以使用 expire 命令为锁添加一个超时时间，超过该时间则自动释放锁。

setnx key value：只有在 key 不存在时，才将key设置为value值。

Redis的并发竞争key问题

多个系统同时对一个key进行操作，最后执行的顺序和我们期望的顺序不同，导致结果不同。

如何解决并发竞争问题

• Redis实现分布式锁：通过Redis中setnx命令可以实现分布式锁。当获取锁时，调用setnx加锁。锁的value值会随机生成一个UUID。在释放锁时，通过UUID进行判断是否为对应的锁，若是则释放锁。使用expire命令为锁添加一个超时时间，若超过该时间则自动释放锁。
• Zookeeper实现分布式锁：通过Zookeeper临时有序节点可以实现分布式锁。每个Client对某个方法加锁时，在Zookeeper上的与该方法对应的指定节点的目录下，生成一个唯一的瞬时有序节点。通过判断有序节点中，序号是否为最小来获取锁；当释放锁时，只需要删除瞬时有序节点。

Redis集群

哨兵模式

哨兵（Sentinel） 是 Redis 的高可用性解决方案：由一个或多个 Sentinel 实例组成的 Sentinel 系统可以监视任意多个主服务器，以及这些主服务器属下的所有从服务器。

哨兵的作用

• 监控redis主、从数据库是否正常运行
• 主数据库出现故障自动将从数据库转换为主数据库

哨兵的核心知识

• 哨兵至少需要3个实例，来保证自己的健壮性
• 哨兵+redis主从的部署架构，是不保证数据零丢失的，只能保证redis集群的高可用性
• 对于哨兵 + redis 主从这种复杂的部署架构，尽量在测试环境和生产环境，都进行充足的测试和演练。
• 配置哨兵监控一个系统时，只需要配置其监控主数据库即可，哨兵会自动发现所有复制该主数据库的从数据库。

Redis的主从复制

当从数据库启动时，会向主数据库发送sync命令，主数据库接收到sync后开始在后台保存快照rdb，在保存快照期间收到的命令缓存起来，当快照完成时，主数据库会将快照和缓存的命令一块发送给从数据库。复制初始化结束。之后，主数据库每收到1个命令就同步发送给从数据库。 当出现断开重连后，2.8之后的版本会将断线期间的命令传给从数据库。增量复制。213 c

主从复制是乐观复制，当客户端发送写执行给主数据库，主数据库执行完立即将结果返回客户端，并异步的把命令发送给从数据库，从而不影响性能。

SpringBoot

Spring的IOC和AOP吗

AOP

AOP（面向切面）是一种编程范式，提供从另一个角度来考虑程序结构以完善面向对象编程（OOP）。
AOP为开发者提供了一种描述横切关注点的机制，并能够自动将横切关注点织入到面向对象的软件系统中，从而实现了横切关注点的模块化。
AOP能够将那些与业务无关，却为业务模块所共同调用的逻辑或责任，例如事务处理、日志管理、权限控制等，封装起来，便于减少系统的重复代码，降低模块间的耦合度，并有利于未来的可操作性和可维护性。

使用AOP的好处

• 降低模块的耦合度
• 使系统容易扩展
• 提高代码复用性

AOP的基本概念

• 连接点（JoinPoint）：需要在程序中插入横切关注点的点，连接点可能是在类初始化、方法调用、字段调用或处理异常等等。Spring中只支持方法执行连接点。
• 切入点（Pointcut）：一组相关连接点的集合。
• 通知（Advice）：在连接点上执行的行为，增强提供了在AOP中需要在切入点所选择的连接点处进行扩展现有行为的手段。包括前置增强（before advice）、后置增强 (after advice)、环绕增强 （around advice）。
• 切面（Aspect）：通知和切入点的结合。
• 织入（Weaving）：织入是一个过程，是将切面应用到目标对象从而创建出AOP代理对象的过程。
• 代理（Proxy）：通过代理方式来对目标对象应用切面。AOP代理可以用JDK动态代理或CGLIB代理实现。
• 目标对象（Target）：需要被织入关注点的对象。即被代理的对象。

实现AOP的主要设计模式就是动态代理。

IOC

IOC（控制反转）就是依赖倒置原则的一种代码设计思路。就是把原先在代码里面需要实现的对象创建、对象之间的依赖，反转给容器来帮忙实现。
Spring IOC容器通过xml,注解等其它方式配置类及类之间的依赖关系，完成了对象的创建和依赖的管理注入。实现IOC的主要设计模式是工厂模式

使用IOC的好处

• 集中管理，实现类的可配置和易管理。
• 降低了类与类之间的耦合度

Tomcat服务器

Tomcat 服务器^[7]是一个免费的开放源代码的Web 应用服务器，属于轻量级应用服务器，在中小型系统和并发访问用户不是很多的场合下被普遍使用，是开发和调试JSP 程序的首选。

Tomcat的缺省端口

Tomcat目录下的conf文件夹下的server.xml文件中

<Connector connectionTimeout="20000" port="8080" protocol="HTTP/1.1" redirectPort="8443" uriEncoding="utf-8"/>

HTTP工作原理

HTTP协议是浏览器与服务器之间的数据传送协议。作为应用层协议，HTTP是基于TCP/IP协议来传递数据的（HTML文件、图片、查询结果等），HTTP协议不涉及数据包（Packet）传输，主要规定了客户端和服务器之间的通信格式。它的整个过程如下图所示：

1. 用户通过浏览器进行了一个操作，比如输入网址并回车，或者是点击链接，接着浏览器获取了这个事件。
2. 浏览器向服务端发出TCP连接请求。
3. 服务程序接受浏览器的连接请求并经过TCP三次握手建立连接。
4. 浏览器将请求数据打包成一个HTTP协议格式的数据包。
5. 浏览器将该数据包推入网络，数据包经过网络传输，最终达到端服务程序。
6. 服务端程序拿到这个数据包后，同样以HTTP协议格式解包，获取到客户端的意图。
7. 得知客户端意图后进行处理，比如提供静态文件或者调用服务端程序获得动态结果。
8. 服务器将响应结果（可能是HTML或者图片等）按照HTTP协议格式打包。
9. 服务器将响应数据包推入网络，数据包经过网络传输最终达到到浏览器。
10. 浏览器拿到数据包后，以HTTP协议的格式解包，然后解析数据，假设这里的数据是 HTML。
11. 浏览器将HTML文件展示在页面上。

Tomcat整体架构

Tomcat要实现两个核心功能：

1. 处理Socket连接，负责网络字节流与Request和Response对象的转化。
2. 加载和管理Servlet，以及具体处理Request请求。

因此Tomcat设计了两个核心组件

• 连接器（Connector）：负责对外交流
• 容器（Container）：负责内部处理

Coyote连接器架构

Coyote是Tomcat的连接器框架的名称 , 是Tomcat服务器提供的供客户端访问的外部接口。客户端通过Coyote与服务器建立连接、发送请求并接受响应 。

Coyote封装了底层的网络通信（Socket请求及响应处理），为Catalina容器提供了统一的接口，使Catalina容器与具体的请求协议及IO操作方式完全解耦。Coyote 将Socket输入转换封装为Request对象，交由Catalina容器进行处理，处理请求完成后，Catalina通过Coyote提供的Response对象将结果写入输出流 。

布隆过滤器

布隆过滤器（Bloom Filter）^[6]是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

当你往简单数组或列表中插入新数据时，将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话，当你需要在数组或列表中搜索相应值的时候，你必须遍历已有的集合。若集合中存在大量的数据，就会影响数据查找的效率。

针对这个问题，你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值，然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的，当你需要判断列表中是否存在该值时，只需要对值进行哈希处理并在相应的索引位置进行搜索即可，这时的搜索速度是非常快的。

根据定义，布隆过滤器可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。“可能” 表示有一定的概率，也就是说可能存在一定为误判率。那为什么会存在误判呢？下面我们来分析一下具体的原因。

布隆过滤器（Bloom Filter）本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0，如下图所示。

为了将数据项添加到布隆过滤器中，我们会提供 K 个不同的哈希函数，并将结果位置上对应位的值置为 “1”。在前面所提到的哈希表中，我们使用的是单个哈希函数，因此只能输出单个索引值。而对于布隆过滤器来说，我们将使用多个哈希函数，这将会产生多个索引值。

如上图所示，当输入 “semlinker” 时，预设的 3 个哈希函数将输出 2、4、6，我们把相应位置 1。假设另一个输入 ”kakuqo“，哈希函数输出 3、4 和 7。你可能已经注意到，索引位 4 已经被先前的 “semlinker” 标记了。此时，我们已经使用 “semlinker” 和 ”kakuqo“ 两个输入值，填充了位向量。当前位向量的标记状态为：

当对值进行搜索时，与哈希表类似，我们将使用 3 个哈希函数对 ”搜索的值“ 进行哈希运算，并查看其生成的索引值。假设，当我们搜索 ”fullstack“ 时，3 个哈希函数输出的 3 个索引值分别是 2、3 和 7：

从上图可以看出，相应的索引位都被置为 1，这意味着我们可以说 ”fullstack“ 可能已经插入到集合中。事实上这是误报的情形，产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。幸运的是，布隆过滤器有一个可预测的误判率（FPP）：
$$
P_{fpp} \approx (1-e^{-\frac{kn}{m}})^k
$$

• n 是已经添加元素的数量；
• k 哈希的次数；
• m 布隆过滤器的长度（如比特数组的大小）；

当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。

应用

在实际工作中，布隆过滤器常见的应用场景如下：

• 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
• Google Chrome 使用布隆过滤器识别恶意 URL；
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。 除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候，我们先判断该 ID 是否存在，若存在的话，则进行下一步处理。若不存在的话，直接返回，这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。

实战

可以创建一个Maven项目，在pom文件中引入以下坐标

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

然后创建一个测试代码，初始化一百万条数据到过滤器中，然后在原有的基础上增加一万条数据，并且判断这些数据是否存在布隆过滤器中

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}

得到的结果是

已匹配数量 1000309

上述结果出现了误报，误报率比预期多了309个元素
$$
\frac{309}{1000000+10000} \times 100% \approx 3.059%
$$

参考

1. Java多线程同步之ThreadLocal与Synchromized ↩
2. 我给面试官讲解了单例模式后，他对我竖起了大拇指！ ↩
3. HTTP 和 HTTPS 的区别（面试常考题） ↩
4. 一文搞懂MySQL索引所有知识点（建议收藏） ↩
5. 红黑树，超强动静图详解，简单易懂 - 知乎 (zhihu.com) ↩
6. 5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！ - 知乎 (zhihu.com) ↩
7. 学习Tomcat这一篇就够了 ↩