BT-interview-note-ii

自我介绍

项目介绍

java

多态

多态是同一个行为具有多个不同表现形式或形态的能力。即同一个接口，使用不同的实例而执行不同操作。多态是设计模式中的策略模式的关键。

设计模式是软件开发人员在软件开发过程中遇到的一般问题的解决方案、经验总结。设计模式代表着最佳的实践。参考书中提到的有 23 种设计模式，比如工厂模式、单例模式、代理模式、策略模式、MVC 模式等。

策略模式指一个类的行为或其算法可以在运行时更改。策略模式使用的是面向对象的继承和多态机制。Context 是一个使用了某种策略的类，策略模式的实现：

1. 创建一个接口 Strategy
2. 创建接口的实体类
3. 创建 Context 类
4. 使用 Context 来查看当它改变策略 Strategy 时的行为变化。

垃圾回收

分代是指 Java 虚拟机根据对象存活的周期不同，将堆内存划分为新生代（细分为伊甸区、幸存者区）和老年代。根据各个代的特点采用最适合的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成。而老年代中因为对象存活率高、没有额外空间对他进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。

垃圾回收算法：

1. 复制算法：将内存区域划分成相同的两个内存块。每次仅使用一半的空间，JVM生成的新对象放在一半空间中。当一半空间用完时进行GC，把可到达对象复制到另一半空间，然后把使用过的内存空间一次清理掉。新生区的对象往往内存较小，可以使用复制算法，将对象复制到另一半内存上就可以清除，不会造成内存碎片。
2. 标记-清除算法：标记-清除算法对根集合进行扫描，对存活的对象进行标记。标记完成后，再对整个空间内未被标记的对象扫描，进行回收。不需要进行对象进行移动。标记、清除过程效率低，产生大量不连续的内存碎片，提高了垃圾回收的频率。
3. 标记-整理算法：进行对象的标记，但后续不直接对可回收对象进行清理，而是将所有的存活对象往一端空闲空间移动，然后清理掉端边界以外的内存空间。解决了标记-清理算法存在的内存碎片问题。仍需要进行局部对象移动，一定程度上降低了效率。

Spring IOC

开发者使用Spring框架主要是做两件事：①开发Bean；②配置Bean。对于Spring框架来说，它要做的就是根据配置文件来创建Bean实例，并调用Bean实例的方法完成”依赖注入”——这就是所谓IoC的本质。

IOC is Inversion Of Control. It means that the application won’t manage it’s lifecycle/flow of control itself. The framework (Spring) will. So you just tell the framework how you want (some) elements of your app to work together.

DI is dependency injection. It’s a specific kind of IOC where the framework will manage the dependencies that an object uses (you can call dependency: a service).

Bean is an object managed by the Framework.

map

map 接口：存储键值对，能高效通过 key 快速查找 value。

import java.util.HashMap;
import java.util.Map;
	
Map<String, String> map = new HashMap<String, String>();
map.put("key1", "value1");
map.get("key1");
map.remove("key1");

map 常用的实现类：HashMap、Hashtable、TreeMap 等。

Hashtable：与 HashMap类似,不同的是 key 和 value 的值均不允许为 null; 它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。

TreeMap：根据键(key)排序,默认是按升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。

hashmap：根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null(多条会覆盖);允许多条记录的值为 Null。

https://blog.csdn.net/login_sonata/article/details/76598675

hashmap 的实现结构：数组+链表+红黑树（JDK1.8增加了红黑树部分）HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。

rehash

多线程

threadLocal的实现原理；线程池的实现原理，线程运行完run方法就被回收了吗；并发锁的实现；

http连接池

对于线程来讲，如果不需要它返回结果则实现Runnable，而如果需要执行结果的话则可以实现Callable。在线程池同样execute提供一个不需要返回结果的任务执行，而对于需要结果返回的则可调用其submit方法。

https://blog.csdn.net/weixin_43138919/article/details/88948588

线程池类ThreadPoolExecutor

1. 当线程池内线程数小于corePoolSize时，新提交的任务都会创建一个新的线程来执行。
2. 当线程池内线程数等于corePoolSize时，新提交的任务会放入workQueue中，等待线程池中任务调度。
3. 当workQueue已满，且maximumPoolSize>corePoolSize时，新提交任务会创建新线程执行任务。
4. 当提交任务数超过maximumPoolSize时，新提交任务会交给RejectedExecutionHandler处理。
5. 当线程池中超过corePoolSize时，空闲时间达到keepAliveTime时，关闭空闲线程。
6. 当设置allowCoreThreadTimeOut(true)时，线程池中corePoolSize线程空闲时间达到keepAliveTime也将关闭 。

ThreadPoolExecutor#runWorker，Worker在执行完任务后，还会循环获取任务队列里的任务执行（其中的getTask方法），也就是说Worker不仅仅是在执行完给它的任务就释放或者结束，它不会闲着，而是继续从任务队列中获取任务，直到任务队列中没有任务可执行时，它才退出循环完成任务。

