【面经】米哈游数据开发一面面经

链接：https://www.nowcoder.com/discuss/1016179?type=all&order=recall&pos=&page=1&ncTraceId=&channel=-1&source_id=search_all_nctrack&gio_id=7ECACE7605534464872AA4CD0FF6C741-1660799353433

米哈游的考的问题感觉比较全面，多拿几个来练手。欢迎点击此处关注公众号。

一、java

1.String、StringBuffer、StringBuilder 的区别；String 为什么是不可变的字符序列？String 类是 final 的吗？

String 是具有不可变性的，由此我们就引出了可变性的 StringBuffer 类和 StringBuilder 类。

String 设计成不可变的原因有三：

方便实现字符串对象池，如果String可变，那么对象池就需要考虑写时拷贝的问题。
不可变对象是线程安全的。
不可变对象更方便缓存 hashcode，作为 key 时可以更高效率地保存到 HashMap 中。

String 的源码：

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];

    /** Cache the hash code for the string */
    private int hash; // Default to 0

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = -6849794470754667710L;

    /**
     * Class String is special cased within the Serialization Stream Protocol.
     *
     * A String instance is written into an ObjectOutputStream according to
     * <a href="{@docRoot}/../platform/serialization/spec/output.html">
     * Object Serialization Specification, Section 6.2, "Stream Elements"</a>
     */
    private static final ObjectStreamField[] serialPersistentFields =
        new ObjectStreamField[0];

可以看到 String 底层用 final 修饰的 char 数组存储，所以不可变。

并且 String 类也由 final 修饰。

2.java 创建一个新对象的过程是什么样的？

https://blog.csdn.net/justloveyou_/article/details/72466416

创建对象有很多种方式：

new 关键字：最常见的也是最简单的创建对象的方式，通过这种方式我们可以调用任意的构造函数（无参的和有参的）去创建对象。
Class 类的 newInstance 方法：通过 Java 的反射机制使用 Class 类的 newInstance 方法来创建对象。这个 newInstance 方法调用无参的构造器创建对象。
Constructor类的 newInstance 方法：通过 Java 的反射机制使用 Constructor 类的 newInstance 方法来创建对象，可以通过这个 newInstance 方法调用有参数的和私有的构造函数。
Object 类的 clone 方法：通过实现 Cloneable 接口，重写 Object 类的 clone 方法来创建对象（浅拷贝）。

以 new 关键字方式创建对象为例，创建对象步骤如下：

检查类是否已经被加载：new 关键字时创建对象时，首先会去运行时常量池中查找该引用所指向的类有没有被虚拟机加载，如果没有被加载，那么会进行类的加载过程。类的加载过程需要经历：加载、链接、初始化三个阶段。
为对象分配内存空间：
1. 第一种是 jvm 将堆区抽象为两块区域，一块是已经被其他对象占用的区域，另一块是空白区域，中间通过一个指针进行标注，这时只需要将指针向空白区域移动相应大小空间，就完成了内存的分配，当然这种划分的方式要求虚拟机的对内存是地址连续的，且虚拟机带有内存压缩机制，可以在内存分配完成时压缩内存，形成连续地址空间，这种分配内存方式称为“指针碰撞”，但是很明显，这种方式也存在一个比较严重的问题，那就是多线程创建对象时，会导致指针划分不一致的问题，例如 A 线程刚刚将指针移动到新位置，但是 B 线程之前读取到的是指针之前的位置，这样划分内存时就出现不一致的问题，解决这种问题，虚拟机采用了循环 CAS 操作来保证内存的正确划分。
2. 第二种也是为了解决第一种分配方式的不足而创建的方式，多线程分配内存时，虚拟机为每个线程分配了不同的空间，这样每个线程在分配内存时只是在自己的空间中操作，从而避免了上述问题，不需要同步。当然，当线程自己的空间用完了才需要需申请空间，这时候需要进行同步锁定。为每个线程分配的空间称为“本地线程分配缓冲（TLAB）”,是否启用 TLAB 需要通过 -XX:+/-UseTLAB 参数来设定。
为对象的字段赋默认值：分配完内存后，需要对对象的字段进行零值初始化（赋默认值），对象头除外。零值初始化意思就是对对象的字段赋 0 值，或者 null 值，这也就解释了为什么这些字段在不需要进程初始化时候就能直接使用。
设置对象头：对这个将要创建出来的对象，进行信息标记，包括是否为新生代/老年代，对象的哈希码，元数据信息，这些标记存放在对象头信息中。
执行实例的初始化方法 init：init 方法包含成员变量、构造代码块的初始化，按照声明的顺序执行。
执行构造方法。执行对象的构造方法。至此，对象创建成功。

