接触过线程安全的同学想必都使用过synchronized这个关键字，在java同步代码快中，synchronized的使用方式无非有两个:

1. 通过对一个对象进行加锁来实现同步，如下面代码。

1
2
3
4
5

synchronized(lockObject){
    //代码
    
}

2. 对一个方法进行synchronized声明，进而对一个方法进行加锁来实现同步。如下面代码

1
2
3
4

public synchornized void test(){
    //代码
}

但这里需要指出的是，无论是对一个对象进行加锁还是对一个方法进行加锁，实际上，都是对对象进行加锁。

也就是说，对于方式2，实际上虚拟机会根据synchronized修饰的是实例方法还是类方法，去取对应的实例对象或者Class对象来进行加锁。

对于synchronized这个关键字，可能之前大家有听过，他是一个重量级锁，开销很大，建议大家少用点。但大家可能也听说过，但到了jdk1.6之后，该关键字被进行了很多的优化，已经不像以前那样不给力了，建议大家多使用。

那么它是进行了什么样的优化，才使得synchronized又深得人心呢？为何重量级锁开销就大呢？

想必大家也都听说过轻量级锁，重量级锁，自旋锁，自适应自旋锁，偏向锁等等，他们都有哪些区别呢？

刚才和大家说，锁是加在对象上的，那么一个线程是如何知道这个对象被加了锁呢？又是如何知道它加的是什么类型的锁呢？

基于这些问题，下面我讲一步一步讲解synchronized是如何被优化的，是如何从偏向锁到重量级锁的。

锁对象

刚才我们说，锁实际上是加在对象上的，那么被加了锁的对象我们称之为锁对象，在java中，任何一个对象都能成为锁对象。

为了让大家更好着理解虚拟机是如何知道这个对象就是一个锁对象的，我们下面简单介绍一下java中一个对象的结构。

java对象在内存中的存储结构主要有一下三个部分：

1. 对象头
2. 实例数据
3. 填充数据

这里强调一下，对象头里的数据主要是一些运行时的数据。

其简单的结构如下

从该表格中我们可以看到，对象中关于锁的信息是存在Markword里的。

我们来看一段代码

1
2
3
4
5

LockObject lockObject = new LockObject();//随便创建一个对象

synchronized(lockObject){
    //代码
}

当我们创建一个对象LockObject时，该对象的部分Markword关键数据如下。

从图中可以看出，偏向锁的标志位是“01”，状态是“0”，表示该对象还没有被加上偏向锁。（“1”是表示被加上偏向锁）。该对象被创建出来的那一刻，就有了偏向锁的标志位，这也说明了所有对象都是可偏向的，但所有对象的状态都为“0”，也同时说明所有被创建的对象的偏向锁并没有生效。

偏向锁

不过，当线程执行到临界区（critical section）时，此时会利用CAS(Compare and Swap)操作，将线程ID插入到Markword中，同时修改偏向锁的标志位。

所谓临界区，就是只允许一个线程进去执行操作的区域，即同步代码块。CAS是一个原子性操作

此时的Mark word的结构信息如下：

此时偏向锁的状态为“1”，说明对象的偏向锁生效了，同时也可以看到，哪个线程获得了该对象的锁。

那么，什么是偏向锁?

偏向锁是jdk1.6引入的一项锁优化，其中的“偏”是偏心的偏。它的意思就是说，这个锁会偏向于第一个获得它的线程，在接下来的执行过程中，假如该锁没有被其他线程所获取，没有其他线程来竞争该锁，那么持有偏向锁的线程将永远不需要进行同步操作。

也就是说:

在此线程之后的执行过程中，如果再次进入或者退出同一段同步块代码，并不再需要去进行加锁或者解锁操作，而是会做以下的步骤：

1. Load-and-test，也就是简单判断一下当前线程id是否与Markword当中的线程id是否一致.
2. 如果一致，则说明此线程已经成功获得了锁，继续执行下面的代码.
3. 如果不一致，则要检查一下对象是否还是可偏向，即“是否偏向锁”标志位的值。
4. 如果还未偏向，则利用CAS操作来竞争锁，也即是第一次获取锁时的操作。

如果此对象已经偏向了，并且不是偏向自己，则说明存在了竞争。此时可能就要根据另外线程的情况，可能是重新偏向，也有可能是做偏向撤销，但大部分情况下就是升级成轻量级锁了。

可以看出，偏向锁是针对于一个线程而言的，线程获得锁之后就不会再有解锁等操作了，这样可以省略很多开销。假如有两个线程来竞争该锁话，那么偏向锁就失效了，进而升级成轻量级锁了。

为什么要这样做呢？因为经验表明，其实大部分情况下，都会是同一个线程进入同一块同步代码块的。这也是为什么会有偏向锁出现的原因。

在Jdk1.6中，偏向锁的开关是默认开启的，适用于只有一个线程访问同步块的场景。

锁膨胀

刚才说了，当出现有两个线程来竞争锁的话，那么偏向锁就失效了，此时锁就会膨胀，升级为轻量级锁。这也是我们经常所说的锁膨胀

锁撤销

由于偏向锁失效了，那么接下来就得把该锁撤销，锁撤销的开销花费还是挺大的，其大概的过程如下：

1. 在一个安全点停止拥有锁的线程。
2. 遍历线程栈，如果存在锁记录的话，需要修复锁记录和Markword，使其变成无锁状态。
3. 唤醒当前线程，将当前锁升级成轻量级锁。

所以，如果某些同步代码块大多数情况下都是有两个及以上的线程竞争的话，那么偏向锁就会是一种累赘，对于这种情况，我们可以一开始就把偏向锁这个默认功能给关闭

轻量级锁

锁撤销升级为轻量级锁之后，那么对象的Markword也会进行相应的的变化。下面先简单描述下锁撤销之后，升级为轻量级锁的过程：

1. 线程在自己的栈桢中创建锁记录 LockRecord。
2. 将锁对象的对象头中的MarkWord复制到线程的刚刚创建的锁记录中。
3. 将锁记录中的Owner指针指向锁对象。
4. 将锁对象的对象头的MarkWord替换为指向锁记录的指针。

对应的图描述如下(图来自周志明深入java虚拟机)

之后Markwork如下：

注：锁标志位”00”表示轻量级锁

轻量级锁主要有两种

1. 自旋锁
2. 自适应自旋锁

自旋锁

所谓自旋，就是指当有另外一个线程来竞争锁时，这个线程会在原地循环等待，而不是把该线程给阻塞，直到那个获得锁的线程释放锁之后，这个线程就可以马上获得锁的。

注意，锁在原地循环的时候，是会消耗cpu的，就相当于在执行一个啥也没有的for循环。

所以，轻量级锁适用于那些同步代码块执行的很快的场景，这样，线程原地等待很短很短的时间就能够获得锁了。

经验表明，大部分同步代码块执行的时间都是很短很短的，也正是基于这个原因，才有了轻量级锁这么个东西。

自旋锁的一些问题

1. 如果同步代码块执行的很慢，需要消耗大量的时间，那么这个时侯，其他线程在原地等待空消耗cpu，这会让人很难受。
2. 本来一个线程把锁释放之后，当前线程是能够获得锁的，但是假如这个时候有好几个线程都在竞争这个锁的话，那么有可能当前线程会获取不到锁，还得原地等待继续空循环消耗cup，甚至有可能一直获取不到锁。

基于这个问题，我们必须给线程空循环设置一个次数，当线程超过了这个次数，我们就认为，继续使用自旋锁就不适合了，此时锁会再次膨胀，升级为重量级锁。

默认情况下，自旋的次数为10次，用户可以通过-XX:PreBlockSpin来进行更改。

自旋锁是在JDK1.4.2的时候引入的

自适应自旋锁

所谓自适应自旋锁就是线程空循环等待的自旋次数并非是固定的，而是会动态着根据实际情况来改变自旋等待的次数。

其大概原理是这样的：

假如一个线程1刚刚成功获得一个锁，当它把锁释放了之后，线程2获得该锁，并且线程2在运行的过程中，此时线程1又想来获得该锁了，但线程2还没有释放该锁，所以线程1只能自旋等待，但是虚拟机认为，由于线程1刚刚获得过该锁，那么虚拟机觉得线程1这次自旋也是很有可能能够再次成功获得该锁的，所以会延长线程1自旋的次数。

另外，如果对于某一个锁，一个线程自旋之后，很少成功获得该锁，那么以后这个线程要获取该锁时，是有可能直接忽略掉自旋过程，直接升级为重量级锁的，以免空循环等待浪费资源。

轻量级锁也被称为非阻塞同步、乐观锁，因为这个过程并没有把线程阻塞挂起，而是让线程空循环等待，串行执行。

重量级锁

轻量级锁膨胀之后，就升级为重量级锁了。重量级锁是依赖对象内部的monitor锁来实现的，而monitor又依赖操作系统的MutexLock(互斥锁)来实现的，所以重量级锁也被成为互斥锁。

当轻量级所经过锁撤销等步骤升级为重量级锁之后，它的Markword部分数据大体如下

为什么说重量级锁开销大呢

主要是，当系统检查到锁是重量级锁之后，会把等待想要获得锁的线程进行阻塞，被阻塞的线程不会消耗cup。但是阻塞或者唤醒一个线程时，都需要操作系统来帮忙，这就需要从用户态转换到内核态，而转换状态是需要消耗很多时间的，有可能比用户执行代码的时间还要长。

这就是说为什么重量级线程开销很大的。

互斥锁(重量级锁)也称为阻塞同步、悲观锁

总结

通过上面的分析，我们知道了为什么synchronized关键字为何又深得人心，也知道了锁的演变过程。

也就是说，synchronized关键字并非一开始就该对象加上重量级锁，也是从偏向锁，轻量级锁，再到重量级锁的过程。

这个过程也告诉我们，假如我们一开始就知道某个同步代码块的竞争很激烈、很慢的话，那么我们一开始就应该使用重量级锁了，从而省掉一些锁转换的开销。

讲到这里就大概完了，希望能对你有所帮助

完

参考资料