用BlockingQueue数据结构存储任务。

LinkedBlockingQueue

1. 使用takeLock和putLock进行并发控制，添加和删除可以同时进行，提高吞吐量。
2. 对每个锁都提供了一个Condition用来挂起和唤醒其它线程。
3. put 和 take 方法 （空/满 –> 阻塞、唤醒）
4. LinkedBlockingQueue与ArrayBlockingQueue：

阻塞队列	LinkedBlockingQueue	ArrayBlockingQueue
队列大小	可以有界 可以无界Integer.MAX_VALUE	有界，初始化时指定大小
存储容器	node节点的链表	数组
插入和删除	会产生额外的对象实例	不会产生额外的对象实例
添加和删除的并发	可以同时进行	用的是同一个锁，两个操作互斥

编程

创建三个线程，按序输出1, 2, 3 （\lab\ref\backend\src\main\java\test\t1.java）

package test;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class t1 {
    private static Lock lock=new ReentrantLock();
    private static int state=0;

    private static class Worker extends Thread{
        int mod;
        int v;

        Worker(int mod,int v){
            this.mod=mod;
            this.v=v;
        }
        @Override
        public void run()
        {
            while(true){
                lock.lock();
                if(state%mod==v){
                    System.out.println(v+1);
                    state++;
                }
                lock.unlock();
            }
        }
    }
    public static void main(String[] args) {
        Worker a=new Worker(3,0);
        Worker b=new Worker(3,1);
        Worker c=new Worker(3,2);
        a.start();
        b.start();
        c.start();
    }
}

但是这样的代码中有忙等待，性能很低，随着线程数数量增加的话，这样的程序是不适用的。

计算机网络

http报文结构

http请求报文由四个部分组成：请求行、请求头部、空行、请求数据

• 请求行：方法 URL 版本，如：GET /data/info.html HTTP/1.1
• 请求头部：用来准确描述正在获取的资源、服务器或者客户端的行为，定义了HTTP事务中的具体操作参数。如：Accept用于说明可接受的响应内容类型，Content-Type用于说明请求体的MIME类型 （用于POST和PUT请求中），Origin用于说明发起一个针对跨域资源共享的请求（该请求要求服务器在响应中加入一个Access-Control-Allow-Origin的消息头，表示访问控制所允许的来源）。常用的HTTP请求头与响应头
• 空行告诉服务器请求头部到此为止。

HTTP响应报文也由四部分组成：响应行、响应头、空行、响应体。响应行：版本 状态码 描述，如：HTTP/1.1 200 OK

http和https的区别

1. HTTPS协议需要到ca（数字证书认证机构）申请证书，可能需要一定的费用；
2. http（超文本传输协议）是明文传输；HTTPS是ssl加密传输协议；
3. http使用80端口，HTTPS使用443端口；
4. http是无状态的简单连接；HTTPS是由SSL+HTTP构建的有加密传输、身份认证的网络协议，更加安全。

HTTPS协议的主要作用：建立一个信息安全通道保证数据传输的安全；确认网站的真实性。

为什么使用对称加密结合非对称加密

对称加密：加密和解密使用同一秘钥，秘钥通过网络传输。若对称秘钥被截获，仍有可能出现数据被中间人篡改或冒名顶替的问题。

非对称加密：A生成公钥和私钥，私钥保留在本地不再在网络上进行传输，公钥是分发给其他人（一般是下发的证书中包含公钥然后返回给请求者），公钥私钥是一对，私钥加密的只有公钥才能够解密，若能成功解密则证明跟你交互的那个人是当初给你公钥的那个人。A给B发消息，用A的私钥加密，B收到之后用A的公钥解密。即A、B要使用非对称加密，需要各自保留对方的公钥。客户端和服务器交互，服务端一个私钥，而大量客户端用公钥跟他交互。

非对称加密对秘钥的存储成本更低；对称加密（如AES）中的主要运算是位运算，非对称加密（如RSA）中用到了大数乘法、大数模等运算，因此对称加密的速度更快。

两种加密方式结合 -> 安全和效率的动态平衡，将对称加密的密钥使用非对称加密的公钥进行加密，然后发送出去，接收方使用私钥进行解密得到对称加密的密钥，然后双方可以使用对称加密来进行沟通。

客户端如何知道服务器可信 如何验证ca证书可信

等同于：如何保证发布公钥的人不是他人冒名顶替？

找一个受信任的机构”证书中心”（certificate authority，简称CA）做认证，证书中心用自己的私钥给（A的公钥+申请者A的信息等）加密，生成数字证书。当下次A给B发消息的时候A会带上CA签发的数字证书，B收到后用CA的公钥解密证书，解密成功则证明这个的确是CA签发的有效证书，而不是不知名的野鸡机构，从而拿到了里面的A的公钥，证明了A就是CA机构认证过的A,这个的的确确就是A的公钥，错了就找CA机构买单。然后拿A的公钥，去解密数字签名得到摘要，在对原文进行摘要算法之后和这个摘要进行对比，一致则说明没有被篡改。

