鹅厂面试太太太坎坷了—基础篇

calendar 2020-03-05 · 5 分钟 阅读 · 面试总结

面试腾讯或者其他大厂，除了复习上篇文章提到的网络知识点之外是不够的，还需要掌握好Java基础，这也是在初面中高频提问到的知识点，能否进入下一轮面试有着关键的作用，而我在财付通第二轮面试中，就因为算法题没通过，太无奈了。

谈谈Java线程的生命周期及状态转换

通过观察jdk源码中Thead类里的State子类描述了线程的状态。

1public enum State {
2    NEW,
3    RUNNABLE,
4    BLOCKED,
5    WAITING,
6    TIMED_WAITING,
7    TERMINATED;
8}
  • 新建：当线程对象被创建后处于新建状态，例如代码中new Thread()。
  • 可运行：包括就绪与运行中状态，当新建后的线程执行start()方法时进入就绪状态，等待获取CPU、IO等资源，当获取到资源后就会进入到运行中的状态。
  • 阻塞：当线程遇到synchronized方法或主动调用Object.wait()方法时则会进入阻塞状态，等待获取监视器锁。
  • 无限期等待：当调用无参数的Object.wait()、Thread.join()等方法时则会进入无限期等待，直到其他的线程执行完特定的操作后才会结束。
  • 有限期等待：当调用有时间参数的Object.wait()、Thread.join()等方法后，在时间到达后则会结束等待而不需等其他线程完成特定操作。
  • 终止：线程正常执行完任务后或者线程被中断后则处于终止状态。

图片

如何创建Java线程池及每个参数的含义

线程池可通过ExecutorService pool = Executors.newFixedThreadPool(5)或者new ThreadPoolExecutor()两种方式创建，建议使用new ThreadPoolExecutor()的方式创建，自定义线程池的每个参数，对应创建线程池中的构造器如下：

 1public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,TimeUnit unit,
 2    BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler) {
 3if (corePoolSize < 0 ||maximumPoolSize <= 0 ||maximumPoolSize < corePoolSize ||keepAliveTime < 0)
 4            throw new IllegalArgumentException();
 5if (workQueue == null || threadFactory == null || handler == null)
 6      throw new NullPointerException();
 7    this.corePoolSize = corePoolSize;
 8    this.maximumPoolSize = maximumPoolSize;
 9    this.workQueue = workQueue;
10    this.keepAliveTime = unit.toNanos(keepAliveTime);
11    this.threadFactory = threadFactory;
12    this.handler = handler;
13}

  • corePoolSize：核心线程数。

  • maximumPoolSize：最大线程数。

  • unit：空闲存活时间的单位。

  • workQueue：任务队列类。

    • 固定长度的ArrayBlockingQueue
    • 延迟DelayedQueue
    • 无边限LinkedBlockingQueue
    • 同步阻塞SynchronousQueue

  • keepAliveTime：线程空闲存活时间，当空闲的非核心线程超过此时间则会被回收。

  • threadFactory：线程工厂，一般使用默认，可自定义线程工厂设置线程属性。

  • handler：任务拒绝策略，当最大线程数且任务队列已满时，对任务执行拒绝策略

    • AbortPolicy：拒绝任务并抛出异常
    • AbortPolicyWithReport：拒绝任务并忽略异常、记录日志
    • DiscardPolicy：直接丢弃任务，不作任何处理
    • DiscardOldestPolicy：丢弃队列中最久的任务并尝试执行任务
    • CallerRunPolicy：拒绝并由调用线程执行任务
说说Java线程安全的实现方式

  • synchrorized关键字

  • 基于AQS同步框架实现的重入锁ReentrantLock、CountDownLatch、 Semaphore、读写锁ReadWriteLock等。

  • ThreadLocal线程副本

  • Java volitate关键字

  • Java原子变量 AtomicBoolean、AtomicLong等。

你知道java内存模型吗？