1. 深入理解java虚拟机(JVM高级特性与最佳实践)
2. java并发编程
3. Eliminating Synchronization Related Atomic Operations with Biased Locking and Bulk Rebiasing

关注我的公众号：苦逼的码农，获取更多原创文章，后台回复”礼包”送你一份特别的资源大礼包。

个人博客

对于volatile这个关键字，相信很多朋友都听说过，甚至使用过，这个关键字虽然字面上理解起来比较简单，但是要用好起来却不是一件容易的事。

这篇文章将从多个方面来讲解volatile，让你对它更加理解。

计算机中为什么会出现线程不安全的问题

volatile既然是与线程安全有关的问题，那我们先来了解一下计算机在处理数据的过程中为什么会出现线程不安全的问题。

大家都知道，计算机在执行程序时，每条指令都是在CPU中执行的，而执行指令过程中会涉及到数据的读取和写入。由于程序运行过程中的临时数据是存放在主存（物理内存）当中的，这时就存在一个问题，由于CPU执行速度很快，而从内存读取数据和向内存写入数据的过程跟CPU执行指令的速度比起来要慢的多，因此如果任何时候对数据的操作都要通过和内存的交互来进行，会大大降低指令执行的速度。

为了处理这个问题，在CPU里面就有了高速缓存(Cache)的概念。当程序在运行过程中，会将运算需要的数据从主存复制一份到CPU的高速缓存当中，那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据，当运算结束之后，再将高速缓存中的数据刷新到主存当中。

我举个简单的例子，比如cpu在执行下面这段代码的时候,

1

t = t + 1;

会先从高速缓存中查看是否有t的值，如果有，则直接拿来使用，如果没有，则会从主存中读取，读取之后会复制一份存放在高速缓存中方便下次使用。之后cup进行对t加1操作，然后把数据写入高速缓存，最后会把高速缓存中的数据刷新到主存中。

这一过程在单线程运行是没有问题的，但是在多线程中运行就会有问题了。在多核CPU中，每条线程可能运行于不同的CPU中，因此每个线程运行时有自己的高速缓存（对单核CPU来说，其实也会出现这种问题，只不过是以线程调度的形式来分别执行的，本次讲解以多核cup为主）。这时就会出现同一个变量在两个高速缓存中的值不一致问题了。

例如：

两个线程分别读取了t的值，假设此时t的值为0，并且把t的值存到了各自的高速缓存中，然后线程1对t进行了加1操作，此时t的值为1，并且把t的值写回到主存中。但是线程2中高速缓存的值还是0，进行加1操作之后，t的值还是为1，然后再把t的值写回主存。

此时，就出现了线程不安全问题了。

Java中的线程安全问题

上面那种线程安全问题，可能对于不同的操作系统会有不同的处理机制，例如Windows操作系统和Linux的操作系统的处理方法可能会不同。

我们都知道，Java是一种夸平台的语言，因此Java这种语言在处理线程安全问题的时候，会有自己的处理机制，例如volatile关键字，synchronized关键字，并且这种机制适用于各种平台。

Java内存模型规定所有的变量都是存在主存当中（类似于前面说的物理内存），每个线程都有自己的工作内存（类似于前面的高速缓存）。线程对变量的所有操作都必须在工作内存中进行，而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。

由于java中的每个线程有自己的工作空间，这种工作空间相当于上面所说的高速缓存，因此多个线程在处理一个共享变量的时候，就会出现线程安全问题。

这里简单解释下共享变量，上面我们所说的t就是一个共享变量，也就是说，能够被多个线程访问到的变量，我们称之为共享变量。在java中共享变量包括实例变量，静态变量，数组元素。他们都被存放在堆内存中。

volatile关键字

上面扯了一大堆，都没提到volatile关键字的作用，下面开始讲解volatile关键字是如何保证线程安全问题的。

可见性

什么是可见性？

意思就是说，在多线程环境下，某个共享变量如果被其中一个线程给修改了，其他线程能够立即知道这个共享变量已经被修改了，当其他线程要读取这个变量的时候，最终会去内存中读取，而不是从自己的工作空间中读取

例如我们上面说的，当线程1对t进行了加1操作并把数据写回到主存之后，线程2就会知道它自己工作空间内的t已经被修改了，当它要执行加1操作之后，就会去主存中读取。这样，两边的数据就能一致了。

假如一个变量被声明为volatile，那么这个变量就具有了可见性的性质了。这就是volatile关键的作用之一了。

volatile保证变量可见性的原理

当一个变量被声明为volatile时，在编译成会变指令的时候，会多出下面一行：

1

0x00bbacde: lock add1 $0x0,(%esp);

这句指令的意思就是在寄存器执行一个加0的空操作。不过这条指令的前面有一个lock(锁)前缀。

当处理器在处理拥有lock前缀的指令时：

在之前的处理中，lock会导致传输数据的总线被锁定，其他处理器都不能访问总线，从而保证处理lock指令的处理器能够独享操作数据所在的内存区域，而不会被其他处理所干扰。

但由于总线被锁住，其他处理器都会被堵住，从而影响了多处理器的执行效率。为了解决这个问题，在后来的处理器中，处理器遇到lock指令时不会再锁住总线，而是会检查数据所在的内存区域，如果该数据是在处理器的内部缓存中，则会锁定此缓存区域，处理完后把缓存写回到主存中，并且会利用缓存一致性协议来保证其他处理器中的缓存数据的一致性。

缓存一致性协议

刚才我在说可见性的时候，说“如果一个共享变量被一个线程修改了之后，当其他线程要读取这个变量的时候，最终会去内存中读取，而不是从自己的工作空间中读取”，实际上是这样的：

线程中的处理器会一直在总线上嗅探其内部缓存中的内存地址在其他处理器的操作情况，一旦嗅探到某处处理器打算修改其内存地址中的值，而该内存地址刚好也在自己的内部缓存中，那么处理器就会强制让自己对该缓存地址的无效。所以当该处理器要访问该数据的时候，由于发现自己缓存的数据无效了，就会去主存中访问。

有序性

实际上，当我们把代码写好之后，虚拟机不一定会按照我们写的代码的顺序来执行。例如对于下面的两句代码：

1
2

int a = 1;
int b = 2;

对于这两句代码，你会发现无论是先执行a = 1还是执行b = 2，都不会对a,b最终的值造成影响。所以虚拟机在编译的时候，是有可能把他们进行重排序的。

为什么要进行重排序呢？

你想啊，假如执行 int a = 1这句代码需要100ms的时间，但执行int b = 2这句代码需要1ms的时间，并且先执行哪句代码并不会对a,b最终的值造成影响。那当然是先执行int b = 2这句代码了。

所以，虚拟机在进行代码编译优化的时候，对于那些改变顺序之后不会对最终变量的值造成影响的代码，是有可能将他们进行重排序的。

更多代码编译优化可以看我写的另一篇文章：
虚拟机在运行期对代码的优化策略

那么重排序之后真的不会对代码造成影响吗？

实际上，对于有些代码进行重排序之后，虽然对变量的值没有造成影响，但有可能会出现线程安全问题的。具体请看下面的代码

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

public class NoVisibility{
    private static boolean ready;
    private static int number;
    
    private static class Reader extends Thread{
        public void run(){
        while(!ready){
            Thread.yield();
        }
        System.out.println(number);

    }
}
    public static void main(String[] args){
        new Reader().start();
        number = 42;
        ready = true;
    }
}

这段代码最终打印的一定是42吗？如果没有重排序的话，打印的确实会是42，但如果number = 42和ready = true被进行了重排序，颠倒了顺序，那么就有可能打印出0了，而不是42。（因为number的初始值会是0).

因此，重排序是有可能导致线程安全问题的。

如果一个变量被声明volatile的话，那么这个变量不会被进行重排序，也就是说，虚拟机会保证这个变量之前的代码一定会比它先执行，而之后的代码一定会比它慢执行。

例如把上面中的number声明为volatile，那么number = 42一定会比ready = true先执行。

不过这里需要注意的是，虚拟机只是保证这个变量之前的代码一定比它先执行，但并没有保证这个变量之前的代码不可以重排序。之后的也一样。

volatile关键字能够保证代码的有序性，这个也是volatile关键字的作用。

总结一下，一个被volatile声明的变量主要有以下两种特性保证保证线程安全。

1. 可见性。
2. 有序性。

volatile真的能完全保证一个变量的线程安全吗？

我们通过上面的讲解，发现volatile关键字还是挺有用的，不但能够保证变量的可见性，还能保证代码的有序性。

那么，它真的能够保证一个变量在多线程环境下都能被正确的使用吗？

答案是否定的。原因是因为Java里面的运算并非是原子操作。

原子操作

原子操作：即一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断，要么就都不执行。

也就是说，处理器要嘛把这组操作全部执行完，中间不允许被其他操作所打断，要嘛这组操作不要执行。

刚才说Java里面的运行并非是原子操作。我举个例子，例如这句代码

1

int a = b + 1;

处理器在处理代码的时候，需要处理以下三个操作：

1. 从内存中读取b的值。
2. 进行a = b + 1这个运算
3. 把a的值写回到内存中

而这三个操作处理器是不一定就会连续执行的，有可能执行了第一个操作之后，处理器就跑去执行别的操作的。

证明volatile无法保证线程安全的例子

由于Java中的运算并非是原子操作，所以导致volatile声明的变量无法保证线程安全。

对于这句话，我给大家举个例子。代码如下:

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

public class Test{
    public static volatile int t = 0;
    
    public static void main(String[] args){
    
        Thread[] threads = new Thread[10];
        for(int i = 0; i < 10; i++){
            //每个线程对t进行1000次加1的操作
            threads[i] new Thread(new Runnable(){
                @Override
                public void run(){
                    for(int j = 0; j < 1000; j++){
                        t = t + 1;
                    }
                }
            });
            threads[i].start();
        }
        
        //等待所有累加线程都结束
        while(Thread.activeCount() > 1){
            Thread.yield();
        }
        
        //打印t的值
        System.out.println(t);
    }
}

最终的打印结果会是1000 * 10 = 10000吗？答案是否定的。

问题就出现在t = t + 1这句代码中。我们来分析一下

例如：