浏览器认证中间证书的方法：
1.浏览器首先解析网站的数字证书，如果该证书的签发机构能够在可信任签发机构中找到，则为可信任证书，否则进行2
2.从授权信息访问信息段中获得该签发机构的数字证书，并判断该授权机构的数字证书的签发机构是否能够在可信任签发机构中找到，若果找到则该授权机构是可信的，并从授权机构的数字证书中获得授权机构的公钥公钥，如果不在则重复2步骤。如果最终都没有找到可信机构，则为不可信证书。

数据库

###主键索引和非主键索引的区别

以下面这个例子，ID是主键，并且还有一个字段K

那么ID和k的索引如下两图所示

索引的结构同样都是B+树，区别在于叶子节点。主键的叶子节点中存储的是整行的值，而非主键中存储的是主键的值。非主键索引也被称为二级索引，而主键索引也被称为聚簇索引。

###回表查询

查询非主键索引时

（1）先通过普通索引定位到主键值

（2）在通过聚集索引定位到行记录；

回表查询需要查询两次，效率比较低。避免的方法是联合索引，然后不查没有被联合索引的字段。

###主键索引(聚簇索引)是必须的吗？

InnoDB聚集索引的叶子节点存储行记录，因此， InnoDB必须要有，且只有一个聚集索引：

（1）如果表定义了PK，则PK就是聚集索引；

（2）如果表没有定义PK，则第一个not NULL unique列是聚集索引；

（3）否则，InnoDB会创建一个隐藏的row-id作为聚集索引；

画外音：所以PK查询非常快，直接定位行记录。

索引为什么用B+树

首先为什么要用树

哈希表查询很快，但是无法进行范围查询，因此哈希表不合适作为数据库的索引

演化过程

二叉搜索树

子树的高度不平衡导致最坏情况下的查询可能会到达O(n)

#####平衡二叉搜索树(AVL)

平衡的树高避免了最坏的情况，可以保证查询的时间复杂度是O(log(n))。但是数据库不只有查询操作，还有增删改。AVL需要频繁的维护树的结构，这会带来很大的开销

多路平衡搜索树 B树

B树改进了AVL树，减少了平衡树的操作，即降低了维护树结构的开销。

B+树

那么B树和B+树的区别在哪呢？

1. B+跟B树不同B+树的非叶子节点不保存键值对应的数据，这样使得B+树每个节点所能保存的键值大大增加；
2. B+树叶子节点保存了父节点的所有键值和键值对应的数据，每个叶子节点的键值从小到大链接；
3. B+树的根节点键值数量和其子节点个数相等;
4. B+的非叶子节点只进行数据索引，不会存实际的键值对应的数据，所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；

放个图理解的更清楚一点，B树

在B+树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有关键字数据都存在叶子节点，所以每次查找的次数都相同，查询速度比B树更稳定。除此之外，B+树的叶子节点是跟后序节点相连接的，这对范围查找是非常有用的。

乐观锁

乐观锁底层使用原子指令CAS实现(Compare and Swap)。由于是用硬件支持的原子指令，效率非常高，很少有额外的开销。而悲观锁底层用Mutex实现，涉及到一系列的系统调用，额外的开销会比较大。在具体场景上，乐观锁在进行更改时，需要对比之前的的版本号，如果版本号一致即认为数据没有被修改过，可以进行更新；而悲观锁则保证修改数据时线程之间的互斥，在critical section中只有一个线程允许进入。

1、功能限制

与悲观锁相比，乐观锁适用的场景受到了更多的限制，无论是CAS还是版本号机制。

例如，CAS只能保证单个变量操作的原子性，当涉及到多个变量时，CAS是无能为力的，而synchronized则可以通过对整个代码块加锁来处理。再比如版本号机制，如果query的时候是针对表1，而update的时候是针对表2，也很难通过简单的版本号来实现乐观锁。

2、竞争激烈程度

如果悲观锁和乐观锁都可以使用，那么选择就要考虑竞争的激烈程度：

• 当竞争不激烈 (出现并发冲突的概率小)时，乐观锁更有优势，因为悲观锁会锁住代码块或数据，其他线程无法同时访问，影响并发，而且加锁和释放锁都需要消耗额外的资源。
• 当竞争激烈(出现并发冲突的概率大)时，悲观锁更有优势，因为乐观锁在执行更新时频繁失败，需要不断重试，浪费CPU资源。

####IO次数

如果比较成功进行更新的话就是三次IO，如果比较失败不更新的话应该是两次IO

// 假设需要更新的值为A
oldval = load(A)
// 进行一系列的计算
newval = ......
......
val = load(A)
//如果 val == oldval 将 A更新为newval
A.CAS(oldval, val, newval)