Java

搜索技巧

末尾加上PDF，可以搜出一些高质量的文章，包括一些技术分享、大学的课件。

Wikipedia看参考文献，会有很多不错的资料。

关键字：Overview，Demystify

学习过程：从宏观上了解

基础

String

String.intern()

如果常量池中存在当前字符串, 就会直接返回当前字符串. 如果常量池中没有此字符串, 会将此字符串放入常量池中后, 再返回。常量池是堆中的一块特殊区域。

hashCode()和equals()

hashcode规约

• 对同一对象，hashcode方法返回值每次应相同

  如果不同，则会导致根据hashcode变化无法在桶中找到该元素。Python字典中要求key需要是immutable的也是这个原因

• 如果重写了equals()方法，检查条件“两个对象使用equals()方法判断为相等，则hashCode()方法也应该相等”是否成立，如果不成立，则重写hashCode ()方法。

• 不要求不同对象返回不同hashcode，但是如果每个对象都可以返回不同的hashcode，可以提高hash table的性能。

重写equals时为什么要重写hashcode

不重写hashcode方法，涉及到HashMap、HashSet等依赖对象hashcode值的集合会出问题。

HashMap通过hashcode将对象放到对应的桶结构中，在取数据时，根据hashcode定位到桶，然后根据equal在桶中寻找到对象。

如果不重写hashcode，就可能出现两个相同的对象(业务上)，由于hashcode不同，而会在HashMap中存两份。

synchronized关键字原理

synchronized通过monitor来实现线程同步，而monitor是通过mutex lock和condition variable来实现互斥，每个Java对象(包括类对象)都有个mutex lock。在synchronized包裹的代码前后会有monitorenter和moniterexit指令。Monitor中的互斥锁是OS层面来支持，在获取(monitor entry)和释放锁(monitor exit)存在大量的开销。因此HotSpot VM在这方面做了些优化，引入了轻量级锁和偏向锁等。

monitor

监视器是一个可以实现线程互斥和协作的结构。

监视器可以看作一个房子，这个房子有个只能被一个线程占有的特殊的房间，房间里保护的就是临界资源。

如果一个线程需要进入特殊房间，首选需要在大门(Entry Set)中等待，由调度策略决定下一个进入房间的是哪个线程。如果线程由于某种原因被挂起，则进入Wait Set，在合适的时间会被安排到特殊房间里。

进入房子 - entering the monitor

进入特殊房间 - acquiring the monitor

占据特殊房间 - owning the monitor

离开特殊房间 - releasing the monitor

离开房子 - exiting the monitor

Synchornized关键字就是将其包裹的代码块放入特殊房间里，线程需要先enter the monitor后进入entry set，之后acquire the monitor才能运行代码块。

wait和notify也是利用monitor，原理是：当一个线程own the monitor时，可以调用wait方法来将自己挂起，release the monitor并进入到Wait Set中，直到其他在拥有monitor的线程调用notify方法。当线程调用notify时，并不是立马就release the monitor，只有当线程release the monitor后，等待线程才会去acquire the monitor，但是monitor也可能被其他线程获取到，因此即使wait线程获取到monitor，也需要检查下数据是否满足其想要的条件。

synchronized锁的优化

Monitor中的互斥锁是OS层面来支持，在获取(monitor entry)和释放锁(monitor exit)时存在大量的开销。因此HotSpot VM在这方面做了些优化。

对象头

对象头主要包含两部分数据：Mark Word、Klass Pointer(类型指针，用来确定是哪个类的实例)。

Mark Word：存储了对象的HashCode、分代年龄和锁标志位信息。对象的状态不同，Mark Word里存储的信息也会不同。

锁消除(Lock Elision)

通过逃逸分析的技术，如果对象只会被一个线程使用，在编译成字节码的时候会去掉不必要的锁。

1
2
3
4
5
6

public String getFruits (String... fruits ) {
	Vector v = new Vector();
	for (String fruit: fruits)
	v.add(fruit);
	return v.toString();
}