线程1读取了t的值，假如t = 0。之后线程2读取了t的值，此时t = 0。

然后线程1执行了加1的操作，此时t = 1。但是这个时候，处理器还没有把t = 1的值写回主存中。这个时候处理器跑去执行线程2，注意，刚才线程2已经读取了t的值，所以这个时候并不会再去读取t的值了，所以此时t的值还是0，然后线程2执行了对t的加1操作，此时t =1 。

这个时候，就出现了线程安全问题了，两个线程都对t执行了加1操作，但t的值却是1。所以说，volatile关键字并不一定能够保证变量的安全性。

什么情况下volatile能够保证线程安全

刚才虽然说，volatile关键字不一定能够保证线程安全的问题，其实，在大多数情况下volatile还是可以保证变量的线程安全问题的。所以，在满足以下两个条件的情况下，volatile就能保证变量的线程安全问题：

1. 运算结果并不依赖变量的当前值，或者能够确保只有单一的线程修改变量的值。
2. 变量不需要与其他状态变量共同参与不变约束。

讲到这里，关于volatile关键字的就算讲完了。如果有哪里讲的不对的地方，非常欢迎你的指点。下篇应该会讲synchronize关键字。

完

参考书籍：

1. 深入理解Java虚拟机(JVM高级特性与最佳实践)。
2. Java并非编程实战

关注公众号：苦逼的码农，获取更多原创文章，后台回复”礼包”送你一份资源大礼包。

前言

玩公众号有一两个月了，还没介绍过自己，这篇文章简单介绍下自己。

关于我

本人姓林，名秋地，自称帅地，就读于广州某双非大学，专业是软件工程，现在是准大三，热爱编程。不过大一读的专业是与编程无关的，之后转专业到软件工程来，从此陷入码农的世界无法自拔。

刚到软件工程那会，感觉打acm特别有意思，心里对acm比赛充满了兴趣。于是买了各种算法的书籍，也去各大网站刷题。后来刷着刷着，说真的，那些题对于我来说，是真的难啊。一道题做了几个小时，有些题看答案也看了几个小时，没研究几道题一天就过去了。

慢慢着，发现自己并不适合打acm，加上自己参加那些牛客网什么的月赛和周周练之类的，每次都做的不大理想，于是就果断放弃打acm了，跑去好好学习其他技术。

写作历程

之所以会选择写作，主要是基于以下原因：

1. 用在刷题的时间少了，自然也就多了一些时间。个人也比较喜欢上各种博客论坛逛，在论坛里经常是只看不输出，慢慢着，萌生了去尝试写文章的想法。
2. 从小就害怕写作文，看到一个自己心里挺懂的问题，但想要用语言把自己的想法有条理着描述出来，每次都把文字组织的很混乱。于是，也有点想去写文章锻炼一下自己的写作能力。
3. 每次看技术书籍都看到很快，总觉得自己理解了，但每次要用的时候，发现忘了一干二净，然后经常听大佬们说，输出很重要
4. …..

基于以上等原因，我开始了我的第一次写作。

最开始我是在CDNS写的文章。说真的，对于新手来说，写文章真的是太花时间了，一篇简单的文章，都能让我写四五个小时，而且写了之后也没啥人看。心想，要是我拿这四五个小时去看书，不知道还得看多少页的书呢。

大概写了几篇吧，就没去写了。写原创文章真的好累。

然后又过了几个月，心里又萌生了坚持把文章写下去的想法，加上在张哥(stormzhang)(不要告诉我你不知道帅张）的公众号里也一直强调未来写作的重要性，于是自己就真的想逼自己一把，坚持写下去。于是这次就搞了个公众号来写文章记录自己的学习历程。

说真的，自从关注了张哥的公众号之后，收获了不少思想层面上的东西，再次真的非常谢谢张哥。（张哥的公众号：stormzhang)

希望自己能够一直坚持下去…..

写作内容

我的专业是软件工程，并且我现在主要用的语言是Java，所以分享的内容包括：

1. 计算机网络。
2. 数据库。
3. 操作系统。
4. java相关的技术体系。
5. 数据结构与算法。
6. Linux。

主要是自己一边学习，把所学的，感觉比较不错的，会用自己的理解写出来。

自己发现leetcode这个网站的题挺不错，而且感觉相比其他网站的题会容易一点，大佬们也经常建议把里面的题都过一遍。所以写作的内容也会分享在leetcode的刷题贴。

最后

现在是准大三，毕业后的目标是bat等公司，虽然有点难。但，并非没机会。欢迎你的关注，与我一起成长。

完

前言

不知还有多大伙伴还在和我一起继续刷的…不过我也没有日更了，不过题还是要做的，哈哈

题目描述

给定一个字符串 s，找到 s中最长的回文子串。你可以假设 s 的最大长度为1000。

示例1

1
2
3

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例2

1
2

输入: "cbbd"
输出: "bb"

解题

对于这道题，最简单的方法就是暴力求解了。对于很多算法题，我想会暴力求解是最基本的能力，但也绝不能满足于暴力，而且很多题的暴力解法都是很类似的。

这道题与其他的暴力解法一样，外面两层for循环遍历找出所以子串，第三层循环用来判断该子串是否为回文串。
这种算法的时间复杂度为O(n3)。这里我就不给出代码了

优化策略

我们可以换一种思想，假如字符串为回文串，那么把这个字符串首尾两个字符去掉，剩下的子串也会是一个回文串。

基于这种想法，我们就可以这样做了:一个for循环遍历所有字符，单个字符也可以是一个回文串，然后向这个字符的两边各自添加一个字符。判断该字符串是否还是回文串。

例如a是一个回文串，向a的两边添加一个字符，假如添加的这两个字符相同的话，那么添加之后的字符串还是回文串，如果两个字符串不同的话，那么添加之后就不是字符串了，。继续遍历下一个字符。，，，，，

需要注意的地方

不过这里有一个需要注意的地方，我们上面是从单个字符的两边开始向两边拓展添加字符的，这种情况下，最终回文串字符个数是奇数的，例如aba,cabac。

但是回文串的字符个数也有可能是偶数的，例如bb，cbbc，那么对于这种情况，按照单个字符向两边拓展的话就会出问题，因此对于这种情况，我们要从s[i],s[i+1]两边开始拓展。

知道了思路，可以自己先动手试一下能不能写出来。

我做的代码去下:

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

public String longestPalindrome(String s) {

    //先判断是否为空或者长度小于1
    //把||写成了&&害我找了好久都不知道错在哪...
    if(s == null || s.length() < 1){
        return "";
    }
    int left = 0;//用来记录子串的起始位置
    int right = 0;//用来记录子串的末尾位置

    for(int i = 0; i < s.length(); i++){
        //通过findMore这个方法来拓展
        //bab这种情况
        int t1 = findMore(s, i, i);//bab这种情况
        //abba这种情况
        int t2 = findMore(s, i, i+1);

        //选出比较长的那个
        int max = Math.max(t1, t2);
        if(max > right - left){
            left = i - (max - 1)/2;
            right = i + max/2;
        }
    }
    return s.substring(left, right+1);
}

public int findMore(String s, int left, int right){
    while(left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)){
        left--;
        right++;
    }
    return right - left - 1;
}

这种方法的时间复杂度为O(n2)。

不过我去看了官方的解答，那里貌似提供了一个更牛的解法链接，这个解法的时间复杂度为O(n)。假如你有兴趣的话，可以去研究下。

链接：https://articles.leetcode.com/longest-palindromic-substring-part-ii/

在写之前我们先来看几个问题，假如你对这些问题已经很懂了的话，那大可不用看这篇文章，如果不大懂的话，那么可以看看我的想法。

问题1：

1
2
3
4
5
6
7
8
9
10
11

public static void main(String[] args){
    String t1 = new String("2");
    t1.intern();
    String t2 = "2";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出：

JDK1.6是 false false

JDK1.7是 false true;

问题2(把问题1的语句调换一下位置)

1
2
3
4
5
6
7
8
9
10
11

public static void main(String[] args){
    String t1 = new String("2");
    String t2 = "2";
    t1.intern();
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    String t4 = "22";
    t3.intern();
    System.out.println(t3 == t4);
}

答案输出：
false false

对于这两个问题，看了几个人的博客，可谓百花齐放，越看越懵逼

问题3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

答案输出：

true

false

true

true

true

false

问题4：

1

运行时常量池与字符串常量池是什么关系？包含？

在解决问题之前，我们先来简单了解一些常量池的一些知识点(大部分来源于周志明的深入Java虚拟机这本书)。

JVM中的几种常量池

1.class文件常量池

在Class文件中除了有类的版本、字段、方法、接口等描述信息外，还有一项信息是常量池(Constant Pool Table)，用于存放编译期生成的各种字面量和符号引用。

这里简单解释下字面量和符号引用

字面量

字面量类似与我们平常说的常量，主要包括：

1. 文本字符串：就是我们在代码中能够看到的字符串，例如String a = “aa”。其中”aa”就是字面量。
2. 被final修饰的变量。

符号引用

主要包括以下常量：

1. 类和接口和全限定名：例如对于String这个类，它的全限定名就是java/lang/String。
2. 字段的名称和描述符：所谓字段就是类或者接口中声明的变量，包括类级别变量（static)和实例级的变量。
3. 方法的名称和描述符。所谓描述符就相当于方法的参数类型+返回值类型。

2.运行时常量池

我们上面说的class文件中的常量池，它会在类加载后进入方法区中的运行时常量池。并且需要的注意的是，运行时常量池是全局共享的，多个类共用一个运行时常量池。并且class文件中常量池多个相同的字符串在运行时常量池只会存在一份。

注意运行时常量池存在于方法区中。

3.字符串常量池

看名字我们就可以知道字符串常量池会用来存放字符串，也就是说常量池中的文本字符串会在类加载时进入字符串常量池。

那字符串常量池和运行时常量池是什么关系呢？上面我们说常量池中的字面量会在类加载后进入运行时常量池，其中字面量中有包括文本字符串，显然从这段文字我们可以知道字符串常量池存在于运行时常量池中。也就存在于方法区中。

不过在周志明那本深入java虚拟机中有说到，到了JDK1.7时，字符串常量池就被移出了方法区，转移到了堆里了。