上述为无父类的对象创建过程。对于有父类的对象创建过程，还需满足如下条件：

先加载父类；再加载本类；
先执行父类的实例的初始化方法 init（成员变量、构造代码块），父类的构造方法；执行本类的实例的初始化方法 init（成员变量、构造代码块），本类的构造方法。

例如：

public class ClassA {

    private static int y = 1;
    private static String s = "1";

    static {
        y=2;
    }

    private static int x = 1;
    
    static {
        s="2";
    }
    
    static {
        x=2;
    }

    public ClassA() {
        x = x+1;
        y = y+1;
        s = "3";
    }

    public static void main(String[] args) {
        ClassA classA = new ClassA();
    }
}

3.java 的垃圾回收机制

https://blog.csdn.net/justloveyou_/article/details/71216049

如何确定一个对象可以被回收：

引用计数算法：引用计数算法是通过判断对象的引用数量来决定对象是否可以被回收。
可达性分析算法：可达性分析算法是通过判断对象的引用链是否可达来决定对象是否可以被回收。

垃圾收集算法：

标记-清除算法：

分为标记和清除两个阶段。该算法首先从根集合进行扫描，对存活的对象对象标记，标记完毕后，再扫描整个空间中未被标记的对象并进行回收。
不足：
- 效率问题：标记和清除两个过程的效率都不高；
- 空间问题：标记-清除算法不需要进行对象的移动，并且仅对不存活的对象进行处理，因此标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

复制算法：

复制算法将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这种算法适用于对象存活率低的场景，比如新生代。
不足：
- 效率问题：复制收集算法在对象存活率较高时就要进行较多的复制操作，效率将会变低。
- 空间问题：如果不想浪费 50% 的空间，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都 100% 存活的极端情况。

标记整理算法：

类似标记清除算法，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存，类似于磁盘整理的过程，该垃圾回收算法适用于对象存活率高的场景（老年代）。
标记整理算法与标记清除算法最显著的区别是：标记清除算法不进行对象的移动，并且仅对不存活的对象进行处理；而标记整理算法会将所有的存活对象移动到一端，并对不存活对象进行处理，因此其不会产生内存碎片。

分代收集算法：

分代收集算法是基于这样一个事实：不同的对象的生命周期(存活情况)是不一样的，而不同生命周期的对象位于堆中不同的区域，因此对堆内存不同区域采用不同的策略进行回收可以提高 JVM 的执行效率。
新生代的目标就是尽可能快速的收集掉那些生命周期短的对象，一般情况下，所有新生成的对象首先都是放在新生代的。
老年代存放的都是一些生命周期较长的对象，在新生代中经历了 N 次垃圾回收后仍然存活的对象就会被放到老年代中。
永久代主要用于存放静态文件，如 Java 类、方法等。

垃圾收集器：

Serial 收集器（复制算法): 新生代单线程收集器，标记和清理都是单线程，优点是简单高效；
Serial Old 收集器 (标记-整理算法): 老年代单线程收集器，Serial 收集器的老年代版本；
ParNew 收集器 (复制算法): 新生代收并行集器，实际上是 Serial 收集器的多线程版本，在多核 CPU 环境下有着比 Serial 更好的表现；
Parallel Scavenge 收集器 (复制算法): 新生代并行收集器，追求高吞吐量，高效利用 CPU。吞吐量 = 用户线程时间/(用户线程时间 + GC 线程时间)，高吞吐量可以高效率的利用 CPU 时间，尽快完成程序的运算任务，适合后台应用等对交互相应要求不高的场景；
Parallel Old 收集器 (标记-整理算法)：老年代并行收集器，吞吐量优先，Parallel Scavenge 收集器的老年代版本；
CMS(Concurrent Mark Sweep) 收集器（标记-清除算法）：老年代并行收集器，以获取最短回收停顿时间为目标的收集器，具有高并发、低停顿的特点，追求最短 GC 回收停顿时间。
G1(Garbage First) 收集器 (标记-整理算法)： Java 堆并行收集器，G1 收集器是 JDK1.7 提供的一个新收集器，G1 收集器基于“标记-整理”算法实现，也就是说不会产生内存碎片。此外，G1 收集器不同于之前的收集器的一个重要特点是：G1 回收的范围是整个 Java 堆(包括新生代，老年代)，而前六种收集器回收的范围仅限于新生代或老年代。

