5.3问题总结

一、设计模式理解

https://www.cnblogs.com/Kingyk/p/15368574.html
1、单例模式
1.1饿汉模式
一个类只允许创建一个实例（对象），在类加载时候就初始化好
特点：构造私有，静态创建实例，对外提供一个获取示例的方法
优点是：线程安全
缺点是：不支持延迟加载
1.2懒汉模式
特点：给获取实例方法了一把大锁（synchronzed），判断对象是否为空，为空才执行创建实例
优点：支持延迟加载
缺点：不支持高并发
1.3优化，示例判断为null时候才加锁，不给方法加，会引起指令重排
1.4静态内部类
instance 的唯一性、创建过程的线程安全性，都由 JVM 来保证。所以，这种实现方法既保证了线程安全，又能做到延迟加载。
2、原型模式
当要实例化的类是在运行时刻指定时；或者需要创建多个对象
深拷贝和浅拷贝问题
3、工厂模式
3.1、简单工厂
特点：定义一个用于创建对象的接口，让子类决定实例化哪一个类
不同的子类实现接口方法后，返回子类自己的示例对象，适用于：当一个类不知道它所必须创建的对象的类的时候
缺点：工厂模式需要额外创建很多 类，会增加代码的复杂性，
每个 Factory 类只是做简单的 new 操作，功能非常单薄，也没必要设计成独立的类
3.2、工厂方法
特点：工厂的工厂，定义一个静态的map，根据key匹配返回不同的对象
3.3、抽象工厂
定义一个用于创建对象的接口，让子类决定实例化哪一个类，不同于简单工厂的是适用于：一个系统要独立于它的产品的创建、组合时
不同的产品线继承相同的工厂，实现不同的方法，
4、适配器模式
它将不兼容的接口转换为可兼容的接口，让原本由于接口不兼容而不能一起工作的类可以一起工作
5、代理模式
代理模式可以对原有的类进行扩展
5.1静态代理
静态代理需要代理类与目标类有一样的继承父类和实现接口
特点：两个实现了同一个接口的类，一个类对另一个类对象可以做方法执行前后通知。
优点1.可以做到在不修改目标对象的功能前提下,对目标功能扩展.
缺点:
因为代理对象需要与目标对象实现一样的接口,所以会有很多代理类,类太多.同时,一旦接口增加方法,目标对象与代理对象都要维护.
5.2JDK动态代理
特点：动态代理需要使用newProxyInstance(ClassLoader loader方法，
好处：动态代理不用实现目标类的接口，不会出现大量代理类的现象，一般情况下创建一个代理类就可以了。
动态代理对象的生成,是利用JDK的API,动态的在内存中构建代理对象(需要我们指定创建代理对象/目标对象实现的接口的类型)
5.3CGLIB代理
上面的静态代理和动态代理模式都是要求目标对象是实现一个接口的目标对象,但是有时候目标对象只是一个单独的对象,并没有实现任何的接口,这个时候就可以使用以目标对象子类的方式类实现代理,这种方法就叫做:Cglib代理

Cglib包的底层是通过使用一个小而块的字节码处理框架ASM来转换字节码并生成新的类.不鼓励直接使用ASM,因为它要求你必须对JVM内部结构包括class文件的格式和指令集都很熟悉.
6、构造者模式
将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示，使用构造函数配合 set() 方法里面增加逻辑判断，返回不同的结果

一、设计模式六大原则

依赖倒转原则 :针对接口编程,依赖于抽象而不依赖于具体
开闭原则 :对扩展开放,对修改关闭
里氏代换原则 :任何基类可以出现的地方,子类一定可以出现
接口隔离原则 :高内聚低耦合
迪米特法则:最少知道原则 ,一个实体应当尽量少的与其它实体发生相互作用,使得功能模块相互独立
合成复用原则 :尽量使用合成或者聚合的方式,而不是使用继承

二、排序和他的时间复杂度

https://zhuanlan.zhihu.com/p/83756377
什么是排序算法稳定性？
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。

插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
选择排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
冒泡排序
重复走访要排序的序列，两两比较顺序错误就交换，依此类推，直到走完要排序序列，这时最大（最小）数浮动到数列末尾。
快速排序
又称划分交换排序。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
挑选基准值：从数列中挑出一个元素，称为“基准”。
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成。

堆排序
新建堆然后从堆中逐条取出元素。

归并排序
建立在归并操作基础上的一种有效排序方式，采用分治法：比较队列头部的大小然后合并

二、四种常用查找算法

https://blog.csdn.net/AJ_007/article/details/106109437
线性查找：
数组遍历的工程，找到了就返回下标，没有就返回-1，有序无序
二分查找：
一半一半的向要查找的值趋近，就想猜数游戏，大了，那你就猜比你小一半的数，适用于有序数组
插值查找：
适用于有序数组
斐波那契出擦找：
适用于有序数组：

三、char和varchar的区别

1、char定长，不足的部分用空格补齐
varchar变长，

1. char类型的长度是固定的，varchar的长度是可变的。

char类型时定长的类型，即当定义的是char(10)，输入的是"abc"这三个字符时，它们占的空间一样是10个字节，包括7个空字节。当输入的字符长度超过指定的数时，char会截取超出的字符。而且，当存储char值时，MySQL是自动删除输入字符串末尾的空格。

char是适合存储很短的、一般固定长度的字符串。例如，char非常适合存储密码的MD5值，因为这是一个定长的值。对于非常短的列，char比varchar在存储空间上也更有效率。

varchar(n)类型用于存储可变长的，长度为n个字节的可变长度且非Unicode的字符数据。存储大小为输入数据的字节的实际长度+1/2. 比如varchar(10), 然后输入abc三个字符，那么实际存储大小为3个字节。除此之外，varchar还需要使用1或2个额外字节记录字符串的长度，如果列的最大长度小于等于255字节（是定义的最长长度，不是实际长度），则使用1个字节表示长度，否则使用2个字节来表示。

二：效率不同
1、char类型：char类型每次修改的数据长度相同，效率更高。
2、varchar类型：varchar类型每次修改的数据长度不同，效率更低。
三、存储不同
1、char类型：char类型存储的时候是初始预计字符串再加上一个记录字符串长度的字节，占用空间较大。
2、varchar类型：varchar类型存储的时候是实际字符串再加上一个记录字符串长度的字节，占用空间较小。

四、MYSQL组合索引在B+树数据结构中是如何排序的 五、MySQL查询执⾏过程详解 六、equals与==的区别

https://blog.csdn.net/qq_32521381/article/details/106188209
一、对象类型不同

1、equals()：是超类Object中的方法。
2、==：是操作符。
二、比较的对象不同

1、equals()：equals是Object中的方法，在Object中equals方法实际"ruturn (thisobj)“,用到的还是”“,说明如果对象不重写equals方法，实际该对象的equals和”“作用是一样的，都是比较的地址值（因为”"比较的就是地址值），但是大部分类都会重写父类的equals方法，用来检测两个对象是否相等，即两个对象的内容是否相等，例如String就重写了equals方法，用来比较两个字符串内容是否相同。

2、：用于比较引用和比较基本数据类型时具有不同的功能,比较引用数据类型时，如果该对象没有重写equals方法，则比较的是地址值，如果重写了，就按重写的规则来比较两个对象；基本数据类型只能用""比较两个值是否相同，不能用equals（因为基本数据类型不是类，不存在方法）。
三、运行速度不同
1、equals()：没有运行速度快。
2、：运行速度比equals()快，因为==只是比较引用。

七、函数式编程

https://blog.csdn.net/w584212179/article/details/112802273
函数式编程更加强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。
体现在lambda表达式和stream流

八、可以重写static方法吗

1,可以被继承，但是不能被重写，如果父子类静态方法名相同，则会隐藏derive类方法（调用base类的方法）

2.静态方法是编译时绑定的，方法重写是运行时绑定的。
静态方法是类在加载时就被加载到内存中的方法，在整个运行过程中保持不变，因而不能重写。但非静态方法是在对象实例化时才单独申请内存空间，为每一个实例分配独立的运行内存，因而可以重写。

所谓静态就是在运行时，虚拟机已经认定此方法属于哪个类。
JAVA静态方法形式上可以重写，但从本质上来说不是JAVA的重写。因为静态方法只与类相关，不与具体实现相关，声明的是什么类，则引用相应类的静态方法

九、 MVCC原理

一、什么是MVCC
https://blog.csdn.net/Shmily_0/article/details/118389631
多版本控制: 指的是一种提高并发的技术。引入多版本之后，只有写写之间相互阻塞，其他三种操作都可以并行，这样大幅度提高了InnoDB的并发度。
MVCC只在已提交读（Read Committed）和可重复读（Repeatable Read）两个隔离级别下工作，其他两个隔离级别和MVCC是不兼容的。
MVCC的实现原理主要是依赖每一行记录中两个隐藏字段，undo log，ReadView

二、MVcc能解决什么问题，带来真么好处
多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前的数据库的快照。 所以MVCC可以为数据库解决以下问题：

在并发读写数据库时，可以做到在读操作时不用阻塞写操作，写操作也不用阻塞读操作，提高了数据库并发读写的性能。
同时还可以解决脏读，幻读，不可重复读等事务隔离问题，但不能解决更新丢失问题。

三、MVCC的实现原理主要是依赖记录中的 3个隐式字段，undo日志(或者说日志中的版本链) ，ReadView 来实现的。

1.隐式字段
每行记录除了我们自定义的字段外，还有数据库隐式定义的DB_TRX_ID,DB_ROLL_PTR,DB_ROW_ID等字段。

DB_TRX_ID
6byte，最近修改(修改/插入)事务ID：记录创建这条记录/最后一次修改该记录的事务ID。
DB_ROLL_PTR
7byte，回滚指针，指向这条记录的上一个版本（存储于rollback segment里）
DB_ROW_ID
6byte，隐含的自增ID（隐藏主键），如果数据表没有主键，InnoDB会自动以DB_ROW_ID产生一个聚簇索引。
实际还有一个删除flag隐藏字段, 为true时并不代表真的删除，而是删除flag变了（逻辑删除）

不同事务或者相同事务的对同一记录的修改，会导致该记录的undo log成为一条记录版本线性表，既链表，undo log的链首就是最新的旧记录，链尾就是最早的旧记录

Read View遵循一个可见性算法，主要是将要被修改的数据的最新记录中的DB_TRX_ID取出来，与系统当前其他活跃事务的ID去对比（由Read View维护），如果DB_TRX_ID跟Read View的属性做了某些比较，不符合可见性，那就通过DB_ROLL_PTR回滚指针去取出Undo Log中的DB_TRX_ID再比较，即遍历链表的DB_TRX_ID（从链首到链尾，即从最近的一次修改查起），直到找到满足特定条件的DB_TRX_ID, 那么这个DB_TRX_ID所在的旧记录就是当前事务能看见的最新老版本。

四、MVCC能否解决了幻读问题呢
MVCC能解决不可重复读问题,但是不能解决幻读问题，不论是快照读和当前读都不能解决。RR级别解决幻读靠的是锁机制,而不是MVCC机制。

十、Java1.7和1.8的区别

区别：jdk1.8中取消了永久代，取而代之的是Metaspace，这个空间不占用jvm虚拟机的内存，而是占用物理机的内存；jdk8新增了lambda表达式、访问局部变量、函数式接口等特性。

4、方法与构造函数引用，jdk1.8提供了另外一种调用方式::，当 你 需 要使用 方 法 引用时 ， 目 标引用 放 在 分隔符::前 ，方法 的 名 称放在 后 面

1、default关键字，在接口中可以通过使用default关键字编写方法体，实现类可以不用实现该方法，可以进行直接调用

十、hashcode相等的两个对象一定==相等么？

两个对象==相等，则其hashcode一定相等，反之不一定成立。

两个对象equals相等，则其hashcode一定相等，反之不一定成立。【和上一条等价，因为Object的equals实现用的就是 对象的==相等来判断】

十一、重写equals不重写hashCode会存在什么问题

每个覆盖了equals方法的类中，必须覆盖hashCode。如果不这么做，就违背了hashCode的通用约定，也就是上面注释中所说的。如果重写equals不重写hashCode它与散列集合HashMap、HashSet、HashTable、ConcurrentHashMap）无法正常工作。

例如：hashmap它是通过计算Map key的hashCode值来确定在链表中的存储位置的（确定唯一性）。那么这样就可以推测出，如果我们重写了equals但是没重写hashCode，那么可能存在元素重复的矛盾情况。

十二、如何让10个线程按照顺序打印0123456789

https://blog.csdn.net/qq_35571554/article/details/82743952
设定一个orderNum，每个线程执行结束之后，更新orderNum，指明下一个要执行的线程。并且唤醒所有的等待线程。

在每一个线程的开始，要while判断orderNum是否等于自己的要求值！！不是，则wait，是则执行本线程。
@Override
public void run() {
// TODO Auto-generated method stub
//1、判断该资源是否被占用
synchronized(lobject){
//2、如果资源空闲，则判断是否已经打印完成
while(lobject.orderNum <= lobject.MaxValue){
//3、没有打印完则判断是否是自己需要打印的数字
if(lobject.orderNum == printNum){
System.out.print(printNum);
lobject.orderNum++;
if(lobject.orderNum==10){
System.out.println(“线程打印完毕”);
}
//打印完毕后，唤醒所有的线程
lobject.notifyAll();
}else{
//4、不是该线程打印的数字，则继续等待
try {
lobject.wait()；
}

十三、进程间通信的方式有哪些

https://www.php.cn/faq/469981.html
1、管道通常指无名管道，
半双工即数据只能在一个方向上流动,
它只能用于具有亲缘关系的进程之间的通信
不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
2、FIFO，是一种文件类型；
FIFO可以在无关的进程之间交换数据，与无名管道不同。
FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
3、消息队列，是消息的链接表，存放在内核中；
消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取
4、信号量，是一个计数器；
信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
支持信号量组。
5、共享内存。
指两个或多个进程共享一个给定的存储区

十四、怎么保证线程安全？

https://zhuanlan.zhihu.com/p/504400777
导致线程不安全的原因，主要有三点：

原子性：一个或者多个操作在CPU执行的过程中被中断
可见性：一个线程对共享变量的修改，另外一个线程不能立刻看到
有序性：程序执行的顺序没有按照代码的先后顺序执行。ava平台的两种编译器：静态编译器（javac）和动态编译器（jit:just in time）。
区别在于：
静态编译器是将.java文件编译成.class文件，之后便可以解释执行。
动态编译器是将.class文件编译成机器码，之后再由jvm运行。有时候，动态编译器为了程序的整体性能会对指令进行重排序，虽然重排序可以提升程序的性能，但是重排序之后会导致源代码中指定的内存访问顺序与实际的执行顺序不一样，就会出现线程不安全的问题。

下面简单谈谈针对以上的三个问题，java程序如何保证线程安全呢？
针对原子性问题：
JDK里面提供了很多atomic类，比如AtomicInteger、AtomicLong、AtomicBoolean等等：这些类本身可以通过CAS来保证操作的原子性，另外Java也提供了各种锁机制，来保证锁内的代码块在同一时刻只能有一个线程执行，比如使用synchronized加锁，这样，就能够保证一个线程在对资源进行读、改、写操作时，其他线程不可对此资源进行操作，：从而保证了线程的安全性。

针对可见性问题：：同样可以通过synchronized关键字加锁来解决。与此同时，java还提供了volatile关键字，要优于synchronized的性能，同样可以保证修改对其他线程的可见性。volatile一般用于对变量的写操作不依赖于当前值的场景中，比如状态标记量等。

针对重排序问题：可以通过synchronized关键字定义同步代码块或者同步方法保障有序性，另外也可以通过Lock接口来保障有序性。

以上就是保证线程安全的方案！

十五、hashMap jdk1.7和jdk1.8的不同

整体结构和 JDK1.8 中的 HashMap 类似，相比 JDK1.7 中的 ConcurrentHashMap， 它抛弃了原有的 Segment 分段锁实现，采用了 CAS + synchronized 来保证并发的安全性。JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量，和 JDK1.7 一样，使用volatile关键字，保证多线程操作时，变量的可见行！

虽然 HashMap 在多线程环境下操作不安全，但是在 java.util.concurrent 包下，java 为我们提供了 ConcurrentHashMap 类，保证在多线程下 HashMap 操作安全！

在 JDK1.7 中，ConcurrentHashMap 采用了分段锁策略，将一个 HashMap 切割成 Segment 数组，其中 Segment 可以看成一个 HashMap， 不同点是 Segment 继承自 ReentrantLock，在操作的时候给 Segment 赋予了一个对象锁，从而保证多线程环境下并发操作安全。

但是 JDK1.7 中，HashMap 容易因为冲突链表过长，造成查询效率低，所以在 JDK1.8 中，HashMap 引入了红黑树特性，当冲突链表长度大于 8 时，会将链表转化成红黑二叉树结构。

在 JDK1.8 中，与此对应的 ConcurrentHashMap 也是采用了与 HashMap 类似的存储结构，但是 JDK1.8 中 ConcurrentHashMap 并没有采用分段锁的策略，而是在元素的节点上采用 CAS + synchronized 操作来保证并发的安全性，源码的实现比 JDK1.7 要复杂的多。、

十六、HashMap的底层结构和实现原理 十六、为什么扩容因子是0.75

泊松分布有关。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。

十六、HashMap解决hash冲突

https://blog.csdn.net/weixin_26804345/article/details/113076248
当我们通过put(key, value)向hashmap中添加元素时，需要通过散列函数确定元素究竟应该放置在数组中的哪个位置，当不同的元素被放置在了数据的同一个位置时，后放入的元素会以链表的形式，插在前一个元素的尾部，这个时候我们称发生了hash冲突。

开放寻址法（开放定址法根据步长不同可以分为3种）
我们就重新探测一个空闲位置，再将元素插入。
线性探查法，平方探测法，伪随机探测法
缺点：
当冲突多的时候数据容易堆集在一起，这时候对查找不友好
删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不能真正删除结点；

但我们往散列表中插入元素时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，那么我们就从当前位置开始，依次往后遍历，直到找到空余的位置插入为止（插入第一个空余的位置，方便查找）
2. 再哈希法
，用于同义词发生地址冲突时，计算出另一个哈希函数地址，直到不发生冲突位置。这种方法不容易产生堆集，但是会增加计算时间。
所以再哈希法的缺点是：
增加了计算时间。

3. 建立一个公共溢出区
   ，一旦发生冲突，不管他们哈希函数得到的哈希地址是什么，都填入溢出表。
   但这个方法的缺点在于：
   查找冲突数据的时候，需要遍历溢出表才能得到数据。

4. 链地址法(拉链法)
   将冲突位置的元素构造成链表。在添加数据的时候，如果哈希地址与哈希表上的元素冲突，就放在这个位置的链表上。
   拉链法的优点：
   处理冲突的方式简单，且无堆集现象，非同义词绝不会发生冲突，因此平均查找长度较短；
   由于拉链法中各链表上的结点空间是动态申请的，所以它更适合造表前无法确定表长的情况；
   删除结点操作易于实现，只要简单地删除链表上的相应的结点即可。

十七、如何访问一个类的private方法

利用java反射机制得到类的属性和方法
Test test=new Test();
test.getclass.getfields();
test.getclass.getMothods();
够强制调用，但是并不推荐，因为它与面向对象的设计规则背道而驰。违背了我们当初的设计初衷。

十八、四个访问修饰符的区别

public：被public修饰的成员变量或者成员方法，可以直接被类的调用者使用

private：被private修饰的成员变量或者成员方法，不能被类的调用者使用

protected：对于类的子类和同一个包的其他类来说，protected修饰的字段和方法是可以访问的，对于类的调用者来说，protected修饰的字段和方法是不能访问的

无（default）：同一个包内可以访问，包外不能访问

十九、java的基本数据类型，byte的最大最小值

数值型 byte 1字节 、short 2字节、 int 4个字节、 long 8个字节

布尔型 boolean （无字节，在内存中以byte数组类型存储，1个字节，8位）

字符型 float 4个字节、 double 8 个字节
byte范围：-128 到 127

基本数据类型转换 byte short char int long float double
隐式转换 小精度–>大精度 int->double
显式转换（强制转换） 大精度 – > 小精度 double->int 会出现精度丢失， 丢失原因： 小精度的数据类型没有能够容 纳大精度的位数，只能截取其大精度的最 后的位数。

十九、Java中final、finally和finalize的区别

https://blog.csdn.net/cyl101816/article/details/67640843/
1、final修饰符（关键字）。
被final修饰的类，不能作为父类而被子类继承。因此一个类不能既被abstract声明，又被final声明。
将变量或方法声明为final，可以保证他们在使用的过程中不被修改。被声明为final的变量必须在声明时给出变量的初始值，而在以后的引用中只能读取。
被final声明的方法也同样只能使用，即不能方法重写。

、finally是在异常处理时提供finally块来执行任何清除操作。不管有没有异常被抛出、捕获，finally块都会被执行。try块中的内容是在无异常时执行到结束。catch块中的内容，是在try块内容发生catch所声明的异常时，跳转到catch块中执行。finally块则是无论异常是否发生，都会执行finally块的内容，所以在代码逻辑中有需要无论发生什么都必须执行的代码，就可以放在finally块中。

3、finalize是方法名。java技术允许使用finalize（）方法在垃圾收集器将对象从内存中清除出去之前做必要的清理工作。这个方法是由垃圾收集器在确定这个对象没有被引用时对这个对象调用的。它是在object类中定义的，因此所有的类都继承了它。子类覆盖finalize（）方法以整理系统资源或者被执行其他清理工作。finalize（）方法是在垃圾收集器删除对象之前对这个对象调用的。

二十、Spring Boot有哪些常用注解？

https://www.cnblogs.com/October-28/p/15655723.html
@SpringBootApplication、@Repository、@Service、@RestController、@ResponseBody、@Component、@ComponentScan等等。

二一、mysql b+树的查找算法

树可以进行两种查找运算：一种是利用 sqt 链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。

在 B+树中，所有非叶子节点都相当于是叶子节点的索引，而所有的关键字都存放在叶子节点中，所有在从根节点出发做查找操作时，如果非叶子节点上的关键字恰好等于给定值，此时并不算查找完成，而是要继续向下直到叶子节点。

B+树的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。

二二、堆排序原理

一个完全二叉树，其特点在于：

从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层2个元素，第二层4个，第三层8个，以此类推。
而最后一行的元素，都要紧贴在左边，换句话说，每一行的元素都从最左边开始安放，两个元素之间不能有空闲，具备了这两个特点的树，就是一棵完全二叉树。
那么，完全二叉树与堆有什么关系呢？

我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

二三、Java注解究竟是如何起作用的及注解的基本概念

注解实际上就是一个标签
它的定义方式是@interface
注解实际上就是使用反射实现的

当我们注明一个注解的时候，只是制造出了一个标签
当我们给一个类加上注解的时候，就是给这个对象贴上了某个标签
然后实现一个方法：通过反射得到一个对象，然后判断对象上是否有此注解，如果有再进行相应的操作，通过反射我们可以得到这个对象的所有信息，所以想要进行什么操作也是可以的。
元注解基本概念：
元注解是负责对其它注解进行说明的注解，自定义注解时可以使用元注解。Java 5 定义了 4 个注解，分别是 @Documented、@Target、@Retention 和 @Inherited。Java 8 又增加了 @Repeatable 和 @Native 两个注解。
@Documented 注解修饰的注解类会被 Javadoc 工具提取成文档
@Target 注解用来指定一个注解的使用范围，
@Retention 用于描述注解的生命周期，
@Inherited 是一个标记注解，用来指定该注解可以被继承

二四、SQL查询时的join与where筛选比较

https://blog.csdn.net/cillent_boy/article/details/84314114

on是查询后在连接，where是连接后在查询
在使用left jion时，on和where条件的区别如下：

1、 on条件是在生成临时表时使用的条件，它不管on中的条件是否为真，都会返回左边表中的记录。

2、where条件是在临时表生成好后，再对临时表进行过滤的条件。这时已经没有left join的含义（必须返回左边表的记录）了，条件不为真的就全部过滤掉。

ON与where的使用一定要注意场所：

（1）：ON后面的筛选条件主要是针对的是关联表【而对于主表刷选条件不适用】。

（2）：对于主表的筛选条件应放在where后面，不应该放在ON后面。

（3）：对于关联表我们要区分对待。如果是要条件查询后才连接应该把查询件放置于ON后。

            如果是想在连接完毕后才筛选就应把条件放置于where后面。

（4）： 对于关联表我们其实可以先做子查询再做join

二五、ReentrantLock原理分析
https://blog.csdn.net/qq_43049310/article/details/121038549
表示重入锁，它是唯一一个实现了 Lock 接口的类。重入锁指的是线程在获得锁之后，再次获取该锁不需要阻塞，而直接关联一次计数器增加重入次数
ReentrantLock主要利用CAS+AQS队列来实现。它支持公平锁和非公平锁

AQS 是什么
在 Lock 中，用到了一个同步队列 AQS
AQS 的两种功能
从使用层面来说，AQS 的功能分为两种：独占和共享
独占锁，每次只能有一个线程持有锁，比如前面给大家演示的 ReentrantLock 就是以独占方式实现的互斥锁
共 享 锁 ， 允 许 多 个 线 程 同 时 获 取 锁 ， 并 发 访 问 共 享 资 源 ， 比 如ReentrantReadWriteLock

AQS 的内部实现
AQS 队列内部维护的是一个 FIFO 的双向链表，这种结构的特点是每个数据结构都有两个指针，分别指向直接的后继节点和直接前驱节点。所以双向链表可以从任意一个节点开始很方便的访问前驱和后继。每个 Node 其实是由线程封装，当线程争抢锁失败后会封装成 Node 加入到 ASQ 队列中去；当获取锁的线程释放锁以后，会从队列中唤醒一个阻塞的节点(线程)。
CAS 的实现原理
通过 cas 乐观锁的方式来做比较并替换，这段代码的意思是，如果当前内存中的state 的值和预期值 expect 相等，则替换为 update。更新成功返回 true，否则返回 false.
这个操作是原子的，不会出现线程安全问题，这里面涉及到Unsafe这个类的操作，以及涉及到 state 这个属性的意义。state 是 AQS 中的一个属性，它在不同的实现中所表达的含义不一样，对于重入锁的实现来说，表示一个同步状态。它有两个含义的表示
CAS
当 state=0 时，表示无锁状态
当 state>0 时，表示已经有线程获得了锁，也就是 state=1，但是因为
ReentrantLock 允许重入，所以同一个线程多次获得同步锁的时候，state 会递增，比如重入 5 次，那么 state=5。而在释放锁的时候，同样需要释放 5 次直到 state=0其他线程才有资格获得锁

CAS：Compare and Swap，比较并交换。CAS有3个操作数：内存值V、预期值A、要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。该操作是一个原子操作，被广泛的应用在Java的底层实现中。在Java中，CAS主要是由sun.misc.Unsafe这个类通过JNI调用CPU底层指令实现

Unsafe 类
Unsafe 类是在 sun.misc 包下，不属于 Java 标准。但是很多 Java 的基础类库，包括一些被广泛使用的高性能开发库都是基于 Unsafe 类开发的，比如 Netty、Hadoop、Kafka 等；

Unsafe 可认为是 Java 中留下的后门，提供了一些低层次操作，如直接内存访问、线程的挂起和恢复、CAS、线程同步、内存屏障而 CAS 就是 Unsafe 类中提供的一个原子操作，第一个参数为需要改变的对象，第二个为偏移量(即之前求出来的 headOffset 的值)，第三个参数为期待的值，第四个为更新后的值整个方法的作用是如果当前时刻的值等于预期值 var4 相等，则更新为新的期望值 var5，如果更新成功，则返回 true，否则返回 false；

ReentrantLock的基本实现可以概括为：先通过CAS尝试获取锁。如果此时已经有线程占据了锁，那就加入AQS队列并且被挂起。当锁被释放之后，排在CLH队列队首的线程会被唤醒，然后CAS再次尝试获取锁。在这个时候，如果：

非公平锁：如果同时还有另一个线程进来尝试获取，那么有可能会让这个线程抢先获取；

公平锁：如果同时还有另一个线程进来尝试获取，当它发现自己不是在队首的话，就会排到队尾，由队首的线程获取到锁。

二五、Spring IoC和AOP的实现原理解析
https://cloud.tencent.com/developer/article/1846138
https://baijiahao.baidu.com/s?id=1713404380069820518&wfr=spider&for=pc

控制反转（IoC），即上层控制下层，而不是下层控制着上层。我们用依赖注入（Dependency Injection）这种方式来实现控制反转。所谓依赖注入，就是把底层类作为参数传入上层类，实现上层类对下层类的“控制”。
IOC容器的是通过：工厂 + 反射，实现的。
通过一张图来给大家讲解SpirngIOC的实现原理（基于XML配置文件）

spring IOC相关的类：
BeanDefinition:容器中每一个bean都有一个相对应的BeanDefinition实例，该实例负责保存bean对象的所有必要信息，包括bean对象的class类型、是否是抽象类、构造方法和参数、其它属性等等。当客户端向容器请求相应对象时，容器就会通过这些信息为客户端返回一个完整可用的bean实例。
BeanDefinitionRegistry:抽象出bean的注册逻辑，bean对象对应的 BeanDefinition实例会在BeanDefinitionRegistry中进行注册。
BeanFactory：抽象出了bean的管理逻辑，而各个BeanFactory的实现类就具体承担了bean的注册以及管理工作

（1）IOC之容器启动阶段 这个阶段主要会进行：加载配置文件并解析，然后将解析后的数据封装为BeanDefinition实例，最后把这些保存了bean定义的BeanDefinition，注册到相应的BeanDefinitionRegistry，这样容器的启动工作就完成了。当然这个过程还包含了其他很多操作。 （2）IOC之容器实例化阶段 当某个请求通过容器的getBean方法请求某个对象，或者因为依赖关系容器需要隐式的调用getBean时，就会触发第二阶段的活动：容器会首先检查所请求的对象之前是否已经实例化完成。如果没有，则会根据注册的BeanDefinition所提供的信息实例化被请求对象，并为其注入依赖。当该对象装配完毕后，容器会立即将其返回给请求方法使用。

3.Spring AOP底层原理
　　Spring AOP全称为Spring Aspect-Oriented Programming，即面向切面编程，是运行时织入的，那么运行时织入到底是怎么实现的呢？答案就是代理对象。代理对象又可以分为静态代理和动态代理。
　　动态代理：在程序运行时，运用反射机制动态创建而成。
　　生成的代理类的所有方法都拦截了目标类的所有的方法。而拦截器中invoke方法的内容正好就是代理类的各个方法的组成体；

利用JDK代理方式必须有接口的存在。

3.2.2 CGLib代理模式
　　CGLib采用非常底层的字节码技术，可以为一个类创建子类，并在子类中采用方法去技术拦截所有的父类方法的调用，并顺势织入横切逻辑。

CGLib和JDK的原理类似，也是通过方法去反射调用目标对象的方法。

二五、springboot启动原理

https://baijiahao.baidu.com/s?id=1711888823130753987&wfr=spider&for=pc
SpringBoot整个启动流程分为两个步骤：初始化一个SpringApplication对象、执行该对象的run方法。

1、初始化流程中最重要的就是通过SpringFactoriesLoader找到spring.factories文件中配置的ApplicationContextInitializer和ApplicationListener两个接口的实现类名称，以便后期构造相应的实例，ApplicationContextInitializer的主要目的是在ConfigurableApplicationContext做refresh之前，对ConfigurableApplicationContext实例做进一步的设置或处理。
ApplicationListener的目的就没什么好说的了，它是Spring框架对Java事件监听机制的一种框架实现。

Spring Boot应用的整个启动流程都封装在SpringApplication.run方法中，本质上其实就是在spring的基础之上做了封装，做了大量的扩张。
//1.通过SpringFactoriesLoader查找并加载所有的SpringApplicationRunListeners，通过调用
//starting()方法通知所有的SpringApplicationRunListeners：应用开始启动了

//2.创建并配置当前应用将要使用的Environment（用于描述应用程序当前的运行环境）
//3.打印banner
//4.根据是否是web项目，来创建不同的ApplicationContext容器
//5.创建一系列FailureAnalyzer（分析故障并提供相关诊断信息）
//6.初始化ApplicationContext
//7.调用ApplicationContext的refresh()方法,刷新容器
//8.查找当前context中是否注册有CommandLineRunner和ApplicationRunner，如果有则遍历执行它们。
二六、spring的扩展机制

二七、spring的监听机制

二八、ConcurrentHashMap和Hashtable的区别（线程安全和并发性性）

https://blog.csdn.net/love_somnus_/article/details/63686037
Hashtable和ConcurrentHashMap有什么分别呢？它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

二九、LinkedList和ArrayList在尾部插入数据效率对比

https://blog.csdn.net/qq_28817739/article/details/87740998
因为每次都是在尾部插入数据，而LinkedLiist里面有一个last指针一直指向最后一个元素，而ArrayList则根据索引来找到最后一个元素，那么，这两个方式中，效率应该是差不多的；

但是实验结果却不是这样的；
原来 LinkedList每次增加的时候，会new 一个Node对象来存新增加的元素，所以当数据量小的时候，这个时间并不明显，而ArrayList需要扩容，所以LinkedList的效率就会比较高，其中如果ArrayList出现不需要扩容的时候，那么ArrayList的效率应该是比LinkedList高的，当数据量很大的时候，new对象的时间大于扩容的时间，那么就会出现ArrayList’的效率比Linkedlist高了。

三十、一致性哈希算法

https://www.zsythink.net/archives/1182
其实，一致性哈希算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性哈希算法是对2^32取模

一致性哈希算法的优点，如果使用之前的hash算法，服务器数量发生改变时，所有服务器的所有缓存在同一时间失效了，而使用一致性哈希算法时，服务器的数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存会失效，前端的缓存仍然能分担整个系统的压力，而不至于所有压力都在同一时间集中到后端服务器上。

产生的问题：hash环的偏斜
“虚拟节点”是”实际节点”（实际的物理服务器）在hash环上的复制品,一个实际节点可以对应多个虚拟节点。以便减小hash环偏斜所带来的影响，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大。

三二、Java中的String类能否被继承?为什么?以及final和static的区
不能被继承，因为String类有final修饰符，而final修饰的类是不能被继承的。

Static修饰的成员属性和成员方法是和类相关的，没有Static修饰的成员方法和属性是和对象相关的。
Static修饰的成员变量属于全局变量，所有对象共享这个成员变量。(用类名调用)
Static修饰的成员方法内部只能用Static修饰的变量和方法。
Static修饰的代码块，是在类加载时使用。因为虚拟机对类只加载一次，在构造方法之前执行。

3.什么时候变量声明为实例的，什么时候声明为静态的？
如果这个类型的所有对象的某个属性值都是一样的，不建议定义为实例变量，浪费内存空间。
建议定义为类级别特征，定义为静态变量，在方法区中只保留一份，节省内存开销。

一个对象一份的是实例变量。
所有对象一份的是静态变量。
静态变量在类加载时初始化，不需要new对象，静态变量的空间就开出来了。
静态变量存储在方法区。

三一、MySQL查询执⾏过程详解一、执行一个查询过程概述

2服务器先检查查询缓存，如果命中了缓存，则立即返回存储在缓存中的结果。否则进入下一阶段;
3.服务器端进行SQL解析、预处理，再由优化器生成对应的执行计划;
4.MySQL根据优化器生成的执行计划，调用存储引擎的API来执行查询;
5.将结果返回给客户端;

三一、sql

–用一条SQL语句查询出每门课都大于80分的学生姓名
select distinct name from aa where name not in (select distinct name from aa where fengshu<=80)

，查找所有课程成绩90分以上的学生姓名。
select name from student group by name having min(score) >= 90

，查找平均成绩大于等于成绩90分以上的学号和平均成绩。
select sid，agv（score） from student group by sid having agv(score) >= 90

查询平均分大于80的学生名单：
1 select name from (
2 select count() t, sum(score) num, name from grade group by name
3 ) as a where a.num>80t;

https://blog.csdn.net/weixin_36210213/article/details/113515662
下面我们就来实现三个表的联合查询，查询出文件的所有信息的所有信息：

select * from wenjian,admin_group,sort where wenjian.group_id=admin_group_id and admin_group.sort_id=sort.sort_id order by wenjian.wenjian_id DESC;(这里我们把文件表作为主表来查询)

如果我们只是想要文件表中的所有信息，其他两个表中的部分信息，那么我们可以把sql与剧中的 * 替换为wenjian.*,admin_group.group_name,sort.sort_name

如果要实现两个表的联合查询，我们就要用到left join on了，这次我们要查询文件表里面的所有信息与分类表的分类名，查询语句如下：

select w.*,sort.sort_name from wenjian as w left join sort as s on w.sort_id=s.sort_id order by w.wenjian_id dese

MySQL查询每个部门的员工个数
问题：查询每个部门的员工个数

注意！某些部门可能是没有员工的(员工个数为0)。（事实上是department_id在120之后的那些部门）
这时候如果简单利用连接查询并分组，将会使得员工个数为0的部门不会被查询出来。

SELECt e.department_id,COUNT(*)
FROM employees e
JOIN departments d ON e.department_id = d.department_id
GROUP BY e.department_id;