那么我们可以推断，到了JDK1.7以及之后的版本中，运行时常量池并没有包含字符串常量池，运行时常量池存在于方法区中，而字符串常量池存在于堆中。

说了这么多，现在我们开始来解决上面提出了问题。

解决问题

问题1：

1
2
3
4
5
6
7
8
9
10
11

public static void main(String[] args){
    String t1 = new String("1");
    t1.intern();
    String t2 = "1";
    System.out.println(t1 == t2);
    
    String t3 = new String("2") + new String("2");
    t3.intern();
    String t4 = "22";
    System.out.println(t3 == t4);
}

答案输出：

JDK1.6是 false false。

JDK1.7是 false true;

在解决这个问题之前，我们先来看另外一道面试中经常会问到的问题。

1
2

String t = new String("tt");

假如程序中只有这样一行代码，那么这行代码创建了几个对象？

我们上面说过，”tt”属于字面量，那么它会在类加载之后存在于字符串常量池中，也就是说，在 String t = new String(“tt”)这句代码执行之前，字符串常量池就已经创建了”tt”这个字符串对象了，我们都知道，new这个关键字会在堆中创建一个对象。

所以，这段代码创建了两个对象。一个在堆中，一个在字符串常量池中。

那么下面这段代码又是创建了几个对象呢？

1
2

String t1 = new String("tt");
String t2 = new String("tt");

答是这段代码创建了三个对象，我们上面说了，字符串常量池只会保存一份内容相同的字符串。也就是说，在这两句代码执行之前，字符串常量池就已经创建了内容为”tt”的对象了。这两句代码执行之后，又在堆中创建了两个，所以一共创建了三个。

那么下面这段代码又是创建了几个对象？

1

String t = "tt";

答是1个，在这段代码执行之前，字符串常量池已经创建了一个”tt”的对象，但由于这行代码并非用new的方法，所以虚拟机会在字符串常量池中寻找是否有内容为”tt”的字符串对象，如果有，则直接返回这个字符串的引用，所以最终结果只创建了一个对象。

回到我们的问题，在这里我们先解释下String 的intern方法。

例如我们调用了t.intern()。

在JDK1.6的时候，调用了这个方法之后，虚拟机会在字符串常量池在查找是否有内容与”tt”相等的对象，如果有，则返回这个对象，如果没有，则会在字符串常量池中添加这个对象。注意，是把这个对象添加到字符串常量池。

到了JDK1.7之后，如果调用了intern这个方法，虚拟机会在字符串常量池在查找是否有内容与”tt”相等的对象，如果有，则返回这个对象，如果没有。则会在堆中把这个对象的引用复制添加到字符串常量池中。注意，这个时候添加的是对象在堆中的引用。

现在开始来分析问题中的代码

t1 = new String(“1”)。

这句代码执行之前，字符串常量池中已经有”t”这个对象，执行之后会在堆中也创建一个”t”的对象，此时t1指向的是堆中的对象。

t1.intern();

这句代码执行之后，会在字符串常量池寻早内容为”t”的对象，字符串常量池已经存在这个对象了，把这个对象返回(不过返回之后并没有变量来接收)。

t2 = “1”。

这句执行后会在字符串常量池查找内容为”t”的对象，字符串常量池已经有这个对象了，返回给t2，此时t2指向的是常量池中的对象。

一个是常量池中的对象，一个是在堆中的对象，两者能相等吗？因此

t1 与 t2不相等。

接着下面

t3 = new String(“2”) + new String(“2”);

这段代码调用之前，字符串常量池有一个”2”的对象，执行之后，实际上会调用StringBuilder的append()方法类进行拼接，最后在堆中创建一个”22”的对象，注意，此时字面量并没有”22”这个字符串，也就是说在字符串常量池并没有”22”这个对象。此时t3指向堆中”22”这个对象

t3.intern();

执行这个方法之后

在JDK1.6的时候，它在字符串常量池中并没有找到内容为”22”的对象，所以这个时候会把这个对象添加到字符串常量池，并把这个对象返回(此时并没有变量来接收这个返回的对象)。注意添加的是对象，而并非引用。

t4 = “22”。

这句代码执行后，会返回字符串常量池中内容为”22”对象，此时t4指向的是字符串常量池中的对象。

显然，一个对象在字符串常量池，一个在堆中，两个对象并非是同一个对象，因此在JDK1.6的时候，t3与t4不相等。

但是在JDK1.7的时候

t3.intern()执行之后，由于在字符串常量池在并没有内容为”22”的对象，所以会把堆中该对象的引用赋值到字符串常量池。注意此时字符串常量池保存的是堆中这个对象的引用。

t4 = “22”。

执行这句代码之后，从字符串常量池返回给t4的是堆中对象的引用。此时t4指向的实际上是堆中对象的引用，也就是说，t3和t4指向的是同一个对象。

因此t3与t4相等。

不知道你明白了没有？反正我是搞了好久才明白…

问题2

至于问题2，我就只讲下半部分的代码，上半部分如果你看懂了问题1，那么问题2也差不多自然懂了。

1
2
3
4

String t3 = new String("2") + new String("2");
String t4 = "22";
t3.intern();
System.out.println(t3 == t4);

t3 = new String(“2”) + new String(“2”)。

这段代码调用之前，字符串常量池有一个”2”的对象，执行之后，实际上会调用StringBuilder的append()方法类进行拼接，最后在堆中创建一个”22”的对象。此时t3指向堆中”22”这个对象

t4 = “22”。

这句代码执行之前，字符串常量池已经存在”22”这个对象了，所有直接把这个对象返回给t4，此时t4指向的是字符串常量池中的对象.

所以t3和t4肯定不是同一个对象啊，t3.intern这句几乎可以忽略，不会给t3和t4造成任何影响。

问题3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void main(String[] args){
    Integer a = 1;
    Integer b = 2;
    Integer c = 3;
    Integer d = 3;
    Integer e = 321;
    Integer f = 321;
    Long g = 3L;
    
    System.out.println(c == d);
    System.out.Println(e == f);
    System.out.println(c == (a + b));
    System.out.println(c.equals(a+b));
    System.out.println(g == (a + b));
    System.out.println(g.equals(a + b));
}

对于这个问题，我简单说一下可能你就懂了。

(1). 内存中有一个java基本类型封装类的常量池。这些类包括
Byte, Short, Integer, Long, Character, Boolean。需要注意的是，Float和Double这两个类并没有对应的常量池。

(2).上面5种整型的包装类也只是在对象数值在-128~127才可以使用这些常量池。

(3). 在周志明的那本虚拟机中有这样一句话：包装类的
“\==”运行符在不遇到算术运算的情况下不会自动拆箱，以及他们的equals()方法不处理数据类型的关系，可以推断出如果遇到“==”两边有算术运算是话就会自动拆箱和进行数据类型转换处理。

(4).Long的equals方法会先判断是否是Long类型。

(5).无论是Integer还是Long，他们的equals方法比较的是数值。

所以：

System.out.println(c == d)。

由于常量池的作用，c与d指向的是同一个对象(注意此时的==比较的是对象，也就是地址，而不是数值)。因此为true

System.out.println(e == f)。

由于321超过了127，因此常量池失去了作用，所以e和f数值虽然相同，但不是同一个对象，以此为false。

System.out.println(c == (a+b))。

此时==两边有算术运算，会进行拆箱，因此此时比较的是数值，而并非对象。因此为true。

System.out.println(c.equals(a+b))

c与a+b的数值相等，为true。

System.out.pirnln(g == (a + b))

由于==两边有算术运算，所以比较的是数值，因此为true。

System.out.println(g.equals(a+b))。

Long类型的equal在比较是时候，会先判断a+b是否为Long类型，显然a+b不是，因此false

问题到此就结束了，以上便是自己的理解，以上如果有不对劲的地方，非常欢迎你的指点。

完。

关注公众号「苦逼的码农」，获取更多原创文章，后台回复「礼包」送你一份特别的大礼包

与其他语言相比，例如c/c++，我们都知道，java虚拟机对于程序中产生的垃圾，虚拟机是会自动帮我们进行清除管理的，而像c/c++这些语言平台则需要程序员自己手动对内存进行释放。

虽然这种自动帮我们回收垃圾的策略少了一定的灵活性，但却让代码编写者省去了很多工作，同时也提高了很多安全性。(因为像C/C++假如你创建了大量的对象，但却由于自己的疏忽忘了将他们进行释放，可能会造成内存溢出)。

何为垃圾？

刚才说了，虚拟机会自动帮助我们进行垃圾的清除，那什么样的对象我们才可以称为是垃圾对象呢？

假如你创建了一个对象

1

Man m = new Man();

你用一个变量指向了这个对象，显然对于这个对象，你可以用变量m对这个对象进行利用，但过了一段时间，你执行了

1

m = null;

并且也并没有新的变量来指向刚才创建的对象。此时对于这个没有任何变量指向的对象，你觉得它还有用处吗？

显然，对于这种没有被变量指向的对象，它是一点卵用也没有的，它只能在堆随风漂流。

因此，对于这样的对象，我们就可以把它称为垃圾了，它早晚会被垃圾回收器给干掉。

怎么知道它已经是垃圾对象了?

假如代码是你自己编写的，你可能知道这个对象啥时候应该被抛弃，你可以随时让它成为垃圾对象。

但是，你毕竟是你，虚拟机则没那么智能。那虚拟机是如何知道的呢？

上面已经说了，没有变量引用这个对象时，它就是垃圾对象了，基于这个原理，我们可以这样做啊：

我们可以为这个对象设置一个计数器，初始值为0，假如有一个变量指向它，那么计数器就加1，如果这个变量不在指向它了，计数器就减1。那么我们就可以判断，如果这个计数器为0的话，那它就是垃圾对象了，否则就是有用的对象。

对于这种方法，我们称之为引用计数法。

好吧，我们先来夸一夸引用计数法这种方法：

1. 实现简单。
2. 效率高(一个if语句就能解决的问题想不高效都难)。

不好意思，接下来得说说它那个致命的缺点。