这里v的引用不会逃出getFruits方法，因此Vector的synchronized锁可以去掉。

锁粗化(Lock Coarsening)

如下

1
2
3
4
5

public Vector getFruits(Vector v) {	
	v.add("Banana");
	v.add("Melon");
	return v;
}

每调一次add方法都有一次获取锁、释放锁的过程，编译器会用一个锁将它们包起来，这个过程叫做锁粗化。对于循环，锁粗化会导致锁长时间被一个线程持有，因此锁粗化只会应用于非循环的情况。

自旋锁与自适应自旋锁

阻塞或唤醒线程存在上下文切换的代价。因此出现了自旋锁，当发现自旋时间过长时，可以将其转化成重量级锁(即OS层面对锁)，因此称为自适应自旋锁。自旋锁的实现原理是CAS。

轻量级锁

大多数时候，不存在锁的竞争。轻量级锁是根据这个场景进行优化。

1. 拷贝对象头中的Mark Word到当前线程栈帧中的Lock Record
2. CAS将Mark Word的ptr指向线程Lock Record
3. 成功则获取到锁，失败则自旋再尝试，自旋达到一定次数后膨胀为重量级锁。

偏向锁

大多数情况，锁总是被同一个线程获得，因此出现了偏向锁。

当锁对象第一次被线程获取时，虚拟机会将对象头中的标志位设为偏向模式，并通过CAS在Mark Word里存储当前线程ID，在线程进入或退出同步代码块时，不是去获取或释放锁，而是检测Mark Word里存储的线程ID是否与当前线程ID相同即可，因此相比自旋锁，偏向锁少了多处CAS的开销。如果相同，说明已经获取到锁，如果不同，说明偏向的是别的线程，这时候就应该撤销偏向锁，不能继续偏向原来的线程。偏向锁的撤销，需要在如下场景下：

volatile

volatile作用

在单核处理中，同一进程的不同线程访问共享数据时，CPU先将共享变量加载到共享缓存中，不同线程访问该数据时，都是访问的同一个地址，因此volatile的可见性就没有必要了。但是在多核处理器中，每个CPU都会从主存中将数据加载到其自身的缓存中，这时候就可能会出现缓存不一致的问题，当多线程运行在不同的CPU时，就可能导致每个线程看到的数据不一致，volatile就是为了解决这个问题。

volatile修饰的变量具有可见性，对一个volatile变量的写操作及这个写操作之前的所有操作Happens-Before对这个变量的读操作及这个读操作之后的所有操作。

volatile实现原理

volatile需要借助硬件来实现。对volatile变量的写操作，会在正常汇编指令前加一个lock前缀的指令，这个指令在多核处理器会做两件事。

1. 锁总线，其它CPU对内存的读写请求都会被阻塞，直到锁释放，由于锁总线期间其他CPU没法访问内存，因此其开销比较大，后来的处理器都采用锁缓存替代锁总线，通过缓存一致性协议来实现数据一致。缓存一致性协议有多种，常见的是通过嗅探来实现，通过不停的嗅探总线上的数据交换，从而当一个缓存代表它所属的处理器去读写内存时，其它处理器都会得到通知，它们以此来使自己的缓存保持同步。
2. lock后的写操作会回写已修改的数据，同时让其它CPU相关缓存行失效，从而重新从主存中加载最新的数据

ThreadLocal

作用

每个线程保存一个变量的副本。

应用场景

1. 方便传参数，A方法到F方法，中间经过了很多方法，现在需要从A多传一个参数到F，为了避免对中间方法对应用，可以用threadlocal来进行传参。

2. 其实应用场景就跟其作用所说一样，需要使用与线程相关的数据时使用。

原理

已有的条件是什么？:

ThreadLocal变量，线程实例

求解的问题:

ThreadLocal实现原理

