客户端面试

  • 100级台阶,每次上一步或两步,有多少种走法。

573147844013817084101
21

  • 如果200级,你估计有多少种走法(不用编程)。

453973694165307953197296969697410619233826
42

不用编程,估算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.math.BigInteger;
public class Main {

public static void main(String[] args) {
int n = 200;
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
BigInteger res = BigInteger.ZERO;
for (int i = 2; i <= n; i++) {
res = a.add(b);
a = b;
b = res;
}
System.out.println(res);
System.out.println(res.toString().length());

}
}
  • 给出一个数组,找出两个数[a,b]和为n,不存在则返回[-1,-1]。写出两种解法,不能暴力穷举。

  • 讲讲面向过程、面向对象、面向切面。

  • 指针和数组的关系和区别。

  • 讲讲Android handler。

  • 队列和栈的区别和用途。

  • 两个栈实现队列。

  • 输入Url到浏览器显示过程。

  • http请求方法。

  • get和post区别。

  • surficeView和view的区别。

  • app从点击图标开始的启动全过程。

  • 什么是线程安全。

  • 线程安全有哪些机制。

  • 如何保证 int加加(加号打不出来)线程安全。

  • Android线程间通信有哪些机制。

  • cpu调度方式有哪些。

  • 空间局部性和时间局部性。

  • 数据库乐观锁和悲观锁。

  • 数据库索引作用,优缺点。

  • TCP拥塞控制。

  • https加密传输过程。

  • java内存模型。

  • java垃圾回收算法有哪些。

  • 讲讲标记清除算法。

  • java四中引用。

面试笔记

牛客许愿的小米一面,贡献面经

1
许愿能挺进二面,加油,向着目标冲呀~~~~

——java集合相关

object类中的hashCode()方法是做什么的,以及其中的hash()方法是做什么的, 为什么有hash()方法还有hashCode()

hashmap的put过程 主要就是根据自己看过的源码说一下流程
ArrayList LinkList的特点

——多线程相关

synchronized

reettrantLock 除了可重入还有什么关键特性

threadLocal threadLocal 会造成什么问题 为什么会造成内存泄漏

单例模式 synchronized实现懒汉模式 答 内部类 为什么用内部类是线程安全的?

——数据库相关

添加索引的时候要注意什么

索引优化以及在使用索引的时候要注意什么

redis的键的淘汰策略,会达成了redis缓存的淘汰策略

——网络相关

tcp四次握手,最后的状态是什么,回答等待2MSL

为什么要等着2MSL,等待多了会造成什么

http请求的报文结构,keep-alive是用来做什么的

——spring spingboot

spring中对象增强如何实现 回答没听过这个概念,然后被引导回到IOC和AOP,以及AOP是什么,实现过程

——口述算法思路

给一个栈的数据结构,实现另外一个数据结构,要求保留栈的特性,同时能够提供去最大值和最小值的方法,时间复杂度为O(1)

之前一直没明白是要做什么,后来想到做过类似的题。幸好只是说思路,没有要手写,那个时候已经被前面几个回答的不太好的问题难的很紧张,说做个简单的算法题的时候,我的心紧紧一颤,心想,你确定会简单,还好,还好,结果下来没那么难

——网络编程

哪几种IO类型

还有一个问题 有点忘了,这一块在简历上写了,不过掌握的不是很好

——JVM

类加载机制——回答了一下双亲委派模型相关的内容

——有什么想问我的

面试官蛮年轻,真的很好,一直在引导我回答问题,不会的也没有揪着不放很喜欢说,我们接下来问一个简单的问题,哈哈哈,简单简单着就变得不简单了

是自己比较满意的一次面试

既展示了自己所掌握的知识,也暴露了掌握知识中的问题,给自己后面的复习有了一定的指引

感谢CYC大佬的秘籍

1
2
3
4

最后,重要的话再来几次

许愿能挺进二面,加油,向着目标冲呀~~~~

许愿能挺进二面,加油,向着目标冲呀

1
许愿能挺进二面,加油,向着目标冲呀

Java面试题

基础与框架

String类能被继承吗,为什么?

不可以,因为String类有final修饰符,而final修饰的类是不能被继承的,实现细节不允许改变。

1
public final class String implements java.io.Serializable, Comparable<String>, CharSequence

根据程序上下文环境,Java关键字final有“这是无法改变的”或者“终态的”含义,它可以修饰非抽象类、非抽象类成员方法和变量。你可能出于两种理解而需要阻止改变:设计或效率。
  final类不能被继承,没有子类,final类中的方法默认是final的。
  final方法不能被子类的方法覆盖,但可以被继承。
  final成员变量表示常量,只能被赋值一次,赋值后值不再改变。
  final不能用于修饰构造方法。
  注意:父类的private成员方法是不能被子类方法覆盖的,因此private类型的方法默认是final类型的。

