目录
- 知识点01:九大排序算法
- 知识点02:二分查找算法
- 知识点03:二叉树的遍历
- 知识点04:Spring IOC
- 知识点05:Spring AOP
- 知识点06:Spring TX
- 知识点07:Spring MVC
- 知识点08:TCP三次握手
- 知识点09:TCP四次挥手
- 知识点10:单例设计模式
知识点01:九大排序算法
public class Sort {
public static void main(String[] args) {
testTime();
testSort();
}
public static void testTime() {
int[] arr = new int[10000];
for (int i = 0; i < 10000; i++) {
arr[i] = (int) (Math.random() * 100 + 1);
}
long s = System.currentTimeMillis();
long e = System.currentTimeMillis();
System.out.println((e - s) + "ms");
}
public static void testSort() {
int[] arr = new int[50];
for (int i = 0; i < 50; i++) {
arr[i] = (int) (Math.random() * 100 + 1);
}
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int arr[]) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, arr.length);
}
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapAdjust(arr, 0, i);
}
}
public static void heapAdjust(int arr[], int ci, int length) {
int temp = arr[ci];
for (int li = ci * 2 + 1; li < length; li = li * 2 + 1) {
if (li + 1 < length && arr[li] < arr[li + 1]) {
li = li + 1;
}
if (arr[li] > temp) {
arr[ci] = arr[li];
ci = li;
} else {
break;
}
}
arr[ci] = temp;
}
public static void countingSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int[] counts = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
counts[arr[i] - min]++;
}
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
int[] newArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
newArr[--counts[arr[i] - min]] = arr[i];
}
for (int i = 0; i < arr.length; i++) {
arr[i] = newArr[i];
}
}
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
for (int i = 0; i < arr.length; i++) {
arr[i] -= min;
}
int maxLength = String.valueOf(max - min).length();
int[][] bucket = new int[10][arr.length];
int[] bucketIndex = new int[10];
for (int rounds = 0, base = 1; rounds < maxLength; rounds++, base *= 10) {
for (int i = 0; i < arr.length; i++) {
int digit = arr[i] / base % 10;
bucket[digit][bucketIndex[digit]++] = arr[i];
}
int pos = 0;
for (int i = 0; i < bucketIndex.length; i++) {
for (int j = 0; j < bucketIndex[i]; j++) {
arr[pos++] = bucket[i][j];
}
bucketIndex[i] = 0;
}
}
for (int i = 0; i < arr.length; i++) {
arr[i] += min;
}
}
public static void mergeSort(int[] arr, int L, int R, int[] temp) {
if (L >= R) return;
int left = L, middle = (L + R) / 2, right = middle + 1, tIdx = L;
mergeSort(arr, L, middle, temp);
mergeSort(arr, right, R, temp);
while (left <= middle && right <= R) {
if (arr[left] <= arr[right]) {
temp[tIdx++] = arr[left++];
} else {
temp[tIdx++] = arr[right++];
}
}
while (left <= middle) temp[tIdx++] = arr[left++];
while (right <= R) temp[tIdx++] = arr[right++];
for (int i = L; i <= R; i++) {
arr[i] = temp[i];
}
}
public static void quickSort(int[] arr, int L, int R) {
if (L >= R) return;
int left = L, right = R, pivot = arr[L];
while (left < right) {
while (left < right && arr[right] >= pivot) right--;
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) left++;
arr[right] = arr[left];
}
arr[left] = pivot;
quickSort(arr, L, left - 1);
quickSort(arr, left + 1, R);
}
public static void shellSort(int[] arr) {
for (int step = arr.length / 2; step > 0; step /= 2) {
for (int i = step; i < arr.length; i++) {
int temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j -= 1;
}
arr[j + 1] = temp;
}
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
知识点02:二分查找算法
递归版:
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
private static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) return -1;
int middle = (left + right) / 2;
if (target < arr[middle]) {
return binarySearch(arr, left, middle - 1, target);
} else if (target > arr[middle]) {
return binarySearch(arr, middle + 1, right, target);
} else {
return middle;
}
}
迭代版:
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
private static int binarySearch(int[] arr, int left, int right, int target) {
while (left <= right) {
int middle = (left + right) / 2;
if (target < arr[middle]) {
right = middle - 1;
} else if (target > arr[middle]) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
知识点03:二叉树的遍历
树结点:
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode() {}
public TreeNode(int data) {
this.data = data;
}
}
递归版:
public static void preOrder(TreeNode root) {
if (root == null) return;
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
public static void midOrder(TreeNode root) {
if (root == null) return;
midOrder(root.left);
System.out.print(root.data + " ");
midOrder(root.right);
}
public static void postOrder(TreeNode root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
迭代版:
public static void preOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
stack.push(node);
stack.push(null);
} else {
node = stack.pop();
System.out.print(node.data + " ");
}
}
}
public static void midOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (node.right != null) stack.push(node.right);
stack.push(node);
stack.push(null);
if (node.left != null) stack.push(node.left);
} else {
node = stack.pop();
System.out.print(node.data + " ");
}
}
}
public static void postOrder(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
stack.push(node);
stack.push(null);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
} else {
node = stack.pop();
System.out.print(node.data + " ");
}
}
}
层序遍历:
public static void layerOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.data + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
知识点04:Spring IOC
执行流程:
生命周期:
循环依赖:
名称 | 完整定义 | 存储类型 |
---|
一级缓存 | private final Map<String, Object> singletonObjects = new ConcurrentHashMap<>(256); | 成品对象 |
二级缓存 | private final Map<String, Object> earlySingletonObjects = new ConcurrentHashMap<>(16); | 半成品对象 |
三级缓存 | private final Map<String, ObjectFactory<?>> singletonFactories = new HashMap<>(16); | lambda表达式 |
1、如果只有一级缓存能否解决循环依赖问题?
如果只有一级缓存的话,那就意味着成品对象和半成品对象都要放到一级缓存中,在获取对象的时候,就有可能获取到半成品对象,而这个半成品对象是不能直接使用的,因此需要使用一级缓存存放成品对象,用二级缓存存放半成品对象。
2、只有一级二级缓存能否解决循环依赖问题?
只有一级二级缓存可以解决循环依赖问题,但是这个是有前提条件的,前提是不使用AOP,如果开启了AOP,那么Spring将会创建代理对象,如果存在代理对象循环依赖问题任然存在。
3、那么问题又来了,为什么需要三级缓存呢?
三级缓存是为了解决代理过程中的循环依赖问题。
4、使用代码演示一下循环依赖执行整个流程?
<bean id="a" class="io.github.caochenlei.domain.A">
<property name="b" ref="b"></property>
</bean>
<bean id="b" class="io.github.caochenlei.domain.B">
<property name="a" ref="a"></property>
</bean>
public class ABTest {
public static void main(String[] args) {
ApplicationContext applicationContext = new ClassPathXmlApplicationContext("ab.xml");
A a = applicationContext.getBean(A.class);
System.out.println(a);
B b = applicationContext.getBean(B.class);
System.out.println(b);
}
}
知识点05:Spring AOP
常用术语:
- 连接点(Join Point):代表类中有哪些方法可以被增强,这些可以被增强的方法称为连接点。
- 切入点(Pointcut):类中虽然有很多方法可以被增强,但是只有实际被增强的方法称为切入点。
- 通知(Advice):通知描述了增强逻辑代码在切入点处何时执行。
- 前置通知,Before Advice
- 后置通知,AfterReturning Advice
- 异常通知,AfterThrowing Advice
- 最终通知,After Advice
- 环绕通知,Around Advice
- 目标对象(Target Object):被增强的对象称为目标对象,由于AOP框架是使用动态代理实现的,因此该对象始终是代理对象。
- 织入(Weaving):把通知应用到目标对象的切入点的过程就是织入。
- 切面(Aspect):切面是一系列通知和切入点的结合。
代理过程:
执行过程:
知识点06:Spring TX
事务特性:
- 原子性(Atomicity):强调事务的不可分割,要么全成功要么全失败。
- 一致性(Consistency):事务的执行的前后,数据的完整性保持一致。
- 隔离性(Isolation):一个事务的执行中,不该受到其他事务干扰。
- 持久性(Durability):一个事务一旦结束,数据就会持久到数据库。
隔离级别:
若不考虑事务的隔离性,可能会引发读安全性问题:
- 脏读:一个事务读到了另一个事务未提交的数据。
- 不可重复读:一个事务读到了另一个事务已经提交的 update 的数据,导致多次查询结果不一致。
- 幻读 / 虚读:一个事务读到了另一个事务已经提交的 insert 的数据,导致多次查询结果不一致。
要想解决读安全性问题,需要给事务设置隔离级别:
隔离级别 | 说明 | 描述 |
---|
ISOLATION_READ_UNCOMMITTED | 读未提交 | 不能解决以上所有读问题,效率最高,安全性最低,一般不用 |
ISOLATION_READ_COMMITTED | 读已提交 | 避免脏读,不可重复读和幻读有可能发生,Oracle默认的隔离级别 |
ISOLATION_REPEATABLE_READ | 可重复读 | 避免脏读、不可重复读,幻读有可能发生,MySQL默认的隔离级别 |
ISOLATION_SERIALIZABLE | 串行化 | 可以解决以上所有读问题,效率最差,安全性最高,一般不用 |
传播行为:
传播行为 | 当前不存在事务 | 当前存在事务 |
---|
PROPAGATION_REQUIRED | 新建事务 | 使用当前事务 |
PROPAGATION_SUPPORTS | 不使用事务 | 使用当前事务 |
PROPAGATION_MANDATORY | 抛出异常 | 使用当前事务 |
PROPAGATION_REQUIRES_NEW | 新建事务 | 挂起当前事务,新建事务 |
PROPAGATION_NOT_SUPPORTED | 不使用事务 | 挂起当前事务 |
PROPAGATION_NEVER | 不使用事务 | 抛出异常 |
PROPAGATION_NESTED | 新建事务 | 嵌套事务 |
参考:org.springframework.transaction.support.AbstractPlatformTransactionManager#getTransaction
参考:org.springframework.transaction.support.AbstractPlatformTransactionManager#handleExistingTransaction
执行过程:
提交:org.springframework.transaction.support.AbstractPlatformTransactionManager#commit
回滚:org.springframework.transaction.support.AbstractPlatformTransactionManager#rollback
知识点07:Spring MVC
DispatcherServlet初始过程:
DispatcherServlet请求过程:
DispatcherServlet执行流程:
知识点08:TCP三次握手
- 第一次握手: 起初两端都处于CLOSED关闭状态,Client将标志位SYN置为1,随机产生一个值seq=x,并将该数据包发送给Server,Client进入SYN-SENT状态,等待Server确认;
- 第二次握手: Server收到数据包后由标志位SYN=1得知Client请求建立连接,Server将标志位SYN和ACK都置为1,ack=x+1,随机产生一个值seq=y,并将该数据包发送给Client以确认连接请求,Server进入SYN-RCVD状态,此时操作系统为该TCP连接分配TCP缓存和变量;
- 第三次握手: Client收到确认后,检查ack是否为x+1,ACK是否为1,如果正确则将标志位ACK置为1,ack=y+1,并且此时操作系统为该TCP连接分配TCP缓存和变量,并将该数据包发送给Server,Server检查ack是否为y+1,ACK是否为1,如果正确则连接建立成功,Client和Server进入ESTABLISHED状态,完成三次握手,随后Client和Server就可以开始传输数据。
知识点09:TCP四次挥手
- 第一次挥手: A的应用进程先向其TCP发出连接释放报文段(FIN=1,序号seq=u),并停止再发送数据,主动关闭TCP连接,进入FIN-WAIT-1(终止等待1)状态,等待B的确认。
- 第二次挥手: B收到连接释放报文段后即发出确认报文段,(ACK=1,序号seq=v,确认号ack=u+1),B进入CLOSE-WAIT(关闭等待)状态,此时的TCP处于半关闭状态,A到B的连接释放。A收到B的确认后,进入FIN-WAIT-2(终止等待2)状态,等待B发出的连接释放报文段。
- 第三次挥手: B没有要向A发出的数据,B发出连接释放报文段(FIN=1,ACK=1,序号seq=w,确认号ack=u+1),B进入LAST-ACK(最后确认)状态,等待A的确认。
- 第四次挥手: A收到B的连接释放报文段后,对此发出确认报文段(ACK=1,序号seq=u+1,确认号ack=w+1),A进入TIME-WAIT(时间等待)状态。此时TCP未释放掉,需要经过时间等待计时器设置的时间2MSL后,A才进入CLOSED状态。
知识点10:单例设计模式
饿汉式:
class Singleton {
private Singleton() {}
private final static Singleton instance = new Singleton();
public static Singleton getInstance() {
return instance;
}
}
public class SingletonTest {
public static void main(String[] args) {
Singleton instance1 = Singleton.getInstance();
Singleton instance2 = Singleton.getInstance();
System.out.println(instance1 == instance2);
}
}
懒汉式:
class Singleton {
private Singleton() {}
private static Singleton instance;
public static synchronized Singleton getInstance() {
if (instance == null) {
instance = new Singleton();
}
return instance;
}
}
public class SingletonTest {
public static void main(String[] args) {
Singleton instance1 = Singleton.getInstance();
Singleton instance2 = Singleton.getInstance();
System.out.println(instance1 == instance2);
}
}
双检锁:
class Singleton {
private Singleton() {}
private volatile static Singleton instance;
public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
}
public class SingletonTest {
public static void main(String[] args) {
Singleton instance1 = Singleton.getInstance();
Singleton instance2 = Singleton.getInstance();
System.out.println(instance1 == instance2);
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)