Java虚拟机规范中定义了Java内存模型（Java Memory Model，JMM），用于屏蔽掉各种硬件和操作系统的内存访问差异，以实现让Java程序在各种平台下都能达到一致的并发效果，JMM规范了Java虚拟机与计算机内存是如何协同工作的：规定了一个线程如何和何时可以看到由其他线程修改过后的共享变量的值，以及在必须时如何同步的访问共享变量。

线程之间的共享变量存储在主内存（main memory）中，每个线程都有一个私有的本地内存（local memory），本地内存中存储了该线程以读/写共享变量的副本，本地内存是JMM的一个抽象概念，并不真实存在，它涵盖了缓存，写缓冲区，寄存器以及其他的硬件和编译器优化。

JMM内存模型

从上图来看，线程A与线程B之间如要通信的话，必须要经历下面2个步骤：

1、首先线程A把本地内存A中更新过的共享变量刷新到主内存中去。 2、线程B到主内存中去读取线程A之前已更新过的共享变量。

JMM通信

如上图所示，本地内存A和B有主内存中共享变量x的副本。初始时这三个内存中的x值都为0，线程A在执行时，把更新后的x值（假设值为1）临时存放在自己的本地内存A中。当线程A和线程B需要通信时，线程A首先会把自己本地内存中修改后的x值刷新到主内存中，此时主内存中的x值变为了1。随后，线程B到主内存中去读取线程A更新后的x值，此时线程B的本地内存的x值也变为了1。

从整体来看，这两个步骤实质上是线程A在向线程B发送消息，而且这个通信过程必须要经过主内存，而JMM通过控制主内存与每个线程的本地内存之间的交互，来为java程序员提供内存可见性保证。

java volitate关键字作用及原理

一旦一个共享变量（类的成员变量、类的静态成员变量）被volatile关键字修饰后，就具备了两层语义：

  • 保证了不同线程对这个变量操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。

  • 禁止进行指令重排序：指令重排序是编译器和处理器为了高效对程序进行优化的手段，它只能保证程序执行的结果时正确的，但是无法保证程序的操作顺序与代码顺序一致，这在单线程中不会构成问题，但是在多线程中就会出现问题。

用volatile关键字修饰的变量，在生成字节码指令时会多出一个lock前缀指令，而lock前缀指令实际上相当于一个内存屏障（也成内存栅栏），内存屏障会提供3个功能：

  1. 它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面，即在执行到内存屏障这句指令时，在它前面的操作已经全部完成。
  2. 它会强制将对缓存的修改操作立即写入主存；
  3. 如果是写操作，它会导致其他CPU中对应的缓存行无效。
讲讲多线程的先行发生原则

　先行发生原则是java内存模型中定义的两项做错之间的偏序关系，如果说操作A先行发生与操作B，其实就是说在发生操作B之前，操作A产生的影响能被操作B观察到，“影响”包括修改了内存中共享变量的值、发送了消息、调用了方法等。

java内存模型中“天然的”的先行发生关系规则如下： 　　1、程序次序规则： 　　　　在一个线程内，按照程序代码顺序，书写在前面的操作先行发生于书写在后面的操作，准确的说，应该是控制流程序而不是程序代码顺序，因为要考虑分支、循环等结构； 　　2、管程锁规则： 　　　　一个unlock操作先行发生于后面对同一个锁的lock操作，这里必须强调的是同一个锁，“后面”指的是时间上的先后顺序。 　　3、volatile变量规则： 　　　　对一个volatile变量的写操作先行发生于后面对这个变量的读操作，“后面”同样是时间上的先后顺序。 　　4、线程启动规则： 　　　　Thread对象的start()方法先行发生于次线程的每一个动作； 　　5、线程终止规则： 　　　　线程中的所有操作都先行发生于对此线程的终止检测，可以通过Thread.join()方法结束，Thread.isAlive()的返回值等手段检测到线程已终止执行 　　6、线程中断规则： 　　　　对线程interrupt()方法的调用先行发生于被中断线程的代码检测到中断事件的发生，可以通过Thread.interruptd()方法检测到是否有中断发生 　　7、对象终结规则： 　　　　一个对象的初始化完成（构造函数执行结束）先行发生于它的finalize()方法的开始 　　8、传递性 　　　　如果操作A先行发生于操作B，操作B先行发生于操作C，那么就可以认为操作A先行发生于操作C。