实际上，对于这种引用计数的方法，假如它遇到对象互相引用的话，是很难解决的。

先看一段代码：

1
2
3
4
5
6
7
8
9

Man m1 = new Man();
Man m2 = new Man();
//互相引用
m1.instance = m2;//假设Man有instance这个属性
m2.instance = m1;

m1 = null;
m2 = null;
System.gc();//按道理对象应该被回收

这段代码m1和m2都指向null了，按道理两个对象已经是无用对象，应该被回收，但是，两个对象之间彼此有一个instance的属性互相牵引的对方，导致两个对象并没有被回收。

这个缺点够致命吧？

所以，虚拟机并没有采用这种引用计数的方法。

可达性分析

除了这种方法，我们还有其他的方法吗？

答案是有的，必须得有啊。这种方法就是传说中的可达性分析，(我靠，听名字是真的高级啊)。它的工作原理是这样的：

在程序开始时，会建立一个引用根节点(GC Roots)，并构建一个引用图。当需要判断谁是垃圾时，我们可以从这个根节点进行遍历，如果没有被遍历到的节点则是垃圾对象，否则就是有用对象。如下图:

这个方法可以解决循环相互引用的问题，但是这个方法并没有引用计数法高效，毕竟要遍历图啊。

总结下判断是否为垃圾对象的算法：

1. 引用计数法。
2. 可达性分析。

何时进行垃圾回收

可能有人会觉得这个问题很奇怪，觉得看到垃圾就回收不是很好。对于这个我只能说：

1. 看到房间有一点垃圾你会马上扫？还是等到某个时间点或者当垃圾积累到一定的数量再扫？
2. 虚拟机可没那么智能可以马上识别这个对象是垃圾对象，它还得遍历所有对象才能知道有哪些是垃圾对象。

所以说，你总不能几秒(我们假设几秒是贼短的时间）就让虚拟机遍历一下所有对象吧？

这里先说明一下，当垃圾回收器在进行垃圾回收的时候，为了保证垃圾回收不受干扰，是会暂停所有线程的，此时程序无法对外部的请求进行响应。(因为你想啊，当你在可达性分析的时候，那些引用关系还在不断着变化，那不很难受)。

而且频繁的垃圾回收，对于有一些程序，是很影响用户体验的，例如你在玩游戏，系统动不动就停顿一下，怕你是要把这游戏给删了。

所以说，垃圾回收是会等到内存被使用了一定的比例的时候，才会触发垃圾回收。至于这个比例是多少，这可能就是人为规定的了。

怎么回收？

当我们标记好了哪些是垃圾，想要进行回收的时候，该怎么回收比较好呢？

可能有一些人就觉得奇怪，这还不简单，看见它是垃圾，直接回收不就得了。

其实这也不无道理，简单粗暴，直接回收。

是的，确实有这样的算法，看哪些是被我们标记的垃圾，看见了就直接回收。这种算法我们称之为标记–清除算法。

标记-清除算法工作原理：就是先标记出所有需要回收的对象，然后在统一回收所有被标记过的对象。

不过，那些人你可别得意啊，因为这种方法虽然简单暴力，但它有个致命的缺点就是：

标记清除过后，会产生大量的不连续内存碎片，如果不连续的碎片过多的话，，可能会导致有一些大的对象存不进去。这样，会导致下面两个问题：

1. 有些内存浪费了。
2. 对象存不进去，会又一次触发垃圾回收。

复制算法

为了解决这种问题，另外一种算法出现了—复制算法。就是说，它会将可用的内存按容量划分成两块。然后每次只使用其中的一块，当这一块快用完的时候，就会触发垃圾回收，它会把还存活的对象全部复制到另外一块内存中去，然后把这块内存全部清理了。

这样，就不会出现碎片问题了。

居然帮我们解决了我们必须夸一下它：不仅帮我们解决了问题，而且实现上也简单、运行也高效。

但是(凡事都有个但是的)，它也是有缺点的，缺点很明显，发现了没有。假如每次存活的对象都很少很少，那另外一块内存不是几乎没有用到？所以说，这种方法有可能导致另外一半内存几乎没用了。内存那么宝贵，这可是很严重的问题。

优化策略：可以告诉你，有研究显示，其实有98%的对象都是朝生夕死的，也就是说，每次存活的对象确实很少很少。既然我们都知道存活的对象很少很少了，那我们干嘛还1：1的比例来分配？所以说，HotShot虚拟机是默认按8:1的比例来分配的。这样，就不会出现很多内存没用到的问题了。

可能有人会说，万一占比为1/9的内存不够用了怎么办？不就没地方存那些活的对象？实际上，当内存不够用时，可以向其他地方借些内存来使用，例如老年代里的内存。

这里说明一下新生代和老年代：说白了，新生代就是刚刚创建不久的对象，而老年代是已经活了挺久的对象。也就是说，有一些对象是确实活的比较久的，对于这种对象，我们另外给它分配内存来养老，而且垃圾回收时，我们不用每次都来这里查找有没垃圾对象，因为这些对象是垃圾的几率会比较小。

下面在简单介绍另外两种算法：

1. 标记-整理算法：这种算法和标记-清除算法类似，不过它把垃圾清除了之后，会让存活的对象往一个方向靠拢，以此来整理碎片。
2. 分代收集算法：所谓分代就是把对象分成类似上面说的老年代和新生代，在新手代一般每次垃圾回收时死的对象一般都会比较多，而老年代会比较少，基于这种关系，我们就可以采取不同的算法来针对了。

总结下垃圾回收的几种算法：

1. 标记-清除算法。
2. 复制算法。
3. 标记-整理算法。
4. 分代收集算法。

最后给大家几种垃圾回收器

对于垃圾的回收，你是想一边运行程序其他代码一边进行垃圾回收？还是想把垃圾全收好再来执行程序的其他代码？虽然说最终使用cpu的时间是一样，但两种方式还是有区别的。

下面简单介绍几种垃圾回收器，看看他们都使用哪种方。

(1).Serial收集器

serial(串行),看这个英文单词就知道这是一个单线程收集器。也就是说，它在进行垃圾回收时，必须暂停其他所有线程。显然，有时垃圾回收停顿的比较久的话，这对于用户来说是很难受的。

(2).ParNew

这个收集器和Serial很类似，进行垃圾回收的时候，也是得暂停其他所有线程，不过，它可以多条线程工作进行垃圾回收。

(3).Parallel Scavenge收集器

parallel,并行的意思。也是可以多线程进行垃圾回收处理，但是它与ParNew不同。它会严格控制垃圾回收的时间与执行其他代码的时间之间的比例。我们来看一个名词：吞吐量。

吞吐量 = 运行用户代码时间 / (运行用户代码时间 + 垃圾收集时间)。

也就是说，Parallet Scavenge收集器会严格控制吞吐量，至于这个吞吐量是多少，这个可以人为设置。

下面两个收集器重点介绍下

(4).CMS（Concurrent Mark Sweep）收集器

CMS收集器是基于“标记-清除”算法实现的，它的运作过程相对于前面几种收集器来说要更复杂一些，整个过程分为4个步骤，包括：

1. 初始标记（CMS initial mark）
2. 并发标记（CMS concurrent mark）
3. 重新标记（CMS remark）
4. 并发清除（CMS concurrent sweep）

其中初始标记、重新标记这两个步骤仍然需要暂停其他线程。但另外两个步骤可以和其他线程并发执行。初始标记仅仅只是标记一下GCRoots能直接关联到的对象，速度很快，并发标记阶段就是进行GC Roots Tracing的过程 (说白了就是把整个图都遍历了，找出没有的对象)，

而重新标记阶段则是为了修正并发标记期间，因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的停顿时间一般会比初始标记阶段稍长一些，但远比并发标记的时间短。

由于整个过程中耗时最长的并发标记和并发清除过程中，收集器线程都可以与用户线程一起工作，所以总体上来说，CMS收集器的内存回收过程几乎是与与用户线程一起并发地执行。

(5).G1收集器

这个估计是最牛的收集器了。该收集器具有如下特点：

1. 并行与并发：G1能充分利用现代计算器多CPU,多核的硬件优势，可以使用并发或并行的方式来缩短让其他线程暂停的优势。
2. 分代收集：就是类似像分出新生代和老年代那样处理。
3. 空间整合：采用了复制算法+标记-整合算法的特点来回收垃圾。就是整体采用标记-整理算法，局部采用复制算法。
4. 可预测停顿：这个就牛了，就是说，它能让使用者明确指定在一个长度为M毫秒的时间片段内，消耗在垃圾收集上的时间不超过N毫秒。

它的执行过程大体如下：

1. 初始标记。
2. 并发标记。
3. 最终标记。
4. 筛选回收。

这个流程和CMS很相似，它也是在初始标记和最终标记需要暂停其他线程，但其他两个过程就可以和其他线程并发执行。

刚才我们说了G1收集器哪些优点，例如可预测停顿，这也使得筛选回收，是可以预测停顿垃圾回收的时间的，也就是说，停顿的时间是用户自己可以控制的，这也使得一般情况下，在筛选回收的时候，我们会暂停其他线程的执行，把所有时间都用到筛选回收上。

本次讲解到这里。

完

前言

我靠，才坚持了四天，就差点不想坚持了。不行啊，我得把leetcode上的题给刷完，不然怕是不好进入bat的大门。

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 均不为空。

示例

1
2
3
4

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

1
2
3
4

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5``

解题

最简单粗暴的就是把这两个数组头尾连接起来，然后重新给他们排序一下，冒泡排序相信你信手拈来，当然，你也可以装逼用快速排序。

但是，如果这样子做的话，题目给你的有序数组就没啥用了，和无序一个样，所以这样做是不行的。题目要求是时间复杂度不能超过O(log(n+m))，说实话，这个复杂度我是不知道怎么做好，我的做法时间复杂度是O(n+m)。

具体是这样的

居然两个数组都是有序的了，我们可以再弄一个中间数组，然后把两个数组各自从数组头开始比较，哪个元素小，我们就把它存在中间数组。然后接下下一个元素一直比较下去。

我还是直接上代码吧。如下：

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

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int t = m + n;//总长度
        int temp[] = new int[t];
        int i  = 0, j = 0, k = 0;
        double obj;//用来存目标值

        while(i < m && j < n){
            //把数组中比较小的值转移到temp数组中
            if(nums1[i] < nums2[j]){
                temp[k++] = nums1[i++];
            }else{
                temp[k++] = nums2[j++];
            }
        }
        //把剩余的转移过去
    while (i < m){
            temp[k++] = nums1[i++];
    }
    while(j < n){
            temp[k++] = nums2[j++];
    }
    //两个数组的总个数是奇数还是偶数
    if(t % 2 == 0){//偶数
            obj = (temp[t/2] + temp[(t-1)/2]) / 2.0;
    }else{
            obj = temp[t/2];
    }

    return obj;
}