如果一个类不允许其子类覆盖某个方法,则可以把这个方法声明为final方法。
  使用final方法的原因有二:
  第一、把方法锁定,防止任何继承类修改它的意义和实现。
  第二、高效。编译器在遇到调用final方法时候会转入内嵌机制,大大提高执行效率。(这点有待商榷,《Java编程思想》中对于这点存疑)

下面这段话摘自《Java编程思想》第四版第143页:
“使用final方法的原因有两个。第一个原因是把方法锁定,以防任何继承类修改它的含义;第二个原因是效率。在早期的Java实现版本中,会将final方法转为内嵌调用。但是如果方法过于庞大,可能看不到内嵌调用带来的任何性能提升。在最近的Java版本中,不需要使用final方法进行这些优化了。”

关于String类,要了解常量池的概念

1
String s = new String(“xyz”);  //创建了几个对象

答案: 1个或2个, 如果”xyz”已经存在于常量池中,则只在堆中创建”xyz”对象的一个拷贝,否则还要在常量池中在创建一份

1
String s = "a"+"b"+"c"+"d"; //创建了几个对象

答案: 这个和JVM实现有关, 如果常量池为空,可能是1个也可能是7个等

String,Stringbuffer,StringBuilder的区别?

1、用来处理字符串常用的类有3种:String、StringBuffer和StringBuilder
2、三者之间的区别:
都是final类,都不允许被继承;
String类长度是不可变的,StringBuffer和StringBuilder类长度是可以改变的;
StringBuffer类是线程安全的,StringBuilder不是线程安全的;

String 和 StringBuffer:
1、String类型和StringBuffer类型的主要性能区别:String是不可变的对象,因此每次在对String类进行改变的时候都会生成一个新的string对象,然后将指针指向新的string对象,所以经常要改变字符串长度的话不要使用string,因为每次生成对象都会对系统性能产生影响,特别是当内存中引用的对象多了以后,JVM的GC就会开始工作,性能就会降低;

2、使用StringBuffer类时,每次都会对StringBuffer对象本身进行操作,而不是生成新的对象并改变对象引用,所以多数情况下推荐使用StringBuffer,特别是字符串对象经常要改变的情况;

3、在某些情况下,String对象的字符串拼接其实是被Java Compiler编译成了StringBuffer对象的拼接,所以这些时候String对象的速度并不会比StringBuffer对象慢,例如:

1
2
String s1 = “This is only a” + “ simple” + “ test”;
StringBuffer Sb = new StringBuilder(“This is only a”).append(“ simple”).append(“ test”);

生成 String s1对象的速度并不比 StringBuffer慢。其实在Java Compiler里,自动做了如下转换:

1
2
3
4
5
Java Compiler直接把上述第一条语句编译为:
String s2 = “This is only a”;
String s3 = “ simple”;
String s4 = “ test”;
String s1 = s2 + s3 + s4;

传送门

ArrayList和LinkedList有什么区别

ArrayList是实现了基于动态数组的结构,LinkedList则是基于实现链表的数据结构。

数据的更新和查找
ArrayList的所有数据是在同一个地址上,而LinkedList的每个数据都拥有自己的地址.所以在对数据进行查找的时候,由于LinkedList的每个数据地址不一样,get数据的时候ArrayList的速度会优于LinkedList,而更新数据的时候,虽然都是通过循环循环到指定节点修改数据,但LinkedList的查询速度已经是慢的,而且对于LinkedList而言,更新数据时不像ArrayList只需要找到对应下标更新就好,LinkedList需要修改指针,速率不言而喻

数据的增加和删除
对于数据的增加元素,ArrayList是通过移动该元素之后的元素位置,其后元素位置全部+1,所以耗时较长,而LinkedList只需要将该元素前的后续指针指向该元素并将该元素的后续指针指向之后的元素即可。与增加相同,删除元素时ArrayList需要将被删除元素之后的元素位置-1,而LinkedList只需要将之后的元素前置指针指向前一元素,前一元素的指针指向后一元素即可。当然,事实上,若是单一元素的增删,尤其是在List末端增删一个元素,二者效率不相上下。

传送门

类的实例化顺序,比如父类静态数据,构造函数,字段,子类静态数据,构造函数,字段,他们的执行顺序

此题考察的是类加载器实例化时进行的操作步骤(加载–>连接->初始化)。
父类静态变量、
父类静态代码块、
子类静态变量、
子类静态代码块、
父类非静态变量(父类实例成员变量)、
父类构造函数、
子类非静态变量(子类实例成员变量)、
子类构造函数。

