秋招面经四（亿联，一点资讯，滴滴，用友，猿辅导）

亿联

一面（2020-7-20）

1、设计模式

2、springboot的装载过程

3、kafka有没有丢失消息的情况，消息放在内存中的情况

见 -- > 阿里云面经

4、aop

二面（2020-7-24）

1、kafka机制

一点咨询

一面（2020-7-25）

1、GC算法

标记复制，标记清除，标记整理

2、GC的可达性分析的数据结构

树形结构，从GC_roots开始向下遍历，最后依旧连接在一起的就是存活的对象，独立出来的就是死亡对象。

3、hashMap死循环

首先要明确死循环问题在JDK 1.8 之前是存在的，JDK 1.8 通过增加loHead和loTail进行了修复。

主要原因在于，当我们的触发resize函数之后，我们在resize的函数中，加入了transfer函数进行链表的转移。在链表的转移过程中，我们使用的是头插法进行转移，也就是说最后转移之后的链表顺序和之前的链表顺序是相反的。

a - > b - > c
转移之后
c - > b - > a

所以在多线程的情况下，如果我们如果多个线程在对其进行链表转移，会可能导致转移之后的链表是一个循环链表。

一旦产生了这种情况，当我们调用get()方法的时候，就会触发这个死循环链表，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。

4、红黑树左右旋转

见百度一面面经

5、手撕快排，插入排序

二面（2020-7-29）

1、手撕代码

1.1 第一题

1.2 多线程

2、设计模式的七大法则

• 开闭原则：对扩展开放，对修改关闭
• 里氏替换原则：继承必须确保超类所拥有的性质在子类中依然成立。（子类尽量不要重写父类方法）
• 依赖倒置原则：要面向接口编程：不要面向实现编程。
• 单一职责原则：控制类的粒度大小，将对象解耦、提高其内聚性
• 接口隔离原则：要为各个类建立它们需要的专用接口
• 迪米特法则：只和你的直接朋友交谈，不跟“陌生人”说话。
• 合成复用原则：尽量先使用组合或者聚合等关联关系来实现，其次才考虑使用继承关系来实现

3、ISR

属于kafka里面副本的概念：

每一个分区中的所有副本统称为AR（Assigned Replicas），所有与leader副本保持一定同步程度的副本（包括leader副本）组成ISR（In-Sync Replicas）,与leader副本同步滞后过多的副本组成OSR（Out-of-Sync Replicas）。

ISR和HW（high watermark）和LEO（logstartoffset）有密切关系。HW标识了一个特定的消息偏移量offset，消费者只能拉取到这个offset之前的消息。LEO标识当前日志文件中下一条待写入消息的offset，LEO的大小相当于当前日志分区中最后一条消息的offset+1，ISR集合中的最小的LEO即为分区的HW，对消费者而言只能消费HW之前的消息。

4、死锁条件

循环等待，资源互斥，非抢占，持有一部分资源。

5、主要了解几款垃圾回收器

• cms：以获取最短回收停顿时间为目标，基于增量更新的方式，标记清除算法实现，主要有以下几个过程
  • 初始标记
  • 并发标记
  • 重新标记
  • 并发清除

• parallel scavenge：吞度量优先，基于标记-复制算法实现的垃圾收集器，也是一个多线程扫描，新生代收集器
• parallel Old：与parallel scavenge一起搭配使用，以吞吐量为优先，基于标记-整理算法，老年代收集器

• serial/serial old：这是两款垃圾回收器，都是单线程工作，在新生代中，使用复制算法，在老年代中使用标记-整理算法

• parNew收集器：与serial相同，负责新时代，只是在扫描的时候使用的是多线程进行扫描，采用的依旧是标记复制算法

6、对象头：锁机制

偏向锁、无锁，锁的膨胀，自旋锁，jvm内部的自动升级如何完成的

7、磁盘预读

系统是分页读取和存储的，一般一页为4KB，每次读取和存取的最小单元为一页，预读即在读取的起始地址连续读取多个页面。这样可以减少磁盘和内存的IO操作。

8、Redis的底层数据结构

https://www.cnblogs.com/ysocean/p/9080942.html https://www.cnblogs.com/MouseDong/p/11134039.html

Redis 是用 C 语言写的

8.1 String类型

底层的实现有三种方式，sdshdr/int/embstr

它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

存储的形状如上所示。采用这种动态数组的优势：

（1）减少修改字符串的内存重新分配次数

C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。

而对于SDS，由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

