备战春招(6)

in with 0 comment

面经来自牛客
有赞还愿面经,java开发工程师

题目

  1. 讲一下集合(ArrayList、LinkedList,区别)
  2. 讲一下Map(HashMap、ConcurrentHashMap、HasHTable,区别,为什么安全,为什么不安全)
  3. JDK1.8有什么改进?在HashMap上的改进是什么?(链表长度超过8,转换成红黑树)
  4. 讲一下红黑树
  5. MySQL熟悉吗?讲一下事务的隔离等级
  6. MySQL默认的隔离等级是什么?在这个隔离等级下怎样解决幻读?
  7. 索引熟悉吗?说一下索引的作用。
  8. 讲一下索引的底层实现(从二叉树到B树到B+树)
  9. 一个表,如果把有a,b,c三种字段设置成索引,怎样索引不会失效?只有a呢,或者只有b呢?(最左匹配原则)
  10. redis了解吗?讲一下RDB、AOF,讲一下缓存雪崩、缓存击穿、缓存穿透、怎么避免?
  11. 讲一下其中基本的排序算法(插入,选择,冒泡,希尔,快排,归并,堆)
  12. 如果有10亿个数字,找出前1万个最大的数字(bitmap,堆)
  13. 说一下怎样优化你的数据库,多个方面
  14. 熟悉JVM吗,讲一下内存模型
  15. 具体讲一下JAVA堆
  16. JVM调优
  17. 了解JVM的同时应该了解GC吧,讲一下GC
  18. 说一下锁的膨胀

解答

讲一下集合(ArrayList、LinkedList,区别)

这个答案都知道,不妨再看一遍源码

ArrayList

先看它的定义

// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组,如果传入的容量为0时使用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组,传传入容量时使用,添加第一个元素的时候会重新初始为默认容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储元素的数组
 transient Object[] elementData; // non-private to simplify nested class access
// 集合中元素的个数
private int size;

它正如它的名字一样,是通过Array(数组)实现的。
同时它有两个构造方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 如果传入的初始容量大于0,就新建一个数组存储元素
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果传入的初始容量等于0,使用空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 如果传入的初始容量小于0,抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}


public ArrayList() {
    // 如果没有传入初始容量,则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

它的有参构造是定义一个自定义长度的数组;无参是定义一个默认长度为10的数组。
根据理论知识,ArrayList的扩容是通过数组的复制实现的。源码如下

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小,则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量已经超过最大容量了,则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 以新容量拷贝出来一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容大小为就容量的1.5倍,最好copy出一个新的数组。但是它remove元素的时候,是不会缩容的,这个注意下。
所以关于ArrayList总结如下:

  1. ArrayList内部使用数组存储元素,当数组长度不够时进行扩容,每次加一半的空间,ArrayList不会进行缩容;
  2. 正是因为ArrayList是通过数组实现的,所以ArrayList查找元素快,但是增删元素慢,但是也是数组的特性,也让ArrayList在尾部增删元素极快,因为不需要搬移元素。
  3. ArrayList还可以求交集和并集,方法分别是addAll(Collection<? extends E> c)和retainAll(Collection<? extends E> c)

LinkedList

继续,先看它的定义

// 元素个数
transient int size = 0;
// 链表首节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

一个典型的双向链表,所以LinkedList是通过双向链表实现的。
再看它的构造方法

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList的增加元素方法有三种,直接用图演示就如下,分别是头部插入,尾部插入和中间插入。
image.png

同样的,LinkedList的删除元素方法也有三种,直接用图演示就如下,分别是删除头部,删除尾部和删除中间。
image.png

也就是因为LinkedList是通过双向链表实现的,所以它也可以有队列和栈的特性。
队列的特性是FIFO,所以它可以永远是在双向链表的尾部添加元素,在头部删除元素。
栈的特性是LIFO,所以它可以永远是在双向链表的尾部添加元素,在尾部删除删除元素。
总结就是如下:

  1. LinkedList是一个以双向链表实现的List;
  2. LinkedList在查找元素的效率很慢,在增删元素的效率很高,但是在查找头部和尾部的效率高,在增删中间的的元素效率低。
  3. LinkedList因为是以双向链表实现的,所以它还可以作为队列和栈来使用。

ArrayList和LinkedList的区别

  1. 一个是通过数组实现的,一个是通过双向链表实现的。
  2. ArrayList因为它数组实现,所以在查找元素的效率高。
  3. LinkedList因为它是双向链表的实现的,所以他在增删元素的效率高。

讲一下Map(HashMap、ConcurrentHashMap、HasHTable,区别,为什么安全,为什么不安全)

三个Map介绍

HashMap采用key/value存储结构,每个key对应唯一的value,查询和修改的速度都很快,能达到O(1)的平均时间复杂度。它是非线程安全的,且不保证元素存储的顺序;

Hashtable和HashMap,从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的,另外它不允许key和value为null。Hashtable是个过时的集合类,不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换;

ConcurrentHashMap是HashMap的线程安全版本,内部也是使用(数组 + 链表 + 红黑树)的结构来存储元素。相比于同样线程安全的HashTable来说,效率等各方面都有极大地提高,同样的,ConcurrentHashMap也不允许key和value为null。

三个Map线程安全问题

HashMap的线程不安全表现在并发增删的条件下,会导致元素的不一致,还有就是在jdk1.8之前的时候,在并发条件,HashMap扩容会导致在迁移元素的过程中造成链表的互相指向,导致读取元素时造成死循环。

HashTable的线程安全的主要实现是它的内部将几个主要的方法通过Synchronized关键字修饰的,将整个Hash表锁住了,所以在并发增删的条件下是安全的。

ConcurrentHashMap的线程安全的实现主要是使用了分段锁来实现的,它像是HashTable一样锁住整个Hash表,而是通过将Hash表分段的形式,以多个锁来分段的在并发条件下对操作对hash桶锁住,分段锁是来自ReentrantLock。

 static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }

