Java八股

来嘛，背嘛兄弟, 持续更新

Java基础

ArrayList和LinkedList的数据结构与区别

ArrayList内部是一个Object[], 由于内部采用数组实现，所以优点是可以根据下标可以快速访问元素，缺点是在增加删除时，需要移动整个数组，效率较低，并且数组需要占用连续内存。
LinkedList是一个双向链表，因此优点是比较容易添加删除节点，缺点是搜索访问时需要指针从头查找，效率较低，链表不需要连续内存。
ArrayList和LinkedList都是List接口的实现类，他们都是线程不安全的。

ArrayList扩容机制

ArrayList的add方法调用时，会先调用ensureCapacityInternal进行扩容。

HashMap数据结构

首先HashMap在Java7和Java8里实现有一些不一样，java8在7的基础上进行了优化
在Java7中，HashMap内部是一个Node节点数组，其中Node是一个单向链表节点，只指向下一个元素。所以可以说，HashMap内部是一个数组，数组的每个元素是一个链表，即数组+链表。这样的构造是为了解决put时的哈希碰撞问题。

HashMap put过程, 扩容过程，怎么判断元素是否重复?链表转红黑树的原因

HashMap在put一对Key/Value时，有以下步骤：

• HashMap使用自己实现的Hash方法，计算得到Key的hash值
• 检查内部的Node节点数组（可称作哈希槽）是否为空，如果为空，调用resize方法进行初始化（resize也负责扩容）
• 扩容的逻辑：如果哈希槽为空，先创建一个默认初始长度为16的数组；如果哈希槽已经初始化，检查是否达到扩容阈值，默认为0.75*当前长度，如果达到了，扩容为当前2倍
• 接下来继续走put流程，通过（n-1）&hash 计算出元素该位于哈希槽的哪个位置，其中n为当前哈希槽长度，hash为HashMap计算出的key的hash值, 如果该位置上没有东西，直接创建个Node放在这里
• 如果发现此处已有Node，开始判断是否重复，如果此处的Node的hash和key值，和要put的key的hash值和本身的值均相同，那么就认为是重复元素，直接返回。
• 如果发现此处已有Node, 但是并非重复，如果是TreeNode, 即链表已转化为红黑树，此时往红黑树中插入元素
• 如果发现此处已有Node, 但是并非重复，如果不是TreeNode, 即此时还是链表，先将元素插入到链表尾，再调用treeifBin方法，判断如果哈希槽长度小于64，先尝试resize扩大哈希槽；如果哈希槽长度小于64，切链表长度超过8，将链表转化为红黑树。
• 最后再判断，如果当前Map容量超过75%, 即0.75*当前容量, 再resize一次

链表转红黑树，是为了提高查找效率。
试想一下get过程，HashMap计算key的hash值，再定位到hash槽上，此时hash槽上是一个有多个节点的链表，此时HashMap会从链表中查找hash和key值都相同的节点，因为是链表中查询，时间复杂度为 O(n), 而红黑树的查询时间复杂度为O(logN)

3.红黑树数据结构?左旋和右旋过程?
B tree, B+tree,
todo

4.HashMap是否线程安全?线程安全的Map?怎么实现的?
HashMap不是线程安全的Map。线程安全的Map是ConcurrentHashMap。
在java1.7中，ConcurrentHashMap的内部分为多个Segment,每个Segment中是类似HashMap的结构，当对ConcurrentHashMap进行操作时，使用RetrantLock对操作的Segment加锁，可以理解为对一段数据进行加锁。在Java1.8中，ConcurrentHashMap使用的是HashMap一样的数组+链表/红黑树结构，对链表/红黑树的节点使用sychronized,从而达到线程安全。

