备战春招(5)

in with 0 comment

面经来自牛客
怪兽充电凉经

题目

  1. hashmap结构
  2. 红黑树和二叉树区别
  3. 红黑树如何进行平衡的
  4. 如何以空间换时间对hashmap进行优化
  5. 为什么要多线程
  6. 单核的单线程和多线程哪个效率高?为什么
  7. MySQL的索引模型哈希索引模型和B+树索引模型应用场景
  8. b树和b+树区别
  9. b+树怎么查询一个范围数据
  10. explain通常看哪些信息
  11. 如果有两个索引a和b,语句select......where a=...,b=....,索引怎么走
  12. 日志系统知道哪几个
  13. redo log和binlog区别
  14. 为什么要有redo log和binlog
  15. 事务隔离级别有哪些
  16. 读可提交和可重复读区别
  17. 读不可提交和读了提交区别
  18. springmvc的流程

解答

HashMap结构

HashMap老生常谈的一个问题,这个解析再看一下源码吧。
关于HashMap,有个对象

// 数组,又叫作桶(bucket)
transient Node<K,V>[] table;

这个Node的定义如下

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。
所以,根据这个对象再结合我们的理论知识,就可以推出来HashMap的一个简单的结构实现
如下图
image.png

继续根据理论知识,在JDK1.8中,HashMap桶中大于等于8会转换成红黑树,树的数据结构这里就不介绍了,再看源码关于这棵树的定义

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
}

所以,在JDK1.8的前提下,HashMap的结构还可能是这样的
image.png

红黑树和二叉树区别

红黑树的本质上就是一颗二叉树,更确切的来说,红黑树是一颗平衡二叉树。叫它红黑树的原因是红黑树的每个节点上都有存储位表示节点的颜色,可以是红或黑。
梳理下红黑树的特性吧

红黑树具有以下5种性质:

  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶节点(NIL节点,空节点)是黑色的。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这里要关于它的5中性质要注意两个

  1. 特性3中的叶子节点,是只为空(NIL或null)的节点。
  2. 特性5,确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树

红黑树的时间复杂度为O(log n),与树的高度成正比。

红黑树每次的插入、删除操作都需要做平衡,平衡时有可能会改变根节点的位置,颜色转换,左旋,右旋等。

红黑树如何进行平衡的

红黑树每次的插入、删除操作都需要做平衡,平衡时有可能会改变根节点的位置,颜色转换,左旋,右旋等。
主要就变色和左旋、右旋。
先看下左旋的图解
image.png

图中,身为右孩子的Y取代了X的位置,而X变成了自己的左孩子。此为左旋转。
左旋在TreeMap的源码是这样的

 /** From CLR */
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

再看下右旋的图解和源码
image.png

图中,身为左孩子的Y取代了X的位置,而X变成了自己的右孩子。此为右旋转。
源码是这样的

private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

这些就是红黑树的左旋和右旋右旋
推荐一篇博文,这里讲的更生动
漫画算法:什么是红黑树?
再推荐一个演示红黑树的一个网址
红黑树演示

如何以空间换时间对hashmap进行优化

开始看到这个问题,我是懵逼的。。然后想了一下
首先先明白HashMap的一个缺点,根据第一题,HashMap的结构,是数组+链表或者数组+红黑树的结构。其中,HashMap的数组的以HashCode来决定数组下标的,现在问题就明显了。
假设一个桶(数组)内元素肯定不止是一个,在我们查找某个元素的时候,如果是链表或者红黑树,查找元素肯定会遍历多个元素,最后找到我们需要的值。再根据题目,以空间换时间对HashMap优化。
现在很清楚了,通过空间换取时间,就是因为桶中的元素太多了,导致在查找元素的过程中效率会多次遍历,那我们将元素分散一点不就解决了。
所以可以增加桶的个数,即size扩容一次。
谈到了扩容,问题又来了一个。扩容的代价也很大的。那我们可以根据Load Factor(加载因子)来提前给予足够大空间,防止HashMap扩容。这样也是一种以空间换时间的方式来对HashMap优化。
总结一下,以空间换时间来优化。主要就是两个原因

  1. 在查找元素的过程中,可能会遍历多层链表来查找,这样我们就减少链表中的元素的密度,给HashMap扩容就行。
  2. HashMap主动扩容也是很费时的,那我们就提前给它一个足够大的空间和对Load Factor的设置,来限制住HashMap的主动扩容。

为什么要多线程

这个可以根据《Java并发编程的艺术》来回答。

  1. 更多的处理器核心以及超线程技术的广泛应用。如果该程序使用多线程技术,将计算逻辑分配到多个处理器核心上,就会显著减少程序运行的处理时间,并且随着更多处理器核心加入而变得有效率。
  2. 更快的响应时间。将数据一致性不强的操作派发给其他线程处理,如生成快照、发送邮件等。这样做的好处是响应用户请求的线程能够尽可能快地处理完成,缩短响应时间,提升了用户体验。
  3. 更好的编程模型。Java为多线程编程提供了良好、考究并且一致性的编程模型,使开发人员能够更加专注于问题的解决。