4.java 的内存机制，方法区主要存的是什么？

JDK 1.6 运行时数据区域如下图：

在这里插入图片描述

程序计数器：记录正在执行的虚拟机字节码指令的地址（如果正在执行的是本地方法则为空）。

Java 虚拟机栈：每个 Java 方法在执行的同时会创建一个栈帧，用于存储局部变量表、操作数栈、常量池引用等信息。

本地方法栈：与 Java 虚拟机栈类似，区别是本地方法栈为本地方法服务。本地方法一般是用其它语言（C、C++ 或汇编语言等）编写的。

堆：所有对象都在这里分配内存，是垃圾收集的主要区域（“GC 堆”）。

方法区：用于存放已被加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。从 JDK 1.8 开始，移除永久代，并把方法区移至元空间，它位于本地内存中，而不是虚拟机内存中。

运行时常量池：方法区的一部分。Class 文件中的常量池（编译器生成的字面量和符号引用）会在类加载后被放入这个区域。

直接内存：在 JDK 1.4 中新引入了 NIO 类，它可以使用 Native 函数库直接分配堆外内存，然后通过 Java 堆里的 DirectByteBuffer 对象作为这块内存的引用进行操作。这样能在一些场景中显著提高性能，因为避免了在堆内存和堆外内存来回拷贝数据。

5.hashmap 的底层原理？使用链表的时候是头插还是尾插，为什么换为尾插了？什么时候需要重写 hashcode 和 equals

在 JDK7 : HashMap 是由数组，链表组成的。
在 JDK8: HashMap 是由数组，链表，红黑树组成的。

当链表的长度特别长的时候，查询效率将直线下降，查询的时间复杂度为 O(n)。因此，JDK1.8 把它设计为达到一个特定的阈值之后，就将链表转化为红黑树。

JDK1.7 的 HashMap 链表会有死循环的可能，因为 JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.8 做了改进，用的是尾插法，不会产生死循环。

自定义类，需要判断对象在业务逻辑上是否相等，需要重写 hashCode 和 equals。

二、计算机底层原理

1.Linux 中用户态和内核态的区别，为什么这样划分

用户空间：指的就是用户可以操作和访问的空间，这个空间通常存放我们用户自己写的数据等。

内核空间：是系统内核来操作的一块空间，这块空间里面存放系统内核的函数、接口等。

在用户空间下执行，我们把此时运行得程序的这种状态成为用户态，而当这段程序执行在内核的空间执行时，这种状态称为内核态。

本质意义是进行权限保护。限定用户的程序不能随意更改操作系统，如果人人都可以任意读写任意地址空间软件管理便会乱套。内核态可以执行一切特权代码，用户态只能执行那些受限权限的代码。

2.TCP 和 UDP 的区别，UDP 如何能做到可靠传输。

TCP 是一种面向有连接的传输层协议，能够对自己提供的连接实施控制。适用于要求可靠传输的应用，例如文件传输。面向字节流，传输慢。

UDP 是一种面向无连接的传输层协议，不会对自己提供的连接实施控制。适用于实时应用，例如：IP 电话、视频会议、直播等。以报文的方式传输，效率高。

如果我们要用 UDP 去实现可靠的传输，则需要解决两个问题：丢包和后发先至（包的顺序）。解决方法：
1）给数据包编号，按照包的顺序接收并存储；
2）接收端接收到数据包后发送确认信息给发送端，发送端接收确认数据以后再继续发送下一个包，如果接收端收到的数据包的编号不是期望的编号，则要求发送端重新发送。

3.yield 命令是什么

系统调用。

4.计算机的锁是什么

锁是在执行多线程时用于强行限制资源访问的同步机制，即用于在并发控制中保证对互斥要求的满足。

三、数据库

1.有哪些索引？

普通索引。

唯一索引：与普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值（注意和主键不同）。

主键索引：是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。

全文索引：它能够利用分词技术等多种算法智能分析出文本文字中关键词的频率和重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。

组合索引：指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用组合索引时遵循最左前缀集合。

2.联合索引中最左匹配？

最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。例如建立 (a, b) 的联合索引，那么所应树如下：

在这里插入图片描述

可以看到a的值是有顺序的，1，1，2，2，3，3，而b的值是没有顺序的1，2，1，4，1，2。所以 b = 2 这种查询条件没有办法利用索引，因为联合索引首先是按 a 排序的，b 是无序的。

