0%

一、ThreadLocal简介

ThreadLocal叫做线程变量,意思是ThreadLocal中填充的变量属于当前线程,该变量对其他线程而言是隔离的,也就是说该变量是当前线程独有的变量。ThreadLocal为变量在每个线程中都创建了一个副本,那么每个线程可以访问自己内部的副本变量。

ThreadLocal 提供了线程本地的实例。它与普通变量的区别在于,每个使用该变量的线程都会初始化一个完全独立的实例副本。ThreadLocal 变量通常被static final修饰。当一个线程结束时,它所使用的所有 ThreadLocal 相对的实例副本都可被回收。

二、ThreadLocal与Synchronized的区别

1、Synchronized用于线程间的数据共享,而ThreadLocal则用于线程间的数据隔离。

2、Synchronized是利用锁的机制,使变量或代码块在某一时该只能被一个线程访问。而ThreadLocal为每一个线程都提供了变量的副本。

三、ThreadLocal的简单使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class ThreadLocaDemo {

private static ThreadLocal<String> localVar = new ThreadLocal<String>();

static void print(String str) {
//打印当前线程中本地内存中本地变量的值
System.out.println(str + " :" + localVar.get());
//清除本地内存中的本地变量
localVar.remove();
}
public static void main(String[] args) throws InterruptedException {

new Thread(new Runnable() {
public void run() {
ThreadLocaDemo.localVar.set("local_A");
print("A");
//打印本地变量
System.out.println("after remove : " + localVar.get());

}
},"A").start();

Thread.sleep(1000);

new Thread(new Runnable() {
public void run() {
ThreadLocaDemo.localVar.set("local_B");
print("B");
System.out.println("after remove : " + localVar.get());

}
},"B").start();
}
}

A :local_A
after remove : null
B :local_B
after remove : null

从这个示例中我们可以看到,两个线程分表获取了自己线程存放的变量,他们之间变量的获取并不会错乱。

四、ThreadLocal的原理

1.ThreadLocal的set()方法:
1
2
3
4
5
6
7
8
9
10
11
public void set(T value) {
//1、获取当前线程
Thread t = Thread.currentThread();
//2、获取线程中的属性 threadLocalMap ,如果threadLocalMap 不为空,
//则直接更新要保存的变量值,否则创建threadLocalMap,并赋值
ThreadLocalMap map = getMap(t);
if (map != null)
map.set(this, value);
else
createMap(t, value);
}

那么ThreadLocalMap又是什么呢?

下面只是部分源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static class ThreadLocalMap {

/**
* The entries in this hash map extend WeakReference, using
* its main ref field as the key (which is always a
* ThreadLocal object). Note that null keys (i.e. entry.get()
* == null) mean that the key is no longer referenced, so the
* entry can be expunged from table. Such entries are referred to
* as "stale entries" in the code that follows.
*/
static class Entry extends WeakReference<ThreadLocal<?>> {
/** The value associated with this ThreadLocal. */
Object value;

Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}

根据源码可看出ThreadLocalMap是ThreadLocal的内部静态类,而它的构成主要是用Entry来保存数据 ,而且还是继承的弱引用。在Entry内部使用ThreadLocal作为key,使用我们设置的value作为value。

2.ThreadLocal的get方法
1
2
3
4
5
6
7
8
9
10
11
12
13
public T get() {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if (map != null) {
ThreadLocalMap.Entry e = map.getEntry(this);
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T)e.value;
return result;
}
}
return setInitialValue();
}
3、ThreadLocal的数据结构

五、常见使用场景

1.存储用户Session

2.Spring使用ThreadLocal解决线程安全问题

六、ThreadLocal 内存泄露问题是怎么导致的?

ThreadLocalMap 中使用的 key 为 ThreadLocal 的弱引用,而 value 是强引用。所以,如果 ThreadLocal 没有被外部强引用的情况下,在垃圾回收的时候,key 会被清理掉,而 value 不会被清理掉。

