Java面试突击
文章目录
@[toc]
基础
JDK、JDK、JRE的关系
Java基本数据类型
final作用
| final修饰 | 解释 |
|---|---|
| 类 | 不可以被继承 |
| 方法 | 不能被重写 |
| 变量 | 不能被改变，不可变值的是变量的引用，指向的内容可以改变 |
final finally finalize
| 区别 | 描述 |
|---|---|
| final | 如上解释 |
| finally | 一般作用在try-catch代码块中，一般用来存放一些关闭资源的代码 |
| finalize | 属于Object类的一个方法，由垃圾回收器调用finalize()，回收垃圾，一个对象是否可回收的最后判断。 |
static作用
| static作用 | 解释 |
|---|---|
| 1 | 变量或者方法是独立于该类的任何对象，被类的实例对象所共享。 |
| 2 | 该类被第一次加载的时候，就会去加载被static修饰的部分，但只有在类第一次使用时才进行初始化 |
| 3 | 在类加载的时候分配空间，以后创建类对象的时候不会重新分配 |
| 4 | 修饰的变量或者方法是优先于对象存在的，便于被实例对象共享 |
面向对象、面向过程
| 区别 | 优点 | 缺点 |
|---|---|---|
| 面向对象 | 易维护、易复用、易扩展 | 性能比面向过程低 |
| 面向过程 | 能比面向对象高，因为类调用时需要实例化，开销比较大 | 没有面向对象易维护、易复用、易扩展 |
面向对象三大特征
| 面向对象三大特征 | 解释 |
|---|---|
| 封装 | 隐藏对象的属性和实现细节，仅对外提供公共访问方式，将变化隔离，便于使用，提高复用性和安全性 |
| 继承 | 通过使用继承可以提高代码复用性。继承是多态的前提 |
| 多态 | 可以指向子类或具体实现类的实例对象。提高了程序的拓展性 |
String、StringBuffer、StringBuilder
| String | StringBuffer | StringBuilder | |
|---|---|---|---|
| 可变性 | 不可变 | 可变 | 可变 |
| 安全性 | 安全，因为final | 安全，因为加锁 | 不安全 |
| 适用 | 少量操作 | 多线程+大量操作 | 单线程+大量操作 |
Int和Integer的区别
// 问题1：Integer和int比较
Integer a = new Integer(3);
Integer b = 3;
System.out.println(a == b);// false，引用类型和值类型不能比较
Integer d = new Integer(3);
System.out.println(a == d); // false，两个引用类型用==不能比较
int c = 3;
System.out.println(c == d); // true，Integer遇到int比较，Integer会拆箱成int做值比较
System.out.println("-------"); Integer底层提前缓存好了[-128,127]的值，所以创建两个范围的对象时，地址是一样的
// 问题2:Integer值返回缓存
Integer f1 = 100;
Integer f2 = 100;
System.out.println(f1 == f2);// true
Integer f3 = 129;
Integer f4 = 129;
System.out.println(f3 == f4);
System.out.println("-------");// false 原因：当一个Integer对象赋给int值的使用，调用Integer的valueOf方法
public static Integer valueOf(int i) {
// i在[-128,127]时，就会自动去引用常量池中的Integer对象，不会new新的
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
} Equals、==、hashCode区别
| == | equals | hashCode |
|---|---|---|
| 基本数据类型用，比较的是首地址值 | 引用类型用，比较是内容值 | 对象在内存中的地址，算出对象的哈希码值，并将其返回，重写equals方法，必须重写hashCode，因为集合类是通过HashCode判断重复的 |
序列化类中有一个不可序列化的对象
给该类设置关键字transiient告诉JDK不可被序列化
元注解
Java中使用返回值类型@interface表示该类是一个注解配置类，注解配置不能使用class、interface、abstract修饰
// 自定义注解，以下只是简单的演示。实际开发注解还需要一个注解处理器，自行百度学习
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.CLASS)
@Documented
public @interface FruitProvider {
public int id() default -1;
public String name() default "";
public String address() default "";
} public class Apple {
// 使用自定义注解
@FruitProvider(id = 1, name = "红富士", address = "北京市")
private String appleProvider;
public String getAppleProvider() {
return appleProvider;
}
public void setAppleProvider(String appleProvider) {
this.appleProvider = appleProvider;
}
} 四大元注解：目标、保留、文档、继承
@Target：说明注解对象修饰范围
@Retention：该注解保留时长
- source ：在源文件中有效， 源文件中就保留
- class：字节码文件中有效， 即在Class文件中被保留
- runtime：在运行时有效，即在运行时被保留
@Documented：表示被Javadoc文档工具化，只是一个标记注解，没有成员
@Inherited：表示该类型是被继承的，表名该注解类可以作用于其子类
Java的面向对象
| 名称 | 概念 |
|---|---|
| 封装 | 将事物封装成一个类，减少耦合，隐藏细节。保留特定接口和外部联系 |
| 继承 | 从已知的类中派生出一个新的类，可以通过覆盖/重写增强功能 |
| 多态 | 本质是一个程序中存在多个同名的不同方法 |
封装：将事物封装成一个类，减少耦合，隐藏细节。保留特定接口和外部联系
继承：从已知的类中派生出一个新的类，可以通过覆盖/重写增强功能
- Java中类的初始化顺序：
- 父类静态成员变量、静态代码块；子类静态成员变量、静态代码块
- 父类普通成员变量和代码块，再执行父类构造方法
- 子类普通成员变量和代码块，再执行父类构造方法
- 子类特点：
- 父类非private的属性和方法
- 添加自己的方法和属性，对父类进行扩展
- 重新定义父类的方法=方法的覆盖/重写
多态：本质是一个程序中存在多个同名的不同方法
子类的覆盖实现
方法的重载实现
子类作为父类对象使用
什么方法重载、方法重写？
重载（overload）：一个类中存在多个同名的不同方法，这些方法的参数个数、顺序和类型不同均可以构成方法重载
重写（override）：子类对父类非私有方法的重新编写，涉及写的就会有子父类
如果只有方法返回值不同，可以构成重载吗?
不可以，因为我们调用某个方法，并不关心返回值。编译器根据方法名和参数无法确定我们调用的是那个方法。
Java中有goto关键字吗
goto和const是Java中的保留字，现在未使用，未使用的原因是保证程序的可读性，并且避免使用beak+lebel带标签的语句
| 跳出循环方式1 | 跳出循环方式2 | 跳出循环方式3 |
|---|---|---|
| break+label，不推荐使用 | flag+break | throw new 抛出异常 |
抽象类和接口的
| 相同点 | 不同点 |
|---|---|
| 都不能直接实例化。 | 设计理念不同：抽象类是对对象/类的抽象，接口是对行为的抽象 |
| 都可以有默认的实现方法（JDK8以后才有的） | 抽象类只能单一继承，接口可以多重继承；抽象类可以有构造器，接口没有 |
| 都可以不需要实现类或者继承类去实现所有方法 | 抽象类中的抽象方法可以用public/protected/default abstract修饰；抽象类中的变量可以在子类中重新定义并赋值 |
| 如果要实例化，抽象类变量必须实现所有抽象方法，接口变量必须实现所有接口未实现的方法 | 接口的方法默认修饰符是public abstract,可以加statci关键字；接口中的变量默认是public static final，且必须给初值，在实现类中不能被重新定义和赋值 |
接口和抽象类该如何选择？
当我们仅仅只需要定义一些抽象方法而不需要额外的具体方法/变量的时候，用接口；反之，考虑抽象类
接口的普通方法、default修饰方法：
public interface MyInterface {
// 接口的普通方法只能等待实现类实现，不能具体定义
void test();
// 但是JDK8以后，接口可以default声明，然后具体定义
default void say(String message) {
System.out.println("hello:"+message);
}
} public class MyInterfaceImpl implements MyInterface {
// 实现接口里的抽象方法
@Override
public void test() {
System.out.println("test被执行");
}
// 当然也可以重写say方法
public static void main(String[] args) {
MyInterfaceImpl client = new MyInterfaceImpl();
client.test();
client.say("World");
}
} 执行结果：
test被执行 hello:World
如果实现类实现了两个接口，两个接口都有相同的（default）默认方法名，那么该方法重写会报错
解决办法：
- 实现类重写多个多个接口的默认方法
- 手动指定重写哪个接口的默认方法
public interface MyInterface {
void test();
default void say(String message) {
System.out.println("hello:"+message);
}
}
public interface MyInterface1 {
default void say(String message) {
System.out.println("hello1:" + message);
}
}
public class MyInterfaceImpl1 implements MyInterface, MyInterface1 {
@Override
public void test() {
System.out.println("test是普通方法被重写");
}
@Override
public void say(String message) {
// 方法一：System.out.println("实现类重写多个接口相同的默认方法：" + message);
// 方法二：指定重写哪个接口的默认方法
MyInterface.super.say(message);
}
public static void main(String[] args) {
MyInterfaceImpl1 client = new MyInterfaceImpl1();
client.say("好的");
}
} 执行结果：
实现类重写多个接口相同的默认方法：hello+好的
浅拷贝和深拷贝
| 浅拷贝 | 深拷贝 |
|---|---|
| 被复制的对象的所有变量都含有与原来对象相同的值，对拷贝后对象的引用依然指向原来的对象 | 不仅复制对象的所有非引用成员变量值，还要为引用类型的成员变量创建新的实例，并且初始化为形式参数实例值 |
创建对象的方式
| 创建对象方式 | 是否调用构造器 |
|---|---|
| new + 类名 | 是 |
| Class.newInstance | 是 |
| Constructor.newInstance | 是 |
| Clone | 否 |
| 反序列化 | 否 |
值传递和引用传递
值传递：传递是一个对象副本，即使副本改变，也不会影响原对象
引用传递：传递不是实际的对象，而是对象的引用。因此，外部对引用对象的改变会反映到所有的对象上
public class Test {
public static void main(String[] args) {
int a = 1;
// 基本数据类型：值传递，原值不会变
change(a);
System.out.println(a);
}
private static void change(int num) {
num++;
}
} public class Test1 {
public static void main(String[] args) {
// 以下2个是引用传递，会改变原值
StringBuilder hello1 = new StringBuilder("hello1");
StringBuffer hello2 = new StringBuffer("hello2");
// String存放在常量池，虽然是引用传递，但不会改变原值
String hello3 = new String("hello3");
change1(hello1);
change2(hello2);
change3(hello3);
System.out.println(hello1);
System.out.println(hello2);
System.out.println(hello3);
}
private static void change3(String str) {
str += " world";
}
private static void change1(StringBuilder str) {
str.append(" world");
}
private static void change2(StringBuffer str) {
str.append(" world");
}
} public class Test3 {
public static void main(String[] args) {
StringBuffer hello = new StringBuffer("hello");
System.out.println("before：" + hello);
changeData(hello);
// 前后值：都没有发生改变
// 因为changeData中str形参重新执行了str1，与原值hello无关了
System.out.println("after：" + hello);
}
private static void changeData(StringBuffer str) {
StringBuffer str1 = new StringBuffer("Hi");
str = str1;
str1.append("world");
}
} public class PassTest {
public static void main(String[] args) {
int i = 1;
String str = "hello";
Integer num = 200;
int[] arr = {1, 2, 3, 4, 5};
MyData my = new MyData();
change(i, str, num, arr, my);
/*
结果：传值还是传引用？
i = 1 传值。基本数据类型不会变
str = hello 传常量池地址。字符串不变
num = 200，传堆中的地址。原包装类不变，和字符串一样
arr = [2, 2, 3, 4, 5] 传堆中数组的首地址。发生了改变
my.a = 11，传堆中地址，资源类变量发生改变。资源类中的变量，会在堆中生成一个实例
*/
System.out.println("i = " + i);
System.out.println("str = " + str);
System.out.println("num = " + num);
System.out.println("arr = " + Arrays.toString(arr));
System.out.println("my.a = " + my.a);
}
public static void change(int j, String s, Integer num, int[] arr, MyData myData) {
j += 1;
s += "world";
num += 1;
arr[0] += 1;
myData.a += 1;
}
}
class MyData {
int a = 10;
} 结果：
- 基本数据类型是值传递，不会改变原值
- String和包装类是引用传递，但不会改变原值，因为形参指向了另一个新生成的对象，原值不变
- 数组和自定义类时引用传递，会改变原值，因为数组是连续地址空间，没有在堆中新生成实例；自定义类中的成员变量分配在堆中，也没有重新生成实例
i = 1 // 传值。基本数据类型不会变 str = hello // 传常量池地址。字符串不变 num = 200 // 传堆中的地址。原包装类不变，和字符串一样 arr = [2, 2, 3, 4, 5]// 传堆中数组的首地址。发生了改变 my.a = 11// 传堆中地址，资源类变量发生改变。资源类中的变量，会在堆中生成一个实例
权限修饰符
| 作用域 | 当前类 | 同一包 | 子孙类 | 其他包 |
|---|---|---|---|---|
| public | 可以 | 可以 | 可以 | 可以 |
| protected | 可以 | 可以 | 可以 | 不可以 |
| default | 可以 | 可以 | 不可以 | 不可以 |
| private | 可以 | 不可以 | 不可以 | 不可以 |
反射机制
反射优缺点
| 反射优点 | 反射缺点 | 反射使用场景 |
|---|---|---|
| 装载到JVM中得的信息，动态获取类的属性方法等信息，提高语言灵活性和扩展性 | 性能较差，速度低于直接运行 | Spring等框架 |
| 提高代码复用率 | 程序的可维护性降低 | 动态代理 |
获取字节码
| 方式1 | 方式2 | 方式3 |
|---|---|---|
| 类名.class | 对象名.getClass() | Class.forName(classPath) |
public class User {
String username;
String password;
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public String getPassword() {
return password;
}
public void setPassword(String password) {
this.password = password;
}
@Override
public String toString() {
return "User{" +
"username='" + username + '\'' +
", password='" + password + '\'' +
'}';
}
} public class ThreeClassGetDemo {
public static void main(String[] args) throws ClassNotFoundException {
// 方式一：类.class
Class<Integer> intClass = int.class;
// 方式二：对象.getClass()
User user = new User();
Class<? extends User> userClass = user.getClass();
// 方式三：Class.forName(类名)
String ClassName = "基础.反射.User";
Class<?> userClass1 = Class.forName(ClassName);
}
} public class UserClassDemo {
public static void main(String[] args) {
String className = "基础.反射.User";
try {
// 通过反射获取userClass
Class<?> userClassByForName = Class.forName(className);
// 获取构造器
Constructor<?> constructor = userClassByForName.getConstructor();
// 生成user实例
User user = (User) constructor.newInstance();
user.setUsername("张三");
user.setPassword("123");
System.out.println(user);
// 反射来修改成员变量
Class<? extends User> userClassByuser = user.getClass();
userClassByuser.getDeclaredField("username").set(user, "张三1");
userClassByuser.getDeclaredField("password").set(user, "456");
// 反射修改方法
Method setUsername = userClassByuser.getMethod("setUsername", String.class);
setUsername.invoke(user, "张三2");
System.out.println(user);
} catch (Exception e) {
e.printStackTrace();
}
}
} 打印结果：
User{username='张三', password='123'}
User{username='张三2', password='456'} 获取构造器等
| 获取构造器 | 获取成员变量 | 获取成员方法 | |
|---|---|---|---|
| 非私有 | getConstructor(类型.class) | getMethod(名, 参数.class); | getDeclaredField("id"); |
| 私有 | getDeclaredConstructor(类型.class)和setAccessible（true） | getDeclaredMethod(名, 参数.class);setAccessible（true） | getDeclaredField("id");setAccessible（true） |
定义测试的User：看到原类的构造器、成员属性、方法，想着怎么使用反射生成
package reflect;
public class User {
private int id=1;
private String name="张三";
private static Date date;
public User() {
}
public User(int id) {
this.id = id;
}
private User(String name) {
this.name = name;
}
public User(int id, String name) {
this.id = id;
this.name = name;
}
public void fun1() {
System.out.println("无参的fun1被调用");
}
public void fun2(int id) {
System.out.println("fun2:" + id);
}
public void fun3(int id, String s) {
System.out.println("fun3:" + id + "," + s);
}
private void fun4(Date date) {
System.out.println("fun4:" + date);
}
public static void fun5() {
System.out.println("fun5");
}
public static void fun6(String[] args) {
System.out.println(args.length);
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public static Date getDate() {
return date;
}
public static void setDate(Date date) {
User.date = date;
}
} public class Demo1 {
/**
* 获取非私有构造器
*/
@Test
public void test2() throws Exception {
Class<?> userClazz = Class.forName("reflect.User");
Constructor<?> c1 = userClazz.getConstructor();
Constructor<?> c2 = userClazz.getConstructor(int.class);
Constructor<?> c3 = userClazz.getConstructor(int.class, String.class);
User user = (User) c3.newInstance(1, "A");
System.out.println(user);
}
/**
* 获取私有构造器
*/
@Test
public void test3() throws Exception {
Class<?> userClazz = Class.forName("reflect.User");
// 私有需要declared修饰
Constructor<?> c = userClazz.getDeclaredConstructor(String.class);
// setAccessible设置暴露破解
c.setAccessible(true);
User user = (User) c.newInstance("A");
System.out.println(user);
}
/**
* 获取所有构造器：私有和非私有
*/
@Test
public void test4() throws Exception {
Class<?> userClazz = Class.forName("reflect.User");
Constructor<?>[] constructors = userClazz.getDeclaredConstructors();
for (Constructor c : constructors) {
System.out.println(c);
}
}
} 特殊情况：因为1.4是将字符数组分开作为小个体，String[]作为方法参数需要（Object）强转/new Object[]{包装}
public class Demo2 {
/**
* 获取非私有的成员方法
*/
@Test
public void test1() throws Exception {
Class<?> claszz = Class.forName("reflect.User");
User user = (User) claszz.newInstance();
Method fun1 = claszz.getMethod("fun1", null);
fun1.invoke(user, null);
Method fun2 = claszz.getMethod("fun2", int.class);
fun2.invoke(user, 1);
Method fun3 = claszz.getMethod("fun3", int.class, String.class);
fun3.invoke(user, 1, "A");
}
/**
* 获得私有方法
*/
@Test
public void test2() throws Exception {
Class<?> claszz = Class.forName("reflect.User");
User user = (User) claszz.newInstance();
// declared修饰private
Method fun4 = claszz.getDeclaredMethod("fun4", Date.class);
// setAccessible设置暴露破解
fun4.setAccessible(true);
fun4.invoke(user, new Date());
}
/**
* 获得无数组参数的静态方法
*/
@Test
public void test3() throws Exception {
Class<?> claszz = Class.forName("reflect.User");
Method fun5 = claszz.getDeclaredMethod("fun5");
fun5.invoke(null);
}
/**
* 特殊情况：获得String数组参数的静态方法
*/
@Test
public void test4() throws Exception {
Class<?> claszz = Class.forName("reflect.User");
Method fun6 = claszz.getDeclaredMethod("fun6", String[].class);
// fun6.invoke(null, new String[]{"1","2"}); 是要报错的，因为JDK4是把字符数组当做一个个对象解析
// 以下两种方式解决：
fun6.invoke(null, (Object) new String[]{"1", "2"});
fun6.invoke(null, new Object[]{new String[]{"1", "2"}});
}
} 一般来说成员属性都是私有的：getDeclaredField（setAccessible）后set值
public class Demo3 {
/**
* 获取非静态的私有成员变量
*/
@Test
public void test1() throws Exception {
Class<?> userClass = Class.forName("bean.User");
User user = (User) userClass.newInstance();
Field id = userClass.getDeclaredField("id");
id.setAccessible(true);
id.set(user, 2);
Field name = userClass.getDeclaredField("name");
name.setAccessible(true);
name.set(user, "李四");
System.out.println(user);
}
/**
* 获取静态成员变量
*/
@Test
public void test2() throws Exception {
Class<?> userClass = Class.forName("bean.User");
Field date = userClass.getDeclaredField("date");
date.setAccessible(true);
date.set(null, new Date());
System.out.println("User的Date:" + User.getDate());
}
} String.intern问题
public class StringQuestion {
/*
intern:返回值一个字符串，内容与此字符串相同，但一定取自具有唯一字符串的池
*/
public static void main(String[] args) {
String str1 = new StringBuilder("58").append("同城").toString();
System.out.println(str1);
System.out.println(str1.intern());
System.out.println(str1 == str1.intern());
System.out.println("-----------");
String str2 = new StringBuilder("ja").append("va").toString();
System.out.println(str2);
System.out.println(str2.intern());
System.out.println(str2 == str2.intern());
}
} 58同城 58同城 true ----------- java java false
第一个是true，第二个为什么是false？
因为JDK初始化sun.misc.Version会在常量池自动生成一个“Java”，与剩余生成的”Java“地址肯定不一样。其余字符串都是用户创建才会在常量池生成
public class Version {
private static final String launcher_name = "java";
private static final String java_version = "1.8.0_271";
private static final String java_runtime_name = "Java(TM) SE Runtime Environment";
private static final String java_profile_name = "";
...
} 异常分类
异常的概念：异常指在方法不能按照 常方式 ，可以通过抛出异常的方式退出 该方法，在异常中封装了方法执行 程中的错误信息及原因 调用 该异 常后可根据务的情况选择处理该异常或者继续抛出。
| 异常分类 | 概述 |
|---|---|
| Error | Java 程序运行错误 ，如果程序在启动时出现 Error 则启 动失败；如果程序在运行过程中出现 Error ，则系统将退出进程 |
| Exception | Java 程序运行异常，即运行中的程序发生了人们不期望发生的情况，可以被Java异常机制处理 |
| Exception分类 | 解释 | 常见 |
|---|---|---|
| RuntimeException | Java 虚拟机正常运行期间抛出的异常 | NullPointerException、ClassCastException ArraylndexOutOfBundsException |
| CheckedException | 编译阶段 Java 编译器会检查 CheckedException 异常井强调捕获 | IO Exception、SQLExcption、ClassNotFoundException |
捕获异常
public class ThrowException {
// 抛出异常的3种方式
// 1.throw：获取方法中的异常，throw 后面的语句块将无法被执行(finally除外)
private static void getThrow() {
String str = "str";
int index = 10;
if (index > str.length()) {
throw new StringIndexOutOfBoundsException("index > str.length");
} else {
System.out.println(str);
}
}
// 2.throws作用在方法上
private static int getThrows(int a, int b) throws Exception {
return a / b;
}
// 3.tryCatch包裹
private static void getTryCatch() {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
System.out.println("最后必须会执行");
}
}
} 内部类
| 内部类 | 解释 |
|---|---|
| 静态内部类 | 可以访问外部类的静态变量和方法 |
| 成员内部类 | 非静态内部类，不能定义静态方法和变量（final除外） |
| 局部内部类 | 类中方法中定义的一个类 |
| 匿名内部类 | 继承一个父类或者实现一个接口的方式直接定义并使用的类 |
public class Outer {
private void test(final int i) {
new Service() {
public void method() {
for (int j = 0; j < i; j++) {
System.out.println("匿名内部类" );
}
}
}.method();
}
}
//匿名内部类必须继承或实现一个已有的接口
interface Service{
void method();
} 泛型标记
泛型上下限
| 泛型上下限 | 解释 |
|---|---|
| <? extends T> | ?是T的子类/T接口的子接口 |
| <? super T> | ?是T的父类/T接口的父接口 |
定义泛型
泛型类
泛型类的使用：类名后<?>
public class TDemo<T> {
private T value;
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public static void main(String[] args) {
TDemo<Integer> tDemo1 = new TDemo<>();
TDemo<String> tDemo2 = new TDemo<>();
tDemo1.setValue(1);
System.out.println(tDemo1.getValue());
tDemo2.setValue("a");
System.out.println(tDemo2.getValue());
}
} 泛型方法
泛型方法使用：在方法返回值前定义泛型<?>，也可以继承一些接口<? extends Comparable<e>></e>
public static <E extends Comparable<E>> void bubbleSort0(E[] arr) {
// 只需要n-1层外部循环
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i && arr[j].compareTo(arr[j + 1]) > 0; j++) {
swap(arr, j, j + 1);
}
}
} 泛型接口
接口<?>,其实现类指定类型如implement 接口
public interface TInterfer<T> {
public T getId();
} public class TInterferImpl implements TInterfer<String> {
@Override
public String getId() {
return UUID.randomUUID().toString().substring(0, 3);
}
} 序列化
| 名词 | 关键字 | 特性 |
|---|---|---|
| 序列化 | implements Serializable | 底层字节数组,保存对象的状态信息，不能保存静态变量 |
| 反序列化 | transient | 被该关键字修饰的，不能被反系列化 |
集合
List、Set、Map
集合中的最上层接口只有2类：Map和Collection，List和Set是Collection的下一层。
| 三者名称 | 特性 | 安全类 | 安全原理 |
|---|---|---|---|
| List | 有序、可重复 | CopyOnWriteArrayList | 读写分离，写时复制 |
| Set | 无需、不可重复 | CopyOnWriteArraySet | 读写分离，写时复制 |
| Map | 键值对形式存储 | ConcurrentMap | 没哈希冲突就CAS，有哈希冲突就Syn加锁 |
LIst
| LIst类 | 底层数据结构 | 特性 | 安全性 |
|---|---|---|---|
| ArrayList | 数据 | 增删慢，查询快， | 不安全，安全需要CopyOnWriteArrayList |
| Vector | 数组 | 增删慢，查询快 | 安全，底层是对每一个结点都加Syn |
| LinkedList | 双向链表 | 增删快，查询慢 | 不安全，安全需要CopyOnWriteLinkedList |
Queue
| Queue | 解释 |
|---|---|
| ArrayBlockingQueue | 数组结构组成的有界阻塞队列 |
| LinkedBlockingQueue | 由链表组成的有界阻塞队列（大小默认是21亿，不推荐默认使用） |
| LinkedBlockingDeque | 由链表结构组成的双向阻塞队列 |
| PriorityBlockingQueue | 支持优先级排序的无界阻塞队列 |
| DelayBlockingQueue | 使用优先级队列实现的延迟无界队列 |
| SynchronousQueue | 不存储元素的阻塞队列=单个元素的队列 |
| LinkedTransferQueue | 由链表结构组成的无界阻塞队列 |
Set
| Set | 底层 | 特性 |
|---|---|---|
| HashSet | HashMap<key,PRESENT> | 无序不重复 |
| TreeSet | 二叉树 | 排序不重复 |
| LinkedHashSet | LinkedHashMap<key,PRESENT> | 可前后遍历，不重复 |
Map
| Map | 底层 | 安全性 |
|---|---|---|
| HashMap | 数组+链表/红黑树 | Map不安全 |
| ConcurrentMap | 数组+链表/红黑树 | 安全，原理是冲突syn+不冲突CAS |
| TreeMap | 二叉树 | 不安全 |
| LinkedHashMap | 双向链表 | 不安全 |
HashMap
| HashMap | 描述 |
|---|---|
| 底层数据结构 | 数组+链表/红黑树 |
| 存储数据流程 | 如下所示 |
| 长度 | 默认16，装载因子为0.75 |
| 阈值 | 扩容成红黑树的阈值为8 |
存储数据的流程
- 对key的hash后获得数组index;2.数组位置为空，初始化容量为16
- 数组位置为空，初试化容量为16
- hash后没有碰撞，就放入数组
- 有碰撞且节点已存在，则替换掉原来的对象
- 有碰撞且节点已经是树结构，则挂载到树上
- 有碰撞且节点已经是链表结构，则添加到链表末尾，并判断链表是否需要转换为树结构（链表结点大于8就转换）
- 完成put操作后，判断是否需要resize()操作
hashMap不安全原因
- 在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。源码是1.7时的 transfer函数，自己点进去看
- 在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。源码是1.8时的resize函数，自己点进去看
HashMap和Hashtable
| 特性 | HashMap | Hashtable |
|---|---|---|
| 安全性 | 不安全，分为1.7和1.8 | 单个线程安全，原因是加了同步锁 |
| hashcode | 对key的hashcode重新计算 | 直接使用key的HashCode |
| key,value | 都可以为null | 都不能为null（注意，idea不会提示报错，但是运行出现空指针异常，源码有提示） |
| 长度 | 默认16，扩容翻倍 | 默认11，扩容+1 |
key,value为空的问题：
public static void main(String[] args) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
hashmap.put(null, null);// hashmap两个都可以存null
Hashtable<Integer, Integer> hashtable = new Hashtable<>();
hashtable.put(null, null);//hashtable任一个都不能存null，但idea不会报错，运行会出现空指针异常
} HashMap的长度为什么是2的幂次方？
答：提高数组利用率，减少冲突（碰撞）的次数，提高HashMap查询效率
// 源码计算index的操作：n是table.length if ((p = tab[i = (n - 1) & hash]) == null)
ConcurrentHashMap
线程安全的底层原理：没有哈希冲突就大量CAS插入+如果有哈希冲突就Syn加锁
TreeMap
treeMap底层使用红黑树，会按照Key来排序
- 如果是字符串，就会按照字典序来排序
- 如果是自定义类，就要使用2种方法指定比较规则
- 实现Compareable接口，但是需要重新定义比较规则就要修改源码，麻烦
- 创建实例时候，传入一个比较器Comparator，重新定义规则不需要修改源码，推荐使用
public class TreeMapDemo {
public static void main(String[] args) {
// treeMap中自定义类需要指定比较器
// 方式一：自定义类实现Comparable接口
TreeMap<User, User> treeMap1 = new TreeMap<>();
// 方式二：创建实例指定比较器Comparator
TreeMap<User, User> treeMap2 = new TreeMap<>(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// 定义比较规则
return 0;
}
});
}
}
public class User implements Comparable {
private String id;
private String username;
@Override
public int compareTo(Object obj) {
// 这里定义比较规则
return 0;
}
} ArrayList和LinkedList
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 底层 | 动态数组，查询快，插入慢 | 双向链表，查询慢，插入快 |
| 安全 | 不安全 | 不安全 |
| 接口 | 都是List接口的实现类，存储有序，可重复 | 都是List接口的实现类，存储有序，可重复 |
Vetor和CopyOnWriteList
list安全类是如下两个：Vetor、CopyOnWriteList； Collections.synchronizedLis是JDK包装实现线程安全的工具类
| Vector | Collections.synchronizedList | CopyOnWriteList | |
|---|---|---|---|
| 线程安全原理 | synchronized加载方法上 | 内部类封装SynchronizedList方法 | 写加锁，读不加锁，通过volatile保证可见性 |
public synchronized int capacity() {
return elementData.length;
}
// Vetor锁都加在方法上
public synchronized int size() {
return elementCount;
}
public synchronized boolean isEmpty() {
return elementCount == 0;
}
...
} static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
// Collections.synchronizedList:内部类SynchronizedList，锁加载内部类里面
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
....
} // CopyOnWriteList 写加锁
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
// CopyOnWriteList是复制数组保证线程安全
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
// CopyOnWriteList 读不加锁，原数组通过 transient volatile保证不可系列化和可见性
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
public E get(int index) {
return get(getArray(), index);
} LinkedHashMap和LinkedHashSet
答：LinkedHashMap可以记录下元素的插入顺序和访问顺序
- LinkedHashMap内部的Entry继承于HashMap.Node，这两个类都实现了Map.Entry<K,V>
- 底层链表是双向链表，Node不光有value，next，还有before和after属性，保证了各个元素的插入顺序
- 通过构造方法public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)， accessOrder传入true可以实现LRU缓存算法（访问顺序）
LRU算法
最近最少使用算法: 根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
public class LRUTest {
// 0.指定map长度size=5
private static final int size = 5;
public static void main(String[] args) {
// 1. LinkedHashMap三大参数，重写removeEldestEntry
Map<String, String> map = new LinkedHashMap<String, String>(size, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > size;
}
};
// 2.添加5个数，使得map满
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println("map:" + map.toString());
// 3.指定map满了，再put就会移除表头第一个元素:1=1
map.put("6", "6");
System.out.println("map:" + map.toString());
// 4.get取出的元素，表示是常用的，放回到表尾
map.get("3");
System.out.println("map:" + map.toString());
}
} 执行结果：
map:{1=1, 2=2, 3=3, 4=4, 5=5}
map:{2=2, 3=3, 4=4, 5=5, 6=6}
map:{2=2, 4=4, 5=5, 6=6, 3=3} 手写LRU算法
public class LRUCache {
// 力扣146同一题
class DoubleNode {
int key;
int value;
DoubleNode pre;
DoubleNode next;
DoubleNode(int key, int value) {
this.key = key;
this.value = value;
}
DoubleNode() {
}
}
private HashMap<Integer, DoubleNode> cache = new HashMap<>();
private int size;
private int capacity;
private DoubleNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.head = new DoubleNode();
this.tail = new DoubleNode();
// 创建伪头部和伪尾部，减少添加和删除的逻辑
head.next = tail;
tail.pre = head;
}
public int get(int key) {
// 1.获取get元素
DoubleNode node = cache.get(key);
// 2.get元素不存就返回-1
if (node == null) {
return -1;
}
// 3.get元素就移动至头部，规定常用元素移动至头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
// 1.获取put元素
DoubleNode node = cache.get(key);
// 2.put元素不存在
if (node == null) {
// 生成它
DoubleNode nowNode = new DoubleNode(key, value);
// 放进cache
cache.put(key, nowNode);
// 添加进头部
addToHead(nowNode);
// 长度++
size++;
// 判断是否超过指定长度
if (size > capacity) {
DoubleNode tail = removeTail();
cache.remove(tail.key);
size--;
}
} else {
// 3.node存在就更新value，然后移动至头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DoubleNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private DoubleNode removeTail() {
DoubleNode del = tail.pre;
removeNode(del);
return del;
}
private void removeNode(DoubleNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DoubleNode node) {
removeNode(node);
addToHead(node);
}
} Iterator和ListIterator
| Iterator | ListIterator | |
|---|---|---|
| 使用集合 | List、set | 只能是List |
| 前后遍历 | 只能想后遍历 | 前后遍历都行 |
public class IteratorDemo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
} 快速失败和安全失败
| fail-fast | fail-safe | |
|---|---|---|
| 报错 | 失败/异常，会立刻报错 | 失败/异常，直接忽略，不会报错 |
| 异常 | 抛出CorrentModificationException | 不会抛出异常 |
| 适用包 | java.util下的集合类 | java.util.concurrent下的集合类 |
| 原理 | 迭代器检查modCount和expectedModCount | CopyOnWriteXX写加锁，读不加锁，两者不冲突 |
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedModCount值，是的话就返回遍历；否则抛出异常，终止遍历
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
...
// modCount记录当前线程更改状态
++modCount;
...
return null;
} 数组和List和遍历转换
| 数组 | List | |
|---|---|---|
| 遍历 | Arrays.toString（arr） | 直接遍历 |
| 相互转换 | 不推荐Arrays.asList(arr)。推荐Collections.singletonList(arr); | arrayList.toArray(new Integer[3]) |
public class ArrayAndList {
public static void main(String[] args) {
// 1.数组遍历:Arrays.toString
int[] arr = {1, 2, 3};
System.out.println(Arrays.toString(arr));
// 2.数组转成list，泛型说明不推荐使用，多此一举
List<int[]> ints1 = Arrays.asList(arr);
List<int[]> ints = Collections.singletonList(arr);
for (int[] anInt : ints) {
System.out.println(Arrays.toString(anInt));
}
System.out.println("------------");
// 3.list遍历：直接遍历即可
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
System.out.println(arrayList);
// 4.list转换成数组，list名.toArray(指定数组类型和长度)
Integer[] integers = arrayList.toArray(new Integer[3]);
System.out.println(Arrays.toString(integers));
}
} JVM
JVM运行机制
内存结构
| 堆 | 方法区 | 栈 | 本地方法栈 | PCR | |
|---|---|---|---|---|---|
| 存放对象 | 实例化对象，分为年轻代、老年代、永久代 | 常量、静态变量、类信息、JIT后代码 | 栈帧（局部变量表、操作数栈、动态链接、方法出口） | 本地Native方法 | 存放当前线程执行的字节码的位置指示器 |
| 私有/共享 | 共享 | 共享 | 私有 | 私有 | 私有 |
| 异常 | OutOfMemoryError | OutOfMemoryError | StackOverflowError | StackOverflowError | 不会抛出异常 |
| 调参 | -Xms、-Xmx、-Xmn | -XX：MetaspaceSize | -Xss |
堆
年轻代：占堆的1/3。分类如下
| 堆分类 | 解释 | 补充 |
|---|---|---|
| Eden | Java新创建的对象，如果新对象属于大对象，直接放到老年代 | 调整老年代对象大小：XX:PretenureSizeThreshold |
| SurvivorFrom | 将上一次MinorGC的幸存者作为这一次MinorGC的扫描对象 | |
| SurvivorTo | 上一次MinorGC的幸存者，对象晋升为老年代次数默认15次 | 调整晋升为老年代次数：XX:MaxTenuringThreshold |
老年代：占堆的2/3
永久代：存放永久的Class和Meta数据，不会发生垃圾回收
如何确定垃圾
| 引用计数法 | GC Roots | |
|---|---|---|
| 优点 | 简单 | 不会产生循环依赖问题 |
| 缺点 | 无法解决对象之间的循环依赖问题 | 比引用计数法复杂 |
| 对象 | 堆中存在的对象 | 栈引用的对象、方法区中的静态引用、JNI中的引用 |
垃圾回收算法
| 名称 | 优点 | 缺点 |
|---|---|---|
| 复制算法 | 最简单高效，不会产生碎片。年轻代默认算法 | 利用率低下，只有一半 |
| 标记清除算法 | 利用率较高 | 效率低+空间碎片问题 |
| 标记整理算法 | 解决了空间碎片问题 | 效率还是不高 |
| 分代收集算法 | 新生代用复制算法；老年代用后两者结合算法 | 并不是一种算法，而是一种思想 |
标记清除算法
复制算法
标记整理算法
分代收集算法
四种引用状态
强引用：普通存在， P p = new P()，只要强引用存在，垃圾收集器永远不会回收掉被引用的对象。是造成内存泄露的主要原因。
软引用：通过SoftReference类来实现软引用，在内存不足的时候会将这些软引用回收掉。
弱引用：通过WeakReference类来实现弱引用，每次垃圾回收的时候肯定会回收掉弱引用。
虚引用：也称为幽灵引用或者幻影引用，通过PhantomReference类实现。设置虚引用只是为了对象被回收时候收到一个系统通知。
垃圾收集器
生产环境中常用的GC收集器：新生代ParNewGC，老年代CMSGC
| 名称 | 周期 | 算法 | 特点 |
|---|---|---|---|
| Serial收集器 | 新生代 | 单线程复制算法 | 1.单线程收集器；2.缺点是STW |
| ParNew收集器 | 新生代 | 多线程复制算法 | Serial多线程版本 |
| Parallel Scavenge收集器 | 新生代 | 多线程复制算法 | 1.吞吐量优先；2.自适应调节吞吐量策略；3.多线程并行收集 |
| Serial Old收集器 | 老年代 | 单线程标记整理算法 | Serial老年代版本 |
| Parallel Old收集器 | 老年代 | 多线程标记整理算法 | Parallel Scavenge老年代版本 |
| CMS收集器 | 老年代 | 多线程标记清除算法 | 并发收集、低停顿、缺点还是会产生空间碎片 |
| G1收集器 | 老年代 | 标记整理+清除算法 | 并行与并发、分代收集、空间整理、可预测停顿 |
Serial收集器
ParNew收集器
Parallel Scavenge收集器
Serial Old收集器
ParallelOld收集器
CMS收集器
概念：一种以获取最短回收停顿时间为目标的GC。CMS是基于标记-清除算法实现的，是一种老年代收集器，通常与ParNew一起使用。
CMS的垃圾收集过程分为5步：有4步的说法，5步的说法，7步的说法，这里按照5步的说法
初始标记：需要“Stop the World”，初始标记仅仅只是标记一下GC Root能直接关联到的对象，速度很快。
并发标记：是主要标记过程，这个标记过程是和用户线程并发执行的。
如果在重新标记之前刚好发生了一次MinorGC，会不会导致重新标记阶段Stop the World时间太长？
答：不会的，在并发标记阶段其实还包括了一次并发的预清理阶段，虚拟机会主动等待年轻代发生垃圾回收，这样可以将重新标记对象引用关系的步骤放在并发标记阶段，有效降低重新标记阶段Stop The World的时间。
重新标记：需要“Stop the World”，为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录（停顿时间比初始标记长，但比并发标记短得多）。
并发清除：和用户线程并发执行的，基于标记结果来清理对象。
并发重置：重置CMS的数据结构，等待下一次垃圾回收，与用户线程同时运行
CMS优缺点：
| CMS优点 | CMS缺点 |
|---|---|
| 并发收集，停顿时间低 | 对CPU资源非常敏感；收集过程中会产生浮动垃圾；标记-清除方式会产生内存碎片 |
由于在应用运行的同时进行垃圾回收，所以有些垃圾可能在垃圾回收进行完成时产生，这样就造成了“Floating Garbage”，这些垃圾需要在下次垃圾回收周期时才能回收掉。所以，并发收集器一般需要20%的预留空间用于这些浮动垃圾。
CMS时特殊情况：concurrent-mode-failure
现象说明：在 CMS GC 过程中，如果在并行清理的过程中老年代的空间不足以容纳应用产生的垃圾，则会抛出 “concurrent mode failure”。
影响：老年代的 CMS GC 会转入 STW 的串行，所有应用线程被暂停，停顿时间变长。
可能的原因及解决方案：
- 老年代使用太多时才触发 CMS GC，可以调整
- XX:CMSInitiatingOccupancyFraction=N，告诉虚拟机当 old 区域的空间上升到 N% 的时候就开启 CMS； - CMS GC 后空间碎片太多，可以加上
- XX:+UseCMSCompactAtFullCollection和-XX:CMSFullGCsBeforeCompaction=n参数，表示经过 n 次 CMS GC 后做一次碎片整理。 - 垃圾产生速度超过清理速度（比如说新生代晋升到老年代的阈值过小、Survivor 空间过小、存在大对象等），可以通过调整对应的参数或者关注程序代码来解决。
G1收集器
JVM常用调参
public static void main(String[] args) {
String JAVA_OPTS =
"-Xms4096m –Xmx4096m " +
"-XX:NewRatio=2 -XX:SurvivorRatio=8 -Xloggc:/home/work/log/serviceName/gc.log -XX:+PrintGCDetails " +
"-XX:+PrintGCTimeStamps -XX:+PrintGCApplicationStoppedTime -XX:+UseConcMarkSweepGC -XX:+UseParNewGC" +
"-XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSCompactAtFullCollection -XX:CMSFullGCsBeforeCompaction=10 ";
}
| JVM 参数 | 说明 |
|---|---|
| Xms | 初始堆大小 |
| Xmx | 最大堆大小 |
| Xmn | 年轻代大小 |
| Xss | 每个线程的堆栈大小 |
| MetaspaceSize | 首次触发 Full GC 的阈值，该值越大触发 Metaspace GC 的时机就越晚 |
| MaxMetaspaceSize | 设置 metaspace 区域的最大值 |
| +UseConcMarkSweepGC | 设置老年代的垃圾回收器为 CMS |
| +UseParNewGC | 设置年轻代的垃圾回收器为并行收集 |
| CMSFullGCsBeforeCompaction=5 | 设置进行 5 次 full gc（CMS）后进行内存压缩。由于并发收集器不对内存空间进行压缩 / 整理，所以运行一段时间以后会产生 "碎片"，使得运行效率降低。此值设置运行多少次 full gc 以后对内存空间进行压缩 / 整理 |
| +UseCMSCompactAtFullCollection | 在 full gc 的时候对内存空间进行压缩，和 CMSFullGCsBeforeCompaction 配合使用 |
| +DisableExplicitGC | System.gc () 调用无效 |
| -verbose:gc | 显示每次 gc 事件的信息 |
| +PrintGCDetails | 开启详细 gc 日志模式 |
| +PrintGCTimeStamps | 将自 JVM 启动至今的时间戳添加到 gc 日志 |
| -Xloggc:/home/admin/logs/gc.log | 将 gc 日导输出到指定的 /home/admin/logs/gc.log |
| +HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=/home/admin/logs | 当堆内存空间溢出时输出堆的内存快照到指定的 /home/admin/logs |
类加载阶段
加载：JVM读取Class文件，根据Class文件描述创建Java.lang.Class对象的过程
验证：确保Class文件是否符合虚拟机的要求
准备：为类变量分配内空间并设置变量的初始值，初始值指不同数据类型的默认值，但是final和非final不一样
public class InitFinal {
// 没有加final：value1在类初始化的“准备”阶段分配为int类型的默认值0，在“初始化”阶段才分配为10
private static int value1 = 10;
// final表示：value2在类初始化的“准备”阶段分配为10
private static final int value2 = 10;
} 解析：将常量池中的符号引用替换为直接引用
初始化：执行类构造器的<client>方法为类进行初始化，引出了下面的类初始化顺序的面试题</client>
类初始化阶段
- 父类的静态方法、静态代码块
- 子类的静态方法、静态代码块
- 父类被重写的静态方法，父类也要先执行；父类被重写的非静态方法，父类不执行
- 子类的重写父类的非静态方法
- 父类的非静态代码块、构造器
- 子类的非静态代码块、构造器
public class Father {
// 这个方法被子类重写，类初始化是父类被重写的不执行，调到执行子类重写的方法
private int i = test();
private static int j = method();
// 2 静态代码块
static{
System.out.print("(1)");
}
// 7 父类构造方法
Father(){
System.out.print("(2)");
}
// 6 非静态代码块
{
System.out.print("(3)");
}
// 这个方法被子类重写，类初始化是父类被重写的不执行
public int test(){
System.out.print("(4)");
return 1;
}
// 1 执行静态方法
public static int method(){
System.out.print("(5)");
return 1;
}
} public class Son extends Father{
// 8 父类类初始化完成，顺序执行子类非静态方法，又输出一遍9
private int i = test();
private static int j = method();
// 4 静态代码块
static {
System.out.print("(6)");
}
// 10 子类构造方法
Son() {
System.out.print("(7)");
}
// 9 子类非静态代码块
{
System.out.print("(8)");
}
// 5 被重写的非静态方法test方法
public int test() {
System.out.print("(9)");
return 1;
}
// 3 静态方法
public static int method() {
System.out.print("(10)");
return 1;
}
public static void main(String[] args) {
// 实例化初始化过程1:包含子父类静态加载
new Son();
// 实例化初始化过程2:不包含所有的静态加载
new Son();
}
} 执行结果：
(5)(1)(10)(6)(9)(3)(2)(9)(8)(7) (9)(3)(2)(9)(8)(7)
类加载器
类加载机制：JVM通过双亲委派进行类的加载，当某个类加载器在接到加载类的请求时，将加载任务依次委托给上一级加载器，如果分类能加载，就父类加载；父类不能记载，再子类往下依次判断是否能加载
- 启动类加载器（bootstrapClassLoader）：负责加载支撑JVM运行的位于JRE的
lib目录下的核心类库，比如 rt.jar、charsets.jar等。底层是用C++书写，所以JVM输出为null。 - 扩展类加载器（extClassLoader）：负责加载支撑JVM运行的位于JRE的lib目录下的
ext扩展目录中的JAR 类包 - 应用类加载器（appClassLoader）：用户
classpath下自己写的类 - 自定义加载器（重写某些方法）：负责加载用户
自定义路径下的类包
public class ClassLoaderDemo {
public static void main(String[] args) {
ClassLoader bootstrapCL = String.class.getClassLoader();
System.out.println("启动类加载器：" + bootstrapCL);
ClassLoader extCL = DESCipher.class.getClassLoader();
System.out.println("扩展类加载器：" + extCL);
ClassLoader appCL = ClassLoaderDemo.class.getClassLoader();
System.out.println("应用类加载器：" + appCL);
}
} 执行结果：
启动类加载器：null// 启动类加载器调用底层c++,无返回值 扩展类加载器：sun.misc.Launcher$ExtClassLoader@873330 应用类加载器：sun.misc.Launcher$AppClassLoader@b4aac2
双亲委派机制
概念：加载某个类时会先找父亲加载，层层向上，如果都不行，再逐步向下由儿子加载。
双亲委派源码：ClassLoader的loadClass()方法
protected Class<?> loadClass(String name, boolean resolve)
throws ClassNotFoundException
{
synchronized (getClassLoadingLock(name)) {
// First, check if the class has already been loaded
Class<?> c = findLoadedClass(name);
if (c == null) {
long t0 = System.nanoTime();
try {
if (parent != null) {
c = parent.loadClass(name, false);
} else {
c = findBootstrapClassOrNull(name);
}
} catch (ClassNotFoundException e) {
// ClassNotFoundException thrown if class not found
// from the non-null parent class loader
}
if (c == null) {
// If still not found, then invoke findClass in order
// to find the class.
long t1 = System.nanoTime();
c = findClass(name);
// this is the defining class loader; record the stats
sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
sun.misc.PerfCounter.getFindClasses().increment();
}
}
if (resolve) {
resolveClass(c);
}
return c;
}
} 设计双亲委派机制的好处：
- 沙箱安全机制，保证安全性：比如自己写的String类不会被加载，防止JDK核心API不会被随意篡改
- 避免类的重复加载，保证唯一性：当父类加载过该类后，子类不会再加载，保证了被加载类的唯一性
自定义类加载器和打破双亲委派机制
自定义类加载器只需要extends ClassLoader 类，该类有两个核心方法：
loadClass(String, boolean)，实现了双亲委派机制findClass()，默认实现是空方法，所以我们自定义类加载器主要是重写findClass方法。
package 基础面试.JVM;
import java.io.FileInputStream;
import java.lang.reflect.Method;
public class MyClassLoader {
static class MyStaticCL extends ClassLoader {
private String classPath;
public MyStaticCL(String classPath) {
this.classPath = classPath.replaceAll("\\.", "/");
}
private byte[] loadByte(String name) throws Exception {
name = name.replaceAll("\\.", "/");
FileInputStream fis = new FileInputStream(classPath + "/" + name + ".class");
int len = fis.available();
byte[] data = new byte[len];
fis.read(data);
fis.close();
return data;
}
// 自定义类加载器：重写findClass
@Override
protected Class<?> findClass(String name) throws ClassNotFoundException {
try {
byte[] data = loadByte(name);
// 转换成class对象返回
return defineClass(name, data, 0, data.length);
} catch (Exception e) {
e.printStackTrace();
throw new ClassNotFoundException();
}
}
// 打破双亲委派：重写loadClass
@Override
public Class<?> loadClass(String name, boolean resolve) throws ClassNotFoundException {
synchronized (getClassLoadingLock(name)) {
Class<?> c = findLoadedClass(name);
if (c == null) {
long t0 = System.nanoTime();
long t1 = System.nanoTime();
// ，否则使用双亲委派
if (!name.startsWith("基础面试.JVM")) {
c = this.getParent().loadClass(name);
} else {
c = findClass(name);
}
sun.misc.PerfCounter.getParentDelegationTime().addTime(t1 - t0);
sun.misc.PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
sun.misc.PerfCounter.getFindClasses().increment();
}
if (resolve) {
resolveClass(c);
}
return c;
}
}
}
public static void main(String[] args) throws Exception {
String classpath = "E:\\product\\test";
// 指定类加载器：E:\product\test\基础面试\JVM下的user.class
String userClass = "基础面试.JVM.User";
MyStaticCL classLoader = new MyStaticCL(classpath);
Class<?> userClass1 = classLoader.loadClass(userClass);
Object object = userClass1.newInstance();
Method method = userClass1.getDeclaredMethod("print", null);
method.invoke(object, null);
System.out.println("自定义加载器名字:" + userClass1.getClassLoader().getClass().getName());
}
}
package 基础面试.JVM;
public class User {
private String userName ;
public String getUserName() {
return userName;
}
public void setUserName(String userName) {
this.userName = userName;
}
public void print(){
System.out.println("MyStaticCL加载的User.print方法");
}
} 执行结果：
MyStaticCL加载的User.print方法 自定义加载器名字:基础面试.JVM.MyClassLoader$MyStaticCL
JUC
JMM
原子性，可见性与有序性
原子性
| 原子性 | 解释 |
|---|---|
| 概念 | 执行线程对共享资源发生写操作，其他线程只能看到结果，而中间过程看不到 |
| 例子 | 银行转账流程中，A账户减少了100元，那么B账户就会多100元，这两个动作是一个原子操作。我们不会看到A减少了100元，但是B余额保持不变的中间结果 |
| 实现 | 加锁；CAS；基本和引用类型中除了Long和Double的写操作都是原子类型 |
可见性
| 可见性 | 解释 |
|---|---|
| 概念 | 一个线程对于共享变量的更新，对于后续访问该变量的线程是否可见的问题。 |
| 例子和实现 | 请看volatile的模拟可见性代码 |
有序性
| 有序性 | 解释 |
|---|---|
| 概念 | 计算机在执行程序时，为了提高性能，存在编译器和处理器对指令重排的问题 |
| 例子 | 如下的Demo1、Demo2 |
| 实现 | 使用volatile |
/*
1 分配对象的内存空间（堆上）
2 初始化对象
3 设置instance指向刚分配的内存地址
第二步和第三步可能会发生重排序，导致引用型变量指向了一个不为null但是也不完整的对象。（在多线程下的单例模式中，我们必须通过volatile来禁止指令重排序）
*/
Instance instance = new Instance() public class ReSortDemo {
int a;
boolean flag = false;
// 重排序demo1
public void method1() {
// 这里可能出现指令重排问题：
// 线程一：编译器优化使得，flag先为true，然后线程二走method2进去，a=0+1=1,出现线程不安全的问题
a = 1;
flag = true;
}
public void method2() {
if (flag) {
a = a + 1;
System.out.println("最终的a:" + a);
}
}
// 重排序demo2：
void resetSort() {
int a = 1; // 语句1
int b = 2; // 语句2
int x = a + 1;// 语句3
int y = a * a;// 语句4
/* 指令重排：编译器优化、会将语句顺序打乱
重排可能性：1234、1324、2134
但是4是不能在1之前的，因为编译器优化会保证数据结果之间的依赖性
*/
}
} 乐观锁和悲观锁
| 乐观锁 | 悲观锁 | |
|---|---|---|
| 概念 | 读数据时，其他线程不会修改；写数据时再判断是否被修改 | 读写数据时，其他线程都会修改 |
| 加锁 | 写时先读出当前版本号，然后加锁 | 每次读写都加锁 |
| 原理 | CAS比较并交换 | AQS抽象队列同步器 |
Synchronized
概念：synchronized是关键字，是一个独占悲观锁，也是可重入锁。
底层原理：
- 进入时，执行monitorenter，将计数器+1，释放锁monitorexit时，计数器-1
- 当一个线程判断到计数器为0时，则当前锁空闲，可以占用；反之，当前线程进入等待状态
作用范围：
- 作用成员变量和非静态方法，锁的是对象的实例=this对象
- 作用静态方法，锁的是Class实例，因为静态方法需要Class而不属于对象
- 作用代码块，锁的是所有代码块中的对象
Reentrant
概念：继承里Lock接口，是一个可重入独占锁，默认是非公平锁。
底层原理：通过AQS来实现锁的获取和释放
如何避免死锁：
- 晌应中断
- 可轮询锁
- 定时锁
public class InterruptDeadLock {
private ReentrantLock lock1 = new ReentrantLock();
private ReentrantLock lock2 = new ReentrantLock();
public Thread lock1() {
Thread t = new Thread(() -> {
try {
lock1.lockInterruptibly();
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
lock2.lockInterruptibly();
System.out.println(Thread.currentThread().getName() + ",执行完毕");
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
if (lock1.isHeldByCurrentThread()) {
lock1.unlock();
}
if (lock2.isHeldByCurrentThread()) {
lock2.unlock();
}
System.out.println(Thread.currentThread().getName() + ",finally退出完毕");
}
});
t.start();
return t;
}
public Thread lock2() {
Thread t = new Thread(() -> {
try {
lock2.lockInterruptibly();
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
lock1.lockInterruptibly();
System.out.println(Thread.currentThread().getName() + ",执行完毕");
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
if (lock1.isHeldByCurrentThread()) {
lock1.unlock();
}
if (lock2.isHeldByCurrentThread()) {
lock2.unlock();
}
System.out.println(Thread.currentThread().getName() + ",finally退出完毕");
}
});
t.start();
return t;
}
public static void main(String[] args) {
long time = System.currentTimeMillis();
InterruptDeadLock interruptDeadLock = new InterruptDeadLock();
Thread t1 = interruptDeadLock.lock1();
Thread t2 = interruptDeadLock.lock2();
// 出现死锁，t2就开始释放锁
while (true) {
if (System.currentTimeMillis() - time >= 3000) {
t2.interrupt();
}
}
}
} java.lang.InterruptedException Thread-0,执行完毕 Thread-0,finally退出完毕 Thread-1,finally退出完毕
volatile
| 名称 | 原子性 | 可见性 | 有序性 |
|---|---|---|---|
| 是否保证 | 不保证，原因请看下面模拟的代码 | 保证 | 保证 |
| 底层原理 | 编译器优化指令重排，volatile不能保证 | 修改汇编Lock前缀指令，监听MESI缓存一致性协议 | 读写的内存屏障指令 |
模拟原子性：volatile不保证可见性，使用AtomicInteger就可以保证原子性
// 不保证原子性：使用javap -c反编译查看原因
private static void NotAutomaticByVolatile() {
// 1.资源类
MyResources myResources = new MyResources();
// 2.模拟volatile不保证原子性
for (int i = 0; i < 20; i++) {
new Thread(() -> {
for (int j = 0; j < 1000; j++) {
myResources.add1();
}
}, String.valueOf(i)).start();
}
// 3.默认的2个线程是main和GC，所以让大于这个2个线程的等待
while (Thread.activeCount() > 2) {
Thread.yield();
}
// 4.volatile修饰的共享变量，不能保证原子性
System.out.println(Thread.currentThread().getName() + ",data:" + myResources.data);
}
public class MyResources {
volatile int data = 0;
void add() {
this.data = 1;
}
void add1() {
this.data++;
}
} 
模拟可见性：volatile是一个轻量级的同步锁，保证可见性
private static void seeOkByVolatile() {
MyResources myResources = new MyResources();
new Thread(() -> {
System.out.println(Thread.currentThread().getName() + ",进入啦");
try {
TimeUnit.SECONDS.sleep(3);
} catch (InterruptedException e) {
e.printStackTrace();
}
myResources.add();
System.out.println(Thread.currentThread().getName() + ",已经修改data：" + myResources.data);
}, "线程A").start();
while (myResources.data == 0) {
/* System.out.println(Thread.currentThread().getName() + ",while等待");*/
}
System.out.println(Thread.currentThread().getName() + ",模拟结束,data:" + myResources.data);
}
public class MyResources {
volatile int data = 0;
void add() {
this.data = 1;
}
} volatile实现可见性的底层原理：
模拟有序性：单例设计模式
public class SingletonDemo {
private static volatile SingletonDemo instance;
private SingletonDemo() {
System.out.println(Thread.currentThread().getName() + " 线程，创建实例了");
}
// 单线程下的单例设计模式是不安全的，会重复new 实例
public static SingletonDemo getInstance() {
if (instance == null) {
instance = new SingletonDemo();
}
return instance;
}
// 共享变量未加volatile修饰的双端锁：由于指令重排序，还是有线程不安全的问题
public static SingletonDemo getInstance1() {
if (instance == null) {
synchronized (SingletonDemo.class) {
if (instance == null) {
instance = new SingletonDemo();
}
}
}
return instance;
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
new Thread(() -> {
SingletonDemo.getInstance1();
}, String.valueOf(i)).start();
}
}
} 执行结果：无论多少次，就只能有一个线程创建实例
0 线程，创建实例了
volatile实现有效性底层原理：读写的内存屏障指令
原子性和CAS
AtomicInteger和CAS
| AtomicInteger | 解释 |
|---|---|
| 概念 | AtomicInteger 内部使用 CAS 原子语义来处理加减等操作 |
| CAS底层原理 | 自旋锁+Unsafe类（原子操作） |
| 缺点 | 循环时间长，开销大；只能保证单个共享变量的原子操作；存在ABA问题 |
// 不保证原子性：使用javap -c反编译查看原因
private static void atomicByAtomicInteger() {
// 1.资源类
MyResources myResources = new MyResources();
// 2.atomicInteger保证原子性
for (int i = 0; i < 20; i++) {
new Thread(() -> {
for (int j = 0; j < 1000; j++) {
myResources.add1();// i++等操作是不保证原子性
myResources.addByAtomic();// 使用automicInteger保证原子性
}
}, String.valueOf(i)).start();
}
// 3.默认的2个线程是main和GC，所以让大于这个2个线程的等待
while (Thread.activeCount() > 2) {
Thread.yield();
}
System.out.println(Thread.currentThread().getName() + ",data:" + myResources.data);
System.out.println(Thread.currentThread().getName() + ",atomicInteger:" + myResources.atomicInteger);
}
public class MyResources {
volatile int data = 0;
AtomicInteger atomicInteger = new AtomicInteger();
void add() {
this.data = 1;
}
void add1() {
this.data++;
}
void addByAtomic() {
this.atomicInteger.getAndIncrement();
}
} ABA问题
CAS会出现ABA问题：自旋操作只关心A和A的结果，中间B可能出现很多次，于是线程不安全
public class ABAQuestion {
public static void main(String[] args) {
AtomicReference<Integer> reference = new AtomicReference<>(1);
new Thread(() -> {
reference.compareAndSet(1, 2);
reference.compareAndSet(2, 1);
}, "线程1").start();
new Thread(() -> {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
reference.compareAndSet(1, 1000);
System.out.println(Thread.currentThread().getName() + ",update:" + reference.get());
}, "线程2").start();
}
} 解决ABA问题
解决ABA问题：使用AtomicStampedReference每次CAS指定版本号/时间戳
public class ABASolution {
public static void main(String[] args) {
AtomicStampedReference<Integer> stampedReference = new AtomicStampedReference<>(100, 1);
new Thread(() -> {
int stamp = stampedReference.getStamp();
System.out.println(Thread.currentThread().getName() + " 版本号1:" + stamp);
//暂停1s等t2线程
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
stampedReference.compareAndSet(100, 101, stamp, stamp + 1);
System.out.println(Thread.currentThread().getName() + " 版本号2:" + stampedReference.getStamp());
stampedReference.compareAndSet(101, 100, stampedReference.getStamp(), stampedReference.getStamp() + 1);
System.out.println(Thread.currentThread().getName() + " 版本号3:" + stampedReference.getStamp());
System.out.println(Thread.currentThread().getName() + " 当前实际值:" + stampedReference.getReference());
}, "t1").start();
new Thread(() -> {
int exceptStamp = stampedReference.getStamp();
System.out.println(Thread.currentThread().getName() + " 期望版本号:" + exceptStamp);
//暂停3s等t1线程
try {
TimeUnit.SECONDS.sleep(3);
} catch (InterruptedException e) {
e.printStackTrace();
}
// t1 线程执行完毕后，版本号 = 3 与 这里的 exceptStamp永不相同，所以执行会失败
boolean result = stampedReference.compareAndSet(100, 200, exceptStamp, exceptStamp + 1);
int nowStamp = stampedReference.getStamp();
System.out.println(Thread.currentThread().getName() + " 修改值结果:" + result + " 当前版本号：" + nowStamp + " 期望版本号:" + exceptStamp);
System.out.println(Thread.currentThread().getName() + " 当前实际值:" + stampedReference.getReference());
}, "t2").start();
}
} 执行结果：
t1 版本号1:1 t2 期望版本号:1 t1 版本号2:2 t1 版本号3:3 t1 当前实际值:100 t2 修改值结果:false 当前版本号：3 期望版本号:1 t2 当前实际值:100
单例设计模式
6种常见的单例模式写法
public class Singleton1 {
private static Singleton1 instance;
private Singleton1() {
}
// 方式1：懒汉式，线程不安全
public static Singleton1 getInstance() {
if (instance == null) {
instance = new Singleton1();
}
return instance;
}
} public class Singleton2 {
private static Singleton2 instance;
private Singleton2() {
}
// 方式2：懒汉式，线程安全，加了synchronized
public static synchronized Singleton2 getInstance() {
if (instance == null) {
instance = new Singleton2();
}
return instance;
}
} public class Singleton3 {
private static Singleton3 instance = new Singleton3();
private Singleton3() {
}
// 方式2：饿汉式，线程安全，因为classloader机制避免了多线程的同步问题
public static synchronized Singleton3 getInstance() {
return instance;
}
}
public class Singleton4 {
// volatile防止代码指令重排
private volatile static Singleton4 instance;
private Singleton4() {
}
// 方式4：双端锁+volatile
public static Singleton4 getInstance() {
// 双端锁提高效率
if (instance == null) {
synchronized (Singleton4.class) {
if (instance == null) {
instance = new Singleton4();
}
}
}
return instance;
}
} public class Singleton5 {
private Singleton5() {
}
private static class SingletonHandle {
private static final Singleton5 INSTANCE = new Singleton5();
}
// 方式5：静态内部类，比方式4更合理，因为内部类被装载了，才会使用；并且类加载机制保障了线程安全
public static Singleton5 getInstance() {
return SingletonHandle.INSTANCE;
}
} public enum Singleton6 {
INSTANCE;
// 方式6：枚举，更简洁，自动支持序列化机制，绝对防止多次实例化。
public void whateverMethod() {
}
} 集合不安全
并发修改异常：ConcurrentModificationException
// 普通的集合类都是线程不安全的:java.util.ConcurrentModificationException
private static void ListIsNotSafe() {
List<String> list = new ArrayList<>();
for (int i = 0; i < 30; i++) {
new Thread(() -> {
list.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(list.toString());
}, String.valueOf(i)).start();
}
} 集合安全的方法
集合安全：
1.老API：Vector
2.集合安全工具类：Collections.synchronizedList
3.读写锁：new CopyOnWriteArrayList<>() private static void ListSafe() {
List<String> list = new ArrayList<>();
List<String> list1 = new Vector<>();
List<String> list2 = Collections.synchronizedList(list);
List<String> list3 = new CopyOnWriteArrayList<>();
for (int i = 0; i < 30; i++) {
new Thread(() -> {
list.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(list.toString());
}, String.valueOf(i)).start();
}
} CopyOnWrite
底层原理：读写分离，写时复制
// CopyOnWriteArrayList的add源码
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
} HashSet底层
底层就是HashMap，但是add（e），是将key=e，value= PRESENT(map中的对象关联的虚拟值)
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
...
public boolean add(E e) {
return map.put(e, PRESENT)==null;
} 重入锁
Syn是可重入锁
class Phone {
public synchronized void method1() {
System.out.println(Thread.currentThread().getName() + ",进入method1");
method2();
}
private synchronized void method2() {
System.out.println(Thread.currentThread().getName() + ",进入method2");
}
}
public class SynIsRepeatableLock {
public static void main(String[] args) {
Phone phone = new Phone();
new Thread(() -> {
phone.method1();
}, "线程1").start();
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
new Thread(() -> {
phone.method1();
}, "线程2").start();
}
} ReentrantLock是重入锁：（补充）加锁几次和解锁几次必须配对，如果配对都会生效
class Resources implements Runnable {
Lock lock = new ReentrantLock();
@Override
public void run() {
method1();
}
// 补充：加锁几次和解锁几次必须配对，如果配对都会生效
private void method1() {
lock.lock();
lock.lock();
System.out.println(Thread.currentThread().getName() + ",进入method1");
method2();
lock.unlock();
lock.unlock();
}
private void method2() {
lock.lock();
System.out.println(Thread.currentThread().getName() + ",进入method2");
lock.unlock();
}
}
public class ReenIsRepeatableLock {
public static void main(String[] args) {
Resources resources = new Resources();
Thread t1 = new Thread(resources);
Thread t2 = new Thread(resources);
t1.start();
t2.start();
}
} 自旋锁
| 自旋锁 | 解释 |
|---|---|
| 概念 | 正在获取锁的现在不会立刻阻塞，会循环等待其他线程释放锁的资源 |
| 优点 | 减少上下文线程切换的消耗 |
| 缺点 | 循环等待，消耗的是CPU资源 |
手写一个自旋锁：
class MyResource {
}
public class WhileLockDemo {
AtomicReference<MyResource> atomicReference = new AtomicReference<>();
MyResource myResource = new MyResource();
private void method1() {
System.out.println(Thread.currentThread().getName() + ",加锁啦");
while (!atomicReference.compareAndSet(null, myResource)) {
}
}
private void method2() {
atomicReference.compareAndSet(myResource, null);
System.out.println(Thread.currentThread().getName() + ",解锁啦");
}
public static void main(String[] args) {
WhileLockDemo demo = new WhileLockDemo();
new Thread(() -> {
demo.method1();
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
demo.method2();
}, "线程1").start();
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
new Thread(() -> {
demo.method1();
demo.method2();
}, "线程2").start();
}
} 读写锁
class MyCache {
//缓存应用的资源，必须使用volatile修饰
private volatile Map<String, Object> map = new HashMap<>();
//加入读写锁
private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
/**
* 模拟写锁上锁解锁
*/
public void put(String key, Object value) {
//写锁上锁
readWriteLock.writeLock().lock();
try {
System.out.println(Thread.currentThread().getName() + "\t 正在写入，不可共享");
map.put(key, value);
//模拟网络拥堵
try {
TimeUnit.MILLISECONDS.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "\t 写入完成");
} catch (Exception e) {
e.printStackTrace();
} finally {
//写锁解锁
readWriteLock.writeLock().unlock();
}
}
/**
* 模拟读锁上锁解锁
*/
public void get(String key) {
//读锁上锁
readWriteLock.readLock().lock();
try {
System.out.println(Thread.currentThread().getName() + "\t 正在读取，可共享");
Object result = map.get(key);
//模拟网络拥堵
try {
TimeUnit.MILLISECONDS.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "\t 读取完成：" + result);
} catch (Exception e) {
e.printStackTrace();
} finally {
//读锁解锁
readWriteLock.readLock().unlock();
}
}
} public class ReadWriteLockDemo {
public static void main(String[] args) {
//模拟读写锁：主要是学习map用volatile修饰
MyCache cache = new MyCache();
//写锁：独占
for (int i = 1; i <= 5; i++) {
final int tempInt = 1;
new Thread(() -> {
cache.put(tempInt + "", tempInt + "");
}, String.valueOf(i)).start();
}
//读锁：可共享
for (int i = 1; i <= 5; i++) {
final int tempInt = 1;
new Thread(() -> {
cache.get(tempInt + "");
}, String.valueOf(i)).start();
}
}
} 执行结果：
2 正在写入，不可共享 2 写入完成 1 正在写入，不可共享 1 写入完成 3 正在写入，不可共享 3 写入完成 4 正在写入，不可共享 4 写入完成 5 正在写入，不可共享 5 写入完成 1 正在读取，可共享 2 正在读取，可共享 3 正在读取，可共享 4 正在读取，可共享 5 正在读取，可共享 3 读取完成：1 2 读取完成：1 1 读取完成：1 5 读取完成：1 4 读取完成：1
Reentrant、Semaphore、CountDownLatch、CyclicBarrier区别
| Reentrant | Semaphore | CountDownLatch | CyclicBarrier |
|---|---|---|---|
| 一次只允许一个线程访问某个资源 | 可以指定多个线程同时访问某个资源 | 一个或者多个线程，等待其他多个线程完成某件事情之后才能执行 | 多个线程互相等待，直到达到同一个同步点（屏障），再继续一起执行。 |
Semaphore
概念：一种基于技术的信号量，调用方法是acquire()、release()
public class SemaphoreDemo {
public static void main(String[] args) {
// 模拟3个车位，同时只能有3个线程同时访问，形参=1就是syn
// 1.同步器semaphore（信号量）：指定X个线程可以获取资源
Semaphore semaphore = new Semaphore(3);
// 2.创建4个线程=有4个车位
for (int i = 1; i <= 4; i++) {
new Thread(() -> {
try {
// 3.信号量开始计算
semaphore.acquire();
System.out.println(Thread.currentThread().getName() + "\t 抢到车位");
TimeUnit.SECONDS.sleep(1);
System.out.println(Thread.currentThread().getName() + "\t 停1s后离开车位");
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
// 4.信号量释放计数
semaphore.release();
}
}, String.valueOf(i)).start();
}
}
} 执行结果：
1 抢到车位 3 抢到车位 2 抢到车位 2 停1s后离开车位 1 停1s后离开车位 3 停1s后离开车位 4 抢到车位 4 停1s后离开车位
CountDownLatch
概念：单线程等待，调用方法是await()
- 使用枚举类给线程命名，学习countDownLatch和枚举类减少if判断作用
public enum CountryEnum {
ONE(1, "齐"),
TWE(2, "燕"),
THREE(3, "楚"),
FOUR(4, "赵"),
FIVE(5, "魏"),
SIX(6, "韩");
private Integer retCode;
private String retMessage;
//Enum自带Setter，只用生产getter
public Integer getRetCode() {
return retCode;
}
public String getRetMessage() {
return retMessage;
}
//构造器
CountryEnum(Integer retCode, String retMessage) {
this.retCode = retCode;
this.retMessage = retMessage;
}
//获取枚举类中的值
public static CountryEnum forEach_CountryEnum(Integer codeIndex) {
// 枚举自带的元素数组，可用于遍历
CountryEnum[] eles = CountryEnum.values();
for (CountryEnum ele : eles) {
if (codeIndex == ele.getRetCode()) {
return ele;
}
}
return null;
}
} public class CountDownLatchDemo {
public static void main(String[] args) throws Exception {
CountDownLatch countDownLatch = new CountDownLatch(6);
for (int i = 1; i <= 6; i++) {
new Thread(() -> {
System.out.println(Thread.currentThread().getName() + "国，被灭了");
countDownLatch.countDown();
// 使用枚举类给线程命名，学习countDownLatch和枚举类减少if判断作用
}, CountryEnum.forEach_CountryEnum(i).getRetMessage()).start();
}
countDownLatch.await();
System.out.println(Thread.currentThread().getName() + "：秦国一统天下");
}
} 执行结果：
齐国，被灭了 魏国，被灭了 赵国，被灭了 楚国，被灭了 燕国，被灭了 韩国，被灭了 main：秦国一统天下
CyclicBarrier
概念：循环屏障，多线程等待，调用方法是await()
public class CyclicBarrierDemo {
public static void main(String[] args) {
// 同步器CyclicBarrier：指定屏障前等待线程数量, 到达屏障后执行的语句
CyclicBarrier barrier = new CyclicBarrier(7, () -> {
// 构造器第二个参数：Runnable接口
System.out.println("龙珠齐，召唤神龙");
});
for (int i = 1; i <= 7; i++) {
final int resources = i;
new Thread(() -> {
System.out.println(Thread.currentThread().getName() + "\t 收集到第" + resources + "颗龙珠");
//满足屏障初始化条件才能执行，否则等待
try {
barrier.await();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (BrokenBarrierException e) {
e.printStackTrace();
}
}, String.valueOf(i)).start();
}
} 执行结果:
1 收集到第1颗龙珠 3 收集到第3颗龙珠 4 收集到第4颗龙珠 2 收集到第2颗龙珠 5 收集到第5颗龙珠 6 收集到第6颗龙珠 7 收集到第7颗龙珠 龙珠齐，召唤神龙
AQS
概念：是1个抽象的队列同步器，通过维护 1个共资源状态（ Volatile Int State ）和一个先进先出（ FIFO ）的线程等待队列实现同步
底层原理：维护了一个共享资源的变量state
多线程
创建线程的方式
- extends Thread
- implements Runnable
- implements Callable<类型>
- 使用线程池创建
public class ThreadDemo1 extends Thread {
// 1.继承Thread
// 2.重写run
@Override
public void run() {
System.out.println("threadDemo1 extends thread");
}
public static void main(String[] args) {
// 3.调用start方法
new ThreadDemo1().start();
}
} public class ThreadDemo2 implements Runnable {
// 1.implements Runnable
// 2.重写run
@Override
public void run() {
System.out.println("ThreadDemo2 implements Runnable");
}
public static void main(String[] args) {
// 3.调用run方法
new ThreadDemo2().run();
}
} public class ThreadDemo3 implements Callable<String> {
// 1.3 implements Callable<T>
// 2.重写call方法
@Override
public String call() throws Exception {
return "ThreadDemo3 implements Callable<String>";
}
public static void main(String[] args) {
try {
// 3.call()方法执行
System.out.println(new ThreadDemo3().call());
} catch (Exception e) {
e.printStackTrace();
}
}
} public class ThreadDemo3 implements Callable<String> {
// 1.3 implements Callable<T>
// 2.重写call方法
@Override
public String call() throws Exception {
return "ThreadDemo3 implements Callable<String>";
}
public static void main(String[] args) {
try {
// 3.call()方法执行
System.out.println(new ThreadDemo3().call());
} catch (Exception e) {
e.printStackTrace();
}
}
} public class ThreadDemo4 {
public static void main(String[] args) {
ThreadPoolExecutor pool = new ThreadPoolExecutor(
2, 2,
1L, TimeUnit.SECONDS,
new ArrayBlockingQueue<>(5));
pool.execute(() -> {
System.out.println("执行业务逻辑");
});
pool.shutdown();
}
} Callable和Runnable的区别
| 区别 | Callable | Runnable |
|---|---|---|
| 返回值 | Callable有返回值，调用Callable接口的线程结束后该返回值 | 无返回值 |
| 重写方法 | call(） | run() |
| 调用形式 | Callable 在Thread中没有构造方法支持，所以使用FutureTask作为中间人传入，再作为参数传入Thread | Thread中传入参数 |
class CallableThread implements Callable<Integer> {
@Override
public Integer call() throws Exception {
System.out.println("多个线程抢一个futureTask，只有有一个进入。Come in Callable");
TimeUnit.SECONDS.sleep(2);
return 100;
}
}
class RunnableThread implements Runnable {
@Override
public void run() {
System.out.println("Runnable,没有返回值");
}
} public class CallableDemo {
public static void main(String[] args) throws ExecutionException, InterruptedException {
// 1.Callable利用中间人FutureTask先存放资源类
FutureTask<Integer> futureTask = new FutureTask<Integer>(new CallableThread());
Thread thread1 = new Thread(futureTask, "线程一");
Thread thread2 = new Thread(futureTask, "线程二");
// 2.多个线程强一个futureTask，只运行一个Callable
thread1.start();
thread2.start();
// 3.main线程模拟器其他线程的运算结果
Integer otherRes = 100;
// 4.FutureTask使用方法：使得CallableThread执行完再走，防止其余线程阻塞影响效率
while (!futureTask.isDone()) {
}
// 5.获取CallableThread执行结果
Integer res = futureTask.get();
System.out.println(Thread.currentThread().getName() + "\t 所有线程的计算结果：" + (otherRes + res));
}
} 执行结果：
多个线程抢一个futureTask，只有有一个进入。Come in Callable main 所有线程的计算结果：200
线程状态
| 线程状态 | 描述 |
|---|---|
| new | 新建。属于一个已经创建的线程，但是还没有调用start方法启动的线程所处的状态。 |
| runnable | 就绪。有可能正在运行，或者正在等待CPU资源。总体上就是当我们创建线程并且启动之后，就属于Runnable状态。 |
| blocked | 阻塞。当线程准备进入synchronized同步块或同步方法的时候，申请一个监视器锁而进行的等待，会使线程进入BLOCKED状态 |
| waiting/timed_waiting | 等待。调用了Object.wait（）或者Thread.join（）或者LockSupport.park（）。处于该状态下的线程在等待另一个线程 执行一些其余action来将其唤醒。 |
| running | 运行。处于运行状态的线程 主要 run 方法 中的逻辑代码 |
| terminated | 消亡。比较容易理解，那就是线程执行结束了，run方法执行结束表示线程处于消亡状态了。 |
线程的基本方法
6种常见方法
| 方法名 | 描述 |
|---|---|
| sleep | 线程休眠，是Thread类的静态方法，不会释放锁，使得线程进入TIMED-WAITING状态 |
| wait | 线程等待，是Object类的非静态方***释放占有的锁，使得线程进入WAITING状态，所以通常用于同步代码块 |
| interrupt | 线程中断，影响该线程内部的一个中断标识位，但并不会因为调用了 interrupt 方法而改变线程状态 |
| yield | 线程让步，使当前线程让出（释放） CPU 时间片， 与其他线程重新竞争 |
| join | 线程加入，等待其他线程终止，当前线程调用子或另一个线程join方法，当前线程阻塞等待join线程执行完毕 |
| notify | 线程唤醒，是Object类的非静态方法，唤醒等待的一个线程，如果全部线程都在等待，则随机唤醒 |
sleep和wait区别
| 区别 | sleep | wait |
|---|---|---|
| 父亲不同 | Thread类 | Object类 |
| 含义不同 | 必须指定等待时间，结束后，恢复运行状态 | 可以不指定等待时间 |
| 是否释放锁不同 | 不会释放对象锁 | 会释放锁，notify唤醒后，才会重新获取对象锁 |
start和run区别
| 区别 | start | run |
|---|---|---|
| 含义不同 | 启动线程，无需等待run方法执行完毕就可继续执行下面代码 | 指定运行线程的run方法，执行完run方法后，线程终止 |
| 状态不同 | thread.start（）线程处于就绪状态，没有运行 | thread.run()线程处于运行状态 |
终止线程方式
正常运行结束
使用退出标志位退出线程
public class StopThread1 extends Thread { // 1.volatile修饰的标志位 private volatile boolean exit = false; @Override public void run() { // 2.while判断是否跳出 while (!exit) { // 执行业务逻辑代码 System.out.println("执行业务逻辑，使得exit=true"); } } }使用interrpter终止线程
- 在调用sleep等方法后，抛出异常后，配合break跳出循环，才能结束run方法
public class StopThread2 extends Thread { @Override public void run() { // 1.未阻塞判断中断标志位跳出 while (!isInterrupted()) { try { // 2.线程处于阻塞状态，调用interrupter方法后会抛出异常 Thread.sleep(5 * 1000); } catch (InterruptedException e) { e.printStackTrace(); // 3.抛出异常后，break才跳出循环，才能结束run方法 break; } } } }使用stop方法终止线程
- 直接调用Thread.stop()是很危险的，极度不安全
线程死锁
两个或两个以上的进程（线程）在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。
死锁条件
| 死锁条件 | 概述 | 破坏死锁 |
|---|---|---|
| 互斥条件 | 该资源任意一个时刻只由一个线程占用 | 无法破坏，因为使用锁的本意就是想让它们互斥的（临界资源需要互斥访问） |
| 请求和保持 | 一个线程 / 进程因请求资源而阻塞时，对已获得的资源保持不放 | 一次性申请所有的资源 |
| 不剥夺 | 线程 / 进程已获得的资源在末使用完之前不能被其他线程 / 进程强行剥夺，只有自己使用完毕后才释放资源 | 占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源 |
| 循环等待 | 若干线程 / 进程之间形成一种头尾相接的循环等待资源关系 | 按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件（最常用） |
手写死锁
写法1：
public class DeadLockDemo1 {
// 资源1，让线程1获得
private static Object resource1 = new Object();
// 资源2，让线程2获得
private static Object resource2 = new Object();
public static void main(String[] args) {
// 线程1
new Thread(() -> {
synchronized (resource1) {
System.out.println(Thread.currentThread().getName() + ":get resource1");
// 线程1等待1s，让线程2获得资源2
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + ":waiting get resource2");
synchronized (resource2) {
System.out.println(Thread.currentThread().getName() + ":get resource2");
}
}
}, "线程 1").start();
new Thread(() -> {
synchronized (resource2) {
System.out.println(Thread.currentThread().getName() + ":get resource2");
// 线程2等待1s，让线程1获得资源1
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + ":waiting get resource1");
synchronized (resource1) {
System.out.println(Thread.currentThread().getName() + ":get resource1");
}
}
}, "线程 2").start();
}
} 执行结果：
线程 1:get resource1 线程 2:get resource2 线程 1:waiting get resource2 线程 2:waiting get resource1
如何避免上述的死锁：让线程2获得资源的锁的顺序和线程1一样，因为破坏了相互等待的条件，所以避免了死锁
写法2：
public class DeadThread implements Runnable{
String lockA;
String lockB;
public DeadThread(String lockA, String lockB) {
this.lockA = lockA;
this.lockB = lockB;
}
@Override
public void run() {
synchronized (lockA) {
System.out.println(Thread.currentThread().getName() + "\t 自己持有" + lockA + ",想持有" + lockB);
try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); }
synchronized (lockB) {
System.out.println(Thread.currentThread().getName() + "\t 自己持有" + lockB + ",想持有" + lockA);
}
}
}
} public class DeadLockDemo2 {
public static void main(String[] args) {
String lockA = "lockA";
String lockB = "lockB";
new Thread(new DeadThread(lockA, lockB), "A").start();
//lockA和lockB互换
new Thread(new DeadThread(lockB, lockA), "B").start();
}
} A 自己持有lockA,想持有lockB B 自己持有lockB,想持有lockA ...
排查死锁
| windows系统 | 解释 |
|---|---|
| jps -l | 输出当前包下进程包，对应的Java程序完全的包名，应用主类名下 |
| jstack 死锁进程名 | 查看指定进程名的在JVM栈中的状态 |
阻塞队列
| 阻塞队列 | 解释 |
|---|---|
| 概念 | 队列空，线程再去拿就阻塞；队列满，线程再添加就阻塞 |
| 好处 | 出现阻塞队列后，程序员不用手动去阻塞队列和唤醒队列 |
| 阻塞队列分类 | 解释 |
|---|---|
| ArrayBlockingQueue | 数组结构组成的有界阻塞队列 |
| LinkedBlockingQueue | 由链表组成的有界阻塞队列（大小默认是21亿，不推荐默认使用） |
| LinkedBlockingDeque | 由链表结构组成的双向阻塞队列 |
| PriorityBlockingQueue | 支持优先级排序的无界阻塞队列 |
| DelayBlockingQueue | 使用优先级队列实现的延迟无界队列 |
| SynchronousQueue | 不存储元素的阻塞队列=单个元素的队列 |
| LinkedTransferQueue | 由链表结构组成的无界阻塞队列 |
| 核心API | 抛出异常 | 返回布尔 | 阻塞 | 超时 |
|---|---|---|---|---|
| 插入 | add(e) | offer(e) | put(e) | offer(e,time,unit) |
| 移除 | remove() | poll() | take() | poll(time,unit) |
| 检查 | element() | peek() | 不可用 | 不可用 |
ArrayBlockingQueue
public class BlockingQueueDemo {
public static void main(String[] args) throws InterruptedException {
ArrayBlockingQueue<String> blockingQueue = new ArrayBlockingQueue<String>(3);
// 抛出异常组：add/remove/element：会抛出异常:IllegalStateException,一言不合就报异常不推荐使用
blockingQueue.add("1");
blockingQueue.add("2");
blockingQueue.add("3");
// blockingQueue.add("4"); 直接抛出异常
blockingQueue.remove("1");
blockingQueue.remove("2");
blockingQueue.remove("3");
System.out.println("--抛出异常组--");
// 返回布尔型组：offer/poll/peek:失败返回布尔型
blockingQueue.offer("11");
blockingQueue.offer("12");
blockingQueue.offer("13");
System.out.println(blockingQueue.offer("14"));
blockingQueue.poll();
blockingQueue.poll();
blockingQueue.poll();
System.out.println("--返回布尔组--");
// 等待组：put/take:满了就一直等待，等待是为了只要有数据出去立马添加
blockingQueue.put("a");
blockingQueue.put("b");
blockingQueue.put("c");
// blockingQueue.put("d"); 这样会一直等待
// System.out.println(blockingQueue.take());
System.out.println(blockingQueue.take());
System.out.println(blockingQueue.take());
System.out.println(blockingQueue.take());
System.out.println("--等待组--");
// 设置时间组：offer/poll设置失败等待时间
System.out.println(blockingQueue.offer("a", 1L, TimeUnit.SECONDS));
System.out.println(blockingQueue.offer("b", 1L, TimeUnit.SECONDS));
System.out.println(blockingQueue.offer("c", 1L, TimeUnit.SECONDS));
System.out.println("--设置时间组--");
}
} SynchronousQueue
public class SynchronsBlockingQueue {
public static void main(String[] args) {
// SynchronousQueue:一个线程生产一个，等待别的线程消费完才能进行下去
SynchronousQueue<Integer> blockingQueue = new SynchronousQueue();
new Thread(() -> {
try {
System.out.println(Thread.currentThread().getName() + "，生产了1");
blockingQueue.put(1);
TimeUnit.SECONDS.sleep(1);
//阻塞：SynchronousQueue使用put必须等待别的线程take后
System.out.println(Thread.currentThread().getName() + "，生产了2");
blockingQueue.put(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "线程1").start();
new Thread(() -> {
try {
//消费：：SynchronousQueue使用put必须等待别的线程take消费
System.out.println(Thread.currentThread().getName() + "，消费了" + blockingQueue.take());
TimeUnit.SECONDS.sleep(1);
System.out.println(Thread.currentThread().getName() + "，消费了" + blockingQueue.take());
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "线程2").start();
}
} 执行结果：
线程1，生产了1 线程2，消费了1 线程1，生产了2 线程2，消费了2
Synchronized和ReenTrantLock区别
相同点：
- 都是可重入锁，默认都是非公平锁
- 都保证了可见性和互斥性
| 不同点 | syn | lock |
|---|---|---|
| 含义 | 关键字，隐式获取锁和释放锁 | Api层面，显示获锁和释放锁 |
| 使用 | 不需要手动释放 | 需要手动释放，否则死锁 |
| 中断 | 不可中断，除非抛出异常或者正常运行完毕 | 可响应式中断,try/trylock(time)/lockInterruptibly |
| 公平 | 只能是非公平锁 | 默认非公平，传参为true表示公平 |
| 底层 | 同步阻塞，悲观策略 | 同步非阻塞，乐观并发策略 |
练习题：(Lock能精确唤醒) AA打印5次，BB打印10次，CC打印15次，紧接着AA打印5次，...重复10论
class MyRenLockResources {
// 1=AA,2=BB,3=CC
private int threadName = 1;
private Lock lock = new ReentrantLock();
private Condition a = lock.newCondition();
private Condition b = lock.newCondition();
private Condition c = lock.newCondition();
public void print5() {
lock.lock();
try {
//1 判断 防止虚假唤醒，使用while
while (threadName != 1) {
//不等于1 就不是AA干活，AA等待
a.await();
}
//2 干活 模拟打印5次
for (int i = 1; i <= 5; i++) {
System.out.println(Thread.currentThread().getName() + "\t" + i);
}
//3 通知别的线程
threadName = 2;
b.signal();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
public void print10() {
lock.lock();
try {
//1 判断 防止虚假唤醒，使用while
while (threadName != 2) {
//不等于1 就不是AA干活，AA等待
b.await();
}
//2 干活 模拟打印5次
for (int i = 1; i <= 10; i++) {
System.out.println(Thread.currentThread().getName() + "\t" + i);
}
//3 通知别的线程
threadName = 3;
c.signal();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
public void print15() {
lock.lock();
try {
//1 判断 防止虚假唤醒，使用while
while (threadName != 3) {
//不等于1 就不是AA干活，AA等待
c.await();
}
//2 干活 模拟打印5次
for (int i = 1; i <= 15; i++) {
System.out.println(Thread.currentThread().getName() + "\t" + i);
}
//3 通知别的线程
threadName = 1;
a.signal();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
} public class SyncAndReentrantLockDemo {
public static void main(String[] args) {
MyRenLockResources myResources = new MyRenLockResources();
new Thread(() -> {
for (int i = 1; i <= 10; i++) {
myResources.print5();
}
}, "AA").start();
new Thread(() -> {
for (int i = 1; i <= 10; i++) {
myResources.print10();
}
}, "BB").start();
new Thread(() -> {
for (int i = 1; i <= 10; i++) {
myResources.print15();
}
}, "CC").start();
}
} 线程池参数
使用ThreadPoolExecutor自建线程池（推荐使用）/Executors工具类（不推荐使用）
// 线程池7大参数
public ThreadPoolExecutor(
// 核心线程数
int corePoolSize,
// 最大线程数
int maximumPoolSize,
// 空闲线程存活时间
long keepAliveTime,
// 线程存活时间单位
TimeUnit unit,
// 阻塞队列
BlockingQueue<Runnable> workQueue,
// 线程工厂
ThreadFactory threadFactory,
// 饱和拒绝策略
RejectedExecutionHandler handler
) | 线程池参数 | 解释 |
|---|---|
| corePoolSize | 线程池中的核心线程数，当提交一个任务时，线程池创建一个新线程执行任务，直到当前线程数等于corePoolSize；如果当前线程数为corePoolSize，继续提交的任务被保存到阻塞队列中，等待被执行；如果执行了线程池的prestartAllCoreThreads()方法，线程池会提前创建并启动所有核心线程。 |
| maximumPoolSize | 线程池中允许的最大线程数。如果当前阻塞队列满了，且继续提交任务，则创建新的线程执行任务，前提是当前线程数小于maximumPoolSize； |
| keepAliveTime | 线程池维护线程所允许的空闲时间。当线程池中的线程数量大于corePoolSize的时候，如果这时没有新的任务提交，核心线程外的线程不会立即销毁，而是会等待，直到等待的时间超过了keepAliveTime； |
| unit | keepAliveTime的单位 |
| workQueue | 用来保存等待被执行的任务的阻塞队列，且任务必须实现Runable接口，在JDK中提供了如下阻塞队列 |
| threadFactory | 它是ThreadFactory类型的变量，用来创建新线程。默认使用Executors.defaultThreadFactory() 来创建线程。使用默认的ThreadFactory来创建线程时，会使新创建的线程具有相同的NORM_PRIORITY优先级并且是非守护线程，同时也设置了线程的名称。 |
| handler | 线程池的饱和策略，当阻塞队列满了，且没有空闲的工作线程，如果继续提交任务，必须采取一种策略处理该任务，线程池提供了4种策略 |
| workQueue阻塞队列 | 解释 |
|---|---|
| ArrayBlockingQueue | 基于数组结构的有界阻塞队列，按FIFO排序任务 |
| LinkedBlockingQuene | 基于链表结构的阻塞队列，按FIFO排序任务，吞吐量通常要高于ArrayBlockingQuene |
| SynchronousQuene | 一个不存储元素的阻塞队列，每个插入操作必须等到另一个线程调用移除操作，否则插入操作一直处于阻塞状态，吞吐量通常要高于LinkedBlockingQuene |
| PriorityBlockingQuene | 具有优先级的无界阻塞队列 |
| handler拒绝策略 | 解释 |
|---|---|
| AbortPolicy | 直接抛出异常，默认策略 |
| CallerRunsPolicy | 用调用者所在的线程（如以下的main线程）来执行任务 |
| DiscardOldestPolicy | 丢弃阻塞队列中靠最前的任务，并执行当前任务 |
| DiscardPolicy | 直接丢弃任务 |
线程池核心组件
创建线程池
方式一：Executors
ExecutorService，其中定义了线程池的具体行为，常见的四种方法如上图红线处
public class ExecutorsDemo {
public static void main(String[] args) {
// 创建线程池方式1：Executors，里面封装了很多，但都不推荐使用
// newFixedThreadPool：核心和最大线程数相同，等待队列是LinkedBlockingQueue，等待时间0
ExecutorService fixedPool = Executors.newFixedThreadPool(5);
// newCachedThreadPool：核心为0，等待队列是SynchronousQueue，最大线程数是最大整数，等待时间60s
ExecutorService cachedPool = Executors.newCachedThreadPool();
// newSingleThreadExecutor：核心和最大为0，等待队列是LinkedBlockingQueue，等待时间0
ExecutorService singletonPool = Executors.newSingleThreadExecutor();
for (int i = 0; i < 10; i++) {
fixedPool.execute(() -> {
System.out.println(Thread.currentThread().getName() + ",办理业务");
});
}
fixedPool.shutdown();
}
} 5种常用的线程池，但是阿里巴巴开发手册都不推荐使用
方式二：new ThreadPoolExecutor
public class ThreadPoolDemo {
public static void main(String[] args) {
// 1 推荐使用使用自建的线程池，学习7大参数
ThreadPoolExecutor myThreadPool = new ThreadPoolExecutor(
2, 5, 1L, TimeUnit.SECONDS,
new ArrayBlockingQueue<>(5),
Executors.defaultThreadFactory(),
// AbortPolicy:直接抛出异常
// CallerRunsPolicy:用调用者所在的线程（本类中的main）来执行任务
// DiscardPolicy:丢弃进来的任务
// DiscardOldestPolicy:丢弃之前的第一个任务
new ThreadPoolExecutor.CallerRunsPolicy());
for (int i = 1; i <= 20; i++) {
int resource = i;
// 2.执行线程池中的线程
myThreadPool.execute(() -> {
System.out.println(Thread.currentThread().getName() + "\t 线程进入，\t 获得资源: " + resource);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
});
}
// 3.终止线程池
myThreadPool.shutdown();
// 4.while判断线程池是否终止
while (!myThreadPool.isTerminated()) {
}
System.out.println("所有线程已经终止");
}
} pool-1-thread-1 线程进入， 获得资源: 1 pool-1-thread-4 线程进入， 获得资源: 9 pool-1-thread-3 线程进入， 获得资源: 8 main 线程进入， 获得资源: 11 pool-1-thread-2 线程进入， 获得资源: 2 pool-1-thread-5 线程进入， 获得资源: 10 main 线程进入， 获得资源: 12 pool-1-thread-2 线程进入， 获得资源: 3 pool-1-thread-3 线程进入， 获得资源: 4 pool-1-thread-1 线程进入， 获得资源: 5 pool-1-thread-4 线程进入， 获得资源: 7 pool-1-thread-5 线程进入， 获得资源: 6 main 线程进入， 获得资源: 18 pool-1-thread-2 线程进入， 获得资源: 13 pool-1-thread-4 线程进入， 获得资源: 14 pool-1-thread-1 线程进入， 获得资源: 16 pool-1-thread-3 线程进入， 获得资源: 15 pool-1-thread-5 线程进入， 获得资源: 17 pool-1-thread-2 线程进入， 获得资源: 19 pool-1-thread-1 线程进入， 获得资源: 20 所有线程已经终止
线程池执行原理
- 创建一个线程池，在还没有任务提交的时候，默认线程池里面是没有线程的。当然，你也可以调用prestartCoreThread方法，来预先创建一个核心线程。
- 线程池里还没有线程或者线程池里存活的线程数小于核心线程数corePoolSize时，这时对于一个新提交的任务，线程池会创建一个线程去处理提交的任务。当线程池里面存活的线程数小于等于核心线程数corePoolSize时，线程池里面的线程会一直存活着，就算空闲时间超过了keepAliveTime，线程也不会被销毁，而是一直阻塞在那里一直等待任务队列的任务来执行。
- 当线程池里面存活的线程数已经等于corePoolSize了，这是对于一个新提交的任务，会被放进任务队列workQueue排队等待执行。而之前创建的线程并不会被销毁，而是不断的去拿阻塞队列里面的任务，当任务队列为空时，线程会阻塞，直到有任务被放进任务队列，线程拿到任务后继续执行，执行完了过后会继续去拿任务。这也是为什么线程池队列要是用阻塞队列。
- 当线程池里面存活的线程数已经等于corePoolSize了,并且任务队列也满了，这里假设maximumPoolSize>corePoolSize(如果等于的话，就直接拒绝了),这时如果再来新的任务，线程池就会继续创建新的线程来处理新的任务，直到线程数达到maximumPoolSize，就不会再创建了。这些新创建的线程执行完了当前任务过后，在任务队列里面还有任务的时候也不会销毁，而是去任务队列拿任务出来执行。在当前线程数大于corePoolSize过后，线程执行完当前任务，会有一个判断当前线程是否需要销毁的逻辑：如果能从任务队列中拿到任务，那么继续执行，如果拿任务时阻塞（说明队列中没有任务），那超过keepAliveTime时间就直接返回null并且销毁当前线程，直到线程池里面的线程数等于corePoolSize之后才不会进行线程销毁。
- 如果当前的线程数达到了maximumPoolSize，并且任务队列也满了，这种情况下还有新的任务过来，那就直接采用拒绝的处理器进行处理。默认的处理器逻辑是抛出一个RejectedExecutionException异常。你也就可以指定其他的处理器，或者自定义一个拒绝处理器来实现拒绝逻辑的处理（比如讲这些任务存储起来）。JDK提供了四种拒绝策略处理类：AbortPolicy（抛出一个异常，默认的），DiscardPolicy（直接丢弃任务），DiscardOldestPolicy（丢弃队列里最老的任务，将当前这个任务继续提交给线程池），CallerRunsPolicy（交给线程池调用所在的线程进行处理）。
ThreadLocal
| ThreadLocal | 解释 |
|---|---|
| 概念 | 提供每个线程存储自身专属的局部变量值 |
| 实现原理 | 调用 ThreadLocal 的 set () 方法时，实际上就是往 ThreadLocalMap 设置值，key 是 ThreadLocal 对象，值是传递进来的对象；调用 ThreadLocal 的 get () 方法时，实际上就是往 ThreadLocalMap 获取值，key 是 ThreadLocal 对象 ThreadLocal 本身并不存储值，它只是作为一个 key 来让线程从 ThreadLocalMap 获取 value。因为这个原理，所以 ThreadLocal 能够实现 “数据隔离”，获取当前线程的局部变量值，不受其他线程影响。 |
| 风险 | ThreadLocal 被 ThreadLocalMap 中的 entry 的 key 弱引用，如果 ThreadLocal 没有被强引用， 那么 GC 时 Entry 的 key 就会被回收，但是对应的 value 却不会回收。就会造成内存泄漏 |
| 解决办法 | 每次使用完 ThreadLocal，都调用它的 remove () 方法，清除数据 |
Web
进程和线程
| 进程 | 线程 | |
|---|---|---|
| 概念 | 进程是资源分配的最小单位 | 线程是CPU调度的最小单位 |
| 不同点 | 进程 | 线程 |
|---|---|---|
| 根本区别 | 进程是操作系统资源分配的基本单位 | 线程是CPU调度的最小单位 |
| 资源开销 | 大 | 线程可频繁切换 |
| 环境运行 | 操作系统中能同时运行多个进程 | 同一个进程包括多个线程 |
进程调度算法
| 解释 | |
|---|---|
| 先来先服务算法 | 在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或儿个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列 |
| 短进程优先调度算法 | 就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机 |
| 优先级调度算法 | 每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行 |
| 时间片轮转调度算法 | 系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如l00ms 。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。 |
| 高响应比优先调度算法 | FCFS调度算法和SPF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。响应比的变化规律可描述为:响应比＝(等待时间＋要求服务时间)/要求服务时间 |
| 多级反馈队列调度算法 | 通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/0 设备利用率和缩短响应时间而照顾I/0 型进程；同时，也不必事先估计进程的执行时间。 |
OSI\TCP\IP协议
TCP
TCP/UDP区别
HTTP传输过程
HTTP传输过程
HTTP 和 HTTPS
| HTTP | HTTPS | |
|---|---|---|
| 端口 | 80 | 443 |
| 安全性 | HTTP运⾏在TCP之上，所有传输的内容都是明⽂，客户端和服务器端都⽆法验证对⽅的身份 | HTTPS是运⾏在SSL/TLS之上的HTTP协议，SSL/TLS 运⾏在TCP之上。所有传输的内容都经过加密。 |
| 资源消耗 | 小 | 大 |
三次握手
| 三次握手 | 解释 |
|---|---|
| 第一次握手 | 客户端发送syn包(syn=j)到服务器,并进入SYN_SEND状态,等待服务器确认 |
| 第二次握手 | 服务器收到syn包,必须确认客户的SYN（ack=j+1）,同时自己也发送一个SYN包（syn=k）,即SYN+ACK包,此时服务器进入SYN_RECV状态； |
| 第三次握手 | 户端收到服务器的SYN＋ACK包,向服务器发送确认包ACK(ack=k+1),此包发送完毕,客户端和服务器进入ESTABLISHED状态,完成三次握手。 |
四次挥手
| 四次挥手 | 解释 |
|---|---|
| 第一次挥手 | 客户端-发送⼀个 FIN，⽤来关闭客户端到服务器的数据传送 |
| 第二次挥手 | 服务器-收到这个 FIN，它发回⼀个ACK，确认序号为收到的序号加1 。和 SYN ⼀样，⼀个 |
| 第三次挥手 | 服务器-关闭与客户端的连接，发送⼀个FIN给客户端 |
| 第四次挥手 | 客户端-发回 ACK 报⽂确认，并将确认序号设置为收到序号加1 |
状态码
| 状态码 | 英文名 | 说明 |
|---|---|---|
| 100 | Continue | 表示迄今为止的所有内容都是可行的，客户端应该继续请求，如果已经完成，则忽略它。 |
| 101 | Switching Protocol | 表示服务器正在切换协议。只能切换到更高级的协议，例如，切换到 HTTP 的新版本协议。 |
| 200 | OK | 请求已成功，请求所希望的响应头或数据体将随此响应返回。 |
| 202 | Accepted | 服务器已接受请求，但尚未完成。最终该请求可能会也可能不会被执行，并且可能在处理发生时被禁止。 |
| 301 | Moved Permanently | 永久性重定向。被请求的资源已永久移动到新 URI，返回信息会包括新的 URI，浏览器会自动定向到新 URI。如果可能，拥有链接编辑功能的客户端应当自动把请求的地址修改为从服务器反馈回来的地址 |
| 400 | Bad Request | 通常有两种情况：一是语义有误，当前请求无法被服务器理解；二是请求参数有误。 |
| 401 | Unauthorized | 请求要求身份验证。 该响应必须包含一个适用于被请求资源的 WWW-Authenticate 信息头用以询问用户信息。客户端可以重复提交一个包含恰当的 Authorization 头信息的请求。如果当前请求已经包含了 Authorization 证书，那么 401 响应代表着服务器验证已经拒绝了那些证书。对于需要登录的网页，服务器可能返回此响应。 |
| 403 | Forbidden | 服务器已经理解请求，但是拒绝执行它。 |
| 404 | Not Found | 服务器找不到请求的资源 |
| 405 | Method Not Allowed | 禁用请求中指定的方法 |
| 500 | Internal Server Error | 服务器内部错误，不知道如何处理； |
| 502 | Bad Gateway | 前面的网关代理服务器联系不到后端的服务器 |
| 503 | Service Unavailable | 服务器没有准备好处理请求。 常见原因是服务器因维护或重载而停机 |
| 504 | Gateway Timeout | 前面的网关代理服务器能联系到后端的服务器，但是后端的服务器在规定的时间内没有给代理服务器响应 |
页面响应过程
DNS解析
TCP连接
发送HTTP请求
服务器处理请求并返回HTTP报⽂
浏览器解析渲染⻚⾯
连接结束
forward和Redirect
| 区别 | forward | redirect |
|---|---|---|
| 地址栏 | 服务端内部重定向 | 发送一个状态码到浏览器，浏览器再次访问这个新地址 |
| 数据共享 | 共享数据 | 不共享数据 |
| 应用场景 | 比如：用户登录 | 比如：用户注销放回主页面 |
| 效率 | 高 | 低 |
| 次数 | 一次 | 两次 |
| 本质 | 服务端的行为 | 客户端的行为 |
Spring
Spring组成
Spring模块总述
Spring核心容器层
- Spring Beans：基于工厂模式创建对象的实例，通过XML文件实现了声明式的对象管理，将对象复杂关系交给框架管理
- Spring Core：实现Spring核心功能，包括IOC和依赖注入
- Spring Context：继承自Spring Beans模块，并且添加了国际化、事件传播、资源加载和透明创建上下文等功能
- Spring EL：提供丰富的表达式语言，用于在运行过程中查询和操作对象实例
Spring数据访问层
Spring核心Jar包
Spring常用注解
Autowired、Resource
相同点：都是对象的依赖注入的注解，都可以用于成员变量和方法上
不同点：
- 默认方式不同：Autowired是基于bean的类型去查找的，Resources是基于bean的name去查找的
- 注解来源不同：Autowired是Spring带的注解，Resources是JDK自带的注解
- 使用场景不同：如果有多个相同类型的bean，最好使用Resources（name=“指定名”）装配=Autowired+Qualified
IOC
概念：IOC也叫控制反转，将对象间的依赖关系交给Spring容器，使用配置文件来创建所依赖的对象，由主动创建对象改为了被动方式，实现解耦合。
使用方式：可以通过注解@Autowired和@Resource来注入对象， context:annotation-config/元素开启注解。被注入的对象必须被下边的四个注解之一标注：@Controller、@Service、@Repository、@Component
底层原理：反射
装配流程：
Bean的作用域
| 作用域 | 解释 |
|---|---|
| singleton | IOC容器只会创建一个共享Bean，无论有多少个Bean引用它，都始终只指向一个Bean对象 |
| prototype | IOC容器每次都会创建一个新的实例Bean |
| request | 同一次Http请求会返回同一个实例，不同的Http请求则会创建新的实例，请求结束后实例销毁 |
| session | 同一次Http Session中容器会返回同一个实例，不同的Session请求则会创建新的实例，请求结束实例销毁 |
| global-session | 一个全局的Http Session中容器会返回同一个实例，仅在使用Portlet Context时生效 |
Spring中Bean的作用域常使用的是singleton，也就是单例作用域。那么单例Bean是线程安全的吗？
单例Bean和线程安全与否没有必然的关系。多个线程在多个工作内存和主内存交互的时候会出现不一致的地方，那么就不是线程安全的。大部分的Spring Bean并没有可变的状态(比如Service类和DAO类)，所以一定程度上可以说Spring的单例Bean是线程安全的。如果你的Bean有多种状态的话（比如 View Model 对象），就需要自行保证线程安全。在一般情况下，只有无状态的Bean才可以在多线程环境下共享。
AOP
底层原理：动态代理
AOP中有如下的操作术语：
- Joinpoint(连接点)： 类里面可以被增强的方法，这些方法称为连接点
- Pointcut(切入点)：所谓切入点是指我们要对哪些Joinpoint进行拦截的定义
- Advice(通知/增强)：所谓通知是指拦截到Joinpoint之后所要做的事情就是通知。
- Aspect(切面)：是切入点和通知（引介）的结合
- Introduction(引介)：引介是一种特殊的通知在不修改类代码的前提下，Introduction可以在运行期为类动态地添加一些方法或属性
- Target(目标对象)：代（dai）理的目标对象(要增强的类)
- Weaving(织入)：是把增强应用到目标的过程，把advice 应用到 target的过程
- Proxy（代(dai)理）：一个类被AOP织入增强后，就产生一个结果代（dai）理类
动态代理
概念：程序运行时生成代理类
| 代理方式 | 实现 | 优点 | 缺点 | 特点 |
|---|---|---|---|---|
| JDK静态代理 | 代理类和委托类实现同一接口，代理类硬编码接口 | 简单 | 重复编码，不易修改 | 无 |
| JDK动态代理 | 继承InvoktionHandle接口，重写invoke方法 | 代码复用率高，不需重复编码 | 只能够代理实现了接口的委托类 | 底层使用反射 |
| Cglib动态代理 | 继承MethodInterceptor，重写intercept方法 | 可以对类/接口增强，且被代理类无需实现接口 | 不能对final类或方法代理 | 底层是字节码调用ASM框架生成新的类 |
JDK动态代理
- 被代理类和其接口
public interface UserManager {
void addUser(String username,String password);
} public class UserManagerImpl implements UserManager {
@Override
public void addUser(String username, String password) {
System.out.println("UserName：" + username + " PassWord:" + password);
}
} - 继承InvoktionHandle接口，重写invoke方法
- 重点学习JDK动态代理类的书写模版，即下面的序号处是通用模版
public class JDKProxy implements InvocationHandler {
// 代理类继承InvocationHandler，重写invoke方法
// 1.获取被代理对象
private Object target;
public JDKProxy(Object target) {
this.target = target;
}
// 2.代理类获取被代理角色
private Object getProxyInstance() {
// 返回给代理类和被代理增强的接口，并生成被代理对象实例
return Proxy.newProxyInstance(
target.getClass().getClassLoader(),
target.getClass().getInterfaces(),// 第二个参数说明JDK动态代理只针对接口增强
this);
}
// 3.代理类重写invoke方法
@Override
public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
// 增强方法1
System.out.println("增强方法1：JDK动态代理开始");
// 被代理对象接口实现的的返回值 = 固定写法
Object result = method.invoke(target, args);
// 增强方法2
System.out.println("增强方法2：JDK动态代理结束");
return result;
}
// 4.测试线程
public static void main(String[] args) {
UserManagerImpl userManager = new UserManagerImpl();
JDKProxy jdkProxy = new JDKProxy(userManager);
UserManager user = (UserManager) jdkProxy.getProxyInstance();
user.addUser("张三", "123");
}
} Cglib动态代理
- 被代理类
public class UserCglibServiceImpl {
public void hobby() {
System.out.println("跳舞");
}
} - 继承MethodInterceptor，重写intercept方法
public class UserCglibServiceProxy implements MethodInterceptor {
// 1.设置被代理对象
private Object target;
public UserCglibServiceProxy(Object target) {
this.target = target;
}
// 2.创建被代理对象
public Object getProxyInstance() {
// 工具类
Enhancer en = new Enhancer();
// 设置被代理作为父类
en.setSuperclass(target.getClass());
// 将本类设置为回调函数
en.setCallback(this);
// 返回被代理对象
return en.create();
}
// 3.重写intercept方法，用法和JDK动态代理一样
@Override
public Object intercept(Object o, Method method, Object[] args, MethodProxy methodProxy) throws Throwable {
System.out.println("增强方法1：cglib动态代理开始");
Object invoke = method.invoke(target, args);
System.out.println("增强方法2：cglib动态代理结束");
return invoke;
}
// 4.测试线程
public static void main(String[] args) {
UserCglibServiceImpl target1 = new UserCglibServiceImpl();
UserCglibServiceImpl target2 =(UserCglibServiceImpl) new UserCglibServiceProxy(target1).getProxyInstance();
target2.hobby();
}
} Spring事务
- 编程式事务管理：使用TransactionTemplate实现。
- 声明式事务管理：建立在AOP之上的。其本质是通过AOP功能，对方法前后进行拦截，将事务处理的功能编织到拦截的方法中，也就是在目标方法开始之前加入一个事务，在执行完目标方法之后根据执行情况提交或者回滚事务。事务选择：
- 优点：非侵入式的开发方式，使业务代码不受污染，只要加上注解就可以获得完全的事务支持
- 缺点：最细粒度只能作用到方法级别，无法做到像编程式事务那样可以作用到代码块级别。
当多个Spring事务存在的时候，Spring定义了下边的7个传播行为来处理这些事务行为：
| 事务传播行为 | 解释 |
|---|---|
| propagation_required | 有事务，就加入当前事务；没有事务，就创建新的事务（默认） |
| propagation_required_new | 无论有没有事务，都创建新的事务 |
| propagation_supports | 有事务，就加入当前事务；没有事务，就以非实物执行 |
| propagation_not_supported | 有事务，将当期事务挂起，以非事务执行；没有事务，以非实物执行 |
| propagation_mandatory | 有事务，就加入当前事务；没有事务，就抛出异常 |
| propagation_never | 有事务，抛出异常，以非事务执行；没有事务，以非事务执行 |
| propagation_nested | 有事务，则嵌套事务内执行；没有事务，就新建一个事务 |
Spring事务的隔离级别和MySQL事务的隔离级别类似，依然存在读未提交，读已提交，可重复读以及串行四种隔离级别。
| 隔离级别 | 脏读 | 不可重复度 | 幻读 |
|---|---|---|---|
| 读未提交（Read Uncommitted） | 可能 | 可能 | 可能 |
| 读已提交（Read Commited） | 不可能 | 可能 | 可能 |
| 可重复读（默认级别，Repeatable Read） | 不可能 | 不可能 | 可能 |
| 可串行化（Serializable） | 不可能 | 不可能 | 不可能 |
| 事务并发问题 | 描述 |
|---|---|
| 更新丢失 | 最后的更新覆盖了其他事务所做的更新 |
| 脏读 | 事务A读取到了事务B修改但未提交的数据。此时，如果事务B回滚事务，事务A读取的数据就无效，不满足一致性要求。 |
| 不可重复读 | 事务A内部的相同查询语句在不同时刻读出的结果不一致，不符合隔离性。 |
| 幻读 | 事务A读取到了事务B提交的新增数据，不符合隔离性 |
SpringMVC的流程
Mybatis的缓存
SpringBoot
自动装配过程
主要启动类中的@SpringBootApplication注解封装了@SpringBootConfiguration、@EnableAutoConfiguration
@SpringBootApplication// 点进去
public class GatewayApplication {
public static void main(String[] args) {
SpringApplication.run(GatewayApplication.class, args);
}
} // 四大元注解
@Target({ElementType.TYPE})
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Inherited
// 以下是SpringbootApplication重要的3个注解
@SpringBootConfiguration
@EnableAutoConfiguration// 这个就是自动装配的灵魂注解
@ComponentScan @SpringBootConfiguration
说明这是一个Springboot的配置文件，里面的 @Component ，说明启动类本身也是Spring中的一个组件而已，负责启动应用！
@EnableAutoConfiguration
自动装配的核心注解，点进去看的AutoConfigurationImportSelector是核心中的核心
@AutoConfigurationPackage @Import(AutoConfigurationImportSelector.class)
@AutoConfigurationPackages.Registrar.class:主启动所在的包及以下的所有子包都扫描进spring容器中
@Import(AutoConfigurationImportSelector.class) ，找到getCandidateConfigurations方法
getCandidateConfigurations方法:获得候选的配置
protected List<String> getCandidateConfigurations(AnnotationMetadata metadata, AnnotationAttributes attributes) {
List<String> configurations = SpringFactoriesLoader.loadFactoryNames(getSpringFactoriesLoaderFactoryClass(),
getBeanClassLoader());
Assert.notEmpty(configurations, "No auto configuration classes found in META-INF/spring.factories. If you "
+ "are using a custom packaging, make sure that file is correct.");
return configurations;
} 找到SpringFactoriesLoader.loadFactoryNames，点进去，找到loadSpringFactories方法
public static final String FACTORIES_RESOURCE_LOCATION = "META-INF/spring.factories";
public static List<String> loadFactoryNames(Class<?> factoryType, @Nullable ClassLoader classLoader) {
String factoryTypeName = factoryType.getName();
return loadSpringFactories(classLoader).getOrDefault(factoryTypeName, Collections.emptyList());
}
private static Map<String, List<String>> loadSpringFactories(@Nullable ClassLoader classLoader) {
//获得classLoader
MultiValueMap<String, String> result = cache.get(classLoader);
if (result != null) {
return result;
}
...
} org.springframework.boot.test.autoconfigure/META-INF/spring.factories：就是预存的配置文件
@ComponentScan
- 自动扫描并加载符合条件的组件bean,并将这个组件bean注入到IOC容器中
@ComponentScan(excludeFilters = { @Filter(type = FilterType.CUSTOM, classes = TypeExcludeFilter.class),
@Filter(type = FilterType.CUSTOM, classes = AutoConfigurationExcludeFilter.class) }) 自动装配总结
自动配置真正实现是从classpath中搜寻所有的
META-INF/spring.factories配置文件 ，并将其中对应的org.springframework.boot.autoconfigure.包下的配置项，通过反射实例化为对应标注了 @Configuration的JavaConfig形式的IOC容器配置类 ， 然后将这些都汇总成为一个实例并加载到IOC容器中。用户如何书写yml配置，需要去查看
META-INF/spring.factories下的某自动配置，如HttpEncodingAutoConfigurationEnableConfigrutionProperties(xxx.class):表明这是一个自动配置类，加载某些配置XXXProperties.class：封装配置文件中的属性，yam中需要填入= 它指定的前缀+方法
Mysql
三大范式
| 三大范式 | 解释 | 例子 |
|---|---|---|
| 第一范式 | 每列都是不可再分的原子操作 | 地址字段可以再细分为国家+省+市等，就不符合第一范式 |
| 第二范式 | 非主键字段不能对主键产生部分依赖 | 订单表中包含产品字段，就不符合第二范式 |
| 第三范式 | 非主键字段不能对主键产生传递依赖 | 订单表中包含顾客表的主键和顾客表其他字段，就不符合第三范式 |
存储引擎
| 存储引擎 | 解释 |
|---|---|
| InnoDB | 支持事务、行级锁定和外键，Mysql5.5.5之后默认引擎 |
| MyISAM | 较高的插入、查询速度，但不支持事务。Mysql5.5.5之前的默认引擎 |
| Memory | 基于散列，存储在内存中，对临时表有用。常用于存放临时数据 |
| Archive | 支持高并发的插入操作，但是本身不是事务安全的。常用存储归档数据 |
InnoDB
- 只使用.ibd的后缀的文件存储数据和索引，数据文件和索引文件是聚集的，速度快。
- 聚簇索引：每张表的主键构建的B+树，同时叶子节点中存放的即为整张表的记录数据。
- 辅助索引：用户定义地索引，又称二级索引/非主键索引。叶子节点=键值+书签。Innodb存储引擎的书签就是相应行数据的主键索引值。
- 为什么非主键索引结构,叶子节点存储的是主键值？(一致性和节省存储空间)
为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
- 主键：如果不设置主键ID，Mysql就会从第一列开始找不相同的一列为默认主键ID，如果没有这一列，就会自行创建以一个rowId作为主键Id。所以设置主键，减少Mysql底层行为，符合高效原则
- 整型主键：B+树存储主键，比较整型比字符型速度快很多
- 自增主键：基于B+树的添加结点原则，叶子节点有双指针，该列所有数据都是递增的，如果查询一个不是自增的主键，可能导致该叶子节点分裂，节点中的冗余数据在叶子和父亲节点都存在一次，影响比较效率。
Mysql查询文件页大小：默认是16K，文件页可以理解为B+树中一个节点大小。
SHOW GLOBAL STATUS like 'Innodb_page_size’;
为什么Mysql中将文件页默认设置为16K？
- 效率高，并且树不高的情况也能存储大量数据。
- 比如，一个叶子节点中存储的一条数据大小为1K(通常都小于1K)，一个叶子节点就能存储16条数据。非叶子结点中，假设主键ID为
bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)。一颗高度为3的B+树能存储的数据为：1170117016=21902400（千万级条）
MyISAM
- 使用.myi、.myd存储索引和数据，数据文件和索引文件是非聚集的。
- 主键索引存储在.myi文件中，叶子节点存储的是主键在磁盘的内存地址，再去.myd文件查数据（与InnoDB的区别）
InnoDB和MyISAM区别
| InnoDB和MyISAM区别 | InnoDB | MyISAM |
|---|---|---|
| 事务 | 支持 | 不支持 |
| 锁 | 行级锁和表锁 | 表级锁 |
| MVCC | 支持 | 不支持 |
| 外键 | 支持 | 不支持 |
| 行数 | 不保存 | 内置计数器，保存行数 |
| 概念 | 数据和索引都存储在.idb文件上 | 索引存在.myi上，数据存在.myd上 |
| 特性 | 支持事务、外键、恢复 | 优点是读取数据快，缺点是更新数据慢 |
Mysql底层数据结构
Mysql底层使用B+树，原因如下：
（1）减少IO操作：索引文件很大，不能全部存储在内存中，只能存储到磁盘上，因此索引的数据结构要尽量减少查找过程中磁盘 I/O 的存取次数；
（2）降低检索次数：数据库系统利用了磁盘预读原理和磁盘预读，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。而 B + 树的高度是 2~4，检索一次最多只需要访问 4 个节点（4 次，即树的高度）。
为什么不用B树作为底层数据结构：
| 为什么不用B树作为底层数据结构 | B+树 | B树 |
|---|---|---|
| 非叶子结点 | 只存索引 | 索引+数据，查找效率较低 |
| 叶子节点 | 索引+数据；并且可以向后遍历 | 索引+数据；不能向后遍历 |
索引类型
| Mysql索引类型 | 解释 |
|---|---|
| 普通索引 | 表中普通列构成的索引，没有任何限制 |
| 唯一索引 | 必须唯一，允许有空值。如果是组合索引，列值的组合必须唯一 |
| 主键索引 | 特殊的唯一索引，根据主键建立索引，不能为空和重复 |
| 全文索引 | =倒排索引，快速匹配文档的方式 |
| 组合索引 | 多个列建立的索引，这多个列中的值不允许有空值 |
注意：聚簇索引和非聚簇索引不是索引类型，是一种存储数据的方式！
| 聚簇索引和非聚簇索引 | 解释 |
|---|---|
| 聚簇索引 | 又称为主索引，该索引中键值的逻辑顺序决定了表中相应行的物理顺序。因为数据真正的数据只能有一种排序方式，所以一个表上只能有一个聚簇索引 |
| 非聚簇索引 | 又称为辅助索引、普通索引，该索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表可以包含多个非聚集索引 |
组合索引底层数据结构
存储原则：最左前缀原理（左到右，依次大小比较）
非常重要：查询时，是怎样使用到了该联合主键？
- 必须先定位最左字段，才能是正确使用了联合索引，比如联合主键如下图所示，只能是
where name =XX开头才能走联合索引，否则会失效。
总结：判断是否使用联合索引，联想下面这张图是否能走！
索引失效
- 条件中有 or；
- like 查询（以 % 开头）；
- 如果列类型是字符串，那一定要在条件中将数据使用引号引用起来，否则不使用索引；
- 对列进行函数运算（如 where md5 (password) = “xxxx”）；
- 负向查询条件会导致无法使用索引，比如 NOT IN,NOT LIKE,!= 等；
- 对于联合索引，不是使用的第一部分 (第一个)，则不会使用索引（最左匹配）；
- 如果 mysql 评估使用全表扫描要比使用索引快，则不使用索引
Float、Decimal 类型存储金额
| 名称 | 解释 |
|---|---|
| Float、Double | 非标准数据类型，存储金额时存储的是近似值，存在精度问题 |
| Decimal、Numeric | 标准数据类型，存储金额时存储的是精确值（以字符串的形式保存数值） |
悲观锁和乐观锁
| 悲观锁 | 乐观锁 | |
|---|---|---|
| 概念 | 对于同一个数据的并发操作，认在使用数据时一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改 | 认为在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试） |
| 应用场景 | 传统的关系型数据库中使用较广，比如行锁，表锁等，都是在做操作之前先上锁。Java 中 synchronized 和 ReentrantLock 等独占锁也是悲观锁思想的实现 | 可以用版本号机制或 CAS 算法实现，Java 中的 AtomicInteger 等原子变量类使用的就是乐观锁 CAS 算法。 |
| 响应速度 | 慢 | 快 |
| 业务场景 | 读少写多 | 读多写少 |
事务
概念：执行一系列基本操作后，这些基本操作组成一个逻辑工作单元一起向数据库提交，要么都执行，要么都不执行，叫数据库事务
ACID原则
| ACID原则 | 解释 |
|---|---|
| 原子性 | 事务是一个完整操作，参与事务的逻辑单元要么都执行，要么都不执行 |
| 一致性 | 在事务执行完毕后，数据都必须处于一致的状态 |
| 隔离性 | 对数据进行修改的所有并发实发都会彼此隔离的，它不应以任何方式依赖或影响其他事务 |
| 持久性 | 在事务操作完成后，对数据的修改将持久化到永久存储中 |
事务隔离级别
事务个隔离级别越高，并发问题越少，但是付出的代价也越大
show variables like 'tx_isolation';# 查看隔离级别 set tx_isolation = 'REPEATABLE-READ';# 默认隔离级别就是可重复读，Spring框架如果没有指定也是可重复读
| 隔离级别 | 脏读 | 不可重复度 | 幻读 |
|---|---|---|---|
| 读未提交（Read Uncommitted） | 可能 | 可能 | 可能 |
| 读已提交（Read Commited） | 不可能 | 可能 | 可能 |
| 可重复读（默认级别，Repeatable Read） | 不可能 | 不可能 | 可能 |
| 可串行化（Serializable） | 不可能 | 不可能 | 不可能 |
| 事务并发问题 | 描述 |
|---|---|
| 更新丢失 | 最后的更新覆盖了其他事务所做的更新 |
| 脏读 | 事务A读取到了事务B修改但未提交的数据。此时，如果事务B回滚事务，事务A读取的数据就无效，不满足一致性 |
| 不可重复读 | 事务A内部的相同查询语句在不同时刻读出的结果不一致，不符合隔离性。 |
| 幻读 | 事务A读取到了事务B提交的新增数据，不符合隔离性 |
事务7大传播行为
| 事务传播行为 | 解释 |
|---|---|
| propagation_required | 有事务，就加入当前事务；没有事务，就创建新的事务（默认） |
| propagation_required_new | 无论有没有事务，都创建新的事务 |
| propagation_supports | 有事务，就加入当前事务；没有事务，就以非实物执行 |
| propagation_not_supported | 有事务，将当期事务挂起，以非事务执行；没有事务，以非实物执行 |
| propagation_mandatory | 有事务，就加入当前事务；没有事务，就抛出异常 |
| propagation_never | 有事务，抛出异常，以非事务执行；没有事务，以非事务执行 |
| propagation_nested | 有事务，则嵌套事务内执行；没有事务，就新建一个事务 |
实现分布式锁
基于数据库实现。 利用主键唯一的特性，如果有多个请求同时提交到数据库的话，数据库会保证只有一个操作可以成功，那么我们就可以认为操作成功的那个线程获得了该方法的锁，当方法执行完毕之后，想要释放锁的话，删除这条数据库记录即可。易于理解，但是可能出现单点故障，性能也可能成为瓶颈。
基于 redis 实现。 主要利用 redis 的 setnx () 和 expire () 方法。使用步骤：
- setnx (lockkey, 1) 如果返回 0，则说明占位失败；如果返回 1，则说明占位成功；
- expire () 命令对 lockkey 设置超时时间，为的是避免死锁问题；
- 执行完业务代码后，可以通过 delete 命令删除 key。
基于 Zookeeper 实现分布式锁。 利用临时节点与 watch 机制。每个锁占用一个普通节点 /lock，当需要获取锁时在 /lock 目录下创建一个临时节点，创建成功则表示获取锁成功，失败则 watch/lock 节点，有删除操作后再去争锁。临时节点好处在于当进程挂掉后能自动上锁的节点自动删除即取消锁。
加问： redis 的 setnx () 和 expire () 方法出现宕机怎么办呐？
- setnx (lockkey, 当前时间 + 过期超时时间)，如果返回 1，则获取锁成功；如果返回 0 则没有获取到锁，转向 B。
- get (lockkey) 获取值 oldExpireTime ，并将这个 value 值与当前的系统时间进行比较，如果小于当前系统时间，则认为这个锁已经超时，可以允许别的请求重新获取，转向 C。
- 计算 newExpireTime = 当前时间 + 过期超时时间，然后 getset (lockkey, newExpireTime) 会返回调用前的 lockkey 的值 currentExpireTime。
- 判断 currentExpireTime 与 oldExpireTime 是否相等，如果相等，说明当前 getset 设置成功，获取到了锁。如果不相等，说明这个锁又被别的请求获取走了，那么当前请求可以直接返回失败，或者继续重试。
- 在获取到锁之后，当前线程可以开始自己的业务处理，当处理完毕后，比较自己的处理时间和对于锁设置的超时时间，如果小于锁设置的超时时间，则直接执行 delete 释放锁；如果大于锁设置的超时时间，则不需要再锁进行处理。
数据库优化
应用层架构优化。核心是减少对数据库的调用次数，本质上是从业务应用层来审视流程是否合理，常用的方案有：
- 引入缓存，虚拟一层中间层，减少对数据库的读写；
- 将多次单个调用改为批量调用，比如说循环十次主键 select * FROM t where id = 'xx’改为使用 IN 一性次读取 select * FROM t where id IN (‘xx’,‘xx’,…)；
- 使用搜索引擎。
数据库架构优化。核心是优化各种配置，提升数据库的性能，可分为：
- 优化 SQL 及索引，以达到减少数据访问、返回更少数据、减少交互次数等目标。常用的手段包括：创建并正确地使用索引（比如说减少回表查询）、优化执行计划、数据分页处理、只取需要的字段、慢查询优化、使用搜索引擎等；
- 优化数据库表结构。常用的的手段包括：使用占用空间最小的数据类型、使用简单的数据类型、尽可能地使用 NOT NULL 定义字段、尽量少使用 text 字段、分库分表等；
- 优化系统配置。包括操作系统的配置优化和数据库的配置优化。
- 操作系统优化。数据库是基于操作系统（多为 Linux 系统）的，所以对于合理使用操作系统也会影响到数据库的性能。比如将数据库服务器应和业务服务器隔离、或者设置 net.ipv4.tcp_max_syn_backlog = 65535 以增加 tcp 支持的队列数等等；
- 数据库配置文件优化，以 MySQL 配置为例，可以修改 innodb_buffer_pool_size（设置数据和索引缓存的缓冲池）、max_connections 等参数。
- 优化硬件配置。比如说使用更好的服务器、更快的硬盘、更大的内存等等。
Redis
答：redis（Remote Dictionary Server远程字典服务），是一款高性能的(key/value)分布式内存数据库，基于内存运行并支持持久化的NoSQL数据库。因为数据都在内存中，所以运行速度快。redis支持丰富的数据类型并且支持事务，事务中的所有命令会被序列化、按顺序执行，在执行的过程中不会被其他客户端发送来的命令打断
数据类型
redis支持五种数据类型作为其Value，redis的Key都是字符串类型的。以下是value的数据类型
| 名称 | 解释 | 场景 | 底层 |
|---|---|---|---|
| String | 最常用 | 计数功能，比如微博数等 | 动态字符串(SDS |
| hash | value也是一个键值对 | 合用于存储对象。比如我们可以 hash 数据结构来存储用户信息，商品信息等等 | 字典、压缩列表 |
| set | 一个无序集合，且其中的元素不重复 | 全局去重的功能，比如说是否给帖子点赞数；也可以判断某个元素是否在 set，比如说判断是否给某个回复点赞。另外还可以利用交集、并集、差集等操作来支撑更多的业务场景，比如说找出两个微博 ID 的共同好友等； | 字典、整数集合 |
| list | 一个链表集合，可以重复元素 | 可以做简单的消息队列的功能，比如论坛点赞人列表、微博粉丝列表等；另外还可以利用 lrange 命令，可以从某个元素开始读取多少个元素，实现简单的高性能分页，类似微博那种下拉不断分页的东西，性能极佳，用户体验好 | 压缩列表、双端链表 |
| zset | 相比 set 增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列 | 可以用于取排行榜 top N 的用户 | 压缩列表、跳跃表和字典 |
常用指令
String的常用指令
Hash常用命令
List常用命令
set常用指令
zset常用指令
bitmap常用指令
redis配置文件
在解压目录下有个配置文件 redis.windows.conf（大家可以自行查阅），在配置文件中对redis进行了分模块配置，常用的模块如下：
- NETWORK：该模块可以配置一些redis服务器地址，端口以及超时时间等
- GENERAL：该模块可以对日志文件的路径和日志级别等进行配置
- SNAPSHOTTING：redis持久化配置信息等
- REPLICATION：redis集群配置等信息
- MEMORY MANAGEMENT：内存管理，包括数据过期删除策略信息的设置
- APPEND ONLY MODE：日志持久化方式信息设置
Redis管道
Redis事务
淘汰机制
| 策略 | 描述 |
|---|---|
| volatile-lru | 从已设置过期时间的数据集中挑选最近最少使用的数据淘汰 |
| volatile-ttl | 从已设置过期时间的数据集中挑选将要过期的数据淘汰 |
| volatile-random | 从已设置过期时间的数据集中任意选择数据淘汰 |
| allkeys-lru | 从所有数据集中挑选最近最少使用的数据淘汰 |
| allkeys-random | 从所有数据集中任意选择数据进行淘汰 |
| noeviction | 当内存不足以容纳新写入数据时，新写入操作会报错。很少使用 |
前缀 volatile 和 allkeys 用于区分淘汰数据的数据集是从已设置过期时间的数据集还是从全部数据集中选取，后面的 lru、ttl 以及 random 是三种不同的淘汰策略，再加上一种 no-enviction 永不回收的策略。其中最常使用的是 volatile-lru/allkeys-lru
RDB和AOF区别
| 持久化方式 | RDB | |
|---|---|---|
| 概念 | 数据集快照的方式，定时将 redis 存储的数据生成快照并存储到磁盘等.rdb介质上 | 所有的命令行记录以 redis 命令请求协议的格式完全持久化存储) 保存为 .aof 文件 |
| 特点 | 优点是适合存储大量数据，性能最好；缺点是安全性低 | 优点是数据安全；缺点是速度慢，AOF文件较大 |
Redis三种集群模式
缓存雪崩
缓存雪崩：同一时刻，缓存大量失效，导致大量原本应该走缓存的请求去查询数据库，给数据库造成大量压力，容易使其宕机
解决办法：
- 前端请求加锁访问，但是吞吐量会明显下降，适合并发量较低的情况。
- 后端采用限流算法，限制请求流量，但有损业务，比如使用Hystrix限流降级组件
- 设置不同的过期时间：将缓存过期时间分散开，比如说设置过期时间时再加上一个较小的随机值时间，使得每个 key 的过期时间，不会集中在同一时刻失效；
- 使用集群或者哨兵：保证缓存层服务高可用性，比如使用Redis Sentinel或Redis Cluster。
缓存穿透
缓存穿透：由于缓存系统故障或者用户频繁查询系统中不存在的数据，请求直接打在数据库上，造成数据库过载，引发并发问题
解决办法：
- 布隆过滤器，将所有可能存在的数据哈希到一个足够大的 bitmap 中，在查询的时候先去布隆过滤器去查询 key 是否存在，不存在的 key 就直接返回；
- cache null策略，如果一个查询结果为null，仍然把该null作为value存到缓存层中，但设置它的过期时间很短，当用户再次请求相同key时，缓存层直接返回该null不走数据库查询，减轻数据库压力
布隆过滤器
布隆过滤器就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。
向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。
向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都为 1，只要有一个位为 0，那么说明布隆过滤器中这个key 不存在。如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。
方法适用于数据命中不高、 数据相对固定、 实时性低（通常是数据集较大） 的应用场景， 代码维护较为复杂， 但是缓存空间占用很少。
可以用guvua包自带的布隆过滤器，引入依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>22.0</version>
</dependency> 示例伪代码：
import com.google.common.hash.BloomFilter;
//初始化布隆过滤器
//1000：期望存入的数据个数，0.001：期望的误差率
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.001);
//把所有数据存入布隆过滤器
void init(){
for (String key: keys) {
bloomFilter.put(key);
}
}
String get(String key) {
// 从布隆过滤器这一级缓存判断下key是否存在
Boolean exist = bloomFilter.mightContain(key);
if(!exist){
return "";
}
// 从缓存中获取数据
String cacheValue = cache.get(key);
// 缓存为空
if (StringUtils.isBlank(cacheValue)) {
// 从存储中获取
String storageValue = storage.get(key);
cache.set(key, storageValue);
// 如果存储数据为空， 需要设置一个过期时间(300秒)
if (storageValue == null) {
cache.expire(key, 60 * 5);
}
return storageValue;
} else {
// 缓存非空
return cacheValue;
}
} 算法
排序算法
冒泡排序
public static <E extends Comparable<E>> void bubbleSort1(E[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 优化：设置交换标志位
boolean isSwap = false;
for (int j = 0; j < arr.length - 1 - i && arr[j].compareTo(arr[j + 1]) > 0; j++) {
swap(arr, j, j + 1);
isSwap = true;
}
// 内层没有发生交换，说明前面已经都排好序了，就不用再次比较
if (!isSwap) {
break;
}
}
} 选择排序
public static <E extends Comparable<E>> void selectionSort(E[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[minIndex].compareTo(arr[j]) < 0 ? minIndex : j;
}
swap(arr, i, minIndex);
}
} 插入排序
public static <E extends Comparable<E>> void insertSort1(E[] data) {
for (int i = 0; i < data.length; i++) {
E temp = data[i];
int j;
// 内层循环从后往前找位置腾出
for (j = i; j - 1 >= 0 && temp.compareTo(data[j - 1]) < 0; j--) {
data[j] = data[j - 1];
}
// 空出的位置赋值temp
data[j] = temp;
}
} 归并排序
public static <E extends Comparable<E>> void mergeSort(E[] arr) {
// 优化3：只生成一次辅助数组，并且merge中没有偏移量的操作了
// Arrays.copyOf将源数组指定长度的元素复制成一个新数组
E[] temp = Arrays.copyOf(arr, arr.length);
mergeSort(arr, 0, arr.length - 1, temp);
}
private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, E[] temp) {
// 优化2：指定长度内，可使用直接插入排序优化，但这种优化效果不明显，所以这里放弃使用
if (l >= r) {
return;
}
// 先分解
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid, temp);
mergeSort(arr, mid + 1, r, temp);
// 优化1:arr[mid]>arr[mid]+1,再归并
if (arr[mid].compareTo(arr[mid + 1]) > 0) {
merge(arr, l, mid, r, temp);
}
}
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
System.arraycopy(arr, l, temp, l, r - l + 1);
// p,q遍历左右数组
int p = l, q = mid + 1;
// i遍历原数组
for (int i = l; i <= r; i++) {
if (p > mid) {
arr[i] = temp[q++];
} else if (q > r) {
arr[i] = temp[p++];
} else if (temp[p].compareTo(temp[q]) <= 0) {
arr[i] = temp[p++];
} else {
arr[i] = temp[q++];
}
}
} 快速排序
荷兰国旗问题
问题：将<t数放左边，=t放中间，>t的放右边
private static void question1(int[] arr, int l, int r, int t) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < t) {
swap(arr, ++less, l++);
} else if (arr[l] > t) {
swap(arr, --more, l);
} else {
l++;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} 单路快排
public static <E extends Comparable<E>> void quickSort(E[] arr) {
// 优化1：内存操作只生成一个random
Random random = new Random();
quickSort(arr, 0, arr.length - 1, random);
}
private static <E extends Comparable<E>> void quickSort(E[] arr, int l, int r, Random random) {
if (l >= r) return;
// 先划分区间
int p = partition(arr, l, r, random);
// 在递归排序
quickSort(arr, l, p - 1, random);
quickSort(arr, p + 1, r, random);
}
private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {
// 优化2：生成[l,r]的随机值并交换，解决有序数组的问题
int p = l + random.nextInt(r - l + 1);
swap(arr, l, p);
// 比较基准：arr[l]
// j指向<基准的最后一个数的索引
int j = l;
for (int i = l + 1; i <= r; i++) {
// 这里实现了>=的放右边
if (arr[i].compareTo(arr[l]) < 0) {
j++;
swap(arr, i, j);
}
}
// 循环跳出，将指向<value区间最后一个元素的j与指向枢纽j的元素交换
swap(arr, l, j);
return j;
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
} 双路快排
// 双路快速排序
public static <E extends Comparable<E>> void quickSort2ways(E[] arr) {
Random random = new Random();
quickSort2ways(arr, 0, arr.length - 1, random);
}
private static <E extends Comparable<E>> void quickSort2ways(E[] arr, int l, int r, Random random) {
if (l >= r) return;
int p = partition(arr, l, r, random);
quickSort2ways(arr, l, p - 1, random);
quickSort2ways(arr, p + 1, r, random);
}
private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {
int p = l + random.nextInt(r - l + 1);
swap(arr, l, p);
// i指向<=的区间的后一个元素，j指向>=区间的前一个元素
// 初始化i指向l前一个位置，j指向数组末尾
int i = l + 1, j = r;
while (true) {
while (i <= j && arr[i].compareTo(arr[l]) < 0) {
i++;
}
while (i <= j && arr[j].compareTo(arr[l]) > 0) {
j--;
}
// 前面有i++,j--,判断一下i>=j
if (i >= j) {
break;
}
// 走到这里，说明左边的j指向>=准基，右边的i指向<=准基
// 于是，就交换，将j指向的大的数换到i的位置上
swap(arr, i, j);
// 移动指针
i++;
j--;
}
// 将j和目标值l交换
swap(arr, l, j);
return j;
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
} 三路快排
// 三路快排:波波老师写法
public static <E extends Comparable<E>> void quickSort3ways(E[] arr) {
Random random = new Random();
quickSort3ways(arr, 0, arr.length - 1, random);
}
private static <E extends Comparable<E>> void quickSort3ways(E[] arr, int l, int r, Random random) {
if (l >= r) return;
int p = l + random.nextInt(r - l + 1);
swap(arr, l, p);
// 核心：arr[l+1,lt]<v ; arr[lt+1,i-1]=v ; arr[gt,r]>v
// lt指向<的最后一个元素，i指针遍历，gt指向>的第一个元素
int lt = l, i = l + 1, gt = r + 1;
while (i < gt) {
if (arr[i].compareTo(arr[l]) < 0) {
lt++;
swap(arr, i, lt);
i++;
} else if (arr[i].compareTo(arr[l]) > 0) {
gt--;
swap(arr, i, gt);
// 原先的gt--后的值没有比较过，i继续指向它，不用i++
} else {
// arr[i]==arr[l]
i++;
}
}
swap(arr, l, lt);
// 三路快排抛弃掉中间的部分，不再递归
quickSort3ways(arr, l, lt - 1, random);
quickSort3ways(arr, gt, r, random);
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
} 堆排序
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 1.从小到大排序，先转成大根堆，让数组第一位成数组最大值，便于与末尾交换
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
// 2.交换数组第一位和末尾，最大值放到数组末尾
int size = arr.length;
swap(arr, 0, --size);
// 3.堆化排序
while (size > 0) {
heapIfy(arr, 0, size);
swap(arr, 0, --size);
}
}
// 数组转成大根堆
private static void heapInsert(int[] arr, int i) {
// 孩子节点大于父节点就交换
while (arr[i] > arr[(i - 1) / 2]) {
swap(arr, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
// 堆化调整
private static void heapIfy(int[] arr, int index, int size) {
// 1.获取当前下标的左孩子索引
int left = 2 * index + 1;
// 2.while遍历，找到左右孩子中最大值与index交换
while (left < size) {
// 3.先找出左右孩子中最大值索引
int largest = left + 1 < size &&
arr[left + 1] > arr[left] ? left + 1 : left;
// 4.再找出左右孩子中最大值与arr[index]中最大值索引
largest = arr[largest] > arr[index] ? largest : index;
// 5.如果最大值还是当前索引，就停止堆化调整
if (largest == index) {
break;
}
// 6.找到最大值索引就交换
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
} 希尔排序
public class ShellSort {
private ShellSort() {
}
// 希尔排序1：三重循环
public static <E extends Comparable<E>> void shellSort1(E[] arr) {
// 希尔的步长
int step = arr.length / 2;
while (step >= 1) {
// start是每个子数组的起始位置
for (int start = 0; start < step; start++) {
// 以下是使用插入排序
// 对每个子数组进行插入排序:data[start+step,start+2h...data.length-1]
for (int i = start + step; i < arr.length; i += step) {
E temp = arr[i];
int j;
// 前一个元素是j-step
for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) {
arr[j] = arr[j - step];
}
arr[j] = temp;
}
}
step = step / 2;
}
}
// 希尔排序2:二重循环，背这个版本
public static <E extends Comparable<E>> void shellSort2(E[] arr) {
// 希尔的步长
int step = arr.length / 2;
while (step >= 1) {
// 对每个子数组进行插入排序:data[start+h,start+2h...data.length-1]
for (int i = step; i < arr.length; i++) {
E temp = arr[i];
int j;
// 前一个元素是j-step
for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) {
arr[j] = arr[j - step];
}
arr[j] = temp;
}
step = step / 2;
}
}
// 希尔排序3：修改步长序列
public static <E extends Comparable<E>> void shellSort3(E[] arr) {
// 希尔的步长
int step = 1;
while (step < arr.length) {
step = step * 3 + 1;
}
while (step >= 1) {
// 对每个子数组进行插入排序:data[start+h,start+2h...data.length-1]
for (int i = step; i < arr.length; i++) {
E temp = arr[i];
int j;
// 前一个元素是j-step
for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) {
arr[j] = arr[j - step];
}
arr[j] = temp;
}
step = step / 3;
}
}
}
桶排序
public class BucketSort {
public static void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 1.从所有数中找出最大值
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 2.生成max+1个元素的桶数组，因为[0.max]有max+1的元素
int[] bucket = new int[max + 1];
// 3.遍历数组，每个元素出现的个数加入桶
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
// 4.遍历桶，将非0数据放回原数组
int i = 0;// i遍历数组
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
} 计数排序
力扣75题为例
public class LC75 {
// 计数排序法:针对本题的方法，只能判断指定点的计数排序
public void sortColors(int[] nums) {
int[] cnt = new int[3];
// nums[i]对应arr[X]索引的元素个数
for (int num : nums) {
cnt[num]++;
}
// 存放0位置
// nums[0,cnt-1]=0
for (int i = 0; i < cnt[0]; i++) {
nums[i] = 0;
}
// 存放1位置
// nums[cnt[0],cnt[0]+cnt[1]]=1
for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) {
nums[i] = 1;
}
// 存放2位置
// nums[cnt[0]+cnt[1],n-1]
for (int i = cnt[0] + cnt[1]; i < nums.length; i++) {
nums[i] = 2;
}
}
// 计数排序法：通用写法
public void sortColors1(int[] nums) {
// 1.指定处理元素区间长度R和计数数组cnt，处理元素范围[0,R)的计数排序
int R = 3;
int[] cnt = new int[R];
for (int num : nums) {
cnt[num]++;
}
// 2.创建index数组，长度为R+1
int[] index = new int[R + 1];
for (int i = 0; i < R; i++) {
// [index[i],index[i+1]]的值为i
// index[i]表示前i的元素的合
index[i + 1] = index[i] + cnt[i];
}
// 3.业务逻辑代码
for (int i = 0; i + 1 < index.length; i++) {
for (int j = index[i]; j < index[i + 1]; j++) {
nums[j] = i;
}
}
}
} 斐波那契
public class Solution {
public int fib(int n) {
if (n < 0) {
throw new RuntimeException("n<0");
} else {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
public int fib1(int n) {
if (n < 0) {
throw new RuntimeException("n<0");
} else {
if (n < 2) {
return n;
}
int a = 0;
int b = 1;
int sum = 0;
for (int i = 2; i <= n; i++) {
sum = a + b;
a = b;
b = sum;
}
return sum;
}
}
} 二分查找
标准二分查找模版
public static int binarySearch1(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
} 搜索旋转排序数组
// 33：搜索旋转排序数组
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
}
// 左边有序
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {// 右边有序
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
} 平方根问题
public class Solution {
public int mySqrt(int x) {
int l = 1, r = (x / 2) + 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (mid == x / mid) {
return mid;
} else if (mid > x / mid) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return r;
}
} 栈实现队列
public class MyQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public MyQueue() {
stackPush = new Stack<>();
stackPop = new Stack<>();
}
// push栈向pop栈压入方法：摊还时间复杂度
private void pushToPop() {
// 原则:pop栈为空，必须将push栈全部压入
while (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
}
public void push(int x) {
pushToPop();
stackPush.push(x);
pushToPop();
}
public int pop() {
if (empty()) {
throw new IllegalArgumentException("Stack is Empty");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (empty()) {
throw new IllegalArgumentException("Stack is Empty");
}
pushToPop();
return stackPop.peek();
}
public boolean empty() {
// 两个栈都空才是队列空
return stackPush.isEmpty() && stackPop.isEmpty();
}
} 队列实现栈
class MyStack {
// 用一个队列实现栈
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
// 1.先记录模拟栈原数据个数
int n = queue.size();
// 2.新数据进栈
queue.offer(x);
// 3.之前个数的元素重新入栈
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
} 设计一个getMin功能的栈
public class Mystack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public Mystack() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
public void push(int newValue) {
if (stackMin.isEmpty()) {
stackMin.push(newValue);
} else if (newValue < getMin()) {
stackMin.push(newValue);
} else {
stackMin.push(getMin());
}
stackData.push(newValue);
}
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
stackMin.pop();
return stackData.pop();
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty");
}
return stackMin.peek();
}
} 生产者消费者问题
syn版本
class MyResources1 {
private int num = 0;
// 方式一：synchronized+wait+notifyAll
//生产者,规定：生产一个，消费一个
public synchronized void productor() {
//1 判断，生产者等待的条件：产品数量等待消费，num>0
while (num != 0) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//2 干活
num++;
System.out.println(Thread.currentThread().getName() + "\tnum值：" + num);
//3 通知唤醒
notifyAll();
}
//消费者
public synchronized void consumer() {
//1 判断 多线程是while判断
while (num == 0) {
try {
wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
//2 干活：消费
num--;
System.out.println(Thread.currentThread().getName() + "\tnum值：" + num);
//3 通知唤醒
notifyAll();
}
} public class ProductorAndConsumerDemo {
public static void main(String[] args) {
MyResources1 myResources = new MyResources1();
//MyResources2 myResources = new MyResources2();
for (int i = 1; i <= 5; i++) {
new Thread(() -> {
try {
myResources.productor();
} catch (Exception e) {
e.printStackTrace();
}
}, "线程1").start();
}
for (int i = 1; i <= 5; i++) {
new Thread(() -> {
try {
myResources.consumer();
} catch (Exception e) {
e.printStackTrace();
}
}, "线程2").start();
}
}
}
执行结果：
线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0
Lock版本
class MyResources2 {
private int num = 0;
private Lock lock = new ReentrantLock();
private Condition condition = lock.newCondition();
// 方式二：lock/condition+await+signalAll
//生产者,规定：生产一个，消费一个
public void productor() {
lock.lock();
try {
//1 判断，生产者等待的条件：产品数量等待消费，num>0
while (num != 0) {
condition.await();
}
//2 干活
num++;
System.out.println(Thread.currentThread().getName() + "\tnum值：" + num);
//3 通知唤醒
condition.signalAll();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
//消费者
public void consumer() {
lock.lock();
try {
//1 判断 多线程是while判断
while (num == 0) {
condition.await();
}
//2 干活：消费
num--;
System.out.println(Thread.currentThread().getName() + "\tnum值：" + num);
//3 通知唤醒
condition.signalAll();
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
} public class ProductorAndConsumerDemo {
public static void main(String[] args) {
//MyResources1 myResources = new MyResources1();
MyResources2 myResources = new MyResources2();
for (int i = 1; i <= 5; i++) {
new Thread(() -> {
try {
myResources.productor();
} catch (Exception e) {
e.printStackTrace();
}
}, "线程1").start();
}
for (int i = 1; i <= 5; i++) {
new Thread(() -> {
try {
myResources.consumer();
} catch (Exception e) {
e.printStackTrace();
}
}, "线程2").start();
}
}
} 执行结果：
线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0 线程1 num值：1 线程2 num值：0
阻塞队列版
class MyResources3 {
// 标识位，进行生产+消费，volatile保证可见性
private volatile boolean FLAG = true;
// 多线程使用AtomicInteger，不用int
private AtomicInteger atomicInteger = new AtomicInteger();
// 生产环境：不能具体使用7种具体类
BlockingQueue<String> blockingQueue = null;
// 生产环境：穿接口
public MyResources3(BlockingQueue<String> blockingQueue) {
this.blockingQueue = blockingQueue;
// 输出/日志打印一下，便于排查
System.out.println(blockingQueue.getClass().getName());
}
public void provider() throws Exception {
String data = null;
boolean retValue;
while (FLAG) {
data = atomicInteger.incrementAndGet() + "";
retValue = blockingQueue.offer(data, 2L, TimeUnit.SECONDS);
if (retValue) {
System.out.println(Thread.currentThread().getName() + "\t 插入数据：" + data + "成功");
} else {
System.out.println(Thread.currentThread().getName() + "\t 插入数据：" + data + "失败");
}
//生产休息，等待消费
TimeUnit.SECONDS.sleep(1);
}
//生产永久结束
System.out.println(Thread.currentThread().getName() + "\t生产结束，不再生产");
}
public void consumer() throws Exception {
String result = null;
while (FLAG) {
result = blockingQueue.poll(2L, TimeUnit.SECONDS);
//消费永久结束队=列里面没有值，消费也失败，就将标识改为false
if (result == null || result.equalsIgnoreCase("")) {
FLAG = false;
System.out.println(Thread.currentThread().getName() + "\t没有产品，消费退出");
return;//退出
}
System.out.println(Thread.currentThread().getName() + "\t 消费数据：" + result + "成功");
}
}
public void stop() {
this.FLAG = false;
}
} public class ProviderAndConsumerByBlockQueue {
public static void main(String[] args) {
BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(10);
MyResources3 myShare = new MyResources3(blockingQueue);
new Thread(() -> {
System.out.println(Thread.currentThread().getName() + "\t 生产线程启动");
try {
myShare.provider();
} catch (Exception e) {
e.printStackTrace();
}
}, "生产者").start();
new Thread(() -> {
System.out.println(Thread.currentThread().getName() + "\t 消费线程启动");
try {
myShare.consumer();
} catch (Exception e) {
e.printStackTrace();
}
}, "消费着").start();
//暂停一会儿
try {
TimeUnit.SECONDS.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("5s到，全部活动结束");
myShare.stop();
}
} 执行结果：
生产者 生产线程启动 消费着 消费线程启动 生产者 插入数据：1成功 消费着 消费数据：1成功 生产者 插入数据：2成功 消费着 消费数据：2成功 生产者 插入数据：3成功 消费着 消费数据：3成功 生产者 插入数据：4成功 消费着 消费数据：4成功 生产者 插入数据：5成功 消费着 消费数据：5成功 5s到，全部活动结束 生产者 生产结束，不再生产 消费着 没有产品，消费退出
LRU算法
力扣146：LRU算法
public class LRUCache {
class DoubleNode {
int key;
int value;
DoubleNode pre;
DoubleNode next;
DoubleNode(int key, int value) {
this.key = key;
this.value = value;
}
DoubleNode() {
}
}
private HashMap<Integer, DoubleNode> cache = new HashMap<>();
private int size;
private int capacity;
private DoubleNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.head = new DoubleNode();
this.tail = new DoubleNode();
// 创建伪头部和伪尾部，减少添加和删除的逻辑
head.next = tail;
tail.pre = head;
}
public int get(int key) {
// 1.获取get元素
DoubleNode node = cache.get(key);
// 2.get元素不存就返回-1
if (node == null) {
return -1;
}
// 3.get元素就移动至头部，规定常用元素移动至头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
// 1.获取put元素
DoubleNode node = cache.get(key);
// 2.put元素不存在
if (node == null) {
// 生成它
DoubleNode nowNode = new DoubleNode(key, value);
// 放进cache
cache.put(key, nowNode);
// 添加进头部
addToHead(nowNode);
// 长度++
size++;
// 判断是否超过指定长度
if (size > capacity) {
DoubleNode tail = removeTail();
cache.remove(tail.key);
size--;
}
} else {
// 3.node存在就更新value，然后移动至头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DoubleNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private DoubleNode removeTail() {
DoubleNode del = tail.pre;
removeNode(del);
return del;
}
private void removeNode(DoubleNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DoubleNode node) {
removeNode(node);
addToHead(node);
}
} 反转链表
public class ReverseList {
// 反转单链表：迭代
public Node reverserList(Node head) {
if (head == null || head.next == null) {
return head;
}
// 利用head遍历，节省一个空间
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
// 反转单链表：递归
public Node reverserList1(Node head) {
if (head == null || head.next == null) {
return head;
}
// 递归获取末尾节点
Node res = reverserList1(head.next);
// 如下的head从倒数第二个节点开始反转链表
head.next.next = head;
head.next = null;
return res;
}
// 反转双链表：迭代法
public DoubleNode reverserList(DoubleNode head) {
if (head == null || head.next == null) {
return head;
}
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
// 双向链表多加这一行
head.last = next;
pre = head;
head = next;
}
return pre;
}
} 判断链表有环
public class Solution {
// 141. 环形链表 I:判断是否有环
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return false;
}
ListNode fast = head.next.next;
ListNode slow = head.next;
while (fast != slow) {
if (fast.next == null || fast.next.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}
// 142. 环形链表 II:返回有环的第一个结点
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode fast = head.next.next;
ListNode slow = head.next;
// 1.使快慢指针第一次相遇
while (fast != slow) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// 2.如果相遇，快指针必须重新指向head
fast = head;
// 3.规律：第二次相遇的时候，一定在第一个入环的节点处
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
} 根号问题
public class Solution {
public static void main(String[] args) {
// JDK自带的根号api:2.23606797749979
System.out.println(Math.sqrt(5));
// 自己的实现根号的方法:2.236067
System.out.println(mathSqrt(5, 6));
}
/**
* @param n 开根号的数据
* @param m 精确的位数
* @return
*/
private static double mathSqrt(int n, int m) {
double[] decimals = new double[m];
if (m > 0) {
decimals = decimal(m);
}
int num = IntegerNum(n);
return square(n, num, decimals);
}
/**
* 计算整数位
*/
private static int IntegerNum(int n) {
if (n == 1) {
return 1;
}
int temp = 0;
for (int i = 1; i <= (n / 2 + 1); i++) {
if (i * i == n) {
temp = i;
break;
}
if (i * i > n) {
temp = i - 1;
break;
}
}
return temp;
}
/**
* 计算小数位
* 返回:[0.1, 0.01...]
*/
private static double[] decimal(int m) {
double[] arr = new double[m];
int index = 0;
while (index != m) {
double temp = 1;
for (int i = 0; i <= index; i++) {
temp *= 10;
}
arr[index] = 1 / temp;
index++;
}
return arr;
}
/**
* 合并整数位和小数位
*/
private static double square(int n, double num, double[] arr) {
double temp = num;
for (int p = 0; p < arr.length; p++) {
// 上一轮计算后的值赋给num
if (p > 0) {
num = temp;
}
// 小数位最高9位：比如0.1,0.2到0.9
for (int i = 1; i <= 9; i++) {
// 每次+0.1、0.2...+上一轮计算的值
temp = i * arr[p] + num;
if (temp * temp == n) {
return temp;
}
if (temp * temp > n) {
BigDecimal c1 = new BigDecimal(Double.toString(temp));
BigDecimal c2 = new BigDecimal(Double.toString(arr[p]));
temp = c1.subtract(c2).doubleValue();
break;
}
}
}
return temp;
}
} 合并两个有序数组
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int[] temp = new int[m + n];
int p = 0, q = 0, i = 0;
while (p < m && q < n) {
temp[i++] = nums1[p] < nums2[q] ? nums1[p++] : nums2[q++];
}
while (p < m) {
temp[i++] = nums1[p++];
}
while (q < n) {
temp[i++] = nums2[q++];
}
for (int j = 0; j < temp.length; j++) {
nums1[j] = temp[j];
}
} 二叉树最大深度
public class Solution {
// 递归法
public int maxDepth1(TreeNode root) {
if (root == null) {
return 0;
}
int lh = maxDepth1(root.left);
int rh = maxDepth1(root.right);
return Math.max(lh, rh) + 1;
}
// DFS法
public int maxDepth2(TreeNode root) {
if (root == null) {
return 0;
}
// 队列存每一层的结点个数
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int height = 0;
while (!queue.isEmpty()) {
// 队列非空，先获得当前层的所有结点个数
int nodeCount = queue.size();
// 将队列里的孩子节点入队，当前层结点个数-1
while (nodeCount > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
nodeCount--;
}
height++;
}
return height;
}
} 