每个线程一个变量，通过ThreadLocal的方法获取到该值，很容易想到的就是Map。即线程实例为键，变量为值。那么这个map保存在哪呢？正常想到的想法是保存在ThreadLocal对象里，即ThreadLocal t 有个Map，这个Map保存了线程和其值的关系。但是线程对象大多数是临时对象，也就是说ThreaLocal的这个Map需要经常更新，不然就会保持对线程的引用，导致线程无法回收。既然线程的变量存活周期与线程是一样的，那么何不把这个变量保存在线程对象中呢，由于线程会有不同类型的threadlocal局部变量，因此需要一个字段能够包含这所有的threalocal，做法还是用map，key是ThreadLocal变量，而value是线程真正对应的值。Entry(ThreadLocal<?> k, Object v)

JVM

JVM内存区域

类加载机制

GC

GC要做的三件事：

1. 哪些内存需要回收(what)

2. 什么时候回收(when)

3. 怎么回收(how)

哪些内存需要回收

可达性分析，GC Roots Tracing：当对象与GC Roots没有引用链相连时，该对象为不可达对象。GC Roots包括如下

1. System Class

​ 由bootstrap/system 类加载器加载的类

2. Native Code

​ Native code中的局部变量和全局变量

3. Thread Block

​ 当前活跃线程里引用的对象

4. Thread

​ 已启动的线程

5. Stack Local

   Java方法的local变量或参数

当一个对象被标记为不可达后，下一个垃圾回收会试图回收该对象，如果对象重写了finalize方法，并且在这个方法自救成功(将自身赋予某个引用)，则不会被回收，但是如果没有重写finalize或者已经执行过该方法，则自救失败。

什么时候回收要与怎么回收一起来看，Java主要采用了分代回收，将堆内存分成了新生代和老年代。

怎么回收

通过垃圾收集器进行垃圾回收

垃圾回收分为三步：

1. 标记(Mark)

要进行垃圾回收，首先要确定哪些是垃圾嘛，这一步将对对象进行扫描，来确定哪些对象需要回收

2. 清除

既然知道哪些对象要回收，那么这一步就从内存中删掉这些对象

3. 整理(compact)

如上所示，在清除时会产生内存碎片，可以在清除后进行整理，来清除内存碎片。

在上述步骤中，标记和整理是比较耗时的，随着对象越来越多，垃圾回收的时间也就越长，而实际上，一个应用的大多数对象其实存活时间是很短的，分代回收的思想是不同代的对象存活时间不一样，因此垃圾回收的频率应该也不一样，尽量做到：当开始垃圾回收时，能做到大多数对象被标记为可被回收，使得标记阶段做的活不是白费的。这就是为什么采用分代回收。

如图所示

大多数对象最初都被分配到新生代，对新生代里的对象的预期就是存活时间不长，当新生代区域满时，就会发生minor gc，当对象在新生代中存活超过一定的gc次数，就会被移动到老年代中，当老年代也需要回收时，此时会发生full gc。

GC流程如下：

1. 对象首先放到eden区，eden区满时，发生minor gc，存活对象移动到S0，清除eden区。同时，对象被标记存活年龄。

2. 下一次minor gc时，存活对象和S0的对象移动到S1，清除eden和S0区。

3. 下一次，存活对象则从S1到S0，如此反复，当对象存活超过一定次数，移动到老年代。

​ 为什么设置S0、S1？首先，为什么需要survivor区？如果没有survivor区，eden区满了之后就会被送到老年代，这会导致很快发生Full GC。这些对象可能还是属于死得早的对象，只不过逃过了第一次垃圾回收，设置S区作为缓冲区可以使得这些年轻对象仍在年轻代被回收。为什么需要两个S区？主要是为了避免内存碎片，如果只有一个，那么在第二次minor gc时，可能eden和survivor区都会有部分对象存活，如果把eden区存活对象放到s区，很明显会产生内存碎片。为了避免内存碎片，新增一个s区，将所有存活对象移动到另一个空的s区中去。