这样一来,ThreadLocalMap 中就会出现 key 为 null 的 Entry。假如我们不做任何措施的话,value 永远无法被 GC 回收,这个时候就可能会产生内存泄露。ThreadLocalMap 实现中已经考虑了这种情况,在调用 set()get()remove() 方法的时候,会清理掉 key 为 null 的记录。使用完 ThreadLocal方法后 最好手动调用remove()方法。

一、代理模式

代理是一种结构设计模式,可让您为另一个对象提供替代品。 代理控制对原始对象的访问,允许您在请求到达原始对象之前或之后执行某些操作。

二、静态代理

(1)概念:

对目标对象的每个方法的增强都是手动完成。在编译时就已经将接口、被代理类、代理类等确定下来。在程序运行之前,代理类的.class文件就已经生成。

(2)静态代理简单实现
这里借用班长给学生代交班费的例子

1.创建接口并确定接口具体行为

1
2
3
4
public interface Person {
//上交班费
void giveMoney();
}

2.被代理对象实现接口,完成具体的业务逻辑

1
2
3
4
5
6
7
8
9
10
11
12
public class Student implements Person {
private String name;

public Student(String name) {
this.name = name;
}

@Override
public void giveMoney() {
System.out.println(name + "上交班费50元");
}
}

3.代理类实现接口对被代理类的执行进行控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//学生代理类,也实现了Person接口,保存一个学生实体,这样既可以代理学生产生行为
public class StudentsProxy implements Person{
//被代理的学生
Student stu;

public StudentsProxy(Person stu) {
// 只代理学生对象
this.stu = (Student)stu;
}

//代理上交班费,调用被代理学生的上交班费行为
@Override
public void giveMoney() {
System.out.println("交之前做的事");
stu.giveMoney();
System.out.println("交之后做的事");
}
}

4.测试

1
2
3
4
5
6
7
8
9
10
11
12
13
public class StaticProxyTest {
public static void main(String[] args) {
//被代理的学生张三,他的班费上交有代理对象monitor(班长)完成
Person zhangsan = new Student("张三");

//生成代理对象,并将张三传给代理对象
Person monitor = new StudentsProxy(zhangsan);

//班长代理上交班费
monitor.giveMoney();
}
}

交之前做的事
张三上交班费50元
交之后做的事

三、动态代理

(1)概念:

代理类在程序运行时创建的代理方式被成为动态代理。

我们上面静态代理的例子中,代理类(studentProxy)是自己定义好的,在程序运行之前就已经编译完成。然而动态代理,代理类并不是在Java代码中定义的,而是在运行时根据我们在Java代码中的“指示”动态生成的。相比于静态代理, 动态代理的优势在于可以很方便的对代理类的函数进行统一的处理,而不用修改每个代理类中的方法。 比如说,想要在每个代理的方法前都加上一个处理方法:

1
2
3
4
5
public void giveMoney() {
//调用被代理方法前加入处理方法
beforeMethod();
stu.giveMoney();
}

这里只有一个giveMoney方法,就写一次beforeMethod方法,但是如果除了giveMonney还有很多其他的方法,那就需要写很多次beforeMethod方法,麻烦。所以建议使用动态代理实现。

(2)动态代理简单实现:

在java的java.lang.reflect包下提供了一个Proxy类和一个InvocationHandler接口,通过这个类和这个接口可以生成JDK动态代理类和动态代理对象。

1.创建接口并确定接口具体行为

1
2
3
4
public interface Person {
//上交班费
void giveMoney();
}

2.被代理对象实现接口,完成具体的业务逻辑

1
2
3
4
5
6
7
8
9
10
11
12
public class Student implements Person {
private String name;

public Student(String name) {
this.name = name;
}

@Override
public void giveMoney() {
System.out.println(name + "上交班费50元");
}
}