单核的单线程和多线程哪个效率高?为什么

如果在单核的前提下,可能单线程比多线程的效率更高吧。
因为使用多线程就是充分利用多核处理器的优势。但是在单核就不一定了。因为多线程在单cpu中其实也是顺序执行的,只不过系统可以帮你切换那个执行而已,在执行的过程中,还是存在上下文切换的问题。同时,上下文的切换的过程会提高系统开销。但是单线程就是根据程序顺序执行(不谈重排序),不会存在上下文切换等线程切换的开销问题。故而,在单核的情况下,单线程的效率会比多线程的效率高。

MySQL的索引模型哈希索引模型和B+树索引模型应用场景

先回一下哈希索引:
哈希索引是基于哈希表实现的。在MySQL中,只有Memory引擎显式支持哈希索引。在InnoDB有一个特殊的功能叫做“自适应哈希索引”。当InnoDB注意到某些索引值被使用的非常频繁时,它会在内存中基于B-Tree索引之上再创建一个哈希索引。这就让B—Tree也具有哈希索引的一些优点。
应用场景
哈希索引的优点是索引自身只需要存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。所以再存储大量字符串的时候,如URL,这个时候就用哈希索引比较好。如果使用B+Tree就会存储的内容很大。但是使用哈希索引缺点是需要手动维护哈希值。
B+树索引适用于全键值、键值范围或者键值前缀查找。

b树和b+树区别

有两个

b+树怎么查询一个范围数据

如果使用B+树索引查找某个列的范围数据,在使用like的情况下,会使其右边所有列都无法使用索引优化查找。 所以在查询列值的数量有限,那么可以通过使用多个等于条件来代替范围条件。

explain通常看哪些信息

使用explain很简单,就是在sql语句前面加上explain就行。
使用EXPLAIN解析SQL执行计划时,如果有下面几种情况,就需要特别关注下了:

其他状态例如:Using index、Using index condition、Using index for group-by 则都还好,不用紧张。

如果有两个索引a和b,语句select......where a=...,b=....,索引怎么走

这个根据匹配最左前缀,那个索引在前面就走谁,题目中a在前面,那走a。

日志系统知道哪几个

不知道。哈哈

redo log和binlog区别

这个知道
在MySQL的使用中,更新操作也是很频繁的,如果每一次更新操作都根据条件找到对应的记录,然后将记录更新,再写回磁盘,那么IO成本以及查找记录的成本都很高。所以,出现了日志模块,即我们的update更新操作是先写日志,在合适的时间才会去写磁盘,日志更新完毕就将执行结果返回给了客户端。

MySQL中的日志模块主要有redo log(重做日志)和binlog(归档日志)。

为什么要有redo log和binlog

在MySQL的使用中,更新操作也是很频繁的,如果每一次更新操作都根据条件找到对应的记录,然后将记录更新,再写回磁盘,那么IO成本以及查找记录的成本都很高。所以,出现了日志模块,即我们的update更新操作是先写日志,在合适的时间才会去写磁盘,日志更新完毕就将执行结果返回给了客户端。

事务隔离级别有哪些

读可提交和可重复读区别

看上面

读不可提交和读了提交区别

看上面的上面

springmvc的流程

这个问题多看多记吧。。不过看源码是最好的

  1. 用户向服务端发送一次请求,这个请求会先到前端控制器DispatcherServlet(也叫中央控制器)。
  2. DispatcherServlet接收到请求后会调用HandlerMapping处理器映射器。由此得知,该请求该由哪个Controller来处理(并未调用Controller,只是得知)
  3. DispatcherServlet调用HandlerAdapter处理器适配器,告诉处理器适配器应该要去执行哪个Controller
  4. HandlerAdapter处理器适配器去执行Controller并得到ModelAndView(数据和视图),并层层返回给DispatcherServlet
  5. DispatcherServlet将ModelAndView交给ViewReslover视图解析器解析,然后返回真正的视图。
  6. DispatcherServlet将模型数据填充到视图中
  7. DispatcherServlet将结果响应给用户

总结

这个面经是怪兽充电的面经,就是那个租充电宝的,哈哈。问题还是挺致命的。一些Java基础我倒是没啥问题,主要是MySQL方面的,还是有点弱。不过还在找到了这篇面经,学到了很多MySQL的一些知识。比如哈希索引,然后还进一步的学到关于索引匹配和索引失效的例子。
如果在写这篇博客前,遇到这些问题,我应该很多问题回答不到点上,虽然都知道,但是具体的回答,还是有些问题的,给自己打5分吧。难受。但是下次在遇到MySQL这些问题应该可以回答的稍微好许多。