1、空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。

2、惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 free 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

（2）二进制安全

因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

8.2 链表

底层使用的是linkedList（数据量大的时候），和ziplist（数据量小的时候），以及3.0出来的quicklist

C 语言内部是没有内置这种数据结构的实现，所以Redis自己构建了链表的实现。链表定义：

typedef  struct listNode{
       //前置节点
       struct listNode *prev;
       //后置节点
       struct listNode *next;
       //节点的值
       void *value;  
}listNode

通过多个 listNode 结构就可以组成链表，这是一个双向链表，Redis还提供了操作链表的数据结构：

typedef struct list{
     //表头节点
     listNode *head;
     //表尾节点
     listNode *tail;
     //链表所包含的节点数量
     unsigned long len;
     //节点值复制函数
     void (*free) (void *ptr);
     //节点值释放函数
     void (*free) (void *ptr);
     //节点值对比函数
     int (*match) (void *ptr,void *key);
}list;

结构示意图：

Redis链表特性：

①、双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。

②、无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。

③、带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。

④、多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

8.3 字典（hash）

底层实现是：ziplist和hashtable

字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。

Redis 的字典使用哈希表作为底层实现，

typedef struct dictht{
     //哈希表数组
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩码，用于计算索引值
     //总是等于 size-1
     unsigned long sizemask;
     //该哈希表已有节点的数量
     unsigned long used;
 
}dictht

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

（1）解决哈希冲突：

方法是链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

（2）扩容和收缩：

当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：

• 如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
• 重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。
• 所有键值对都迁徙完毕后，释放原哈希表的内存空间。

（3）触发扩容的条件：

• 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。
• 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小

（4）渐近式 rehash

什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。

所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

8.4 sorted set

http://zhangtielei.com/posts/blog-redis-skiplist.html

当数据量较少的时候，使用的是ziplist，当数据超过一定的数量之后，转为zset

zset的实现使用的是字典+skiplist的组合方式，并且对skiplist进行了一定程度的扩展，每个skiplist节点上都有后向指针跳跃的节点个数，用这种方式来保证查找按照排序来进行。

8.5 集合

底层使用的是intset，hashtable

intset是一个自定义的结构体，使用数组实现，所以当Redis中的set编码为intset的时候是有序的。

当set编码为hashtable的时候，是无序的。

9、如何判断发生死锁

• 可以使用-jstack命令，在jstack中可以直接看出代码中的哪一行出现了死锁。
• 或者使用jconsole.exe，直接检测死锁即可

10、mysql为什么用B+树，不用B树，不用红黑树？

https://blog.csdn.net/xiedelong/article/details/81417049

B-树/B+树 的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。另一个优点是： B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

11、建议

会一点Python、shell、Redis、es、jdk、mysql

滴滴

一面（2020-7-28）

二面（2020-7-28）

1、为什么帖子点赞要用set数据结构，用hash可以么？

2、事务的隔离机制

3、synchronize的底层实现

https://www.jianshu.com/p/c97227e592e1

• ``synchronized修饰的方法在字节码中添加了一个ACC_SYNCHRONIZED的flags，当线程执行到某个方法时，JVM会去检查该方法的ACC_SYNCHRONIZED访问标志是否被设置，如果设置了那线程会去获取这个对象所对应的monitor对象（每一个对象都有且仅有一个与之对应的monitor对象）,获取成功后才执行方法体，方法执行完再释放monitor对象，在这一期间，任何其他线程都无法获得这个monitor对象。
• 同步代码块则是在同步代码块前插入monitorenter，在同步代码块结束后插入monitorexit``。而线程执行同步代码块时遇到的monitorenter和monitorexit指令依赖monitor对象完成。这两者实现的方式本质上无区别，只是方法的同步是一种隐式的方式，不通过字节码实现。

4、GC算法

标记复制、标记清除、标记整理

三面（2020-7-28）

1、操作系统进程和线程

用友

一面(2020-08-07)：

1、单线程在for循环里面修改和遍历list，如何操作？

https://blog.csdn.net/sxfda/article/details/50017711