3.自定义 InvocationHandler 并重写invoke方法,在 invoke方法中我们会调用原生方法(被代理类的方法)并自定义一些处理逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class StuInvocationHandler implements InvocationHandler {
//invocationHandler持有的被代理对象
private Object target;

public StuInvocationHandler(Object target) {
this.target = target;
}

/**
* proxy:代表动态代理对象
* method:代表正在执行的方法
* args:代表调用目标方法时传入的实参
*/
@Override
public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
System.out.println("代理执行" +method.getName() + "方法");
Object result = method.invoke(target, args);
return result;
}
}

4.测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ProxyTest {
public static void main(String[] args) {

//创建一个实例对象,这个对象是被代理的对象
Person zhangsan = new Student("张三");

//创建一个与代理对象相关联的InvocationHandler
InvocationHandler stuHandler = new StuInvocationHandler(zhangsan);

//创建一个代理对象stuProxy来代理zhangsan,代理对象的每个执行方法都会替换执行Invocation中的invoke方法
Person stuProxy = (Person) Proxy.newProxyInstance(stu.getClass().getClassLoader(), stu.getClass().getInterfaces(), stuHandler);

//代理执行上交班费的方法
stuProxy.giveMoney();
}
}

代理执行giveMoney方法
张三上交班费50元

四、CGLIB 动态代理

(1)概念:

JDK 动态代理有一个最致命的问题是其只能代理实现了接口的类。为了解决这个问题,我们可以用 CGLIB 动态代理机制来避免。

(2)简单实现:

1.定义一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class NoInterfaceStudent {
private String name;

public NoInterfaceStudent() {
}

public NoInterfaceStudent(String name) {
this.name = name;
}



public void giveMoney() {
System.out.println(name + "上交班费50元");
}
}

2.自定义 MethodInterceptor并重写 intercept方法,intercept用于拦截增强被代理类的方法,和 JDK 动态代理中的 invoke方法类似;

1
2
3
4
5
6
7
8
//首先实现一个MethodInterceptor,方法调用会被转发到该类的intercept()方法。
public class MyMethodInterceptor implements MethodInterceptor {
@Override
public Object intercept(Object o, Method method, Object[] objects, MethodProxy methodProxy) throws Throwable {
System.out.println("CGLIB代理执行" +method.getName() + "方法");
return methodProxy.invokeSuper(o, objects);
}
}

3.通过 Enhancer类的create()创建代理类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class CglibProxyFactory {

public static Object getProxy(Class<?> clazz) {
// 创建动态代理增强类
Enhancer enhancer = new Enhancer();
// 设置类加载器
enhancer.setClassLoader(clazz.getClassLoader());
// 设置被代理类
enhancer.setSuperclass(clazz);
// 设置方法拦截器
enhancer.setCallback(new MyMethodInterceptor());
// 创建代理类
return enhancer.create();
}
}

4.测试

1
2
3
4
5
6
public class CglibTest {
public static void main(String[] args) {
NoInterfaceStudent proxy =(NoInterfaceStudent) CglibProxyFactory.getProxy(NoInterfaceStudent.class);
proxy.giveMoney();
}
}

CGLIB代理执行giveMoney方法
上交班费50元

五、静态代理和动态代理的对比

1、灵活性:动态代理更加灵活,不需要必须实现接口,可以直接代理实现类,并且可以不需要针对每个目标类都创建一个代理类。另外,静态代理中,接口一旦新增加方法,目标对象和代理对象都要进行修改,这是非常麻烦的!

2、JVM层面:静态代理在编译时就将接口、实现类、代理类这些都变成了一个个实际的 class 文件。而动态代理是在运行时动态生成类字节码,并加载到 JVM 中的。

六、JDK 动态代理和 CGLIB 动态代理对比

1、JDK 动态代理只能代理实现了接口的类或者直接代理接口,而 CGLIB 可以代理未实现任何接口的类。 另外, CGLIB 动态代理是通过生成一个被代理类的子类来拦截被代理类的方法调用,因此不能代理声明为 final 类型的类和方法。