java bio与nio的区别

首先我们需要先了解下阻塞与非阻塞，同步与异步的区别：

阻塞和非阻塞区分：请求的线程是否是阻塞的状态，重点在于线程是否需要等待。

同步与异步的区分：数据是去内核缓冲还是进程缓冲取，以及是否是通知进程还是进程自己去查询（这里涉及到用户线程和内核线程的知识）。

BIO即同步阻塞IO，在数据的读取写入必须阻塞在一个线程内等待其完成，这里用煲仔饭作为例子，假设一个煮煲仔饭场景，BIO的工作模式就是让一个线程停留在一个煲仔饭中，直到这个煲仔饭煮好后才去处理下一个煲仔饭，但实际上线程在等待煲仔饭煮好的时间段什么都没有做，也不知道io操作中什么时候有数据可读，所以一直是阻塞的模式。

NIO即同步非阻塞IO，还是拿煮煲仔饭来说，NIO的做法是让一个线程不断的轮询每个煲仔饭是否煮熟的状态，如果煲仔饭的状态发生了改变，就进行下一步的操作。

什么是IO多路复用

IO多路复用是一种同步IO模型，实现一个线程可以监视多个文件句柄，一旦某个文件句柄就绪，就能通知应用程序进行相应的读写操作，当没有文件句柄就绪时会阻塞应用程序，不占用cpu，其中多路是指网络连接，复用指的是同一个线程。

IO多路复用有哪些实现

select：select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理，但缺点是：

  • 单个进程可监视的fd数量被限制，即能监听端口的大小有限。
  • 对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低。
  • 需要维护一个存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大。

poll：poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd，整个过程经历了多次无谓的遍历，它没有最大连接数的限制，原因是它是基于链表来存储的，但是同样有一个缺点：

  • 大量的fd的数组被整体复制于用户态和内核地址空间之间，而有些复制是没有意义。
  • poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

epoll：有EPOLLLT和EPOLLET两种触发模式，LT是默认的模式，ET是“高速”模式。LT模式下，只要这个fd还有数据可读，每次 epoll_wait都会返回它的事件，提醒用户程序去操作，而在ET（边缘触发）模式中，它只会提示一次，直到下次再有数据流入之前都不会再提示了，无 论fd中是否还有数据可读，它有以下的优点：

  • 没有最大并发连接的限制，能打开的FD的上限远大于1024（1G的内存上能监听约10万个端口）

  • 效率提升，不是轮询的方式，不会随着FD数目的增加效率下降。只有活跃可用的FD才会调用callback函数；即Epoll最大的优点就在于它只管你“活跃”的连接，而跟连接总数无关，因此在实际的网络环境中，Epoll的效率就会远远高于select和poll。

  • 内存拷贝，利用mmap()文件映射内存加速与内核空间的消息传递；即epoll使用mmap减少复制开销。

讲讲ByteBuffer类pos，mark，limit，lenght的含义？

在NIO中有三个重要的概念，buffer缓冲，channel通道和selector选择器。

channel是连接对应于传统io的流，而buffer就是channel交换数据的地方，buffer有很多类型，每一个基本类型都有一个buffer，但是网络中用的最多的是ByteBuffer，我们通过操作channel向程序内读写数据都是通过ByteBuffer来进行的，这样可以在一次io中尽可能多地传递数据，这也是buffer的作用，在ByteBuffer类中主要有以下的字段标识数据。

  • capacity:指buffer最大能放大少数据，此一般在buffer在创建时被指定。
  • limit：指buffer在进行读写操作时，不能超过此下标，在写时limit 与 capacity一般相等，当读数据时，limit为有效数据的长度
  • position：指操作的当前下标 可以理解为指针，读写一个数据，指针下移。
  • mark：指临时存放下标的指，当进行mark()操作时，mark会保存position的值，当进行reset()操作时，又把mark的指赋予position值 ，mark的值总是小于等于position的值。
  • flip： 把limit设置为当前position，同时把position设置为0 在读出数据前调用 即把指针放到开始位置,读数据时只读到限制位置。
  • compact：把当前从position位置到limit位置的字节移动到从0开始。
  • clear：重置了缓冲区的主要索引值.不必为了每次读写都创建新的缓冲区,那样做会降低性能