传送门

用过哪些Map,都有什么区别,HashMap是线程安全的吗,并发下使用的Map是什么,他们内部原理分别是什么,比如hashcode,扩容等

Hashtable,HashMap,ConcurrentHashMap

线程不安全的HashMap
因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。

HashMap
HashMap内部实现是一个桶数组,每个桶中存放着一个单链表的头结点。其中每个结点存储的是一个键值对整体(Entry),HashMap采用拉链法解决哈希冲突

传送门

效率低下的HashTable容器
HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。

ConcurrentHashMap的锁分段技术
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问HashTable的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

传送门

hashcode() 方法,在object类中定义如下:

1
public native int hashCode();

native说明是一个本地方法,它的实现是根据本地机器相关的。当然我们可以在自己写的类中覆盖hashcode()方法,比如String、Integer、Double。。。。等等这些类都是覆盖了hashcode()方法的
例如String类中:就是以31为权,每一位为字符的ASCII值进行运算,用自然溢出来等效取模。(为什么取31?主要是因为31是一个奇质数,所以31i=32i-i=(i<<5)-i,这种位移与减法结合的计算相比一般的运算快很多).

1
2
3
4
5
6
7
8
9
10
11
12
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;

for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

HashMap为什么get和set那么快,concurrentHashMap为什么能提高并发

HashMap 底层是基于 数组 + 链表 组成的

传送门

抽象类和接口的区别,类可以继承多个类么,接口可以继承多个接口么,类可以实现多个接口么

实现 抽象类使用extends关键字来继承抽象类。如果子类不是抽象类的话,它需要提供抽象类中所有声明的方法的实现。子类使用关键字implements来实现接口。它需要提供接口中所有声明的方法的实现。
抽象类和接口的区别

由于Java不支持多继承,子类不能够继承多个类,但可以实现多个接口。因此你就可以使用接口来解决它。

接口可以继承多个接口。
java类是单继承的。classB Extends classA
java接口可以多继承。Interface3 Extends Interface0, Interface1, interface……
不允许类多重继承的主要原因是,如果A同时继承B和C,而B和C同时有一个D方法,A如何决定该继承那一个呢?
但接口不存在这样的问题,接口全都是抽象方法继承谁都无所谓,所以接口可以继承多个接口。

什么情况下会发生栈内存溢出

方法递归调用产生这种结果

栈是线程私有的,他的生命周期与线程相同,每个方法在执行的时候都会创建一个栈帧,用来存储局部变量表,操作数栈,动态链接,方法出口灯信息。局部变量表又包含基本数据类型,对象引用类型(局部变量表编译器完成,运行期间不会变化)

所以我们可以理解为栈溢出就是方法执行是创建的栈帧超过了栈的深度。那么最有可能的就是方法递归调用产生这种结果。栈溢出(StackOverflowError)

什么是nio,原理

NIO是为了弥补传统I/O工作模式的不足而研发的,NIO的工具包提出了基于Selector(选择器)、Buffer(缓冲区)、Channel(通道)的新模式;Selector(选择器)、可选择的Channel(通道)和SelectionKey(选择键)配合起来使用,可以实现并发的非阻塞型I/O能力。

NIO的工作原理是什么?

  在并发型服务器程序中使用NIO,实际上是通过网络事件驱动模型实现的。我们应用Select机制,不用为每一个客户端连接新启线程处理,而是将其注册到特定的Selector对象上,这就可以在单线程中利用Selector对象管理大量并发的网络连接,更好的利用了系统资源;采用非阻塞I/O的通信方式,不要求阻塞等待I/O操作完成即可返回,从而减少了管理I/O连接导致的系统开销,大幅度提高了系统性能。

  当有读或写等注册事件发生时,可以从Selector中获得相应的SelectionKey,从SelectionKey中可以找到发生的事件和该事件所发生的具体的SelectableChannel,以获得客户端发送过来的数据。由于在非阻塞网络I/O中采用了事件触发机制,处理程序可以得到系统的主动通知,从而可以实现底层网络I/O无阻塞、流畅地读写,而不像在原来的阻塞模式下处理程序需要不断循环等待。使用NIO,可以编写出性能更好、更易扩展的并发型服务器程序。

  并发型服务器程序的实现代码:应用NIO工具包,基于非阻塞网络I/O设计的并发型服务器程序与以往基于阻塞I/O的实现程序有很大不同,在使用非阻塞网络I/O的情况下,程序读取数据和写入数据的时机不是由程序员控制的,而是Selector决定的。

  使用非阻塞型I/O进行并发型服务器程序设计分三个部分:1. 向Selector对象注册感兴趣的事件;2.从Selector中获取所感兴趣的事件;3. 根据不同的事件进行相应的处理。

  在进行并发型服务器程序设计时,通过合理地使用NIO工具包,就可以达到一个或者几个Socket线程就可以处理N多个Socket的连接,大大降低我们对服务器程序的预算压力。同时我们利用它更好地提高系统的性能,使我们的工作得到更加有效地开展。