一个ConcurrentHashMap包含一个Segment数组。Segment的结构于HashMap类似,是一种数组加链表的结构。一个Segment包含一个hashEntry数组。每个Segment守护着一个HashEntry数组里的元素,每当对HashEntry进行修改时,必须先获得它对应的Segment锁。

JDK1.8有什么改进?在HashMap上的改进是什么?(链表长度超过8,转换成红黑树)

JDK1.8对HashMap的改动,我知道的主要有两个

  1. 在结构上加入了红黑树,当桶的链表长度大于等于8时,进行树化,将链表转化为红黑树,当桶中元素个数小于6时,反树化,将红黑树转换为链表。
  2. 在并发安全上,HashMap修复了在并发扩容的过程中造成的链表的互相指向导致遍历死循环,它的实现是将之前的元素一个一个移位转换为整个桶内元素一起移位。

讲一下红黑树

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

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

红黑树是一种平衡二叉树,它在增删元素都会进行变色、左旋或右旋的操作来保证二叉树填满。

MySQL熟悉吗?讲一下事务的隔离等级

MySQL在隔离级别定义了四种

  1. 未提交读
    在该级别,事务中的修改即没有提交,对其他事务也都是可见的。所以事务可以读取未提交的数据,会导致脏读。实际应用一般很少使用。
  2. 不可重复读
    指的是一个事务从开始直到提交之前,所做的任何修改对其他事务都是不可见的。两次执行同样的查询,可能会得到不一样的结果。
  3. 可重复读
    该级别保证了同一个事务中多次读取同样记录的结果是一致的。但是可重复读无法解决幻读问题。可重复读是MySQL的默认事务隔离级别
  4. 可串行化(序列化)
    它是最高隔离级别。它通过强制事务串行执行,避免了幻读问题。简单的说,就是在读取的每一行数据上都加锁。但是可能导致大量的超时和锁争用问题。

MySQL默认的隔离等级是什么?在这个隔离等级下怎样解决幻读?

MySQL默认隔离级别是可重复读。
关于幻读,它是指当某个事务在读取某个范围内的记录时,另外一个事务又在该范围内插入了新的记录,当之前的事务再次读取该范围的记录时,会产生幻行。即读取的记录数量前后不一致。
在可重复读解决幻读可以通过MVCC(多版本并发控制)来解决幻读问题。

MVCC

MVCC是行级锁的一个变种,它在很多情况下避免了加锁操作,因此开销更低。
MVCC的实现是通过保存数据在某个时间点的快照来实现。也就是说,不管执行多长时间,每个事务看到的数据都是一致的。简单点说就是根据事务开始的时间不同,每个事务对同一张表,同一时刻看到的数据可能是不一样的。
不同的存储引擎的MVCC实现是不同的,典型的有乐观并发控制和悲观并发控制。在InnoDB的MVCC是通过每行记录后面保存两个隐藏的列来实现的。一个是保存了行的创建时间,一个是保存行的过期时间。两个隐藏列保存的都是系统版本号。每开始一个新的事务,系统版本号都会自动递增。事务开始时刻的系统版本号都会作为事务的版本号,用来和查询到的每行记录的版本号进行比较。
推荐一个视频,下面介绍的关于MVCC
MySQL的MVCC底层原理讲解视频

索引熟悉吗?说一下索引的作用。