2、就二者的效率来说,大部分情况都是 JDK 动态代理更优秀。

一、继承Thread类创建线程类

  • 定义Thread类的子类,并重写该类的run方法,该run方法的方法体就代表了线程要完成的任务。因此把run()方法称为执行体。

  • 创建Thread子类的实例,即创建了线程对象。

  • 调用线程对象的start()方法来启动该线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyThread extends Thread{//继承Thread类

  public void run(){
  //重写run方法
  }

}

public class Main {
  public static void main(String[] args){
    new MyThread().start();//创建并启动线程

  }
}

二、通过Runnable接口创建线程类

  • 定义Runnable接口的实现类,并重写该接口的run()方法,该run()方法的方法体同样是该线程的线程执行体。
  • 创建Runnable实现类的实例,并以此实例作为Thread的target来创建Thread对象,该Thread对象才是真正的线程对象。
  • 调用线程对象的start()方法来启动该线程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyThread2 implements Runnable {//实现Runnable接口
  public void run(){
  //重写run方法
  }
}

public class Main {
  public static void main(String[] args){
    //创建并启动线程
    MyThread2 myThread=new MyThread2();
    Thread thread=new Thread(myThread);
    thread().start();
  }
}

三、通过Callable和Future创建线程

1
2
3
public interface Callable<V> {
V call() throws Exception;
}
  • 创建Callable接口的实现类,并实现call()方法,该call()方法将作为线程执行体,并且有返回值。

  • 创建Callable实现类的实例,使用FutureTask类来包装Callable对象,该FutureTask对象封装了该Callable对象的call()方法的返回值。(FutureTask是一个包装器,它通过接受Callable来创建,它同时实现了Future和Runnable接口。)

  • 使用FutureTask对象作为Thread对象的target创建并启动新线程。

  • 调用FutureTask对象的get()方法来获得子线程执行结束后的返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ThreadDemo implements Callable<Integer> {
@Override
public Integer call() throws Exception
{
int i = 0;
for(;i<100;i++)
{
System.out.println(Thread.currentThread().getName()+" "+i);
}
return i;
}

public static void main(String[] args) throws ExecutionException, InterruptedException {
ThreadDemo threadDemo = new ThreadDemo();
FutureTask<Integer> ft = new FutureTask<>(threadDemo);
new Thread(ft).start();
System.out.println(ft.get());

}
}

四、三种创建方式对比

1、采用实现Runnable、Callable接口的方式创建多线程时

好处:

线程类只是实现了Runnable接口或Callable接口,还可以继承其他类。

在这种方式下,多个线程可以共享同一个target对象,所以非常适合多个相同线程来处理同一份资源的情况,从而可以将CPU、代码和数据分开,形成清晰的模型,较好地体现了面向对象的思想。

坏处:

编程稍微复杂,如果要访问当前线程,则必须使用Thread.currentThread()方法。

2、使用继承Thread类的方式创建多线程时

好处:

编写简单,如果需要访问当前线程,则无需使用Thread.currentThread()方法,直接使用this即可获得当前线程。

坏处

线程类已经继承了Thread类,所以不能再继承其他父类。

五、Runnable和Callable的区别

1、Callable规定(重写)的方法是call(),Runnable规定(重写)的方法是run()。

2、Callable的任务执行后可返回值,而Runnable的任务是不能返回值的。

3、call方法可以抛出异常,run方法不可以。

4、运行Callable任务可以拿到一个Future对象,表示异步计算的结果。它提供了检查计算是否完成的方法,以等待计算的完成,并检索计算的结果。通过Future对象可以了解任务执行情况,可取消任务的执行,还可获取执行结果。

一、什么是跨域

1.什么是同源策略及其限制内容?