传送门

反射中,Class.forName和ClassLoader区别

Java中Class.forName和classloader都可以用来对类进行加载。

  • Class.forName(“className”);

    其实这种方法调运的是:Class.forName(className, true, ClassLoader.getCallerClassLoader())方法
    参数一:className,需要加载的类的名称。
    参数二:true,是否对class进行初始化(需要initialize)
    参数三:classLoader,对应的类加载器
  • ClassLoader.laodClass(“className”);

    其实这种方法调运的是:ClassLoader.loadClass(name, false)方法
    参数一:name,需要加载的类的名称
    参数二:false,这个类加载以后是否需要去连接(不需要linking)

可见Class.forName除了将类的.class文件加载到jvm中之外,还会对类进行解释,执行类中的static块。

而classloader只干一件事情,就是将.class文件加载到jvm中,不会执行static中的内容,只有在newInstance才会去执行static块。

传送门

tomcat结构,类加载器流程

Tomcat 的总体结构

image.png

从上图中可以看出 Tomcat 的心脏是两个组件:Connector 和 Container,关于这两个组件将在后面详细介绍。Connector 组件是可以被替换,这样可以提供给服务器设计者更多的选择,因为这个组件是如此重要,不仅跟服务器的设计的本身,而且和不同的应用场景也十分相关,所以一个 Container 可以选择对应多个 Connector。多个 Connector 和一个 Container 就形成了一个 Service,Service 的概念大家都很熟悉了,有了 Service 就可以对外提供服务了,但是 Service 还要一个生存的环境,必须要有人能够给她生命、掌握其生死大权,那就非 Server 莫属了。所以整个 Tomcat 的生命周期由 Server 控制。

什么是类加载器?
虚拟机设计团队把类加载阶段中的“通过一个类的全限定名来获取描述此类的二进制字节流”这个动作放到Java虚拟机外部去实现,以便让应用程序自己决定如何去获取所需要的类。实现这个动作的代码模块称为“类加载器”。

传送门

讲讲Spring事务的传播属性,AOP原理,动态代理与cglib实现的区别,AOP有哪几种实现方式

Spring的beanFactory和factoryBean的区别

Spring加载流程

Spring如何管理事务的

多线程

线城池的最大线程数目根据什么确定

多线程的几种实现方式,什么是线程安全,什么是重排序

volatile的原理,作用,能代替锁么

sleep和wait的区别,以及wait的实现原理

Lock与synchronized 的区别,synchronized 的原理,什么是自旋锁,偏向锁,轻量级锁,什么叫可重入锁,什么叫公平锁和非公平锁

用过哪些原子类,他们的参数以及原理是什么

用过哪些线程池,他们的原理简单概括下,构造函数的各个参数的含义,比如coreSize,maxsize等

有一个第三方接口,有很多个线程去调用获取数据,现在规定每秒钟最多有10个线程同时调用它,如何做到。

spring的controller是单例还是多例,怎么保证并发的安全

用三个线程按顺序循环打印abc三个字母,比如abcabcabc

ThreadLocal用过么,原理是什么,用的时候要注意什么

如果让你实现一个并发安全的链表,你会怎么做

JVM相关

jvm中一次完整的GC流程(从ygc到fgc)是怎样的,重点讲讲对象如何晋升到老年代,几种主要的jvm参数等

你知道哪几种垃圾收集器,各自的优缺点,重点讲下cms

当出现了内存溢出,你怎么排错

JVM内存模型的相关知识了解多少

简单说说你了解的类加载器

JAVA的反射机制

网络

http1.0和http1.1有什么区别

TCP三次握手和四次挥手的流程,为什么断开连接要4次,如果握手只有两次,会出现什么

TIME_WAIT和CLOSE_WAIT的区别

说说你知道的几种HTTP响应码

当你用浏览器打开一个链接的时候,计算机做了哪些工作步骤

Linux下IO模型有几种,各自的含义是什么

TCP/IP如何保证可靠性,数据包有哪些数据组成

架构设计与分布式:

tomcat如何调优,各种参数的意义

常见的缓存策略有哪些,你们项目中用到了什么缓存系统,如何设计的,Redis的使用要注意什么,持久化方式,内存设置,集群,淘汰策略等