5.CAS原理?怎么解决ABA问题?
CAS指Compare and Swap , 比较后再交换值。
其中比较的对象有3个，可以用一句话来说，就是 把x的y值替换成z值
其中x是要替换的目标, y是当前值, z是要替换成的值。
CAS可以实现乐观锁，当线程要去修改某个目标时，先做一次CAS，如果满足条件，就操作成功，否则开始自旋直到满足条件，这样线程就不会挂起。
按照上述CAS定义，就会出现如下情况:
线程a需要将当前的1增加到2，而线程b抢先将1改成了3，线程c又将3改回到1，此时线程a进入，发现当前值仍然是1，便觉得满足条件，而实际上真实数据已经绕了一大圈回来了。
对一个线程来说，不同通过现有的3个比较对象判断出是否发生过ABA时，便要引入新的变量来辅助判断，通常来说，会引入一个简单的标志位，例如changed, 来标志是否发生过更改，或者假如版本号，来标识发生修改的次数。

AQS?

见另一篇文章** **https://jarryzhou.space/article/tkq7gc

线程池原理

线程池是一种针对线程的池化技术。线程池提前准备好一些线程，另其能重复使用，以减少线程创建和销毁的开销，并且可以通过参数控制线程占用的资源，自如线程数，等待时间等。
线程池有以下几个核心参数：
核心线程数 - 核心线程的数量，核心线程空闲时不会销毁。
最大线程数 - 线程池最大可容纳线程数
keepAliveTime - 除了核心线程外其它线程空闲时最大存活时间
blockingQueue - 任务等待队列
threadFactory - 线程工厂
rejectedExecutionHandler - 拒绝处理器

线程池有哪几种拒绝策略

线程池有4种拒绝策略

AbortPolicy abortPolicy = new ThreadPoolExecutor.AbortPolicy();
DiscardPolicy discardPolicy = new ThreadPoolExecutor.DiscardPolicy();
DiscardOldestPolicy discardOldestPolicy = new ThreadPoolExecutor.DiscardOldestPolicy();
CallerRunsPolicy callerRunsPolicy = new ThreadPoolExecutor.CallerRunsPolicy();

线程池的线程用完后如何回收

谈谈对synchronized的理解,底层如何实现

sychronized是java中用于线程同步的关键字，可以作用于类，对象，方法，代码块，字段上。被Sychronized修饰的部分表示只允许单个线程进入，它是一种悲观锁。
java堆中的对象内存模型主要分为3个部分:

  - 对象头 - 又主要分为两个部分，Mark Word 标识极端，用于存放对象运行时的一些标记 和 Class Pointer 类型指针，指向对象类型元数据
  - 实例属性数据 - 对象实例的属性数据
  - 对齐填充数据 - 为了对齐到8字节的整数倍而填充的数据

其中对象上的锁的信息，存放在对象头的MarkWord当中,锁有4个级别，从低到高分别为无锁，偏向锁，轻量锁，重量锁。

锁升级的过程

锁升级，指的是JVM对synchronized关键字的优化，另其在不同情况下，使用不同的策略，以达到高效的目的。
锁升级是一个从无锁定到重量锁的不可逆过程。
当遇到synchronized关键字时，线程尝试获取对象锁，走了以下流程：
当对象上没有锁，就直接获取锁，并将线程id设置到对象头中，使之成为偏向锁，偏向此线程，并且不会显式释放，若下次同样线程到来，就没有锁定和释放锁的过程，节约了资源。这样做是因为根据经验，在实际场景中，锁大多数情况下都只被一个线程获得。
此时，若另一个线程到来，遇到偏向锁，若偏向的线程已死，或者当前对象不处于被锁定状态，则对象重置到无锁状态，然后再成为新线程的偏向锁。若偏向的线程还继续持有锁，那么此时自动升级到轻量锁。
轻量级锁就是常见的自旋锁，线程通过CAS，尝试获得对象锁，当超过了自旋限制仍未成功获得锁时，或者又来了新的竞争者，则升级为重量级锁，即将除了获得锁的线程以外的所有线程阻塞，防止cpu浪费。

讲一下volatile?讲讲几个内存屏障，嗅探机制

