1、手撕观察者模式
抽象观察者接口(Observer)
- 为所有的具体观察者定义一个接口,在得到主题通知时更新自己。
public interface Observer {
/**
* 更新内容
*/
public void update(String msg);
}
- 为所有的具体观察者定义一个接口,在得到主题通知时更新自己。
抽象主题接口(Subject)
- 它把所有观察者对象的引用保存到一个聚集里,每个主题都可以有任何数量的观察者。抽象主题提供一个接口,可以增加和删除观察者对象,以及通知所有观察者。
public interface Subject {
/**
* 添加观察者
*/
void attach(Observer observer);
/**
* 删除观察者
*/
void detach(Observer observer);
/**
* 通知更新
*/
void notify(String msg);
}
- 它把所有观察者对象的引用保存到一个聚集里,每个主题都可以有任何数量的观察者。抽象主题提供一个接口,可以增加和删除观察者对象,以及通知所有观察者。
观察者接口实现类
实现抽象观察者角色所要求的更新接口,以便使本身的状态与主题状态保持一致。
public class TestObserver implements Observer{
private String info;
public TestObserver(String info){
this.info = info;
}
@Override
public void update(String msg) {
System.out.println(info + "----" + msg);
}
}
主题接口实现类
将有关状态存入具体观察者对象;当具体主题内部状态放生改变时,通知所有注册过的观察者。
public class TestSubject implements Subject{
private List<Observer> mList = new ArrayList();
@Override
public void attach(Observer observer) {
mList.add(observer);
}
@Override
public void detach(Observer observer) {
mList.remove(observer);
}
@Override
public void notify(String msg) {
for (Observer observer : mList) {
observer.update(msg);
}
}
}
测试
public class TestMain {
public static void main(String[] args) {
Subject subject = new TestSubject();
Observer observerA = new TestObserver("A:");
Observer observerB = new TestObserver("B:");
subject.attach(observerA);
subject.attach(observerB);
subject.notify("通知One");
subject.detach(observerA);
subject.notify("通知Two");
}
}
日志打印
2、单例模式
懒汉
public Class Singleton{
private static Singleton instance;
private Singleton(){}
public static Singleton getInstance(){
if(instance == null){
synchronized(Singleton.class){
if(instance == null){
instance = new Singleton();
}
}
}
return instance;
}
}
饿汉
public class Singleton{
private static Singleton instance = new Singleton();
private Singleton(){}
public static Singleton getInstance(){
return instance;
}
}
内部类:推荐;只有第一次调用getInstance方法时,虚拟机才会初始化instance ```java public class Singleton{ private Singleton(){}
public static Singleton getInstance(){
return Inner.instance;
}
static class Inner{
public static final Singleton instance = new Singleton();
}
}
- 枚举模式:推荐;effective java中最佳的单例实现模式就是枚举模式,JVM来帮我们保证线程安全和单一实例,在反射和序列化的场景中,仍能保证单一实例。
```java
public enum Singleton {
// 创建一个枚举对象,该对象天生为单例
INSTANCE;
public Singleton getInstance(){
return INSTANCE;
}
}
3、工厂模式
4、StringBuilder、StringBuffer和String的区别
String原理:https://www.cnblogs.com/paddix/p/5326863.html
1)、Java String 类——String字符串常量
String 是被 final 修饰的,他的长度是不可变的。
说明:
- JVM为了提高性能和减少内存开销,在实例化字符串常量的时候进行了一些优化
- 为字符串开辟一个字符串常量池,类似于缓存区
- String类拼接字符串时, 每次都会生成一个StringBuilder对象, 然后调用两次append()方法把字符串拼接好, 最后通过StringBuilder的toString()方法new出一个新的字符串对象。
- String赋值情形
- String s = “test”;JVM会去常量池寻找是否有该字符串,找到,返回引用实例;找不到,实例化该字符串放入池中,然后返回引用实例
- String s = new String(“test”);每次都会在堆内存中生成新的对象
- 调用intern()方法:首先会去常量池中查找是否有该字符串对应的引用, 如果有就直接返回该字符串;如果没有,就会在常量池中注册该字符串的引用, 然后返回该字符串。
- 总结:每次对String的操作都会生成新的String对象,这样不仅效率低下,而且大量浪费有限的内存空间。
- 我们来看一下这张对String操作时内存变化的图
- 图为:new String(“test”),赋值过程,
- 直接赋值:””;在常量池中做了复用优化,原理类似。
可以看到,初始String值为“hello”,然后在这个字符串后面加上新的字符串“world”,这个过程是需要重新在栈堆内存中开辟内存空间的,最终得到了“hello world”字符串也相应的需要开辟内存空间,这样短短的两个字符串,却需要开辟三次内存空间,不得不说这是对内存空间的极大浪费。
2)、StringBuffer 和 StringBuilder 类
- StringBuffer、StringBuilder字符串变量
- 当对字符串进行修改的时候,需要使用 StringBuffer 和 StringBuilder 类
- 区别
- 和 String 类不同的是,StringBuffer 和 StringBuilder 类的对象能够被多次的修改,并且不产生新的未使用对象。
- 线程
- StringBuilder 和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的(不能同步访问)。
- 由于 StringBuilder 相较于 StringBuffer 有速度优势,所以多数情况下建议使用 StringBuilder 类。然而在应用程序要求线程安全的情况下,则必须使用 StringBuffer 类。
3)、三者的区别
- 字符修改上的区别(主要)
- String:不可变字符串;
- StringBuffer:可变字符串、效率低、线程安全;
- StringBuilder:可变字符序列、效率高、线程不安全;
- 初始化上的区别,String可以空赋值,后者俩者不行,报错
小结:
修饰类
- 当用final修饰一个类时,表明这个类不能被继承。final类中的成员变量可以根据需要设为final,但是要注意final类中的所有成员方法都会被隐式地指定为final方法。
- 修饰方法
- final修饰的方法不能被重写(可以重载多个final修饰的方法)。重写的前提是子类可以从父类中继承此方法,如果父类中final修饰的方法同时访问控制权限为private,将会导致子类中不能直接继承到此方法,因此,此时可以在子类中定义相同的方法名和参数,此时不再产生重写与final的矛盾,而是在子类中重新定义了新的方法。(注:类的private方法会隐式地被指定为final方法。)
修饰变量
- final成员变量表示常量,只能被赋值一次,赋值后值不再改变。
- final修饰一个基本数据类型时:表示该基本数据类型的值一旦在初始化后便不能发生变化。
- final修饰一个引用类型时:则在对其初始化之后便不能再让其指向其他对象了,但该引用所指向的对象的内容是可以发生变化的。本质上是一回事,因为引用的值是一个地址,final要求值,即地址的值不发生变化。
- final修饰一个成员变量(属性):必须要显示初始化,这里有两种初始化方式:
- 第一种是在变量声明的时候初始化
- 第二种方法是在声明变量的时候不赋初值,但是要在这个变量所在的类的所有的构造函数中对这个变量赋初值。
- 当函数的参数类型声明为final时,说明该参数是只读型的。即你可以读取使用该参数,但是无法改变该参数的值。
finally
java的一种异常处理机制
Java中的一个方法名
值
- 实参:num1,num2
- 形参:a,b
public class TestMain {
public static void main(String[] args) {
int num1 = 10;
int num2 = 20;
swap(num1, num2);
}
public void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
}
基本数据类型
- 基本数据类型,值传递的体现是数值的传递,传递的实际是实参数值的拷贝,形参接受到拷贝值,对拷贝值进行操作,并不会影响实参的值。
- 对象
- 对象,对象传递的体现是地址值的传递,传递的实际是实参地址的拷贝,对形参便指向实参的地址,一般对形参进行更改操作,只要地址不改变,实参也会呈现相应的更改
- 注意String类型,赋值操作,会重新赋值对象,地址值改变,更改形参的值,便不会影响到实参的String值,因为形参的地址指向被变更
- 常见的数组,StringBuilder,StringBuffer和对象都会接受到同步更改,StringBuilder和StringBuffer内部也就是个字符数组(char[])
- 对象,对象传递的体现是地址值的传递,传递的实际是实参地址的拷贝,对形参便指向实参的地址,一般对形参进行更改操作,只要地址不改变,实参也会呈现相应的更改
StringBuffer,StringBuilder,ArrayList等等:16,16,10(初始的数组大小)。内部数组动态扩大,实际是本身有个初始化长度,然后又封装了一个扩容机制,扩容机制是重新计算长度,生成一个新的数组,将老数组的数据copy给新数组,即完成数组长度动态增加。
- 核心方法:arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
/**
* Object src : 原数组
* int srcPos : 从元数据的起始位置开始
* Object dest : 目标数组
* int destPos : 目标数组的开始起始位置
* int length : 要copy的数组的长度
*/
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
7、手撕二叉树
1)、二叉树类别
- 核心方法:arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
完美二叉树
- 一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树,树是满的,还是二叉的。
- 完全二叉树(Complete)
- 完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。
- 完满二叉树
- 所有非叶子结点的度都是2,只要你有孩子,你就必然是有两个孩子。
2)、遍历原理
- 遍历是一层一层的向下遍历到最后一层,然后再遍历上一层节点,上一层左右节点如果能向下遍历,则向下遍历到最后一层,将三个节点当成独立块遍历。
- 前序遍历
遍历顺序:根节点,左节点,右节点
遍历结果:A-B-D-E-G-C-F
- 中序遍历
遍历顺序:左节点,根节点,右节点
遍历结果:D-B-G-E-A-C-F
- 后序遍历
遍历顺序:左节点,右节点,根节点
遍历结果:D-G-E-B-F-C-A
3)、代码实现
二叉树结构
/**
* 构造简单的二叉树结构
*/
public class TreeNode{ //节点结构
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode(){ }
public TreeNode(int value){
this.value = value;
}
/**
* 初始化二叉树结构
*/
public static TreeNode[] init(int length){
TreeNode[] node = new TreeNode[length];//以数组形式生成一棵完全二叉树
for(int i = 0; i < length; i++){
node[i] = new TreeNode(i);
}
for(int i = 0; i < length; i++){
if(i*2+1 < length)
node[i].left = node[i*2+1];
if(i*2+2 < length)
node[i].right = node[i*2+2];
}
return node;
}
}
- 假设 init(int length) 初始化结构,入参为10,二叉树结构图如下:
前序遍历
public class TestMain {
public static void main(String[] args){
TreeNode[] node = TreeNode.init(10);
preOrderRe(node[0]);
}
//递归实现
public void preOrderRe(TreeNode biTree){
if(biTree != null){
System.out.print(biTree.value + "-");
preOrderRe(biTree.left);
preOrderRe(biTree.right);
}
}
//非递归实现
public void preOrder(TreeNode biTree){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(biTree != null || !stack.isEmpty()){
//处理完左节点,全部压到堆栈
while(biTree != null){
System.out.print(biTree.value + "-");
stack.push(biTree);
biTree = biTree.left;
}
//从最底层节点回溯
if(!stack.isEmpty()){
biTree = stack.pop();
biTree = biTree.right;
}
}
}
}
- 结果
中序遍历
public class TestMain {
public static void main(String[] args){
TreeNode[] node = TreeNode.init(10);
preOrderRe(node[0]);
}
//中序遍历递归实现
public static void midOrderRe(TreeNode biTree){
if(biTree != null){
midOrderRe(biTree.left);
System.out.print(biTree.value + "-");
midOrderRe(biTree.right);
}
}
//中序遍历费递归实现
public static void midOrder(TreeNode biTree){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(biTree != null || !stack.isEmpty()){
while(biTree != null){
stack.push(biTree);
biTree = biTree.left;
}
if(!stack.isEmpty()){
biTree = stack.pop();
System.out.print(biTree.value + "-");
biTree = biTree.right;
}
}
}
}
- 结果
后序遍历
public class TestMain {
public static void main(String[] args){
TreeNode[] node = TreeNode.init(10);
preOrderRe(node[0]);
}
//后序遍历递归实现
public static void postOrderRe(TreeNode biTree){
if(biTree != null) {
postOrderRe(biTree.left);
postOrderRe(biTree.right);
System.out.print(biTree.value + "-");
}
}
//后序遍历非递归实现
public static void postOrder(TreeNode biTree){
int left = 1;//在辅助栈里表示左节点
int right = 2;//在辅助栈里表示右节点
Stack<TreeNode> stack = new Stack<TreeNode>();
//辅助栈,用来判断子节点返回父节点时处于左节点还是右节点。
Stack<Integer> stack2 = new Stack<Integer>();
while(biTree != null || !stack.empty()){
//将节点压入栈1,并在栈2将节点标记为左节点
while(biTree != null){
stack.push(biTree);
stack2.push(left);
biTree = biTree.left;
}
//如果是从右子节点返回父节点,则任务完成,将两个栈的栈顶弹出
while(!stack.empty() && stack2.peek() == right){
stack2.pop();
System.out.println(stack.pop().value + "-");
}
//如果是从左子节点返回父节点,则将标记改为右子节点
if(!stack.empty() && stack2.peek() == left){
stack2.pop();
stack2.push(right);
biTree = stack.peek().right;
}
}
}
}
- 结果
8、红黑树
红黑树真不是一言俩语能说清,先贴几篇文章
- 清晰理解红黑树的演变—-红黑的含义:https://www.cnblogs.com/tiancai/p/9072813.html
- 30张图带你彻底理解红黑树:https://www.jianshu.com/p/e136ec79235c
9、类的加载机制
https://blog.csdn.net/ns_code/article/details/17881581
10、排序算法
1)冒泡算法
public int[] bubbleSort(int[] arr){
// 外层循环控制比较轮数
for(int i = 0; i < arr.length; i++){
// 内层循环控制每轮比较次数
for(int j = 0; j < arr.length - i - 1; j++){
// 按照从小到大排列
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
2)快速排序算法
public static void quickSort(int[] arr, int low, int high){
if(low>high){
return;
}
int i=low,j=high;
int base = arr[low]; //base就是基准位
while (i<j) {
//先看右边,依次往左递减
while (base<=arr[j] && i<j) {
j--;
}
//再看左边,依次往右递增
while (base>=arr[i] && i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = base;
//递归调用左半数组
quickSort(arr, low, i-1);
//递归调用右半数组
quickSort(arr, i+1, high);
}
3)二分算法
非递归
public static int binarySearch(int[] array, int value) {
int low = 0;
int len = array.length;
int high = len -1;
while(low <= high) {
int mid = (high + low) / 2;
if(array[mid] == value)
return mid;
else if (array[mid] < value)
low = mid +1;
else
high = mid -1;
}
return -1;
}
递归 ```java /**
- 二分法搜索的递归实现
*/
public static int binarySearch(int[] array, int low, int high, int value) {
if(low > high)
int mid = (high + low) / 2; if(array[mid] == value) {return -1;
}else ifarraya[mid] < value) {return mid;
}else {return binarySearch(array, mid+1, high, value);
} } ```return binarySearch(array, low, mid-1, value);
11、类的加载机制
类加载的过程
类从被加载到虚拟机内存中开始,到卸载出内存为止,它的整个生命周期包括:加载、验证、准备、解析、初始化、使用和卸载七个阶段。它们的顺序如下图所示:
其中类加载的过程包括了加载、验证、准备、解析、初始化五个阶段。在这五个阶段中,加载、验证、准备和初始化这四个阶段发生的顺序是确定的,而解析阶段则不一定,它在某些情况下可以在初始化阶段之后开始。另外注意这里的几个阶段是按顺序开始,而不是按顺序进行或完成,因为这些阶段通常都是互相交叉地混合进行的,通常在一个阶段执行的过程中调用或激活另一个阶段。
下面就一个一个去分析一下这几个过程。
1、加载
”加载“是”类加机制”的第一个过程,在加载阶段,虚拟机主要完成三件事:
(1)通过一个类的全限定名来获取其定义的二进制字节流
(2)将这个字节流所代表的的静态存储结构转化为方法区的运行时数据结构
(3)在堆中生成一个代表这个类的Class对象,作为方法区中这些数据的访问入口。
相对于类加载的其他阶段而言,加载阶段是可控性最强的阶段,因为程序员可以使用系统的类加载器加载,还可以使用自己的类加载器加载。我们在最后一部分会详细介绍这个类加载器。在这里我们只需要知道类加载器的作用就是上面虚拟机需要完成的三件事,仅此而已就好了。
2、验证
验证的主要作用就是确保被加载的类的正确性。也是连接阶段的第一步。说白了也就是我们加载好的.class文件不能对我们的虚拟机有危害,所以先检测验证一下。他主要是完成四个阶段的验证:
(1)文件格式的验证:验证.class文件字节流是否符合class文件的格式的规范,并且能够被当前版本的虚拟机处理。这里面主要对魔数、主版本号、常量池等等的校验(魔数、主版本号都是.class文件里面包含的数据信息、在这里可以不用理解)。
(2)元数据验证:主要是对字节码描述的信息进行语义分析,以保证其描述的信息符合java语言规范的要求,比如说验证这个类是不是有父类,类中的字段方法是不是和父类冲突等等。
(3)字节码验证:这是整个验证过程最复杂的阶段,主要是通过数据流和控制流分析,确定程序语义是合法的、符合逻辑的。在元数据验证阶段对数据类型做出验证后,这个阶段主要对类的方法做出分析,保证类的方法在运行时不会做出威海虚拟机安全的事。
(4)符号引用验证:它是验证的最后一个阶段,发生在虚拟机将符号引用转化为直接引用的时候。主要是对类自身以外的信息进行校验。目的是确保解析动作能够完成。
对整个类加载机制而言,验证阶段是一个很重要但是非必需的阶段,如果我们的代码能够确保没有问题,那么我们就没有必要去验证,毕竟验证需要花费一定的的时间。当然我们可以使用-Xverfity:none来关闭大部分的验证。
3、准备
准备阶段主要为类变量分配内存并设置初始值。这些内存都在方法区分配。在这个阶段我们只需要注意两点就好了,也就是类变量和初始值两个关键词:
(1)类变量(static)会分配内存,但是实例变量不会,实例变量主要随着对象的实例化一块分配到java堆中,
(2)这里的初始值指的是数据类型默认值,而不是代码中被显示赋予的值。比如
public static int value = 1; //在这里准备阶段过后的value值为0,而不是1。赋值为1的动作在初始化阶段。
当然还有其他的默认值。
注意,在上面value是被static所修饰的准备阶段之后是0,但是如果同时被final和static修饰准备阶段之后就是1了。我们可以理解为static final在编译器就将结果放入调用它的类的常量池中了。
4、解析
解析阶段主要是虚拟机将常量池中的符号引用转化为直接引用的过程。什么是符号应用和直接引用呢?
符号引用:以一组符号来描述所引用的目标,可以是任何形式的字面量,只要是能无歧义的定位到目标就好,就好比在班级中,老师可以用张三来代表你,也可以用你的学号来代表你,但无论任何方式这些都只是一个代号(符号),这个代号指向你(符号引用)直接引用:直接引用是可以指向目标的指针、相对偏移量或者是一个能直接或间接定位到目标的句柄。和虚拟机实现的内存有关,不同的虚拟机直接引用一般不同。解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用点限定符7类符号引用进行。
5、初始化
这是类加载机制的最后一步,在这个阶段,java程序代码才开始真正执行。我们知道,在准备阶段已经为类变量赋过一次值。在初始化阶端,程序员可以根据自己的需求来赋值了。一句话描述这个阶段就是执行类构造器< clinit >()方法的过程。
在初始化阶段,主要为类的静态变量赋予正确的初始值,JVM负责对类进行初始化,主要对类变量进行初始化。在Java中对类变量进行初始值设定有两种方式:
①声明类变量是指定初始值
②使用静态代码块为类变量指定初始值
JVM初始化步骤
1、假如这个类还没有被加载和连接,则程序先加载并连接该类
2、假如该类的直接父类还没有被初始化,则先初始化其直接父类
3、假如类中有初始化语句,则系统依次执行这些初始化语句
类初始化时机:只有当对类的主动使用的时候才会导致类的初始化,类的主动使用包括以下六种:
创建类的实例,也就是new的方式访问某个类或接口的静态变量,或者对该静态变量赋值调用类的静态方法反射(如 Class.forName(“com.shengsiyuan.Test”))初始化某个类的子类,则其父类也会被初始化Java虚拟机启动时被标明为启动类的类( JavaTest),直接使用 java.exe命令来运行某个主类好了,到目前为止就是类加载机制的整个过程,但是还有一个重要的概念,那就是类加载器。在加载阶段其实我们提到过类加载器,说是在后面详细说,在这就好好地介绍一下类加载器。