同源策略是一种约定,它是浏览器最核心也最基本的安全功能,如果缺少了同源策略,浏览器很容易受到XSS、CSRF等攻击。所谓同源是指"协议+域名+端口"三者相同,即便两个不同的域名指向同一个ip地址,也非同源。

2.常见跨域场景

当协议、子域名、主域名、端口号中任意一个不相同时,都算作不同域。不同域之间相互请求资源,就算作“跨域”。常见跨域场景如下图所示:

二、跨域解决方案

使用CORS(跨源资源共享)来允许跨源访问。

跨源资源共享 (CORS) 是一种基于 HTTP 标头的机制,他允许服务器指示浏览器可以从其他的源(协议,域名,端口)加载资源。

下面进行CORS全局配置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Configuration
public class MyCorsConfiguration {

@Bean
public CorsWebFilter corsWebFilter(){
UrlBasedCorsConfigurationSource source = new UrlBasedCorsConfigurationSource();

CorsConfiguration corsConfiguration = new CorsConfiguration();
//1、配置跨域
corsConfiguration.addAllowedHeader("*");
corsConfiguration.addAllowedMethod("*");
corsConfiguration.addAllowedOrigin("*");
corsConfiguration.setAllowCredentials(true);

source.registerCorsConfiguration("/**",corsConfiguration);
return new CorsWebFilter(source);
}
}

一、微服务

微服务是一种通过多个小型服务组合来构建单个应用的架构风格,这些服务围绕业务能力而非特定的技术标准来构建。各个服务可以采用不同的编程语言,不同的数据存储技术,运行在不同的进程之中。服务采取轻量级的通信机制和自动化的部署机制实现通信与运维。

二、分布式 集群 节点

分布式是指将不同的业务分布在不同的机器。

集群指的是将几台服务器集中在一起,实现同一业务。

节点:集群中的一个服务器

例如:京东是一个分布式系统,众多业务运行在不同的机器,所有业务构成一个大型的业务集群。每一个小的业务,比如用户系统,访问压力大的时候一台服务器是不够的。我们就应该将用户系统部署到多个服务器,也就是每一个业务系统可以做集群化

三、远程调用

在分布式系统中,各个服务可能处于不同主机,但是服务之间不可避免的需要互相调用,我们称为远程调用。

四、负载均衡

分布式系统中,A 服务需要调用 B 服务,B 服务在多台机器中都存在,A 调用任意一个服务器均可完成功能。

为了使每一个服务器都不要太忙或者太闲,我们可以负载均衡地调用每一个服务器,提升网站的健壮性。

常见的负载均衡算法:

  • 轮循均衡(Round Robin):每一次来自网络的请求轮流分配给内部中的服务器,从 1 至 N 然后重新开始。此种均衡算法适合于集群中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。
  • 权重轮循均衡(Weighted Round Robin):根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求。譬如:服务器 A 的权值被设计成 1,B 的权值是 3,C 的权值是 6,则服务器 A、B、C 将分别接收到 10%、30%、60%的服务请求。此种均衡算法能确保高性能的服务器得到更多的使用率,避免低性能的服务器负载过重。
  • 随机均衡(Random):把来自客户端的请求随机分配给内部中的多个服务器,在数据足够大的场景下能达到相对均衡的分布。
  • 权重随机均衡(Weighted Random):此种均衡算法类似于权重轮循算法,不过在分配处理请求时是个随机选择的过程。
  • 一致性哈希均衡(Consistency Hash):根据请求中某一些数据(可以是 MAC、IP 地址,也可以是更上层协议中的某些参数信息)作为特征值来计算需要落在的节点上,算法一般会保证同一个特征值每次都一定落在相同的服务器上。一致性的意思是保证当服务集群某个真实服务器出现故障,只影响该服务器的哈希,而不会导致整个服务集群的哈希键值重新分布。
  • 响应速度均衡(Response Time):负载均衡设备对内部各服务器发出一个探测请求(例如 Ping),然后根据内部中各服务器对探测请求的最快响应时间来决定哪一台服务器来响应客户端的服务请求。
  • 最少连接数均衡(Least Connection):客户端的每一次请求服务在服务器停留的时间可能会有较大的差异,随着工作时间加长,如果采用简单的轮循或随机均衡算法,每一台服务器上的连接进程可能会产生极大的不平衡,并没有达到真正的负载均衡。最少连接数均衡算法对内部中需负载的每一台服务器都有一个数据记录,记录当前该服务器正在处理的连接数量,当有新的服务连接请求时,将把当前请求分配给连接数最少的服务器,使均衡更加符合实际情况,负载更加均衡。此种均衡策略适合长时处理的请求服务,如 FTP 传输。