其中0 <= mark <= position <= limit <= capacity。

SocketChannel的创建流程是怎样的？
1SocketChannel socketChannel = SocketChannel.open();
2socketChannel.connect(new InetSocketAddress("http://127.0.0.1", 80));
3
4ByteBuffer buf = ByteBuffer.allocate(48);
5int bytesRead = socketChannel.read(buf);
手写单例模式的三种实现方式

1、饿汉式(线程安全，调用效率高，但是不能延时加载)：

1public class TalkInstance{ 
2     private static TalkInstance instance = new TalkInstance; 
3     private TalkInstance(){} 
4     public static TalkInstance getInstance(){  
5          return instance;  
6      } 
7}

2.懒汉式(线程安全，调用效率不高，但是能延时加载)：

 1public class TalkInstance {
 2     
 3    //类初始化时，不初始化这个对象(延时加载，真正用的时候再创建)
 4    private static TalkInstance instance;
 5     
 6    //构造器私有化
 7    private TalkInstance(){}
 8     
 9    //方法同步，调用效率低
10    public static synchronized TalkInstance getInstance(){
11        if(instance==null){
12            instance=new TalkInstance();
13        }
14        return instance;
15    }
16}

3.Double CheckLock实现单例：通过双重锁判断机制创建实例

 1public class TalkInstance {
 2        private volatile static TalkInstance instance;
 3
 4        private TalkInstance() {
 5        }
 6
 7        public static TalkInstance newInstance() {
 8            if (instance == null) {
 9                synchronized (TalkInstance.class) {
10                    if (instance == null) {
11                        instance = new TalkInstance();
12                    }
13                }
14            }
15            return instance;
16        }
17    }

4.静态内部类实现模式（线程安全，调用效率高，可以延时加载）

 1public class TalkInstance {
 2
 3    private static class SingletonTalkInstance{
 4        private static final TalkInstance instance=new TalkInstance();
 5    }
 6
 7    private TalkInstance(){}
 8
 9    public static TalkInstance getInstance(){
10        return SingletonTalkInstance.instance;
11    }
12
13}

5.枚举类（线程安全，调用效率高，不能延时加载，可天然的防止反射和反序列化调用）

1public enum TalkInstance {
2
3    //枚举元素本身就是单例
4    INSTANCE;
5
6    public void singletonTalkInstance(){
7    }
8}

对于选用哪种方式创建实例，看根据以下条件抉择：

  • 单例对象、占用资源少、不需要延时加载，枚举优先饿汉。

  • 单例对象、占用资源多、需要延时加载，静态内部类优先懒汉式。

讲讲spring mvc处理请求的整体流程

![spring mvc流程](/Users/keres_liu/文章/时序图/spring mvc流程.png)

1、客户端发起的http请求，tomcat服务器接收到请求，并交由DispatcherServlet转发处理。

2、DispatcherServlet把接受到的请求，根据请求的HandlerMapping信息找到对应的处理请求的处理器（Handler）。

3、通过HandlerAdapter封装后的Handler，在用统一的适配器接口调用Handler(我们常说的Controller控制器)。

4、调用处理器对应的方法完成业务逻辑处理之后，将返回一个ModelAndView给DispatcherServlet。

5、DispatcherServlet交由ViewResolver完成逻辑视图名到真实视图对象的解析工作(ModelAndView是逻辑视图名)。

6、DispatcherServlet根据视图名称查找对应的View对象，并对ModelAndView中的模型数据进行视图渲染，最终返回给客户端。