索引有一下几种:

  1. FULLTEXT
    全文索引,目前只有MyISAM引擎支持。
  2. HASH
    由于HASH的唯一(几乎100%的唯一)及类似键值对的形式,很适合作为索引.HASH索引可以一次定位,一般可以存储较长的字符串,如URL地址,这样可以将URL字符串构建成一个Hash值,总结通过Hash值来查找
  3. B-Tree
    也就是我们常说的索引,一般实现它的是B+树。
  4. R—Tree
    空间索引,在MySQL很少使用,它可以存储一些地点的经纬度。

索引的作用是便于查找数据。比如我们在看书的时候,如果想查找某一章的内容,那就翻开目录,查找对应的页码,我们的目录就是索引。

讲一下索引的底层实现(从二叉树到B树到B+树)

根据博主的提示,就讲下B—Tree的实现吧。
先谈二叉树,它是一种树形数据结构,正如它的名字一样,每个分支都是两个。
其中有个实现,平衡二叉树,它的特点就是左子树的值永远比根节点小,右子树永远比根节点大。
于是它又有了一个变种,B树,它和平衡二叉树的特点一样,但不同但是B树是一颗多叉树又名平衡多路查找树。它的分支不止是两个,使得树的高度变得更低。但它的存储的值全在节点上,导致查找效率不是那么高。所以,它的升级版,B+树来了。
B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。它存储值的位置和B树不同的是,它的存储的位置全在叶子节点,所以使得B+树的查找效率更高,层级也更矮。
分享一篇博文
平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

一个表,如果把有a,b,c三种字段设置成索引,怎样索引不会失效?只有a呢,或者只有b呢?

即最左匹配原则

  1. 最左前缀匹配原则,非常重要的原则,mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配,比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则都可以用到,a,b,d的顺序可以任意调整。
  2. =和in可以乱序,比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序,mysql的查询优化器会帮你优化成索引可以识别的形式

redis了解吗?讲一下RDB、AOF,讲一下缓存雪崩、缓存击穿、缓存穿透、怎么避免?

Redis一般是作为缓存使用,它的读写效率比MySQL快很多

RDB

默认的持久化方式,将内存中的数据写入到二进制文件中,默认的文件名就是dump.rdb,可以通过配置设置(即修改配置文件)自动做持久化的方式。

AOF

开启AOF后会生成一个appendonly.aof文件,文件里面记录着你每次增删改操作的命令。当redis挂掉后可以执行文件来恢复数据。

RDB和AOF比较

  1. RDB存储的是数据,而AOF存储的是增删改操作的命令
  2. 因为两个存储的类型不一样,所以RDB恢复的比较快,但是数据容易丢失,AOF恢复时间长,但是数据一致性高
  3. AOF文件比RDB文件大得多

缓存雪崩

缓存雪崩,是指在某一个时间段,缓存集中过期失效。导致所有的查询压力转移到了数据库上。
解决方法是缓存过期时间分散设置,减少大量查询数据的全部转移到数据库。

缓存击穿

缓存击穿是值一个Key在并发条件下,被大量访问,在这个Key失效的一瞬间。。。同样的,大量查询压力又一次转移到了数据库上。。
被大量访问的数据设置永不过期。

缓存穿透

在我们使用缓存时,一般都是先查找缓存,再去查询数据库,如果数据库有这条数据库,咱们再把这条数据放入缓存中,这样在下一次访问的时候,先查找缓存时候找到了,就不会再去查询数据库了。
但是有一种情况,就是缓存穿透。假设,我们的数据库中,压根没有一条数据,这条数据我们命名为A,那么,有部分坏胚子,他们故意查找这条A数据,我们的代码就一直先找缓存,在找数据库,在找缓存,在找数据库...这样在查询这条数据的压力又到了数据库上。
解决办法是如果数据库没有这条数据,那咱们就在缓存中加入一条有过期时间的数据,比如30S,60S,让数据库的压力减少。

讲一下其中基本的排序算法

直接看这篇文章吧。
备战春招(1)

如果有10亿个数字,找出前1万个最大的数字

这类TOP k的问题说下三个比较好理解的方法。
面对大量数据,如果使用排序算法的话,那效率可想而知。。死翘翘,所以这里要使用分治的思想解决。

  1. 分治
    将10亿个数据分成1000份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。

另外可以使用最小堆来解决
2. 最小堆
首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至10亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。

假设还有一种理想的情况,就是10亿数中,假如我们提前知道有大量重复的数字,那我们先去重,先筛选掉大量数据。这样就可以使用Hash表了
3. 先通过Hash法,把这10亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

说一下怎样优化你的数据库,多个方面

直接看这张图吧,根据图片,应该可以想到优化方法
image.png

熟悉JVM吗,讲一下内存模型