五、服务注册/发现和注册中心

A 服务调用 B 服务,A 服务并不知道 B 服务当前在哪几台服务器有,哪些正常的,哪些服务已经下线。解决这个问题可以引入注册中心。

注册中心可以说是微服务架构中的”通讯录“,它记录了服务和服务地址的映射关系。 在分布式架构中, 服务会注册到这里,当服务需要调用其它服务时,就这里找到服务的地址,进行调用。

注册中心同时也会进行服务健康监测。

六、配置中心

配置中心用来集中管理微服务的配置信息

每一个服务最终都有大量的配置,并且每个服务都可能部署在多台机器上。我们经常需要变更配置,我们可以让每个服务在配置中心获取自己的配置。

七、服务熔断和服务降级

在微服务架构中,微服务之间通过网络进行通信,存在相互依赖,当其中一个服务不可用时,有可能会造成雪崩效应。要防止这样的情况,必须要有容错机制来保护服务。

(1)服务熔断:设置服务的超时,当被调用的服务经常失败到达某个阈值,我们可以开启断路保护机制,后来的请求不再去调用这个服务。本地直接返回默认的数据。

(2)服务降级:在运维期间,当系统处于高峰期,系统资源紧张,我们可以让非核心业务降级运行。降级:某些服务不处理,或者简单处理【抛异常、返回 NULL、调用 Mock 数据、调用 Fallback 处理逻辑】。

八、API网关

微服务中网关的首要职责就是作为统一的出口对外提供服务,将外部访问网关地址的流量,根据适当的规则路由到内部集群中正确的服务节点之上,因此,微服务中的网关,也常被称为“服务网关”或者“API 网关”,微服务中的网关首先应该是个路由器,在满足此前提的基础上,网关还可以根据需要作为流量过滤器来使用,提供某些额外的可选的功能,譬如安全、认证、授权、限流、监控、缓存,等等。

简而言之:

网关 = 路由器(基础职能) + 过滤器(可选职能)

一、什么是状态机

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

----有限状态机(FSM)或有限状态自动机(FSA)、有限自动机,或简称状态机,是计算的数学模型。

状态机是有限状态机(FSM)或有限状态自动机(FSA)或有限自动机的简称,是计算的数学模型。它是一种抽象机器,可以在任何给定时间恰好处于有限数量的状态之一。FSM可以从一种状态变为另一种状态来作为对某些输入的响应;从一种状态到另一种状态的变化称为转换(transition)。FSM 由其状态列表、初始状态和触发每个转换的输入定义。有限状态机有两种类型——确定性有限状态机(deterministic finite-state machines)和非确定性有限状态机(non-deterministic finite-state machines)。确定性有限状态机可以构造成与任何非确定性有限状态机等效。

状态机的行为可以在现代社会的许多设备中观察到,

二、示例:投币式旋转闸门

由状态机建模的简单机制的一个示例是旋转门。作为一个状态机,旋转门有两种可能的状态:锁定和解锁。有两种可能的输入会影响其状态:将硬币放入槽中(coin)和推动手臂(push)。锁定状态下,推臂无效;无论输入多少次推送,它都保持在锁定状态。投入硬币——即给机器一个硬币输入 ——将状态从锁定转变为解锁。在解锁状态下,投入额外的硬币无效;也就是说,提供额外的硬币输入不会改变状态。但是,客户通过双臂推动,给出推动输入,将状态切换回锁定。