有没有使用过structs2框架及了解它的工作流程

structs流程图

1、客户端请求一个HttpServletRequest的请求，例如浏览器中输入http://localhost: 8080/hello_word.action就是提交一个（HttpServletRequest）请求。

2、这个请求经过一系列的过滤器（Filter）如（ActionContextCleanUp、 其他过滤器、FilterDispatcher）。注意：这里是有顺序的，先ActionContext CleanUp，再其他过滤器（Othter Filters、SiteMesh等），最后到FilterDispatcher。

FilterDispatcher是控制器的核心，就是MVC的Struts 2实现中控制层（Controller）的核心。

3、FilterDispatcher询问ActionMapper是否需要调用某个Action来处理这个HttpServletRequest请求，如果ActionMapper决定需要调用某个Action，FilterDispatcher则把请求的处理交给ActionProxy。

4、ActionProxy通过Configuration Manager（struts.xml配置文件）查找需要调用的Action类。例如用户注册示例将找到UserRegAction类。

5、ActionProxy创建一个ActionInvocation实例，同时ActionInvocation通过代理模式调用Action。但在调用之前，ActionInvocation会根据配置加载Action相关的所有Interceptor（拦截器）。

6、 一旦Action执行完毕，ActionInvocation负责根据struts.xml中的配置找到对应的返回结果result

7、最后通过HttpServletResponse返回客户端一个响应。

spring boot与spring的区别

Spring框架为开发Java应用程序提供了全面的基础架构支持，它包含了Spring JDBC、Spring MVC、Spring Security、Spring AOP Spring ORM、Spring Test等模块，可以为开发大大缩短应用程序的开发时间。

Spring Boot基本是Spring框架的扩展，它消除了设置Spring应用程序所需的复杂例行配置，它的目标和Spring的目标是一致的，为更快，更高效的开发生态系统铺平了道路，通过starter这一个依赖，以简化构建和复杂的应用程序配置、可以直接main函数启动，嵌入式web服务器，避免了应用程序部署的复杂性。

MyBatis与Hibernate区别

Hibernate：是一个开源的对象关系映射框架，它将java对象与数据库表建立映射关系，是一个全自动的orm框架，简单来说，hibernate就是将对象数据保存到数据库，将数据库数据读入到对象中。

优点

  • 面向对象开发，不需要编写的SQL语句，只需要操作相应的对象就可以存储、更新、删除、加载对应的数据，可以提高生产效。

  • 使用Hibernate，移植性好，同时拥有二级缓存机制，可以使用第三方缓存。

  • Hibernate实现了透明持久化，当保存一个对象时，不需要继承Hibernate中的任何类、实现任何接口，只是纯粹的POJO对象。

  • Hibernate是一个没有侵入性的框架，没有侵入性的框架我们一般称为轻量级框架。

缺点

  • 使用数据库特性的语句，将很难调优。
  • 对大批量数据更新存在问题。
  • 系统中存在大量的攻击查询功能。
  • 学习门槛高，要熟悉门槛则更高，如何设计O/R映射、在性能和对象模型之间如何权衡取得平衡。

Mybatis：Mybatis框架对jdbc框架进行封装，屏蔽了jdbc的繁琐操作的缺点，开发简单，有以下特点：

  • 入门简单，即学即用，并提供了数据库查询的自动对象绑定功能。
  • 可更为细致的进行SQL优化，减少查询字段，提高性能。
  • 框架比较简陋，功能尚有缺失，虽简化了数据绑定代码，但是整个实际SQL查询需要自己写的，工作量较大，而且SQL移植性差。
红黑树与平衡二叉树的区别

平衡二叉树：带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树高度差不超过1，只要不满足上面的条件，就要通过旋转来保存平衡，而因为旋转非常耗时，由此我们可以知道平衡二叉树适合用于插入与删除次数比较少，查找多的情景。