如何防止缓存雪崩12.用java自己实现一个LRU

分布式集群下如何做到唯一序列号

设计一个秒杀系统,30分钟没付款就自动关闭交易

如何做一个分布式锁

用过哪些MQ,怎么用的,和其他mq比较有什么优缺点,MQ的连接是线程安全的吗

MQ系统的数据如何保证不丢失

分布式事务的原理,如何使用分布式事务

什么是一致性hash

什么是restful,讲讲你理解的restful

如何设计建立和保持100w的长连接?

解释什么是MESI协议(缓存一致性)

说说你知道的几种HASH算法,简单的也可以

什么是paxos算法

redis和memcached 的内存管理的区别

一个在线文档系统,文档可以被编辑,如何防止多人同时对同一份文档进行编辑更新

算法

10亿个数字里里面找最小的10个

有1亿个数字,其中有2个是重复的,快速找到它,时间和空间要最优

2亿个随机生成的无序整数,找出中间大小的值

遍历二叉树

数据库

数据库隔离级别有哪些,各自的含义是什么,MYsql默认的隔离级别是是什么,各个存储引擎优缺点

高并发下,如何做到安全的修改同一行数据,乐观锁和悲观锁是什么,INNODB的行级锁有哪2种,解释其含义

SQL优化的一般步骤是什么,怎么看执行计划,如何理解其中各个字段的含义,索引的原理?

数据库会死锁吗,举一个死锁的例子,mysql怎么解决死锁

MYsql的索引实现方式

聚集索引和非聚集索引的区别

数据库中 BTREE和B+tree区别

面试红黑树

什么是红黑树

红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用。比如在 Java 集合框架中,很多部分(HashMap, TreeMap, TreeSet 等)都有红黑树的应用,这些集合均提供了很好的性能。

由于 TreeMap 就是由红黑树实现的,因此本文将使用 TreeMap 的相关操作的代码进行分析、论证。

黑色高度
从根节点到叶节点的路径上黑色节点的个数,叫做树的黑色高度。

红黑树的 5 个特性

image.png

红黑树在原有的二叉查找树基础上增加了如下几个要求:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

中文意思是:

  1. 每个节点要么是红色,要么是黑色;
  2. 根节点永远是黑色的;
  3. 所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
  4. 每个红色节点的两个子节点一定都是黑色;
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;

注意:
性质 3 中指定红黑树的每个叶子节点都是空节点,而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。

性质 4 的意思是:从每个根到节点的路径上不会有两个连续的红色节点,但黑色节点是可以连续的。
因此若给定黑色节点的个数 N,最短路径的情况是连续的 N 个黑色,树的高度为 N - 1;最长路径的情况为节点红黑相间,树的高度为 2(N - 1) 。

性质 5 是成为红黑树最主要的条件,后序的插入、删除操作都是为了遵守这个规定。

红黑树并不是标准平衡二叉树,它以性质 5 作为一种平衡方法,使自己的性能得到了提升。

红黑树的左旋右旋

image.png

红黑树的左右旋是比较重要的操作,左右旋的目的是调整红黑节点结构,转移黑色节点位置,使其在进行插入、删除后仍能保持红黑树的 5 条性质。

比如 X 左旋(右图转成左图)的结果,是让在 Y 左子树的黑色节点跑到 X 右子树去。

我们以 Java 集合框架中的 TreeMap 中的代码来看下左右旋的具体操作方法:

指定节点 x 的左旋 (右图转成左图):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 //这里 p 代表 x
private void rotateLeft(Entry p) {
if (p != null) {
Entry r = p.right; // p 是上图中的 x,r 就是 y
p.right = r.left; // 左旋后,x 的右子树变成了 y 的左子树 β
if (r.left != null)
r.left.parent = p; //β 确认父亲为 x
r.parent = p.parent; //y 取代 x 的第一步:认 x 的父亲为爹
if (p.parent == null) //要是 x 没有父亲,那 y 就是最老的根节点
root = r;
else if (p.parent.left == p) //如果 x 有父亲并且是它父亲的左孩子,x 的父亲现在认 y 为左孩子,不要 x 了
p.parent.left = r;
else //如果 x 是父亲的右孩子,父亲就认 y 为右孩子,抛弃 x
p.parent.right = r;
r.left = p; //y 逆袭成功,以前的爸爸 x 现在成了它的左孩子
p.parent = r;
}
}

可以看到,x 节点的左旋就是把 x 变成 右孩子 y 的左孩子,同时把 y 的左孩子送给 x 当右子树。

简单点记就是:左旋把右子树里的一个节点(上图 β)移动到了左子树。