​ Full GC具体什么时候发生？前面说到当老年代需要回收时，会触发Full GC。那么什么时候会触发呢，1. 当老年代空间不足时，空间不足包括几种可能：创建大对象、大数组，老年代没有足够大的连续空间时；新生代转入导致空间不足。2.Metaspace空间不足。3.System.gc()方法的调用，这个方法是建议虚拟机进行Full GC，很多时候确实也会导致Full GC。

​ 存活的对象Survivor区放不下怎么办？如果Survivor区太小，放不下的对象会被直接放到老年代，如果Survivor区太大，则会造成无用的浪费。虚拟机会在每次垃圾回收时设置一个threshold，对象被晋升到老年代时的存活次数，这个值保证survivor区的剩余空间大概在一半左右。

垃圾回收算法

对年轻代和老年代，可以采用不同的垃圾回收算法。

Serial GC

单线程进行垃圾回收，没有线程间通信开销，效率比较高，适用于单处理器的机器。

也适用于一台机器上运行多个JVM(超过处理器数量)的情况，可以避免多线程回收对其他JVM的影响。还适用于对停顿时间要求不是很高的场景。

Parallel GC

并行执行年轻代的垃圾回收，适用于对系统吞吐量要求较高的环境。

Concurrent GC

减少应用的停顿时间。

应用可以对年轻代和老年代配置一组相互兼容的垃圾收集器。如下图所示。

stop-the-world pause: 只使应用线程全部暂停的垃圾回收。

所有的垃圾回收在minor gc时都会有stop-the-world pause，但是在full gc时，CMS和G1收集器与其他垃圾收集器的区别在于它们可以在标记阶段做到没有停顿，不过代价是占用更多的CPU资源。

CMS收集器

CMS收集器使用一个或多个线程在后台定期对老年代进行回收。但是由于不进行整理操作，会产生内存碎片。

G1收集器

G1收集器将堆分为了许多region。

堆大小什么时候扩容

MetaSpace大小设置过大导致发生Full GC

并发

线程池的作用

1. 线程的创建和销毁消耗资源，因此通过池技术来达到复用。
2. 对线程进行管控，线程创建无限制的话，对整个系统可能造成致命影响。
3. 根据业务创建线程池，可以对业务进行隔离，避免相互影响。

Java线程池

1

ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, RejectedExecutionHandler handler)

重要参数

• corePoolSize 池中的线程基本个数
• maximumPoolSize 最大线程个数
• keepAliveTime 当线程个数大于corePoolSize时，线程空闲时的最大存活时间
• workQueue 存放任务的阻塞队列
• handler 当队列和最大线程池都满了之后的饱和策略。

通过threadPool.execute(**new** Job())提交一个任务后，经历如下几个步骤

线程池提供了四种拒绝策略，也可以自己实现接口自定义饱和策略：

1、AbortPolicy：直接抛出异常，默认策略；
2、CallerRunsPolicy：用调用者所在的线程来执行任务；
3、DiscardOldestPolicy：丢弃阻塞队列中靠最前的任务，并执行当前任务；
4、DiscardPolicy：直接丢弃任务；

线程池配置的合理性主要还是需要通过测试验证来确定。基本原则是：线程等待时间所占比例越高，需要越多线程；线程cpu时间所占比例越高，需要越少线程。

Thread.run()和Thread.start()区别

run方法就是个普通方法，可以被重复调用，不能起到多线程的目的；调用start方法，会启动新的线程，线程获取到时间片后，会运行run方法，start不能被重复调用，为什么呢？如果在一个Thread对象执行多次并发操作，那么getStackTrace() and getState()应该返回什么？

创建线程有哪几种方式

1. 实现Runnable接口，重写run方法
2. 继承Thread，重写run方法，Thread实现了Runnable接口，与方法1其实原理一样
3. 实现Callable接口，结合FutureTask使用

数据结构

解决哈希冲突的方法

常用方法有开放地址法(Python 字典实现)、拉链法(Java HashMap实现)。参考

操作系统

进程和线程的区别

进程是一个资源的容器，为进程里的所有线程提供共享资源，进程是系统资源分配的单位，线程是系统调度的单位。