旋转门状态机可以用一个状态转换表来表示,显示每个可能的状态,它们之间的转换(基于给机器的输入)和每个输入产生的输出:

Current State Input Next State Output
Locked coin Unlocked Unlocks the turnstile so that the customer can push through.
push Locked None
Unlocked coin Unlocked None
push Locked When the customer has pushed through, locks the turnstile.

旋转栅门状态机也可以用称为状态图(上图)的有向图来表示。每个状态由一个节点(圆圈)表示。 边线(箭头)显示从一种状态到另一种状态的转换。每个箭头都标有触发该转换的输入。不引起状态变化的输入(例如处于 Unlocked 状态的硬币输入)由返回原始状态的圆形箭头表示。 从黑点到 Locked 节点的箭头表示它是初始状态。

三、确定性

在确定性自动机(DFA)中,每个状态对于每个可能的输入都只有一个转换。在非确定性自动机(NFA)中,输入可以导致给定状态的一个、多个或没有转换。幂集构造算法可以将任何非确定性自动机转换为具有相同功能的(通常更复杂的)确定性自动机。

一、什么是内网IP和公网IP?

内网IP

首先介绍一下动态主机配置协议(Dynamic Host Configuration,DHCP),DHCP允许主机自动获取(被分配)一个P地址。网络管理员能够配置DHCP,以使某给定主机每次与网络连接时能得到一个相同的P地址,或者某主机将被分配一个临时的IP地址(temporary IP address),每次与网络连接时该地址也许是不同的。

当电脑和手机连上网后都会获得一个IP,这个IP是由DHCP服务器分配的,并且这个IP地址会发生变化,这种IP就是内网IP。

平常用到的私网IP地址有三种:

10.0.0.0~10.255.255.255

172.16.0.0 ~172.31.255.255

192.168.0.0~192.168.255.255

在不同子网的一个设备可以被分配以上三种IP,因此处于不同子网的两个设备可能具有相同的IP地址。

公网IP

可以与Internet上的其他计算机随意互相访问。我们通常所说的IP地址,其实就是指的公网 IP。互联网上的每台计算机都有一个独立的IP地址,该IP地址唯一确定互联网上的一台计算机。

为什么要有内网IP?

因为IPv4没有足够多的地址,来给每一台电脑都分配一个自己的地址

二、内网IP如何访问公网IP?

要想知道这个答案,首先要知道网络地址转换(Network Address Transla-tion,NAT)。

具备NAT功能的路由器存在NAT转换表,NAT转换表里面存放着 [ 内网IP+端口 ]:[ 公网IP+端口 ] 的对应关系。

数据包在内网中传输的过程中,源IP和目的IP不会发生变化,MAC地址在不断变化。但当数据包要从内网传输到公网时,NAT路由器会把数据包中的[ 内网IP+端口 ]修改成[ 公网IP+端口 ]。反之,当数据包从公网传到内网时,则把[ 公网IP+端口 ]修改成[ 内网IP+端口 ]。

Spring中的Bean是否线程安全,其实跟Spring容器本身无关。Spring框架中没有提供线程安全的策略,因此,Spring容器中在的Bean本身也不具备线程安全的特性。

1、Spring中Bean从哪里来的?

Spring容器中的Bean其实都是根据我们自己写的类来创建的实例。因此,Spring中的Bean是否线程安全,跟Spring容器无关,只是交由Spring容器托管而已。

2、Spring中什么样的Bean存在线程安全问题?

在Spring定义的作用域中,其中有prototype(多例Bean)和singleton(单例Bean)。

多例Bean每次都会新创建新实例,也就是说线程之间不存在Bean共享的问题。因此,多例Bean是不存在线程安全问题的。