同时我们还可以发现在 a 值相等的情况下，b 值又是按顺序排列的，但是这种顺序是相对的。所以最左匹配原则遇上范围查询就会停止，剩下的字段都无法使用索引。例如 a = 1 and b = 2，a, b 字段都可以使用索引，因为在a值确定的情况下b是相对有序的，而 a>1 and b=2，a 字段可以匹配上索引，但 b 值不可以，因为 a 的值是一个范围，在这个范围中 b 是无序的。

3.select a,b,c,d from table where a = 1 and b = 2 order by c desc 建什么索引，如果 b>2 呢？

https://blog.csdn.net/sinat_41917109/article/details/88944290

https://blog.csdn.net/oHeiZhiShi123/article/details/104840183

注意：order by 子句后面的顺序也按照索引列的顺序给出则不用排序。

例如：索引(a,b,c)

select * from table where a=1 and b=2 order by a;  索引排序
select * from table where a=1 and b=2 order by b;  索引排序
select * from table where a=1 and b=2 order by c;  索引排序
select * from table where a=1 order by a;  索引排序
select * from table where a=1 order by b;  索引排序
select * from table where a=1 order by c;  Using filesort

select * from table where a>1 order by a;  索引排序
select * from table where a>1 order by b;  Using filesort
select * from table where a>1 and b=2 order by a;  索引排序
select * from table where a>1 and b=2 order by b;  索引排序
select * from table where a>1 and b=2 order by c;  Using filesort
select * from table where a>1 and b=2 and c=3 order by c;  索引排序
select * from table where a>1 and b>2 order by b;  Using filesort
select * from table where a>1 and b>2 and c= 3 order by c;  索引排序
select * from table where a=1 and b>2 order by b;  索引排序
select * from table where a=1 and b>2 order by c;  Using filesort
select * from table where a=1 and b>2 and c=3 order by c;  索引排序
select * from table where a=1 and b>2 and c>3 order by c;  Using filesort

关于 desc：

mysql 文档中对于索引定义中，ASC 和 DESC 的描述

MySQL < 8.0A key_part specification can end with ASC or DESC. These keywords are permitted for future extensions for specifying ascending or descending index value storage.

Currently, they are parsed but ignored; index values are always stored in ascending order.

MySQL >= 8.0A key_part specification can end with ASC or DESC to specify whether index values are stored in ascending or descending order. The default is ascending if no order specifier is given. ASC and DESC are not permitted for HASH indexes. As of MySQL 8.0.12, ASC and DESC are not permitted for SPATIAL indexes.

所以，在 8.0 之前的版本中, DESC 是无效的，索引 (a ASC, b DESC, c DESC) 等于 (a ASC, b ASC, c ASC)，故而无法使用整个联合索引进行排序。

结论：

如果是 8.0 之后：

a = 1 and b = 2 order by c desc 建立 (a, b, c desc) 索引；
a = 1 and b > 2 order by c desc 建立 (a, b) 索引。

如果是 8.0 之前：

a = 1 and b = 2 order by c desc 建立 (a, b) 索引；
a = 1 and b > 2 order by c desc 建立 (a, b) 索引。

四、数据结构

1.一组数，2个数有1个，其余数有2个，请找出这两个数（时间复杂度为o(n)，空间为o(1)）

力扣 260 只出现一次的数字

https://leetcode.cn/problems/single-number-iii/

// 输入：nums = [1,2,1,3,2,5]
// 输出：[3,5]
// 解释：[5, 3] 也是有效的答案。

class Solution {
    public int[] singleNumber(int[] nums) {
        int eor = 0;
        // 对所有的数进行一次异或操作
        // 易知这个结果就等于 num1 和 num2 的异或结果
        // (相同的数异或结果都为 0, 0 和任意数异或结果都为那个数)
        for (int num : nums) {
            eor ^= num;
        }

        // 那么我可以考虑异或结果的某个非 0 位如最后一个非 0 位
        // 因为我们知道只有当 num1、num2 在该位不一样的时候才会出现异或结果为 1
        // 所以我们以该位是否为 1 对数组进行划分
        // 只要该位为 1 就和 num1 异或
        // 只要该位为 0 就和 num2 异或
        // 这样最终得到就是只出现过一次的两个数
        // (其他在该位为 1 或 0 的数必然出现 0/2 次对异或结果无影响)
        int rightOne = eor & (~eor + 1);    // 寻找最右边的 0
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & rightOne) != 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}