Java编程的特点就是一次编译,多处运行,它能够在不同的操作系统中多处运行离不开JVM的支持。先看一张图
image.png
先介绍它的线程隔离区域

程序计数器

它是一块较小的内存空间,是线程所执行的字节码的行号指示器。字节码解释器就是通过改变这个计数器的值来选取下一条需要执行的字节码指令。

虚拟机栈

在Java每个方法在执行的同时,会在虚拟机栈中创建一个栈帧。栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等。每一个方法从调用直到执行完成的过程,就对应着一个栈帧在虚拟机栈中入栈到出栈的过程,它也同它的名字一直,满足栈的特性。

本地方法栈

本地方法栈和虚拟机栈发挥的作用类似。但是本地方法栈使用的Java方法均为Native方法。

还有线程共享的区域

Java堆

堆是Java虚拟机所管理的内存中最大的一块。此区域的唯一目的就是存放对象实例,几乎所有的对象的实例都在这里分配内存。
堆也是GC管理的主要区域,所以堆还可以细分新生代和老年代。

方法区

它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。它被称为“永久代”。

具体讲一下JAVA堆

如上,如果要补充就是关于它的GC了

JVM调优

JVM调优主要是针对堆来调优的,因为每次GC都会造成Stop The World ,所以在调优方面可以针对堆中的新生代和老年代的大小设置来减少GC的次数。

了解JVM的同时应该了解GC吧,讲一下GC

关于GC主要要考虑三件事情。

  1. 哪些内存需要回收
  2. 什么时候回收
  3. 如何回收

哪些内存需要回收

先看下JVM内存模型。我们在线程隔离区域(程序计数器,虚拟机栈,本地方法栈)随着线程而生,随着线程而灭的。所以在这个区域是不需要GC的。所以,GC的主要区域是Java堆和方法区,这里的内存分配和回收都是动态的。

什么时候回收

这里就需要判断哪些对象是已经无用了。有两个方法判断。

  1. 引用计数法
    引用计数法就是判断对象在某个地方是否被引用过。如果引用了,计数器就+1,引用失效,计数器就-1。在大部分情况下,这种方法都是很高效的。但是Java虚拟机并没有使用这种方法判断对象是否无用,因为有些对象和对象之间存在互相引用。这种方法并不能有效的判断对象是否能够被回收。
  2. 可达性分析算法
    可达性分析算法即通过引用链的关系判断对象是否可以回收。这个算法的基本思想是通过一系列的称为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链相连时,则证明此对象是不可用的。
    可达性分析算法最重要的就是GC Roots对象。所以关于GC Roots的对象包括以下几种:

其实关于这些被作为GC Roots对象不难记,能作为GC Roots对象的,那肯定是最后被回收的或者存活时间最长的对象。

如何回收

主要有几个清除算法

  1. 标记-清除算法,先标记,在清除,但是效率不高,同时清理后会产生大量不连续内存。
  2. 复制算法,将内存按容量划分为大小相等的两块,每次只使用其中的一块。当这一块内存用完了,将还存活的对象复制到另外一块上面,如何把以使用的内存空间一次清理掉。虽然效率提升了,但是这样做的的代价是将内存缩小为了原来了一半。。。
  3. 标记-整理算法,它的过程和标记-清除算法一样,但是后续步骤不是直接对可回收对象进行清理,而是让所有存活的对象都向一端移动,如何直接清理掉端边界以外的内存。但是效率比标记-清除算法低。
  4. 分代收集算法,目前JVM采用的就是分代收集算法,他根据其他清除算法和Java虚拟机中的堆内存分代采用灵活的算法。其中新生代使用复制算法,因为新生代的对象都是朝生夕灭,只有少量对象是存活的。老年代使用标记-清除或者标记-整理算法。因为老年代对象存活率高。

说一下锁的膨胀

Java中,锁一共有四个状态,级别从低到高依次是:无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态。
锁的状态会随着线程竞争情况逐渐升级。当竞争线程尝试占用轻量级锁失败多次之后,轻量级锁就会膨胀为重量级锁,重量级线程指针指向竞争线程,竞争线程也会阻塞,等待轻量级线程释放锁后唤醒他。因为轻量级锁是通过CAS操作来加锁和释放锁的,如果失败,会使用CAS自旋导致锁膨胀。
image.png

总结

这是有赞的一篇面经,问的主要是关于MySQL数据库方面和JVM,还有一些关于JAVA集合,也有一些关于缓存Redis。
这篇面经再一次扎实的基础,同时也学到了很多,比如TOP k问题,数据库优化从哪些方面去考虑。这已经是第6篇备战春招的博客了,发现确实有很多关于MySQL的问题,经过这几篇面经的学习,在MySQL方面不仅扎实了一些简单的基础,也了解到了一些更深层次的知识 。