虽然时间复杂度是O(n+m)，但是提交的时候居然通过了，而且还打败了93%的人。

不过，这里还可以在优化，把时间复杂度降低到O((n+m)/2)。
就是说其实我们不用给整个temp数组排序，我们只要求出前面一半的数组元素就可以知道中间那个元素了，。例如不管一共是偶数个元素还是奇数个元素，我们让temp存到下标为t/2就可以了。然后再来判断t是奇数还是偶数…..

例如上面两个示例，示例1一共有三个元素，那么temp[t/2]=temp[1]=2。然后直接把temp[t/2]=temp[1]取出来返回就可以了。

示例2一共有4个元素，那么temp[t/2]=temp[2]=3。由于是偶数，我们直接把temp[t/2]=3和temp[t/2-1]=2这两个元素取出来处理之后返回就可以了。

至于代码这么写，我就不写了。知道有这么一回事就可以了。

如果你坚持想要O(log(n+m))的时间复杂度，那么可以看官方给的答案：

答案解析

完

1.解释器与JIT编译器

首先我们先来了解一下运行在虚拟机之上的解释器与JIT编译器。

当我们的虚拟机在运行一个java程序的时候，它可以采用两种方式来运行这个java程序：

1. 采用解释器的形式，也就是说，在运行.class运行的时候，解释器一边把.class文件翻译成本地机器码，一边执行。显然这种一边解释翻译一边执行发方式，可以使我们立即启动和执行程序，省去编译的时间。不过由于需要一遍解释翻译，会让程序的执行速度比较慢。
2. 采用JIT编译器的方式：注意，JIT编译器是把.class文件翻译成本地机器码，而javac编译器是把.java源文件编译成.class文件。如果采用JIT编译器的方式则是在启动运行一个程序的时候，先把.class文件全部翻译成本地机器码，然后再来执行，显然，这种方式在执行的时候由于不用对.clasa文件进行翻译，所以执行的速度会比较快。当然，代价就是我们需要花销一定的时间来把字节码翻译成本地机器码。这样，程序在启动的时候，会有更多的延迟。

这两种方式可以说是各有优势，虚拟机(特指HotSpot虚拟机)在执行的时候，一般会采用两种方式结合的策略。

也就是说，在程序执行的时候，有些代码采用解释器的方式，有些代码采用编译器，称之为即时编译。一般我们会对热点代码采用编译器的方式。

2.编译对象与触发条件

上面已经说了，运行过程中，如果遇到热点代码就会触发对该代码进行编译，编译成本地机器码。

什么是热点代码？

热点代码主要有一下两类：

1. 被多次调用的方法。
2. 被多次执行的循环体。

不过这里需要注意的是，由于循环体是存在方法之中的，尽管编译动作是由循环体触发的，但编译器仍然会以这个方法来作为编译的对象。

3.热点探测

判断一段代码是不是热点代码，是不是需要触发即时编译，这样的行为我们称之为热点探测。热点探测判定有以下两种方式：

1. 基于采样的热点探测：这种方式虚拟机会周期性着检查各个线程的栈顶，如果发现某个方法经常出现在栈顶，那么这个方法就是热点方法。可能有人会问，所谓经常，那什么样才算经常，对于这个我只能告诉你，这个取决于你自己的设置，如果自己没有进行相应的设置的话，就采用虚拟机的默认设置。
2. 基于计数器的热点探测：这种方法我们会为每个方法设置一个计数器，统计方法被调用的次数，如果到达一定的次数，我们就把它当作是热点方法。

两种方法的优缺点：

显然第一种方法在实现上是比较简单、高效的，但是缺点也很明显，精确度不高，容易受到线程阻塞等别的外界因素的干扰。

第二种方式的统计结果会很精确，但需要为每个方法建立并维护一个计数器。实现上会相对复杂一点并且开销也会大点。

不过，这里需要指出的是，我们的HotSpot虚拟机采用的是基于计数器的方式。

说明：虚拟机在执行方法的时候，会先判断该方法是否存在已经编译好的版本，如果存在，则执行编译好的本地机器码，否则，采用一边解释一边编译的方式。

4.编译优化技术

先看一段代码：

1
2
3
4
5

int a = 1;
if(false){
    System.out.println("无用代码");
}
int b = 2;

对于这段代码，我们都知道是if语句体里面的代码是一定不可能会被执行到的，也就是说，这实际上是一段一点用处也没有的代码，在执行时只能浪费判断时间。

实际上，对于我们书写的代码，编译器在编译的时候是会进行优化的。对于上面的代码，编译优化之后会变成这样：

1
2

int a = 1;
int b = 2;

那段无用的代码会被消除掉。

各种编译优化策略

我们刚才已经说了，对于有些被多次调用的方法或者循环体，虚拟机会先把他们编译成本地机器码。由于这些热点代码都是一些会被多次重复执行的代码，为了使得编译好的代码更加完美，运行的更快。编译器做了很多的编译优化策略，例如上面的无用代码消除就是其中的一种。

下面我们来讲讲大概都有那些优化策略：

大概预览一波：

1. 公共子表达式消除。
2. 数组范围检查消除。
3. 方法内联。
4. 逃逸分析。

(1).公共子表达式消除

含义：如果一个表达式 E 已经计算过了，并且从先前的计算到现在 E 中的所有变量的值都没有发生变化，那个 E 的这次出现就成为了公共子表达式。对于这样的表示式，没有必要对它再次进行计算了，直接沿用之前的结果就可以了。

我们来举个例子。例如

1

int d = (c * b) * 10 + a + (a + b * c);

这段代码到了即时编译器的手里，它会进行如下优化：

表达式中有两个 b * c的表达式，并且在计算期间b与c的值并不会变。所以这条表达式可能会被视为：

1

int d = E * 10 + a+ (a + E);

接着继续优化成

1

int d = E * 11 + a + a;

接着

1

int d = E * 11 + 2a;

这样，代码在执行的时候，就会节省了一些时间了。

(2).数组范围检查消除

我们知道，java是一门动态安全的语言，对数组的访问不像c/c++那样，可以采用指针指向一块可能不存在的区域。例如假如有一个数组arr[]，在java语言中访问数组arr[i]的时候，是会先进行上下界范围检查的，即先检查i是否满足i >= 0 && i < arr.length这个条件。如果不满足则会抛出相应的异常。这种安全检查策略可以避免溢出。但每次数组访问都会进行这样一次检查无疑在速度性能上造成一定的影响。

实际上，对于这样一种情况，编译器也是可以帮助我们做出相应的优化的。例如对于数组的下标是一个常量的，如arr[2]，只要在编译期根据数据流分析来确定arr.length的值，并判断下标‘2’并没有越界，这样在执行的时候就无需在判断了。

更常见的情况是数组访问发生在循环体中，并且使用循环变量来进行数组的访问，对于这样的情况，只要编译器通过数据流就可以判断循环变量的取值范围是否在[0, arr.length)之内，如果是，那么整个循环中就可以节省很多次数组边界检测判断的操劳了。

对于这些安全检查所消耗的时间，实际上，我们还可以采用另外一种策略–隐式异常处理。例如当我们在访问一个对象arr的属性arr.value的时候，没有优化之前虚拟机是这样处理的：

1
2
3
4
5

if(arr != null){
    return arr.value;
}else{
    throw new NollPointException();
}

采用优化策略之后编程这样子：

1
2
3
4
5

try{
    return arr.value;
}catch(segment_fault){
    uncommon_trap();
}

就是说，虚拟机会注册一个Segment Fault信号的异常处理器(uncommon_trap())，这样当arr不为空的时候，对value的访问可以省去对arr的判断。代价就是当arr为空时，必须转入到异常处理器中恢复并抛出NullPointException异常，这个过程会从用户态转到内核态中处理，结束后在回到用户态，速度远比一次判断空检查慢。当arr极少为null的时候，这样做是值得的，但假如arr经常为null时，那么会得不偿失。

不过，虚拟机还是挺聪明的，它会根据运行期收集到的信息来自动选择最优方案。

(3).方法内联

先看一段代码

1
2
3
4
5
6
7
8
9
10

public static void f(Object obj){
    if)(obj != null){
        System.out.println("do something");
    }
}

public static void test(String[] args){
    Object obj = null;
    f(obj);
}

对于这段代码，如果把两个方法结合在一起看，我们可以发现test()方法里面都是一些无用的代码。因为f(obj)这个方法的调用，没啥卵用。但是如果不做内联优化，后续尽管进行了无用代码的消除，也是无法发现任何无用代码的，因为如果把f(Object obj)和test(String[] args)两个发放分开看的话，我们就无法得只f(obj)是否有用了。

内联优化后的代码可以是这样：

1
2
3
4
5
6
7
8
9
10

public static void f(Object obj){
    if)(obj != null){
        System.out.println("do something");
    }
}

public static void test(String[] args){
    Object obj = null;
    //该方法直接不执行了
}

(4).逃逸分析

逃逸分析是目前Java虚拟机比较前沿的优化技术，它并非是直接优化代码，而是为其他优化手段提供依据发分析技术。

逃逸分析主要是对对象动态作用域进行分析：当一个对象在某个方法被定义后，它有可能被外部的其他方法所引用，例如作为参数传递给其他方法，称之为方法逃逸，也有可能被外部线程访问到，例如类变量，称之为线程逃逸。

假如我们可以证明一个对象并不会发生逃逸的话，我们就可以通过一些方式对这个变量进行一些高效的优化了。如下所示：