指定节点 y 的右旋(左图转成右图):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void rotateRight(Entry p) {
if (p != null) {
Entry l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}

同理,y 节点的右旋就是把 y 变成 左孩子 x 的右孩子,同时把 x 的右孩子送给 x 当左子树。

简单点记就是:右旋把左子树里的一个节点(上图 β)移动到了右子树。

了解左旋、右旋的方法及意义后,就可以了解红黑树的主要操作:插入、删除。

总结

红黑树并不是真正的平衡二叉树,但在实际应用中,红黑树的统计性能要高于平衡二叉树,但极端性能略差。

红黑树的插入、删除调整逻辑比较复杂,但最终目的是满足红黑树的 5 个特性,尤其是 4 和 5。

在插入调整时为了简化操作我们直接把插入的节点涂成红色,这样只要保证插入节点的父节点不是红色就可以了。

而在删除后的调整中,针对删除黑色节点,所在子树缺少一个节点,需要进行弥补或者对别人造成一个黑色节点的伤害。具体调整方法取决于兄弟节点所在子树的情况。

红黑树的插入、删除在树形数据结构中算比较复杂的,理解起来比较难,但只要记住,红黑树有其特殊的平衡规则,而我们为了维持平衡,根据邻树的状况进行旋转或者涂色。

红黑树这么难理解,必定有其过人之处。它的有序、快速特性在很多场景下都有用到,比如 Java 集合框架的 TreeMap, TreeSet 等。

Spring框架面试总结

image.png

介绍spring框架

它是一个一站式(full-stack全栈式)框架,提供了从表现层-springMVC到业务层-spring再到持久层-springdata的一套完整的解决方案。我们在项目中可以只使用spring一个框架,它就可以提供表现层的mvc框架,持久层的Dao框架。它的两大核心IoC和AOP更是为我们程序解耦和代码简洁易维护提供了支持。

Spring的优点?

  1. 降低了组件之间的耦合性 ,实现了软件各层之间的解耦
  2. 可以使用容易提供的众多服务,如事务管理,消息服务等
  3. 容器提供单例模式支持
  4. 容器提供了AOP技术,利用它很容易实现如权限拦截,运行期监控等功能
  5. 容器提供了众多的辅助类,能加快应用的开发
  6. spring对于主流的应用框架提供了集成支持,如hibernate, JPA,Struts等
  7. spring属于低侵入式设计,代码的污染极低
  8. 独立于各种应用服务器
  9. spring的DI机制降低了业务对象替换的复杂性
  10. Spring的高度开放性,并不强制应用完全依赖于Spring,开发者可以自由选择spring 的部分或全部

spring有两种代理方式:

答: 若目标对象实现了若干接口,spring使用JDK的java.lang.reflect.Proxy类代理。

优点:因为有接口,所以使系统更加松耦合

缺点:为每一个目标类创建接口

若目标对象没有实现任何接口,spring使用CGLIB库生成目标对象的子类。

优点:因为代理类与目标类是继承关系,所以不需要有接口的存在。

缺点:因为没有使用接口,所以系统的耦合性没有使用JDK的动态代理好

如何给Spring 容器提供配置元数据?

这里有三种重要的方法给Spring 容器提供配置元数据。

XML配置文件。

基于注解的配置。

基于java的配置。

构造方法注入和设值注入有什么区别?

请注意以下明显的区别:

在设值注入方法支持大部分的依赖注入,如果我们仅需要注入int、string和long型的变量,我们不要用设值的方法注入。

对于基本类型,如果我们没有注入的话,可以为基本类型设置默认值。

在构造方法注入不支持大部分的依赖注入,因为在调用构造方法中必须传入正确的构造参数,否则的话为报错。

设值注入不会重写构造方法的值。

在使用设值注入时有可能还不能保证某种依赖是否已经被注入,也就是说这时对象的依赖关系有可能是不完整的。而在另一种情况下,构造器注入则不允许生成依赖关系不完整的对象。

请介绍一下Spring框架中Bean的生命周期

一、Bean的定义

Spring通常通过配置文件定义Bean。如:

这个配置文件就定义了一个标识为 HelloWorld 的Bean。在一个配置文档中可以定义多个Bean。

二、Bean的初始化

有两种方式初始化Bean。

1、在配置文档中通过指定init-method 属性来完成

2、实现 org.springframwork.beans.factory.InitializingBean接口

那么,当这个Bean的所有属性被Spring的BeanFactory设置完后,会自动调用afterPropertiesSet()方法对Bean进行初始化,于是,配置文件就不用指定 init-method属性了。

三、Bean的调用

有三种方式可以得到Bean并进行调用:

1、使用BeanWrapper

2、使用BeanFactory

3、使用ApplicationConttext

四、Bean的销毁

1、使用配置文件中的 destory-method 属性

2、实现 org.springframwork.bean.factory.DisposebleBean接口

Spring中AOP的应用场景、Aop原理、好处?

答:AOP–Aspect Oriented Programming面向切面编程;用来封装横切关注点,具体可以在下面的场景中使用:

Authentication 权限、Caching 缓存、Context passing 内容传递、Error handling 错误处理Lazy loading懒加载、Debugging调试、logging, tracing, profiling and monitoring 记录跟踪优化 校准、Performance optimization 性能优化、Persistence 持久化、Resource pooling 资源池、Synchronization 同步、Transactions 事务

原理:AOP是面向切面编程,是通过动态代理的方式为程序添加统一功能,集中解决一些公共问题。

优点:1.各个步骤之间的良好隔离性耦合性大大降低

2.源代码无关性,再扩展功能的同时不对源码进行修改操作 

有几种不同类型的自动代理?

BeanNameAutoProxyCreator

DefaultAdvisorAutoProxyCreator

Metadata autoproxying

ApplicationContext通常的实现是什么?

FileSystemXmlApplicationContext :此容器从一个XML文件中加载beans的定义,XML Bean 配置文件的全路径名必须提供给它的构造函数。

ClassPathXmlApplicationContext:此容器也从一个XML文件中加载beans的定义,这里,你需要正确设置classpath因为这个容器将在classpath里找bean配置。

WebXmlApplicationContext:此容器加载一个XML文件,此文件定义了一个WEB应用的所有bean。

有哪些不同类型的IOC(依赖注入)方式?

构造器依赖注入:构造器依赖注入通过容器触发一个类的构造器来实现的,该类有一系列参数,每个参数代表一个对其他类的依赖。

Setter方法注入:Setter方法注入是容器通过调用无参构造器或无参static工厂 方法实例化bean之后,调用该bean的setter方法,即实现了基于setter的依赖注入。

什么是IOC,什么又是DI,他们有什么区别?

一、IOC介绍

IOC是控制反转。

创建对象实例的控制权从代码控制剥离到IOC容器控制(之前的写法,由程序代码直接操控使用new关键字),实际就是你在xml文件控制,控制权的转移是所谓反转,侧重于原理。

二、DI介绍

DI是依赖注入

创建对象实例时,为这个对象注入属性值或其它对象实例,侧重于实现。

spring事务定义

事务的定义:事务是指多个操作单元组成的合集,多个单元操作是整体不可分割的,要么都操作不成功,要么都成功。其必须遵循四个原则(ACID)。

原子性(Atomicity):即事务是不可分割的最小工作单元,事务内的操作要么全做,要么全不做;

一致性(Consistency):在事务执行前数据库的数据处于正确的状态,而事务执行完成后数据库的数据还是应该处于正确的状态,即数据完整性约束没有被破坏;如银行转帐,A转帐给B,必须保证A的钱一定转给B,一定不会出现A的钱转了但B没收到,否则数据库的数据就处于不一致(不正确)的状态。

隔离性(Isolation):并发事务执行之间互不影响,在一个事务内部的操作对其他事务是不产生影响,这需要事务隔离级别来指定隔离性;

持久性(Durability):事务一旦执行成功,它对数据库的数据的改变必须是永久的,不会因比如遇到系统故障或断电造成数据不一致或丢失。

Spring框架中的单例Beans是线程安全的么?

Spring框架并没有对单例bean进行任何多线程的封装处理。关于单例bean的线程安全和并发问题需要开发者自行去搞定。但实际上,大部分的Spring bean并没有可变的状态(比如Serview类和DAO类),所以在某种程度上说Spring的单例bean是线程安全的。如果你的bean有多种状态的话(比如 View Model 对象),就需要自行保证线程安全。

Java面试题(框架+JVM+多线程+算法+数据库)

image.png

基础与框架

  1. String类能被继承吗,为什么
  2. String,Stringbuffer,StringBuilder的区别?
  3. ArrayList和LinkedList有什么区别
  4. 类的实例化顺序,比如父类静态数据,构造函数,字段,子类静态数据,构造函数,字段,他们的执行顺序
  5. 用过哪些Map,都有什么区别,HashMap是线程安全的吗,并发下使用的Map是什么,他们内部原理分别是什么,比如hashcode,扩容等
  6. HashMap为什么get和set那么快,concurrentHashMap为什么能提高并发
  7. 抽象类和接口的区别,类可以继承多个类么,接口可以继承多个接口么,类可以实现多个接口么
  8. 什么情况下会发生栈内存溢出
  9. 什么是nio,原理
  10. 反射中,Class.forName和ClassLoader区别
  11. tomcat结构,类加载器流程
  12. 讲讲Spring事务的传播属性,AOP原理,动态代理与cglib实现的区别,AOP有哪几种实现方式
  13. Spring的beanFactory和factoryBean的区别
  14. Spring加载流程
  15. Spring如何管理事务的

多线程

  1. 线城池的最大线程数目根据什么确定
  2. 多线程的几种实现方式,什么是线程安全,什么是重排序3.volatile的原理,作用,能代替锁么
  3. sleep和wait的区别,以及wait的实现原理
  4. Lock与synchronized 的区别,synchronized 的原理,什么是自旋锁,偏向锁,轻量级锁,什么叫可重入锁,什么叫公平锁和非公平锁
  5. 用过哪些原子类,他们的参数以及原理是什么
  6. 用过哪些线程池,他们的原理简单概括下,构造函数的各个参数的含义,比如coreSize,maxsize等
  7. 有一个第三方接口,有很多个线程去调用获取数据,现在规定每秒钟最多有10个线程同时调用它,如何做到。
  8. spring的controller是单例还是多例,怎么保证并发的安全
  9. 用三个线程按顺序循环打印abc三个字母,比如abcabcabc
  10. ThreadLocal用过么,原理是什么,用的时候要注意什么
  11. 如果让你实现一个并发安全的链表,你会怎么做

JVM相关

  1. jvm中一次完整的GC流程(从ygc到fgc)是怎样的,重点讲讲对象如何晋升到老年代,几种主要的jvm参数等
  2. 你知道哪几种垃圾收集器,各自的优缺点,重点讲下cms
  3. 当出现了内存溢出,你怎么排错
  4. JVM内存模型的相关知识了解多少
  5. 简单说说你了解的类加载器
  6. JAVA的反射机制

网络

  1. http1.0和http1.1有什么区别
  2. TCP三次握手和四次挥手的流程,为什么断开连接要4次,如果握手只有两次,会出现什么
  3. TIME_WAIT和CLOSE_WAIT的区别
  4. 说说你知道的几种HTTP响应码
  5. 当你用浏览器打开一个链接的时候,计算机做了哪些工作步骤
  6. Linux下IO模型有几种,各自的含义是什么
  7. TCP/IP如何保证可靠性,数据包有哪些数据组成
  8. 架构设计与分布式:
  9. tomcat如何调优,各种参数的意义
  10. 常见的缓存策略有哪些,你们项目中用到了什么缓存系统,如何设计的,Redis的使用要注意什么,持久化方式,内存设置,集群,淘汰策略等
  11. 如何防止缓存雪崩12.用java自己实现一个LRU
  12. 分布式集群下如何做到唯一序列号
  13. 设计一个秒杀系统,30分钟没付款就自动关闭交易
  14. 如何做一个分布式锁
  15. 用过哪些MQ,怎么用的,和其他mq比较有什么优缺点,MQ的连接是线程安全的吗
  16. MQ系统的数据如何保证不丢失
  17. 分布式事务的原理,如何使用分布式事务
  18. 什么是一致性hash
  19. 什么是restful,讲讲你理解的restful
  20. 如何设计建立和保持100w的长连接?
  21. 解释什么是MESI协议(缓存一致性)
  22. 说说你知道的几种HASH算法,简单的也可以
  23. 什么是paxos算法
  24. redis和memcached 的内存管理的区别
  25. 一个在线文档系统,文档可以被编辑,如何防止多人同时对同一份文档进行编辑更新

算法

  1. 10亿个数字里里面找最小的10个2、有1亿个数字,其中有2个是重复的,快速找到它,时间和空间要最优3、2亿个随机生成的无序整数,找出中间大小的值4、遍历二叉树六、数据库1.数据库隔离级别有哪些,各自的含义是什么,MYsql默认的隔离级别是是什么,各个存储引擎优缺点
  2. 高并发下,如何做到安全的修改同一行数据,乐观锁和悲观锁是什么,INNODB的行级锁有哪2种,解释其含义
  3. SQL优化的一般步骤是什么,怎么看执行计划,如何理解其中各个字段的含义,索引的原理?
  4. 数据库会死锁吗,举一个死锁的例子,mysql怎么解决死锁
  5. MYsql的索引实现方式
  6. 聚集索引和非聚集索引的区别
  7. 数据库中 BTREE和B+tree区别

作者:程序汪追风
链接:https://juejin.im/post/5d5fd40bf265da03df5f1b3a
来源:掘金

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×