volatile关键字可修饰字段，它有2个功能，一是防止代码编译时的指令重排，二是强制数据刷入本地内存。
指令重排指的是编译字节码时，在不改变程序输出结果的情况下，对代码顺序进行的优化调整。
强制数据从内存中存取
todo

谈一下JMM

一般来说只聊Hotspot的实现。
按照线程之间的可见行，可以分为线程共享的区域，和线程私有的区域
线程共享的区域有：
堆区 - 这是所有线程共享的内存区域，用来存放所有对象实例
方法区 - 存放加载的类信息，常量
线程私有的区域：
栈 - 栈中又分为本地方法栈，jvm栈，
todo

什么是静态代理和动态代理

动态代理有几种方式？

2种，

1. JDK提供的InvocationHandler接口

实现InvocationHandler接口的invoke方法

2. cglib

实现MethodInterceptor的intercept方法

Spring

讲一下spring的IOC和AOP?

IOC的意思是控制反转，是抽象思想的体现，指在编码中依赖抽象层而不是依赖具体实现，进而降低了代码之间的耦合，增加了灵活性，实现了多态。
AOP
TODO

Spring AOP底层实现

aop通过2种方式来实现

1. 动态代理

spring支持jdk动态代理，即invocationHandler接口，以及cglib两种方式。默认的策略是，如果目标类是接口，用jdk代理，如果是对象，使用cglib, 因为接口好继承接口，而已有对象又不方便去修改它，所以分别采用两种策略应对不同情况。
动态代理做aop就好理解了，代理后在前后做一些事情。

2. 静态织入

Spring中有哪些设计模式

工厂-
代理-
单例 - 这tm也算。。
观察者 -

Spring BeanFactory和FactoryBean的区别
BeanFactory是spring容器核心接口，todo

bean的作用域

singleton - 在一个applicationcontext下的单例
prototype - 原型模式，每次从容器中拿，都是新的
globalsession - 每个全局session中是一个，这个只在portlet应用中的概念，servlet应用中与session没有区别
sesstion - 每个http session 一个
request - 每个http request一个

10.bean对象的生命周期?
11.spring的事务传播机制，通过AOP的整个实现过程?
Spring事务具有数据库事务同样的acid特性，此外Spring定义了在方法调用当中事务是如何传递的，即传播机制。
Spring的事务传播机制一共有以下几种
Required
如果当前有事务，加入当前事务，如果没有新建一个

REQUIRES_NEW
无论如何，新建事务，如果原来有事务，将原有事务挂起，执行完本事务后继续

MANDATORY
在原有事务中执行，如果原来没有事务，抛出异常

NEVER
必须在没有事务的情况下执行，否则抛出异常

NOT_SUPPORTED
不开启事务

SUPPORTS
有就用，没有算了

todo

Spring是如何解决循环依赖问题的

Spring靠内设的三级缓存机制解决循环依赖问题
一级缓存singletonObjects：用于保存实例化、注入、初始化完成的bean实例
二级缓存earlySingletonObjects：用于保存实例化完成的bean实例
三级缓存singletonFactories：用于保存bean创建工厂，以便于后面扩展有机会创建代理对象。
从三级到一级，里面的bean是越来越完善的，而查找bean是从一级找到三级
那么看一个互相依赖的例子

@Service
public class TestService1 {
    @Autowired
    private TestService2 testService2;
}

@Service
public class TestService2 {
    @Autowired
    private TestService1 testService1;
}

SpringBoot自动装配原理

数据库相关

mysql索引结构?怎么优化sql?

mysql采用的是B+tree的索引结构，todo

mysql隔离级别?

在说Mysql事务隔离级别之前，先说一下不同隔离级别下可能出现的问题：
脏读 - 读到了其它事务未提交的数据
不可重复读 - 同事务下，2次读取到的数据不一致
幻读 - 同事务下，第一次读到了数据，再读没有了，反之亦可，就像产生了幻觉