1).栈上分配

我们都知道一个对象创建之后是放在堆上的，这个对象可以被其他线程所共享，并且我们知道在堆上的对象如果不再使用时，虚拟机的垃圾收集系统就会对它进行帅选并回收。但无论是回收还是帅选，都是需要花费时间的。

但是假如我们知道这个对象不会逃逸的话，我们就可以直接在栈上对这个对象进行内存分配了，这样，这个对象所占用的内存空间就可以随进栈和出栈而自动被销毁了。这样，垃圾收集系统就可以省了很多帅选、销毁的时间了。

2).同步消除

线程同步本身是一个相对耗时的过程，如果我们能判断这个变量不会逃出线程的话，那么我们就可以对这个变量的同步措施进行消除了。

3).标量替换

什么是标量？

当一个数据无法分解成更小的时候，我们称之为变量，例如像int,long,char等基本数据类型。相对地，如果一个变量可以分解成更小的，我们称之为聚合量，例如Java中的对象。

假如这个对象不会发生逃逸。

我们可以根据程序访问的情况，如果一个方法只是用到一个对象里面的若干个属性，我们在真正执行这个方法的时候，我们可以不创建这个对象，而是直接创建它那几个被使用到的变量来代替。这样，不仅可以节省内存以及时间，而且这些变量可以随出栈入栈而销毁。

不过，对于编译器优化的技术还有很多，上面这几种算是比较典型的。

本次讲解到这里。

完

参考书籍：深入Java虚拟机

如果你习惯在微信公众号看技术文章
想要获取更多资源的同学
欢迎关注我的公众号：苦逼的码农
每周不定时更新文章，同时更新自己算法刷题记录。

煎熬了几分

类初始化

在讲类的初始化之前，我们先来大概了解一下类的声明周期。如下图

类的声明周期可以分为7个阶段，但今天我们只讲初始化阶段。我们我觉得出来使用和卸载阶段外，初始化阶段是最贴近我们平时学的，也是笔试做题过程中最容易遇到的，假如你想了解每一个阶段的话，可以看看深入理解Java虚拟机这本书。

下面开始讲解初始化过程。

注意：

这里需要指出的是，在执行类的初始化之前，其实在准备阶段就已经为类变量分配过内存，并且也已经设置过类变量的初始值了。例如像整数的初始值是0，对象的初始值是null之类的。基本数据类型的初始值如下：

大家先想一个问题，当我们在运行一个java程序时，每个类都会被初始化吗？假如并非每个类都会执行初始化过程，那什么时候一个类会执行初始化过程呢？

答案是并非每个类都会执行初始化过程，你想啊，如果这个类根本就不用用到，那初始化它干嘛，占用空间。

至于何时执行初始化过程，虚拟机规范则是严格规定了有且只有5中情况会马上对类进行初始化。

1. 当使用new这个关键字实例化对象、读取或者设置一个类的静态字段，以及调用一个类的静态方法时会触发类的初始化(注意，被final修饰的静态字段除外)。
2. 使用java.lang.reflect包的方法对类进行反射调用时，如果这个类还没有进行过初始化，则会触发该类的初始化。
3. 当初始化一个类时，如果其父类还没有进行过初始化，则会先触发其父类。
4. 当虚拟机启动时，用户需要指定一个要执行的主类(包含main()方法的那个类)，虚拟机会先初始化这个主类。
5. 当使用JDK 1.7的动态语言支持时，如果一个…..(省略，说了也看不懂，哈哈)。

注意是有且只有。这5种行为我们称为对一个类的主动引用。

初始化过程

类的初始化过程都干了些什么呢？

在类的初始化过程中，说白了就是执行了一个类构造器()方法过程。注意，这个clinit并非类的构造函数(init())。

至于clinit()方法都包含了哪些内容？

实际上，clinit()方法是由编译器自动收集类中的所有类变量的赋值动作和静态语句块(static{}块)中的语句合并产生的，编译器收集的顺序则是由语句在源文件中出现的顺序来决定的。并且静态语句块中只能访问到定义在静态语句块之前的变量，定义在它之后的变量，在前面的静态语句块可以赋值，但不能访问。如下面的程序。

1
2
3
4
5
6
7

public class Test1 {
    static {
        t = 10;//编译可以正常通过
        System.out.println(t);//提示illegal forward reference错误
    }
    static int t = 0;
}

给大家抛个练习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Father {
    public static int t1 = 10;
    static {
        t1 = 20;
    }
}
class Son extends Father{
    public static int t2 = t1;
}
//测试调用
class Test2{
    public static void main(String[] args){
        System.out.println(Son.t2);
    }
}

输出结果是什么呢？

答案是20。我相信大家都知道为啥。因为会先初始化父类啊。

不过这里需要注意的是，对于类来说，执行该类的clinit()方法时，会先执行父类的clinit()方法，但对于接口来说，执行接口的clinit()方法并不会执行父接口的clinit()方法。只有当用到父类接口中定义的变量时，才会执行父接口的clinit()方法。

被动引用

上面说了类初始化的五种情况，我们称之为称之为主动引用。居然存在主动，也意味着存在所谓的被动引用。这里需要提出的是，被动引用并不会触发类的初始化。下面，我们举例几个被动引用的例子：

1. 通过子类引用父类的静态字段，不会触发子类的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 1.通过子类引用父类的静态字段，不会触发子类的初始化
 */
public class FatherClass {
    //静态块
    static {
        System.out.println("FatherClass init");
    }
    public static int value = 10;
}

class SonClass extends FatherClass {
    static {
        System.out.println("SonClass init");
    }
}
 class Test3{
    public static void main(String[] args){
        System.out.println(SonClass.value);
    }
}

输出结果

1

FatherClass init

说明并没有触发子类的初始化

2. 通过数组定义来引用类，不会触发此类的初始化。

1
2
3
4
5

class Test3{
   public static void main(String[] args){
       SonClass[] sonClass = new SonClass[10];//引用上面的SonClass类。
   }      
}

输出结果是啥也没输出。

3. 引用其他类的常量并不会触发那个类的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13

public class FatherClass {
    //静态块
    static {
        System.out.println("FatherClass init");
    }
    public static final String value = "hello";//常量
}

class Test3{
    public static void main(String[] args){
        System.out.println(FatherClass.value);
    }
}

输出结果:hello

实际上，之所以没有输出”FatherClass init”,是因为在编译阶段就已经对这个常量进行了一些优化处理，例如，由于Test3这个类用到了这个常量”hello”，在编译阶段就已经将”hello”这个常量储存到了Test3类的常量池中了，以后对FatherClass.value的引用实际上都被转化为Test3类对自身常量池的引用了。也就是说，在编译成class文件之后，两个class已经没啥毛关系了。

重载

对于重载，我想学过java的都懂，但是今天我们中虚拟机的角度来看看重载是怎么回事。

首先我们先来看一段代码：

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

//定义几个类
public abstract class Animal {
}
class Dog extends Animal{
}
class Lion extends Animal{
}

class Test4{
    public void run(Animal animal){
        System.out.println("动物跑啊跑");
    }
    public void run(Dog dog){
        System.out.println("小狗跑啊跑");
    }
    public void run(Lion lion){
        System.out.println("狮子跑啊跑");
    }
    //测试
    public static void main(String[] args){
        Animal dog = new Dog();
        Animal lion = new Lion();;
        Test4 test4 = new Test4();
        test4.run(dog);
        test4.run(lion);
    }
}

运行结果：

动物跑啊跑

动物跑啊跑

相信大家学过重载的都能猜到是这个结果。但是，为什么会选择这个方法进行重载呢？虚拟机是如何选择的呢？

在此之前我们先来了解两个概念。

先来看一行代码：

Animal dog = new Dog();

对于这一行代码，我们把Animal称之为变量dog的静态类型，而后面的Dog称为变量dog的实际类型。

所谓静态类型也就是说，在代码的编译期就可以判断出来了，也就是说在编译期就可以判断dog的静态类型是啥了。但在编译期无法知道变量dog的实际类型是什么。

现在我们再来看看虚拟机是根据什么来重载选择哪个方法的。

对于静态类型相同，但实际类型不同的变量，虚拟机在重载的时候是根据参数的静态类型而不是实际类型作为判断选择的。并且静态类型在编译器就是已知的了，这也代表在编译阶段，就已经决定好了选择哪一个重载方法。

由于dog和lion的静态类型都是Animal,所以选择了run(Animal animal)这个方法。

不过需要注意的是，有时候是可以有多个重载版本的，也就是说，重载版本并非是唯一的。我们不妨来看下面的代码。

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

public class Test {
    public static void sayHello(Object arg){
        System.out.println("hello Object");
    }
    public static void sayHello(int arg){
        System.out.println("hello int");
    }
    public static void sayHello(long arg){
        System.out.println("hello long");
    }
    public static void sayHello(Character arg){
        System.out.println("hello Character");
    }
    public static void sayHello(char arg){
        System.out.println("hello char");
    }
    public static void sayHello(char... arg){
        System.out.println("hello char...");
    }
    public static void sayHello(Serializable arg){
        System.out.println("hello Serializable");
    }

    //测试
    public static void main(String[] args){
        char a = 'a';
        sayHello('a');
    }
}

运行下代码。
相信大家都知道输出结果是

hello char

因为a的静态类型是char,随意会匹配到sayHello(char arg);

但是，如果我们把sayHello(char arg)这个方法注释掉，再运行下。

结果输出:

hello int

实际上这个时候由于方法中并没有静态类型为char的方法，它就会自动进行类型转换。‘a’除了可以是字符，还可以代表数字97。因此会选择int类型的进行重载。

我们继续注释掉sayHello(int arg)这个方法。结果会输出：

hello long。

这个时候’a’进行两次类型转换，即 ‘a’ -> 97 -> 97L。所以匹配到了sayHell(long arg)方法。

实际上，’a’会按照char ->int -> long -> float ->double的顺序来转换。但并不会转换成byte或者short，因为从char到byte或者short的转换是不安全的。(为什么不安全？留给你思考下)

继续注释掉long类型的方法。输出结果是：

hello Character

