JAVA面经复习（十一）

面试难度：☆☆☆☆☆

问：hashmap、hashtable

答：hashmap采用哈希数组+链表/红黑树进行构建；hashtable则是采用哈希数组，但其操作都需要获取锁，保证了并发下的安全性。

问：hashmap1.8 对比于 1.7的优化（创建、扩容、插入等）

答：
1、底层数据结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构（当链表长度大于8，转为红黑树）。
2、JDK1.8中resize()方法在表为空时，创建表，在表不为空时，扩容；而JDK1.7中resize()方法负责扩容，inflateTable()负责创建表。
3、 1.8中没有区分键为null的情况，而1.7版本中对于键为null的情况调用putForNullKey()方法。但是两个版本中如果键为null，那么调用hash()方法得到的都将是0，所以键为null的元素都始终位于哈希表table[0]中。
4、当1.8中的桶中元素处于链表的情况，遍历最后如果没有匹配的，直接尾部插入；而1.7在遍历的同时没有添加数据，而是另外调用了addEntry()方法，将节点添加到链表头部，因此在rehash时有可能改变链表顺序。
5、1.7中是通过更改hashSeed值修改节点的hash值从而达到rehash时的链表分散，而1.8中键的hash值不会改变，rehash时根据（hash&oldCap）==0将链表分散。
6、1.7在插入数据之前扩容，而1.8插入数据成功之后扩容。

问：concurrentHashmap 1.8、1.7的对比（创建、扩容、插入、结构、获取size等）

答：创建，jdk1.7中初始化segement数组的第一个元素；而在jdk1.8中则是在put的时候检查是否为空，如果为空才进行插入。
扩容，jdk1.7中，Segment 不扩容而是扩容下面的HashEntry数组，每次都是将数组翻倍；而在jdk1.8中Node数组扩容扩大为原来的两倍。
插入，1.7采用头插法，1.8采用尾插法。
结构，jdk1.7中采用数组（Segment） + 数组（HashEntry） + 链表（HashEntry节点）的方式，Segment实际继承自可重入锁（ReentrantLock）。而在jdk1.8中，则直接采用Node数组 + 链表 / 红黑树的方法，降低了查询的时间复杂度。
获取size，jdk1.7采用两次不加锁的运算先计算一次，如果相同则为对应的size，否则再加锁统计一次。1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount。因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数。

问：synchronized 锁升级、锁消除、锁粗化

答：
锁升级：锁分为四个等级，分别是无锁状态、偏向锁状态、轻量级锁状态、重量级锁状态（级别从低到高），在满足一定情况下，syn对应的锁会进入到下一个状态。
1、偏向锁，即线程获取了锁后不会自动释放，而是等待下一次别人获取锁，同时记录线程ID。如果下一次获取锁的对象依旧是自己从而减少了获取锁的时间，如果是第二个线程获取，则判断当前获取锁的线程是否存活，若不存活，则变为无锁。如果任然存活并需要持有锁，则升级成轻量锁状态。
2、轻量锁，本质是为了应对少量线程争取一个资源，但持有不久的情况。采用CAS对一个特有的对象头进行操作，如果发现CAS失败，则进入自旋。若自旋一定次数后任然没有获得锁，则进入重量级锁状态。
3、重量级锁，重量级锁把除获得资源外的线程全部阻塞，减少CPU空转。
锁粗化就是将多个连续的加锁、解锁操作连接在一起，扩展成一个范围更大的锁，避免频繁的加锁解锁操作。
锁消除：Java虚拟机在JIT编译时(可以简单理解为当某段代码即将第一次被执行时进行编译，又称即时编译)，通过对运行上下文的扫描，经过逃逸分析，去除不可能存在共享资源竞争的锁，通过这种方式消除没有必要的锁，可以节省毫无意义的请求锁时间。

问：CAS的问题 （线程忙等、ABA）