线程有自己独立的程序计数器和栈，一个进程内的线程共享地址空间，创建和销毁线程的开销比进程小。线程依赖于进程而存在。

进程间通信比线程间通信要复杂。

多线程和多进程如何选择

多进程的系统鲁棒性更好，适合于分布式场景，内存地址空间隔离，对于不需要共享数据的情况下，可以使用多进程。

线程创建和销毁的开销小，对于一些服务器响应任务，所需线程数量经常变化的场景适合用多线程，而不适合用多进程。线程间可以共享内存地址空间，这也是需要多线程的原因。

强相关的处理用线程，弱相关的处理用进程。多线程更方便于功能的内聚，更有力的进行资源的共享，多进程更方便于功能的可拆分，但多进程会导致资源共享的困难。需要多任务进行大量CPU计算的适合用多线程，因为线程切换比较快。

可能要扩展到多机分布的用进程，实际应用中都是进程+线程的结合方式

数据库

四种隔离级别

读未提交

读不会加锁，其他事务在写的时候会加排它锁(排它锁会阻止其它事务再对其锁定的数据加读或写的锁，但是对不加锁的读无影响)。

读已提交

MVCC机制实现，MVCC版本的生成时机是每次select时，因此会出现不可重复读现象。

可重复读隔离级别的底层实现

MVCC机制，一次事务中，只在第一次select时生成版本，后续的查询都是在这个版本上进行，从而实现了可重复读。但是因为MVCC的快照只对读操作有效，对写操作无效，举例说明会更清晰一点： 事务A依次执行如下3条sql，事务B在语句1和2之间，插入10条age=20的记录，事务A就幻读了。

1
2
3
4
5
6

1. select count(1) from user where age=20;
-- return 0: 当前没有age=20的
2. update user set name=test where age=20;
-- Affects 10 rows: 因为事务B刚写入10条age=20的记录，而写操作是不受MVCC影响，能看到最新数据的，所以更新成功，而一旦操作成功，这些被操作的数据就会对当前事务可见
3. select count(1) from user where age=20;
-- return 10: 出现幻读

REPEATABLE READ级别，可以防止大部分的幻读，但像前边举例读-写-读的情况，使用不加锁的select依然会幻读。

Serializable

读加共享锁，写加排他锁，读写互斥。

为什么索引快

1. 索引块的数量比数据块数量少
2. 键被排序，可以使用查找算法高效查找
3. 索引文件可能足够小，以至于可以永久存放在主存缓冲区中

哪些情况下不会使用索引

• 全表扫描比使用索引快，不会使用索引
• like是以%开头
• 潜在的数据类型转换
• 索引列参与了函数运算
• or关键字，其中一个字段没索引

B+树和B树的区别

B树是充分利用磁盘预读功能而创建的一种数据结构，B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字，树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少，更多的是在内存中对读取进来的数据进行查找。

B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点大小比B树小，同一磁盘块所能容纳的关键字数量也更多，一次能读入内存中的关键字也就越多，IO读写次数也就降低了。

B+树基于范围的查询更简洁，因为叶子节点有指向下一个叶子节点的指针。

B+树的查询效率更加稳定。任何关键字的查找必须走一条从根结点到叶子结点的路。

CBO

CBO会从目标sql诸多可能的执行路径中选择一条成本值(消耗的I/O和CPU资源)最小的执行路径来作为其执行计划。

cbo的缺陷

cbo的缺陷就在于它可能会选错执行计划。

1. 解析多表关联的sql时，可能的执行路径太多，不可能全部遍历。
2. 假设sql都是单独执行的，没有考虑缓存。。。。

索引全扫描(INDEX FULL SCAN)，扫描目标索引所有叶子块的所有索引行。

走索引全扫描能够达到排序的效果，避免了对该索引的索引键值列的真正排序操作。

算法

如何写好while loop

需要思考如下几点：

1. 从上一迭代到下一迭代是怎么转变的，涉及什么数据变化，数据怎么变化
2. 迭代的终止条件是什么

uuid的作用，优缺点