而单例Bean是所有线程共享一个实例,因此,就可能会存在线程安全问题。但是单例Bean又分为无状态Bean和有状态Bean。在多线程操作中只会对Bean的成员变量进行查询操作,不会修改成员变量的值,这样的Bean称之为无状态Bean。所以,无状态的单例Bean是不存在线程安全问题的。但是,在多线程操作中如果需要对Bean中的成员变量进行数据更新操作,这样的Bean称之为有状态Bean,所以,有状态的单例Bean就可能存在线程安全问题。

所以,最终我们得出结论,在Spring中,只有有状态的单例Bean才会存在线程安全问题。

3、如何处理Spring Bean的线程安全问题?

处理有状态单例Bean的线程安全问题有以下三种方法:

1、将Bean的作用域由"singleton"单例 改为"prototype"多例。

2、在类中定义ThreadLocal的成员变量,并将需要的可变成员变量保存在ThreadLocal中,ThreadLocal本身就具备线程隔离的特性,这就相当于为每个线程提供了一个独立的变量副本,从而解决线程安全问题。

根据定理结论,仅仅基于比较进行的排序,所有的这些算法他的最坏时间复杂度,下界是O(N logN),也就是不管有多快,总能制造出一个最坏情况,让他用最快的算法跑,他也只能跑到N logN。

有没有可能更快?

有可能,那就是除了比较之外做一些别的事

为每一个成绩构造一个桶,于是就建了101个桶

当M非常小的时候,其实就是线性算法了

Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.

Algorithm

  • Initialize the root as the current node curr.
  • While curr is not NULL, check if curr has a left child.
  • If curr does not have a left child, print curr and update it to point to the node on the right of curr.
  • Else, make curr the right child of the rightmost node in curr's left subtree.
  • Update curr to this left node.

Demo

Let’s take the binary tree given below and traverse it using Morris (InOrder) traversal.

4 is the root, so it is initialized as curr. 4 has a left child, so it is made the rightmost right child of it’s left subtree (the immediate predecessor to 4 in an InOrder traversal). Finally, 4 is made the right child of 3 and curr is set to 2.

The {2} above refers to 2 and all of its children. Now that the tree has a link back to 4, the traversal continues.

1 is printed because it has no left child and curr is returned to 2, which was made to be 1's right child in the previous iteration. On the next iteration, 2 has both children. However, the dual-condition of the loop makes it stop when it reaches itself; this is an indication that its left subtree has already been traversed. So, it prints itself and continues with its right subtree (3). 3 prints itself, and curr becomes 4 and goes through the same checking process that 2 did. It also realizes that its left subtree has been traversed and continues with the 5. The rest of the tree follows this same pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Node { 
int data;
Node left_node, right_node;

Node(int item)
{
data = item;
left_node = null;
right_node = null;
}
}

class Tree {
Node root;

void Morris(Node root)
{
Node curr, prev;

if (root == null)
return;

curr = root;
while (curr != null) {
if (curr.left_node == null) {
System.out.print(curr.data + " ");
curr = curr.right_node;
}
else {
/* Find the previous (prev) of curr */
prev = curr.left_node;
while (prev.right_node != null && prev.right_node != curr)
prev = prev.right_node;

/* Make curr as right child of its prev */
if (prev.right_node == null) {
prev.right_node = curr;
curr = curr.left_node;
}

/* fix the right child of prev*/

else {
prev.right_node = null;
System.out.print(curr.data + " ");
curr = curr.right_node;
}

}

}
}

public static void main(String args[])
{

Tree tree = new Tree();
tree.root = new Node(4);
tree.root.left_node = new Node(2);
tree.root.right_node = new Node(5);
tree.root.left_node.left_node = new Node(1);
tree.root.left_node.right_node = new Node(3);

tree.Morris(tree.root);
}
}

转自:https://www.educative.io/answers/what-is-morris-traversal