public static void main(String[] args) {
        Collection<String> list = new ArrayList<String>();
        list.add("Android");
        list.add("iPhone");
        list.add("Windows Mobile");

        // example 0
        Iterator<String> itr0 = list.iterator();
        while(itr0.hasNext()){
            String lang = itr0.next();
            itr0.remove();
        }

        // example 1
        Iterator<String> itr1 = list.iterator();
        while(itr1.hasNext()){ //Exception in thread "main" java.util.ConcurrentModificationException
            String lang = itr1.next();
            list.remove(lang);
        }

        // example 2
        System.out.println("example02");
        for(int i = 0; i < list.size(); i++){
            list.remove(i);
        }

        // example 3
        System.out.println("example03");
        for(String language: list){//Exception in thread "main" java.util.ConcurrentModificationException
            list.remove(language);
        }
    
    }

在上面的代码中：example0,example2不会抛出ConcurrentModificationException异常;但example1,example3则会抛出ConcurrentModificationException异常;

原因很简单，在example0和2中，我们只操作Iterator和list对象，这样的话不会产生冲突；但是在example1和3中，我们同时操作了list和iterator，这样会导致两者不一致的情况产生。iterator每次迭代时会检查

ourList.modCount != expectedModCount

不一致时，则抛出ConcurrentModificationException异常;