这时发生了一次自动装箱，’a’被封装为Character类型。

继续注释掉Character类型的方法。输出

hello Serializable

为什么？

一个字符或者数字与序列化有什么关系？实际上，这是因为Serializable是Character类实现的一个接口，当自动装箱之后发现找不到装箱类，但是找到了装箱类实现了的接口类型，所以在一次发生了自动转型。

我们继续注释掉Serialiable，这个时候的输出结果是：

hello Object

这时是’a’装箱后转型为父类了，如果有多个父类，那将从继承关系中从下往上开始搜索，即越接近上层的优先级越低。

继续注释掉Object方法，这时候输出：

hello char…

这个时候’a’被转换为了一个数组元素。

从上面的例子中，我们可以看出，元素的静态类型并非就是一定是固定的，它在编译期根根据优先级原则来进行转换。其实这也是java语言实现重载的本质

重写

我们先来看一段代码

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

//定义几个类
public abstract class Animal {
    public abstract void run();
}
class Dog extends Animal{
    @Override
    public void run() {
        System.out.println("小狗跑啊跑");
    }
}
class Lion extends Animal{
    @Override
    public void run() {
        System.out.println("狮子跑啊跑");
    }
}
class Test4{
    //测试
    public static void main(String[] args){
        Animal dog = new Dog();
        Animal lion = new Lion();;
        dog.run();
        lion.run();
    }
}

运行结果：

小狗跑啊跑
狮子跑啊跑

我相信大家对这个结果是毫无疑问的。他们的静态类型是一样的，虚拟机是怎么知道要执行哪个方法呢？

显然，虚拟机是根据实际类型来执行方法的。我们来看看main()方法中的一部分字节码

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

//声明：我只是挑出了一部分关键的字节码
public static void (java.lang.String[]);
    Code:
    Stack=2, Locals=3, Args_size=1;//可以不用管这个
    //下面的是关键
    0：new #16;//即new Dog
    3: dup
    4: invokespecial #18; //调用初始化方法
    7: astore_1
    8: new #19 ;即new Lion
    11: dup
    12: invokespecial #21;//调用初始化方法
    15: astore_2
    
    16: aload_1; 压入栈顶
    17: invokevirtual #22;//调用run()方法
    20: aload_2 ;压入栈顶
    21: invokevirtual #22;//调用run()方法
    24: return

解释一下这段字节码：

0-15行的作用是创建Dog和Lion对象的内存空间，调用Dog,Lion类型的实例构造器。对应的代码:

Animal dog = new Dog();

Animal lion = new Lion();

接下来的16-21句是关键部分，16、20两句分分别把刚刚创建的两个对象的引用压到栈顶。17和21是run()方法的调用指令。

从指令可以看出，这两条方法的调用指令是完全一样的。可是最终执行的目标方法却并不相同。这是为啥？

实际上：

invokevirtual方法调用指令在执行的时候是这样的：

1. 找到栈顶的第一个元素所指向的对象的实际类型，记作C.
2. 如果类型C中找到run()这个方法，则进行访问权限的检验，如果可以访问，则方法这个方法的直接引用，查找结束；如果这个方法不可以访问，则抛出java.lang.IllegalAccessEror异常。
3. 如果在该对象中没有找到run()方法，则按照继承关系从下往上对C的各个父类进行第二步的搜索和检验。
4. 如果都没有找到，则抛出java.lang.AbstractMethodError异常。

所以虽然指令的调用是相同的，但17行调用run方法时，此时栈顶存放的对象引用是Dog，21行则是Lion。

这，就是java语言中方法重写的本质。

本次的讲解到此结束，希望对你有所帮助。

关注公我的众号：苦逼的码农，获取更多原创文章，后台回复”礼包”送你一份特别的资源大礼包。

前言

深知自己在算法方面上很菜，于是打算通过打卡的方式，逼自己一把。每天在leetcode上打卡，并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路，那么，别犹豫了，上车吧，一起学习一起探讨。

从零打卡leetcode之day 3

1
2
3
4
5
6
7

题目描述：
给定一个int类型的数组，求最大子序列的和。
也就是说，从这个数组中截取一个子数组，这个子数组的元素和最大。

例如：
-1 20 -4 14 -4 -2 
这个数组的最大字序列和为30。即20 -4 14。

解题

1.初级版解法

对于这道题，其实我们可以采取遍历所有可能的组合，然后再比较哪种组合的和最大。

也就是说，我们可以找出所有子序列，然后逐个比较。代码如下。

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

public int solve(int[] arrs){

    int max = 0;//用来存放目标子序列的和

    int temp = 0;//用来存每个子序列的和

    for(int i = 0; i < arrs.length; i++){

        for(int j = i; j < arrs.length; j++){
        
            temp = 0;
            
            //计算子序列的和
            for(int k = 0; k < arrs.length; k++){
                temp += arrs[k];
            }
            //进行比较
            if(temp > max){
                max = temp;
            }
            
        }
    }
    
    return max;
}`

在这三个循环中，外面两个循环枚举出所有子序列，第三个循环计算子序列的和。

看到三个for循环，时间复杂度的O(n3)。这速度，实在是太慢了。我们来优化优化。

2.进阶版

其实，你仔细看一下里面的那两层for循环，会发现其实可以把它们合并成一个for循环的。

也就是说，我们可以在枚举所有子序列的过程中，是可以一边进行数据处理的。还是直接看代码好理解点。如下：

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

public int solve2(int[] arrs){
    
    int max = 0; 
    
    int temp = 0;
    
    for(int i = 0; i < arrs.length; i++){
        
        temp = 0;
        
        for(int j = i; j < arrs.length; j++){
            
            //一边处理数据
            temp += arrs[j];
            
            //进行比较选择
            
            if(max < temp){
                
                max = temp;
            }
        }
    }
    
    return temp;
}

该方法用了两个for循环，时间复杂度为O(n2)，相对来说好了一点。

3.再次优化进阶

这次，我们可以使用递归的思想来处理。递归最重要的就是要找到：

1. 递归的结束条件
2. 把问题分解成若干个子问题。

对于这道题，其实我们可以把序列分成左右两部分。那么，最大子序列和的位置会出现在以下三种情况：

1. 子序列完全在左半部分。
2. 子序列完全在右半部分。
3. 一部分在左，一部分在右。

所以我们只要分别求出左半部分的最大子序列和、右半部分的最大子序列和(注意，问题已经转化为求左右两部分的最大子序列和了，也就是说问题被分解成若干子问题了)、以及跨越左右两部分的最大子序列和。最后比较三者之中哪个比较大就可以了。

如何求解左半部分和右半部分的最大子序列？

其实道理一样，把左半部分和右半部分再次分解左右两部分就可以了。

那么，如何求解跨越左右两部分的最大子序列呢？

其实只要求出包含左半部分中最右边元素的子序列的最大和，以及求出包含右半部分中最左边元素的子序列的最大和，然后让两者相加，即可求出跨域左右两部分的最大子序列和了。

子问题已经分解出来了，那么递归的结束条件是什么？

我们把数组分成左右两部分，其实当左右两部分只有一个元素时，递归结束。

这道题的递归思路算是找出来了，不过，代码实现？假如你对递归不大熟悉的话，可能在实现上还是有那么点困难的。对于递归的学习，大家也可以看我写的关于递归与动态规划的几篇文章。

我就直接抛代码了。

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

//递归版本
public int solve3(int[] arrs, int left, int right){
    int max = 0;

    //表示只有一个元素，无需在分解
    if(left == right){
        //为什么？因为低于0的数肯定不可以是最大值的
        //大不了最大值为0
        max = arrs[left] >= 0 ? arrs[left]:0;
    }else{

        int center = (left + right)/2;
        //求解左半部分最大子序列
        int leftMax = solve3(arrs, left, center);
        //求解右半部分最大子序列
        int rightMax = solve3(arrs, center+1, right);

        //求解kua跨越左右两部分的最大子序列
        //1.求包含左部分最右元素的最大和
        int l = 0;
        int l_max = 0;
        for(int i = center; i >= left; i--){
            l += arrs[i];
            if(l > l_max){
                l_max = l;
            }
        }

        //2.求包含右部分最左元素的最大和
        int r = 0;
        int r_max = 0;
        for(int i = center+1; i <= right; i++){
            r += arrs[i];
            if(r > r_max){
                r_max = r;
            }
        }
        //跨越左右两部分的最大子序列
         max = l_max + r_max;

        //取三者最大值
        if(max < leftMax) max = leftMax;
        if(max < rightMax) max = rightMax;
    }

    return max;
}

递归求解方法的时间复杂度为O(nlgn)。这速度，比第一种做法，不知道快了几个级别….

递归解法可以说是很快的了

但是，等等，我还是不满意…

4.最终版:动态规划

接下来的最终版，时间复杂度可以缩减到O(n), 虽然说是采用了动态规划的思想，不过，我觉得你没学过动态规划也可以看懂。

假如我给你

1

1 2 -4 5 6

五个元素，你在计算前面三个元素的时候，即

1 + 2 + -4 = -1

发现前面三个元素的和是小于0的，那么，这个

1 2 -4

的子序列我们还要吗？显然，这个子序列的和都小于0了，我们是可以直接淘汰的。因为如果还要这个子序列的话，它和后面的5一相加，结果变成了4，我们还不如让我们的目标子序列直接从5开始呢。

先看代码吧，可能反而会好理解点

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

//基于动态规划的思想
public int solve4(int[] arrs){
    int max = 0;//存放目标子序列的最大值
    int temp = 0;//存放子序列的最大值

    for(int i = 0; i < arrs.length; i++){
        temp += arrs[i];
        if(temp > max){
            max = temp;
        }else{
            //如果这个子序列的值小于0，那么淘汰
            //从后面的子序列开始算起
            if(temp < 0){
                temp = 0;
            }
         }
    }
    return max;
}

这道题不是leetcode上的题目，不过我觉得这道题很不错，所以拿出来分享给大家。

如果你有什么不大清楚的，欢迎微信群里讨论，当然也可以直接来问我勒。欢迎转发让更多人加入打卡行列勒。

如果这道题能对你有所帮助，不妨点个赞。哈哈