百度2023届北京Java研发工程师面试凉经

记录一下2022年8月1日百度北京Java后端研发工程师的面试，已凉

面试了接近一个小时，基础知识掌握的太差了，面试官找不到啥深入聊，什么都问了一点，什么都没答上来

自我介绍

聊了下专业背景和课题，课题主要研究的是生物医学相关的，以及为什么想来做Java后端

Java基础

你说你用过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.当然,这些对比都是指数据量很大或者操作很频繁。

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

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

• ThreadLocal是Java类，是通过每个线程单独一份存储空间，牺牲空间来弥补时间来解决多线程访问冲突，ThreadLocal具有线程隔离的效果，只有在线程内才能获取到对应的值，线程外则不能访问到想要的值。

  public class SqlConnectionUtil {
      private static ThreadLocal<SqlConnection> tl = new ThreadLocal<SqlConnection>();
      private static SqlConnection initSqlConnection = null;
      static {
          try {
              initSqlConnection = DriverManager.getSqlConnection("url, name and password");
          } catch (SQLException e) {
              e.printStackTrace();
          }
      }
      
      public SqlConnection getSqlConnection() {
          SqlConnection c = tl.get();
          if(null == c) tl.set(initSqlConnection);
          return tl.get();
      }
  }

• 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();
      }

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(因为不涉年代不在图中)。

数据结构

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

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

• 冒泡排序：每一轮循环都是和相邻的元素比较，然后一步步的将最小的元素或者最大的元素排在前面，时间复杂度是 $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和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. 服务端将非对称加密的公钥发送给客户端；
2. 客户端拿着服务端发来的公钥，对对称加密的key做加密并发给服务端；
3. 服务端拿着自己的私钥对发来的密文解密，从来获取到对称加密的key；
4. 二者利用对称加密的key对需要传输的消息做加解密传输。

数据库

有用过数据库吗，例如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字段的数据确实真实的节省了。

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

联合索引的使用

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

框架

看你项目中有用到SpringBoot和Mybatis，可以聊一下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的好处

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

开放性问题

在百度的业务中，爬取了大量的页面，这些页面无法全部放在内存中，如何优化查找

在面试的时候，只能想到哈希映射或者二叉树索引之类的，或者是数据库索引的B+树的实现方式

面试官最后介绍了一种布隆过滤器算法（站在布隆后面&心脏是最强壮的肌肉）

布隆过滤器算法

布隆过滤器（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) ↩