答：首先CAS的算法基于乐观锁的思想，其对变量不进行上锁的操作，而是采用两次取比较值是否相同的方式来修改。如果线程两次所取的变量的值相同，则可以进行修改。否则此次修改失败需要下一次修改。这样可以很大程度上提高并发的性能，但是问题在于：
1、ABA问题：在两次预取变量A的过程中，变量A可能被修改成了B，又被修改回A。这时候CAS是检测不出变化的。解决方案：（1）考虑版本号；（2）采用类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前的标志是否等于预期标志，如果全部相等，则以原子方式将该应用和该标志的值设置为给定的更新值。
2、循环时间长开销大：自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
解决方案：（1）破坏掉for死循环，当超过一定时间或者一定次数时，return退出；（2）
3、只能保证一个共享变量的原子操作：CAS对多个变量进行访问时候，不能保证操作的原子性。
解决方案：（1）加锁。（2）多个共享变量合并。（3）

问：垃圾回收算法？

答：标记清除、标记整理、复制算法、分代回收算法。

问：垃圾收集器

答：1、Serial串行收集器-复制算法，Serial收集器是新生代单线程收集器，优点是简单高效，算是最基本、发展历史最悠久的收集器。它在进行垃圾收集时，必须暂停其他所有的工作线程，直到它收集完成。
2、ParNew收集器-复制算法，ParNew收集器是新生代并行收集器，其实就是Serial收集器的多线程版本。
3、Parallel Scavenge（并行回收）收集器-复制算法，追求高吞吐量，高效利用 CPU。适合在后台运算而不需要太多交互的任务。
4、Serial Old 收集器-标记整理算法，它同样是一个单线程(串行)收集器，使用标记整理算法。这个收集器的主要意义也是在于给Client模式下的虚拟机使用
5、Parallel Old 收集器-标记整理算法，Parallel Old 是Parallel Scavenge收集器的老年代版本，使用多线程和“标记-整理”算法。这个收集器在1.6中才开始提供。
6、CMS收集器-标记整理算法，CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的收集器。目前很大一部分的Java应用集中在互联网站或者B/S系统的服务端上，这类应用尤其重视服务器的响应速度，希望系统停顿时间最短，以给用户带来较好的体验。CMS收集器就非常符合这类应用的需求。
7、.G1收集器-标记整理算法，JDK1.7后全新的回收器, 用于取代CMS收集器。

问：三色标记法

答：GO中采用的追踪式的垃圾回收算法，其思想主要是将对象分成三种颜色，即灰黑白，最开始所有对象都是白色，然后把其中全局变量和函数栈里的对象置为灰色。第二步把灰色的对象全部置为黑色，然后把原先灰色对象指向的变量都置为灰色，以此类推。等发现没有对象可以被置为灰色时，所有的白色变量就一定是需要被清理的垃圾了。(思想上类似广度优先遍历。)

问：成绩表SC，其中语文编号为0006 （S，C，score）S学生编号、C课程编号、score分数 找出 语文成绩及格、平均成绩不及格的学生编号？

答：不是很优雅的答案，即直接找语文成绩>60的和平均成绩不及格的学生。

select *
from sc
where score>60 and CId in (select CId
                   from course
                   where Cname='语文')  and SId in (select SId
                                                      from sc
                                                      group by SId
                                                      having sum(score)/count(*) <60)

问：索引失效情况

答：1、如果条件中有or，即使其中有条件带索引也不会使用
2、对于多列索引，不是使用的第一部分，则不会使用索引（最左匹配原则）
3、like查询是以%开头
4、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引
5、如果mysql估计使用全表扫描要比使用索引快,则不使用索引
6、索引不能有空字段。

问：b+树相比于其它查找树的优势

答：1、相较于平衡二叉树，二叉树等，B+树属于平衡多叉树，树的深度更小，查询效率更高。
2、B+树由于底部叶子节点串行连接，因此支持范围搜索，比起B树只支持单次搜索，在进行范围查询的时候优势更大。

问：事务隔离级别

答：未提交读，已提交读，可重复读，可序列化。需要注意在mysql中默认是可重复读状态；在Orancle中，可供选择的等级是已提交读和可序列化。

问：回表

答：回表指的是按照索引找到了索引值，再依据索引值再次查询数据表获得数据行的操作。

参考资料：
字节跳动-电商内推-面经收集
HashMap之1.7和1.8的区别
哪些情况下索引会失效？
深入理解CAS算法原理
7种JVM垃圾收集器特点，优劣势、及使用场景
Go 垃圾回收（三）——三色标记法是什么鬼？
Java并发——Synchronized关键字和锁升级，详细分析偏向锁和轻量级锁的升级