2、编程题

    public static void main(String[] args) {
        Integer x;
        int y = 200;
        System.out.println(x ` y);
    }

会报编译错误，x未初始化。

3、UUID是一个32位的16进制数字，如何将其压缩到20位以内，并且可以保证一一对应

看源码后，发现UUID的格式是这样的：

<time_low> "-" <time_mid> "-" <time_high_and_version> "-" <variant_and_sequence> "-" <node></>

它是一堆-分割的16进制的数字，如果只是为了保证唯一性，那这些-对我们来说是没有实际的用处的，可以直接去掉，这样我们就节省了4个字节，剩下32个字节。接下来再想办法继续压缩这32个字节。

16进制的字符一共有16个，等于2的4次方。如果我们去自己对这16个字符进行编码，只需要4个bit就可以表示这16个字符，从0000 - 1111一共16个。

一个byte有8个bit，所以一个字节的高4位和低4位一共能放两个字符编码。

这样我们就能够再节省一半的空间。最终我们就能够以16个字节存储36个字节的uuid了，空间节省了一半多。

猿辅导

一面（2020-8-8）

1、会话技术除了cookie和session还有哪些？

还可以使用token

2、一个编程题

3、Redis中多个不同的操作如何使用事务

尝试一下对多个事务再次进行升级，即分布式事务

4、类加载机制

4.1 加载

通过全限定类名获取此类的二进制字节流，将字节流中代表的静态存储结构转化为方法区的运行时数据结构

4.2 连接

（1）验证

• 文件格式验证：字节流是否符合class文件格式的规范，比如魔数cafebabe
• 原数据验证：语义分析，检查这个类是否有父类，是否继承了final修饰的类
• 字节码验证：最复杂，通过数据流分析和控制分析，确定程序语义是合法的、符合逻辑的
• 符号引用验证：这个验证发生在，验证类自身以外的各类信息进行匹配性校验。该类是否缺少或者被禁止访问它依赖的某些外部类

（2）准备

为正式类中定义的变量（静态变量）分配内存并设为类变量初始值的阶段。此时不包含实例变量。例如

public static int value = 123;

在准备阶段会将value赋值为0，而不是123,。

如果是final修饰的，则会被赋值为程序中的值，例如

public static final int value = 123;

此时在编译的时候，会对value生成一个constantValue属性，在准备阶段，虚拟机直接将value赋值为123，而不是0。

（3）解析

将常量池内的符号引用替换为直接引用的过程。

4.3 初始化

此时虚拟机开始真正开始执行类中编写的java程序代码，将主导权移交给应用程序。在初始化阶段，会根据程序员通过程序编码指定的主观计划去初始化类变量和其他资源。

二面（2020-8-14）

1、spring循环依赖问题

https://mp.weixin.qq.com/s/2u7k_jt-3p_dgTXy4tB7Tg

这里推荐一篇文章看一下，比我说的要好。

2、springIOC的工作流程

https://javadoop.com/post/spring-ioc

3、BeanFactory 和 Context的区别

https://blog.csdn.net/pseudonym_/article/details/72826059

• BeanFactory：BeanFactory是spring中比较原始，比较古老的Factory。因为比较古老，所以BeanFactory无法支持spring插件，例如：AOP、Web应用等功能。
• ApplicationContext：ApplicationContext是BeanFactory的子类，因为古老的BeanFactory无法满足不断更新的spring的需求，于是ApplicationContext就基本上代替了BeanFactory的工作，以一种更面向框架的工作方式以及对上下文进行分层和实现继承，并在这个基础上对功能进行扩展： <1>MessageSource, 提供国际化的消息访问 <2>资源访问（如URL和文件） <3>事件传递 <4>Bean的自动装配 <5>各种不同应用层的Context实现

4、并行流

三面（2020-8-24）

1、如何满足多个值存放在set里面

对key进行分组存储，我们比如有key1，那么我们分组成为a.key1和b.key1，然后每个组里面存放不同的key。使用分组的时候，可以考虑将value设置一下分组属于哪一组。这样完成一个分布式的部署。避免一个key中的set存放过多的情况。

2、动态代理中如果没有interface，怎么实现。在spring里面（AOP原理）

https://www.jianshu.com/p/ec0af8dd9e2a

Spring Boot动态代理分两种，分别是jdk动态代理和CGLIB动态代理。

2.1、默认情况下使用的是jdk动态代理

JDK的动态代理和cglib的动态代理，JDK动态代理是利用反射机制在运行时创建代理类的。

2.2、重点说一下CGLIB动态代理

JDK代理要求被代理的类必须实现接口，有很强的局限性。而CGLIB动态代理则没有此类强制性要求。简单的说，CGLIB会让生成的代理类继承被代理类，并在代理类中对代理方法进行强化处理(前置处理、后置处理等)。在CGLIB底层，其实是借助了ASM这个非常强大的Java字节码生成框架。

被代理类：

实现MethodInterceptor接口生成方法**拦截器**：

生成代理类对象并打印在代理类对象调用方法之后的执行结果：

（1）生成代理类对象

从图1.3中我们看到，代理类对象是由Enhancer类创建的。Enhancer是CGLIB的字节码增强器，可以很方便的对类进行拓展，如图1.3中的为类设置Superclass。

创建代理对象的几个步骤:

• 生成代理类的二进制字节码文件；
• 加载二进制字节码，生成Class对象( 例如使用Class.forName()方法 )；
• 通过反射机制获得实例构造，并创建代理类对象

（2）对委托类进行代理

我们上面贴出了生成的代理类源码。以我们上面的例子为参考，下面我们总结一下CGLIB在进行代理的时候都进行了哪些工作呢

• 生成的代理类HelloServiceImpl![EnhancerByCGLIB](math.svg)82ef2d06，继承被代理类HelloServiceImpl。在这里我们需要注意一点：如果委托类被final修饰，那么它不可被继承，即不可被代理；同样，如果委托类中存在final修饰的方法，那么该方法也不可被代理；
• 代理类会为委托方法生成两个方法，一个是重写的sayHello方法，另一个是CGLIBsayHello0方法，我们可以看到它是直接调用父类的sayHello方法；
• 当执行代理对象的sayHello方法时，会首先判断一下是否存在实现了MethodInterceptor接口的CGLIB$CALLBACK_0;，如果存在，则将调用MethodInterceptor中的intercept方法，如图2.1。

在intercept方法中，我们除了会调用委托方法，还会进行一些增强操作。在Spring AOP中，典型的应用场景就是在某些敏感方法执行前后进行操作日志记录。

（3）代理方法的调用

在CGLIB中，方法的调用并不是通过反射来完成的，而是直接对方法进行调用：FastClass对Class对象进行特别的处理，比如将会用数组保存method的引用，每次调用方法的时候都是通过一个index下标来保持对方法的引用。

3、分布式的解决方案

4、spring中的设计模式

https://github.com/Snailclimb/JavaGuide/blob/master/docs/system-design/framework/spring/Spring-Design-Patterns.md

Spring 框架中用到了哪些设计模式？

• 工厂设计模式 : Spring使用工厂模式通过 BeanFactory、ApplicationContext 创建 bean 对象。
• 代理设计模式 : Spring AOP 功能的实现。
• 单例设计模式 : Spring 中的 Bean 默认都是单例的。
• 模板方法模式 : Spring 中 jdbcTemplate、hibernateTemplate 等以 Template 结尾的对数据库操作的类，它们就使用到了模板模式。
• 包装器设计模式 : 我们的项目需要连接多个数据库，而且不同的客户在每次访问中根据需要会去访问不同的数据库。这种模式让我们可以根据客户的需求能够动态切换不同的数据源。
• 观察者模式: Spring 事件驱动模型就是观察者模式很经典的一个应用。
• 适配器模式 :Spring AOP 的增强或通知(Advice)使用到了适配器模式、spring MVC 中也是用到了适配器模式适配Controller。