Java BAT高频面题
[TOC]
1、hashmap底层原理（数据结构、为什么用红黑树等）
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由 数组+链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由 数组+链表+红黑树组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
- 当链表超过 8 且数据总量超过 64 才会转红黑树。
- 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
2、HashMap 扩容机制
一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的 2 倍。 HashMap 的容量是有上限的，必须小于 1 << 30，即 1073741824。如果容量超出了这个 数，则不再增长，且阈值会被设置为 Integer.MAX_VALUE。
JDK7 中的扩容机制
- 空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数 组。
- 有参构造函数：根据参数确定容量、负载因子、阈值等。
- 第一次 put 时会初始化数组，其容量变为不小于指定容量的 2 的幂数，然后根据负载因 子确定阈值。
- 如果不是第一次扩容，则 新容量=旧容量 x 2 ，新阈值=新容量 x 负载因子 。
JDK8 的扩容机制
- 空参数的构造函数：实例化的 HashMap 默认内部数组是 null，即没有实例化。第一次 调用 put 方法时，则会开始第一次初始化扩容，长度为 16。
- 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的 2 的幂数， 将这个数设置赋值给阈值（threshold）。第一次调用 put 方法时，会将阈值赋值给容量， 然后让 阈值 = 容量 x 负载因子。
- 如果不是第一次扩容，则容量变为原来的 2 倍，阈值也变为原来的 2 倍。（容量和阈值 都变为原来的 2 倍时，负载因子还是不变）。 此外还有几个细节需要注意：
- 首次 put 时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；
- 不是首次 put，则不再初始化，直接存入数据，然后判断是否需要扩容；
2、Jvm内存模型
3、索引的数据结构对比（hash、B树与B+树），为什么不用红黑树
何为索引：以图书馆为例，需借助检索目录，以加快书本查询定位；同理，MySQL索引也即为排好序的一种数据结构，用于提升数据库的查找速度。
哈希(hash)比树(tree)更快，索引结构为什么要设计成树型？
知其然，知其所以然。分析两种数据结构时间复杂度：
（1）哈希（Hash）结构，例如 HashMap，查询、删除、插入、修改的平均时间复杂度都是 O(1)；
（2）树（tree）结构，例如平衡二叉搜索树，查询、删除、插入、修改 的平均时间复杂度都是 O(logN) ；
从中分析可见，若用 Hash 类型的索引结构，无论是在读请求，还是写请求，都比 树（tree）类型的索引结构快；、
那，为何 MySQL 索引结构还设计成树型结构呢？
其一：若是简单的读写请求，Hash结构效果当然更佳；Hash 底层采用哈希表实现，等值查询，可以快速定位，一般情况效率很高。但也不稳定，当出现大量键重复哈希冲突，效率下降。
其二：MySQL 需要满足更多场景的 SQL 查询需求。Hash不支持范围查询，无法用于排序分组（grou by），无法模糊查询（like %），多列索引的最左前缀匹配原则。
而在众多树之中，MySQL最后选择了改进后的B树—>B+树
**那，MySQL 索引为什么使用 B+ 树呢？**而不用 B 树、红黑树？
你事先需要知道的几种树：
二叉搜索树
（1）当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢；
（2）当数据线性增大时，二叉搜索树会呈现单边倒的情况，时间复杂度退化 O(n)，效率更低；
（3）每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO；
AVL 树（平衡二叉搜索树）
平衡树虽然可以弥补 "当数据线性增大时，二叉搜索树会呈现单边倒的情况，时间复杂度退化 O(n) 的情况”，但是他还是具有二叉搜索树一样的缺点。
B树
B树，如下图，它的特点是：
（1）不再是二叉搜索，而是 m 叉搜索（可以根据不同度数分裂），而正由于是 m 分叉的，高度能够大大降低；
（2）并且 B树 叶子节点、非叶子节点，都可以存储数据；如果将每个节点大小设置为页大小，那么利用磁盘预读的特性，可以极大减少磁盘IO；并且，通过中序遍历，可以很快找到节点对应的数据。
思考：那到了 B 树结构，直接用来做索引是否就完美了呢？
虽然 B 树相对其他种树优势很明显，但是在范围查询时，还是很吃力；想要减少磁盘IO，节点最好设置为页大小，节点（页）大小固定后，若每个节点都存数据，每个节点也存不下多少，数据大时树的高度也不低。
于是，B+ 树应运而生，在B树上做小小改动，便是目前完美的索引结构啦。
B+树
B+树，如下图，仍是 m 叉搜索树。在 B树 的基础上，进行了一些改进：
（1）非叶子结点不存data，只存key，查询更稳定，增大了广度；数据只存在叶子节点；
（2）叶子之间，增加了链表。可以很好的支持范围查询，并且获取所有节点，不再需要中序遍历；
相比 B树 具有更优的特性：
（1）范围查找，定位min与max之后，中间叶子节点，就是结果集啦；
（2）叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK（KEY数据小，相同内存情况下，节点可以多存KEY，增大了节点广度(B+树出度更大，进而树高更矮，磁盘IO次数更少)）用于查询加速，适合内存存储；
总结：
-
索引为排好序的一种数据结构，用于提升数据库的查找速度。
-
Hash索引时间复杂度为O(1)，树索引是O(log(n))。Hash 底层是哈希表实现，等值查询，可以快速定位数据。但不支持范围查询，无法用于排序分组，无法模糊查询等操作。
-
B+树作为索引优势：
- 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；
- 非叶子节点存储记录的PK（KEY数据小，相同内存情况下，节点可以多存KEY，增大了节点广度(B+树出度更大，进而树高更矮，磁盘IO次数更少)）用于查询加速，适合内存存储；
- 叶子之间，增加了链表。可以很好的支持范围查询，并且获取所有节点，不再需要中序遍历；
- 更少查询次数：B+树出度更大，树高更低，查询次数更少；
- 很适合磁盘存储，能够充分利用局部性原理，磁盘预读（为了减少IO操作，往往不严格按需读取，而是预读。B+树叶子结点存储相临，读取会快一些）
数据结构可视化网站：https://www.cs.usfca.edu/~galles/visualization/BTree.html
4、Mysql的默认隔离级别、不同等级隔离级别解决的问题与实现原理
隔离级别原理及解决问题分析：
- READ-UNCOMMITTED（读未提交）：原理：直接读取数据，不能解决任何并发问题
- READ-COMMITTED（读已提交）：读操作不加锁，写操作加排他锁，解决了脏读。原理：利用MVCC实现，每一句语句执行前都会生成Read View（一致性视图）
- REPEATABLE-READ（可重复读）：MVCC实现，只有事务开始时会创建Read View，之后事务里的其他查询都用这个Read View。解决了脏读、不可重复读，快照读（普通查询，读取历史数据）使用MVCC解决了幻读，当前读（读取最新提交数据）通过间隙锁解决幻读（lock in share mode、for update、update、detete、insert），间隙锁在可重复读下才生效。（默认隔离级别）
- SERIALIZABLE（可串行化）：原理：使用锁，读加共享锁，写加排他锁，串行执行
总结：读已提交和可重复读实现原理就是MVCC Read View不同的生成时机。可重复读只在事务开始时生成一个Read View，之后都用的这个；读已提交每次执行前都会生成Read View。
5、Java线程池核心参数与工作流程，拒绝策略
线程池好处：降低资源消耗，提高响应速度，方便统一管理。
七大核心参数：核心线程数、最大线程数、keepAlive Time(工作线程空闲后，存活时间)、TimeUnit、workQueue、ThreadFactory、拒绝策略
线程池工作原理：向线程池添加一个任务，首先看线程池中线程数是否小于核心线程数，若小于则创建一个线程执行任务，反之再判断任务队列满没，若没有满则将任务放到任务队列并等待执行，若满了再判断现在线程池中线程数是否大于最大线程数，若没有大于则创建一个线程执行任务，若大于则使用饱和策略进行处理任务。
任务队列：ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue（存一个取一个，阻塞等待）、DelayedWorkQueue
拒绝策略：
1.CallerRunsPolicy 由调用线程处理该任务。
2.AbortPolicy 默认拒绝策略 直接丢弃，抛出异常RejectedExecutionException
3.DiscardPolicy 直接丢弃，不抛出异常
4.DiscardOldestPolicy 丢弃队列最早的任务，然后重新尝试执行任务。
Executors的4种功能线程池：定长、定时、可缓存、单线程化
线程池5大状态：Running(可接收，可处理)、Shutdown(不接收，可处理)、Stop(不接收，不处理，中断正在执行)、Tidying（所有任务终止）、Terminated（线程池彻底终止）。
创建线程池：
《阿⾥巴巴 Java 开发⼿册》中强制线程池不允许使⽤ Executors 去创建，⽽是通过ThreadPoolExecutor 的⽅式，避免使用Executors创建线程池，主要是避免使用其中的默认实现（比如定长缓存池使用链表任务队列，默认长度为Integer.MAX_VALUE，可能堆积大量请求，导致OOM）那么我们可以自己直接调用ThreadPoolExecutor的构造函数自己创建线程池。在创建的同时，给BlockQueue指定容量就可以了。规避资源耗尽的⻛险
-
Executors 返回线程池对象的弊端如下：
-
- newFixedThreadPool 和 newSingleThreadExecutor ： 允许请求的队列⻓度为Integer.MAX_VALUE ，可能堆积⼤量的请求，从⽽导致 OOM。
- newCachedThreadPool和 newScheduledThreadPool ： 允许创建的线程数量为Integer.MAX_VALUE ，可能会创建⼤量线程，从⽽导致 OOM。注意二者产生OOM的原因不一样
-
通过 Executor 框架的⼯具类 Executors 来实现
-
- 定长线程池（newFixedThreadPool）
-
-
- 特点：只有核心线程（corePoolSize=maximumPoolSize），线程数量固定，执行完立即回收，任务队列为链表结构的无界队列（Integer.MAX_VALUE）。
- 应用场景：控制线程最大并发数。
-
-
- 单线程化线程池（newSingleThreadExecutor）
-
-
- 特点：只有1个核心线程，最大线程数为1，无非核心线程，(corePoolSize=maximumPoolSize=1)执行完立即回收，任务队列为链表结构的无界队列（Integer.MAX_VALUE）。
- 应用场景：不适合并发但可能引起IO阻塞性及影响UI线程响应的操作，如数据库操作、文件操作等。
-
-
- 定时线程池（newScheduledThreadPool ）
-
-
- 特点：核心线程数量固定，非核心线程数量无限，执行完闲置10ms后回收，任务队列为延时阻塞队列。(corePoolSize为传进来参数，最大线程数=Integer.MAX_VALUE，使用DelayedWorkQueue())
- 应用场景：执行定时或周期性的任务。
-
-
- 可缓存线程池（newCachedThreadPool）
-
-
- 特点：无核心线程，非核心线程数量无限，执行完闲置60s后回收，任务队列为不存储元素的阻塞队列（SynchronousQueue）。（corePoolSize=0，maximumPoolSize=Integer.MAX_VALUE，keepAlive Time=60L）
- 应用场景：执行大量、耗时少的任务。
-
-
通过ThreadPoolExecutor 构造方法
6、Tcp与Udp区别
tcp可靠传输，面向字节流，拥塞控制，流量控制，一对一
udp不可靠传输，面向报文，没有拥塞控制，流量控制，支持一对一，一对多
tcp首部长度若没有选项字段大小20字节，udp首部长度固定8字节（这也是为何udp没有首部长度字段）
使用场景：
tcp效率要求低，准确性要求高的（文件传输）；udp效率要求高，准备要求相对可以低点（QQ聊天，视频通话）
为何udp快：
不需要建立连接、没有超时重传、对收到数据不需给确认、没有流量控制拥塞控制
tcp首部格式：
20字节源端口、目的端口、序列号、确认号、数据偏移、保留字、URG、ACK、FIN、PSH、FIN
udp首部格式：
首部8字节，源端口、目的端口、包长度、检验和，再计算检验和时还会添加12字节的伪首部
7、键入网址到页面显示，期间发生什么？
8、Redis基本数据类型，平时怎么使用？
9、MySQL事务及特性
事务：一系列操作组成，要么全部成功，要么全部失败
事务ACID特性
- 原子性：一些列操作要么全部成功，要么全部失败
- 隔离性：事务的结果只有提交了其他事务才可见
- 一致性：数据库总时从一个一致状态变到另一个一致状态（事务修改前后的数据总体保证一致 转账）
- 持久性：事务提交后，对数据修改永久的
事务的并发问题：
- 脏读：读到未提交的数据
- 不可重复读：一个事务下，两次读取数据不一致（侧重内容数据的修改）
- 幻读：事务A 按照一定条件进行数据读取， 期间事务B 插入了相同搜索条件的新数据，事务A再次按照原先条件进行读取时，发现了事务B 新插入的数据 称为幻读（侧重新增或删除，插入数据读到多了一行）
10、Tcp三次握手四次挥手及对应的状态
开始客户端服务端都处于CLOSE状态，然后服务端主动监听某个端口，处于listen状态
客户端发送SYN报文：客户端随机初始化seq=x，并将序列号置于TCP首部序列号字段中，并将SYN标志位置为1，发送SYN报文到服务端，客户端变为SYN_SEND
服务端发送SYN+ACK报文：服务端收到客户端的SYN报文，也会随机初始化序列号seq=y，并将序列号置于TCP首部序列号字段，还会将x+1置于确认应答号字段中，然后置SYN=1,ACK=1将报文发给客户端，不包含应用层数据，之后服务端处于SYN_REVD状态
**客户端发送ACK报文：**客户端收到服务端报文，向服务端发送确认的确认，置ACK标志位为1，确认应答号为y+1，然后发给服务端，这次可以携带数据，此后，客户端服务端都处于ESTABLISHED状态。
客户端发起连接请求报文段（客：SYBN_SEND）
服务端为该TCP连接分配缓存与变量，给予确认（服：SYN_REVD）
客户端为该TCP连接分配缓存与变量（客：ESTABLISHED）,给予确认的确认（服：ESTABLISHED）