红黑树：一种二叉查找树，在每个节点增加一个存储位表示结点的颜色，可以是红或黑色(非红即黑)，通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一中弱平衡二叉树(由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的平衡二叉树来说，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索，插入，删除操作较多的情景，我们就用红黑树。

红黑树节点颜色什么时候变换

根据红黑树的性质：

1、每个结点不是红色就是黑色。

2、根节点是黑色的。

3、如果一个节点是红色的，则它的两个孩子结点是黑色的。

4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

5、每个叶子结点都是黑色的 (此处的叶子结点指的是空结点)。

因此可以发现，

  • 如果新插入的节点是黑色，则根据第二个性质可知需要把根节点变为黑色。
  • 如果父节点是红色，则违反第四个性质，此时需要循环判断父节点、叔节点是否满足第四个性质，直到根节点，将根节点颜色设置为黑色。
mysql为什么使用B+数作为存储结构
  • B+树能显著减少IO次数，提高效率。数据库访问数据要通过页，一个页就是一个B+树节点，访问一个节点相当于一次I/O操作，查找一个节点所做的IO次数是这个节点所处的树的高度，B+数存储同样的数据，树的高度更低，因此最快情况下，磁盘的IO次数为数的高度。
  • B+树的查询效率更加稳定，B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，因此会造成查询的效率的不稳定
  • B+树能提高范围查询的效率，B+树使用双向链表串连所有叶子节点，区间查询效率更高。
从包含40亿多个乱序int整数的文件中进行排序，要求内存不超过1G

实现思路：40亿个 int 型数字约占30GB，是无法一次性装入内存的，需要拆分成N个小文件处理，最终再合并成一个排好序的大文件。

1、把这个30GB的大文件，用哈希分成1000个小文件，每个小文件理想情况下平均30MB左右，把40亿个整数对1000取模，取模的结果在0到999之间，每个结果对应一个文件，若哈希函数取得好，能使冲突减小，结果分布更加均匀。

2、拆分完大文件后，得到一些30MB左右的小文件，这时可以放进内存里排序，可以用快速排序，归并排序，堆排序等等。

3、1000个小文件内部排好序之后，接下来要把这些内部有序的小文件合并成一个大的文件，此时可以用堆排序处理，首先遍历1000个文件，每个文件里面取第一个数字，以(数字, 文件号)的组合加入到堆里（假设是从小到大排序，用小顶堆），遍历完后堆里有1000个 (数字，文件号) 这样的元素，然后不断从堆顶拿元素出来，每拿出一个元素，把它的文件号读取出来，然后去对应的文件里，加一个元素进入堆，直到那个文件被读取完，拿出来的元素追加到最终结果的文件里。

求两个二进制字符串a和b相加的结果

二进制加法都是从最低位开始加（从右加到左）。所以对两个字符串要从最后一位开始加。每次相加之前先加上进位。

 1public static String add(String a,String b) {
 2    StringBuilder result = new StringBuilder();
 3    int i = a.length() - 1;
 4    int j = b.length() - 1;
 5
 6    int carry = 0;//保存是否需要进位
 7    while (i >= 0 || j >= 0 || carry > 0) {
 8        int v = carry;//首先把上次的进位赋给该位的和
 9
10        if (i >= 0) {
11            v += a.charAt(i) - '0';  //c-‘0’将字符数c转换为整型数
12        }
13
14        if (j >= 0) {
15            v += b.charAt(j) - '0';
16        }
17        //二进制基数为2，每次将同位的数字相加后，除以基数就是进位
18        carry = v / 2;
19        //1、若v是偶数则v&1=0，若v是奇数则v&1=1
20        //2、二进制每位上的数要么是0要么是1则可使用v&1
21        //3、如果v=2,则进一位.该位为0
22        result.insert(0, (v & 1));
23        i--;
24        j--;
25    }
26  return result.toString();
27}
有64匹马，每一场只能进行8匹马进行竞跑，若统计排名前四的4匹马，最少需要竞跑多少场

这是腾讯经典、高频的一道算法题，答案可参考：https://blog.csdn.net/qq_44756792/article/details/103851500

你手写LRU一个实现

LRU是Least Recently Used的缩写，即最近最少使用，它的原理是新数据插入到链表头，每当缓存命中（即缓存数据被访问），则将数据移到链表头部，当数据超过一定阀值后就淘汰最近最少使用的数据，根据LRU算法思想，使用java实现需要这些条件：

  • 底层数据使用双向链表，以便在链表的任意位置删除数据，当然是用单链表或者数组结构也可以，但非常费劲。 当然双向链表在查找时也麻烦，但下述可以结合HashMap使用
  • 需要将链表的数据按照访问(最近使用)顺序排序。
  • 数据量超过一定阈值后，需要删除Least Recently Used的数据。
  1public class LRUMap {
  2
  3    //链表元素容量
  4    private final int capacity;
  5  
  6    //保存链表的头节点和尾节点
  7    private Node first;
  8  
  9    private Node last;
 10
 11    //从key到node映射的map
 12    private final Map<String, Node> map;
 13
 14    public LRUMap(int capacity) {
 15        this.capacity = capacity;
 16        map = new HashMap<>(capacity);
 17    }
 18
 19    public void put(String key, int value) {
 20        //节点存在，则更新关联的value值
 21        Node node = map.get(key);
 22        if (node != null) {
 23            node.value = value;
 24            removeEldestEntry(node);
 25            return;
 26        }
 27
 28        //不存在创建节点再判断缓存是否满了，如果已达到阀值则删除最后一个节点，并将新节点放到链表头部
 29        node = new Node();
 30        node.key = key;
 31        node.value = value;
 32
 33        if (map.size() == capacity) {
 34            removeLast();
 35        }
 36
 37        setHeadNode(node);
 38        map.put(key, node);
 39    }
 40
 41    public Object get(String key) {
 42        Node node = map.get(key);
 43        if (node == null) {
 44            return -1;
 45        }
 46        removeEldestEntry(node);
 47        return node.value;
 48    }
 49
 50    /**
 51     * 将节点移动到链表头部
 52     *
 53     * @param node 操作的节点
 54     */
 55    private void removeEldestEntry(Node node) {
 56        //要修改很多指针
 57        if (node == first) {
 58            return;
 59        } else if (node == last) {
 60            //若是最后一个节点，将最后一个节点的next指针置为空，然后last指向前一个节点
 61            last.prev.next = null;
 62            last = last.prev;
 63        } else {
 64            //若是中间节点，则中间节点的前节点的后指针指向中间节点的后节点，中间节点的后节点的前指针 指向 中间节点的前节点
 65            node.prev.next = node.next;
 66            node.next.prev = node.prev;
 67        }
 68        //把该节点作为头结点
 69        node.prev = first.prev;
 70        node.next = first;
 71        first.prev = node;
 72        first = node;
 73    }
 74
 75
 76    private void setHeadNode(Node node) {
 77        if (map.isEmpty()) {
 78            first = node;
 79            last = node;
 80        } else {
 81            //把新节点作为头结点
 82            node.next = first;
 83            first.prev = node;
 84            first = node;
 85        }
 86    }
 87
 88    private void removeLast() {
 89        map.remove(last.key);
 90        Node prevNode = last.prev;
 91        //修改last所指的位置
 92        if (prevNode != null) {
 93            prevNode.next = null;
 94            last = prevNode;
 95        }
 96    }
 97
 98    @Override
 99    public String toString() {
100        return map.keySet().toString();
101    }
102
103    // 双向链表节点定义
104    private static class Node {
105
106        private String key;
107        private Object value;
108        Node prev;
109        Node next;
110    }
111}
让你设计个秒杀系统，你应该怎么设计？

这个一道经典的面试题，主要是考察候选人的设计能力，可参考https://www.zhihu.com/question/54895548/answer/1352510403

最后总结

在面试过程中，虽然java相关都回答地不错，但在算法方面却不理想，最后终止了财付通某风险后台开发岗的二面，又沮丧地回家复盘、面壁思过了。