mysql有以下事务隔离级别：
read_uncommited - 未提交读，可以读到其它事务中未提交的数据，此时可能出现脏读，不可重复读，幻读
read_commited - 提交读，提交了才能读到，因此避免了脏读，但是仍可能出现不可重复读和幻读
reapeatable_read - 可重复读，这个是mysql innodb默认的事务隔离级别，避免了脏读，不可重复读，但仍然可能出现幻读
serializable - 串行化，强制事务串行执行，这样就避免了所有问题，但是效率就低了

Mvcc?

MVCC全称Multi-Version Concurrency Control，即多版本并发控制, 是一种并发控制的方法，在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存。
MVCC在MySQL中的实现是为了在有读写冲突的情况下，实现非阻塞并发读，从而提高性能。

在Mysql innodb情况下，有当前读，和快照读的概念。

当前读，指读取最新的数据，并加行级锁防止其它事务的修改，例如select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)

快照读，在串行之前的隔离级别的普通select语句使用的是快照读，它不向记录加锁，因此是非阻塞的，但也因此在并发读情况下可能读到的不是最新记录

mvcc在mysql的具体实现，依赖行记录的3个隐藏字段，undo log ，和Read View
3个隐藏字段：
DB_TRX_ID 最后操作本行记录的事务id
DB_ROLL_PTR 回滚指针，指向上个版本的指针
DB_ROW_ID 隐含的自增ID，row id嘛
undo log:
insert时会产生undo log,用于回滚， 事务提交后丢弃
update/delete时也产生undo log, 也用于回滚，同时用于快照读
todo
13.用过哪些设计模式?
14.自己实现ribbon策略，比如abc三个的权重分别是532你要怎么做，轮询算法怎么实现
15.如果我们不用feign怎么实现通过注解就能调用对应的接口
16.kafka分区的好处，配置等，
17.两个list一个存储id，一个id和name，id相同就把name放入另外一个list，有什么比较高效的方法

18.多线程的拒绝策略和状态有哪些
19.多线程执行任务怎么让他们全部执行完任务后再执行别的任务，自己做怎么实现，多线程中其中一个线程异常如何让所有线程都终止执行
20.springbootapplication中的比较重要的注解有哪些
21.spring.factories中的类加载是怎么实现的
22.refresh主要做了些什么
23.jdk自动支持排序的集合？
25.单向链表做查询效率不高你会怎么优化数据结构
单链表查询要从头开始搜索，时间复杂度O(n).
在数据量大的时候，第一参见HashMap, 将链表转换为红黑树，时间复杂度变为O(logn).
或者做跳跃表

线程池中线程执行完了一个任务接下来是做什么，是等待还是被收回，如果是等待，那么判断的依据是啥，如果是被回收，那么是怎么被回收的。

28.线程池主线程如何捕获线程异常
29.线程池有哪些阻塞队列，他们有哪些优缺点
30.设计一个接口在任一时间轴不允许调用请求超过60次如何设计—-滑动窗口算法
31.用redis命令reset你会怎么设计
32.threadlocal有什么作用，使用会有什么需要注意的地方
33.一个数组，里面存了重复的数据，找到重复最多的；
34.找到一个字符串中最大的对称字符串
35.找到1亿个数据中第5千万大的
36.redis集群/哨兵，区别

分布式/微服务

CAP / BASE理论

分布式事务

分布式缓存

分布式id

1、关于微服务的相关问题 1-2
a、突发的性能问题
b、性能问题
b1、当出现突发的并发时，怎么限流 拒绝服务
nginx / Apache / F5 / Squid 限流
网关限流 spring-gateway spring
算法：
漏桶算法：
限流框架：guava、hystrix、sentinel滑动窗口、
令牌桶算法
突发流量
滑动窗口
redis限流 计算器

2、消息队列相关问题 rabbitmq kafka
a、突发系统断电、正在处理的队列该怎么办
需要消息持久化
正在处理的队列，应该怎么办?
1、有若干条消息正在被处理 需要实现事务，没有事务会出现脏数据
如果有分布式事务 会回滚，如果没有分布式事务 只是回滚当前事务
2、分布式事务的框架
两阶段提交
3、消息并没有被处理
消息队列必须做持久化
4、处理完的消息、处理过程中的消息、没有被处理的消息
获取消息后，先把消息存到数据库、
处理时，表示为处理中
处理完成，标识为处理完成
5、给服务机房配上UBS
7、大并发的消息队列处理
消息队列阻塞
原因：写比度更快、
会造成 消息的丢失
避免消息队列阻塞
读的线程 拿到消息后放到数据库（mysql、redis） ，然后用分布式任务处理
务必要保证读的速度要大于写的速度
b、rabbitmq消息的丢失
断电、网络原因、消息读异常
rabbitmq 消息丢失问题的解决方案？
rabbitmq消费者
autoact 设置为true 自动回复消息
rabbitmq 生产者
发送端 引入事务 确保提交成功
设置持久化
配置集群
d、消息重发消费的问题
幂等 消息的主键的幂等
分布式锁 悲观锁 乐观锁
kafka
kafka的消息会不会丢失？
任何一种消息队列都有可能会发送消息丢失的情况
kafka 通过设计 保证了消息不被丢失
发送消息的方式是send方法，没有callbak 就是发生丢失 如果使用callbak方式 不会被丢失

      cousumer 配置参数 解决消息丢失的问题
         重试没有回复
         重试导致消费者 重复消费的情况

      kafka的吞吐量会大于其他的消息队列
       kafka 的性能高的原因 ： NIO 非阻塞IO
       磁盘顺序写
       kafka 零拷贝
       分区和分段
       批量发送
       数据压缩

3、缓存相关问题 redis
redis缓存 雪崩 击穿 穿透
缓存穿透
key不存在
redis key过期
redis数据加载过程中
解决办法
布隆过滤器
拒绝请求
缓冲等待 互斥锁

     缓存雪崩
        缓存没有热加载 冷启动
        缓存预热 先用工具或脚本把缓存数据跑一遍
        请求排队
    redis使用的时需要注意事项：
       1、内存设置
          数据过大 导致存在了磁盘上而不是内存中
          参数调优
       2、持久化方式
          配置方式
       3、集群应用
           主从模式、哨兵模式、Cluster模式
       4、缓存失效的机制
    高性能的原因
    如何使用redis zookeeper 实现分布式锁
    zookeeper 是如何保证事务的顺序一致性
      全局递增Id
    

4、性能调优
a、秒杀活动 架构设计
1、页面信息静态化（尽量确保不变的信息静态化）
2、图片 、js文件、css文件 地址分别 一级域名化
3、缓存数据
静态文件 缓存到浏览器端 http头中设计
启用CDN
服务端 静态页面缓存
动态内容缓存 redis缓存、本地缓存
活动规则缓存 redis缓存、本地缓存
库存、价格 redis缓存、本地缓存
数据库的缓存 数据库本身的缓存
秒杀 尽量避免让请求访问到数据库
在数据中避免使用事务 尽量不要使用外键、不要让表太分散 ToC的表 尽量不要太分散 使用json大字符串

      4、服务限流

前端f5 / nginx / 网关 /
fallback

      5、服务降级
   b、生产系统 出现性能瓶颈 从哪些方面定位问题
      1、数据库 sql性能、数据量
      2、缓存
         缓存命中率低 击穿 雪崩
      4、服务器 性能 cpu 内存 IO
      5、代码实现方案问题
      6、前端问题
         cdn 页面静态化 页面缓存

中间件

RabbitMQ
Kafka

简单算法

二叉树中序遍历
二叉树前序遍历
二叉树后序遍历
二叉树广度优先遍历
二分查找
冒泡排序
快速排序

微服

突发并发—如何限流/削峰

Donate