shopee提前批面经及答案

JVM字节码文件对象的结构

对象在堆内存的存储布局可分为对象头、实例数据和对齐填充。

对象头主要包含两部分数据：MarkWord、类型指针。MarkWord 用于存储哈希码（HashCode）、GC分代年龄、锁状态标志位、线程持有的锁、偏向线程ID等信息。类型指针即对象指向他的类元数据指针，如果对象是一个 Java 数组，会有一块用于记录数组长度的数据，

实例数据存储代码中所定义的各种类型的字段信息。

对齐填充起占位作用。HotSpot 虚拟机要求对象的起始地址必须是8的整数倍，因此需要对齐填充。

JVM运行期内存空间，每块的作用

线程私有的运行时数据区: 程序计数器、Java 虚拟机栈、本地方法栈。

线程共享的运行时数据区:Java 堆、方法区。

对象一定在堆中吗

类(静态)变量也存储在方法区中。

字符串常量池

运行时常量池存放常量池表，用于存放编译器生成的各种字面量与符号引用。一般除了保存 Class 文件中描述的符号引用外，还会把符号引用翻译的直接引用也存储在运行时常量池。除此之外，也会存放字符串基本类型。

JDK8之前，放在方法区，大小受限于方法区。JDK8将运行时常量池存放堆中。

虚拟机的类加载机制

加载：

通过全类名获取类的二进制字节流. 将类的静态存储结构转化为方法区的运行时数据结构。在内存中生成类的Class对象，作为方法区数据的入口。验证：对文件格式，元数据，字节码，符号引用等验证正确性。

准备：在方法区内为类变量分配内存并设置为0值。

解析：将符号引用转化为直接引用。

初始化：执行类构造器clinit方法，真正初始化。

JVM的双亲委派模型

一个类加载器收到类加载请求之后，首先判断当前类是否被加载过。已经被加载的类会直接返回，如果没有被加载，首先将类加载请求转发给父类加载器，一直转发到启动类加载器，只有当父类加载器无法完成时才尝试自己加载。

加载类顺序：BootstrapClassLoader->ExtensionClassLoader->AppClassLoader->CustomClassLoader 检查类是否加载顺序：CustomClassLoader->AppClassLoader->ExtensionClassLoader->BootstrapClassLoader

ArrayList和Linkedlist底层

ArrayList 使用数组实现，是容量可变的非线程安全列表，随机访问快，集合扩容时会创建更大的数组，把原有数组复制到新数组。

LinkedList 本质是双向链表，与 ArrayList 相比插入和删除速度更快，但随机访问元素很慢。

JVM垃圾收集每种算法

标记清除算法：先标记需清除的对象，之后统一回收。这种方法效率不高，会产生大量不连续的碎片。

标记整理算法：先标记存活对象，然后让所有存活对象向一端移动，之后清理端边界以外的内存

标记复制算法：将可用内存按容量划分为大小相等的两块，每次只使用其中一块。当使用的这块空间用完了，就将存活对象复制到另一块，再把已使用过的内存空间一次清理掉。

调用system.gc()一定会发生垃圾收集吗？为什么？

调用System.gc()的时候，其实并不会马上进行垃圾回收,只会把这次gc请求记录下来。需配合System.runFinalization()才会进行真正回收

说一下对于树的理解

数据结构树是一种由有限节点组成的层次关系的集合。其特点如下：

1. 每个节点有零个或多个子节点；
2. 只有一个节点没有父节点，该节点称为根节点；
3. 除根节点外，每个节点有且只有一个父节点；

简述二叉树

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

简述二叉查找树（二叉搜索树）

1. 二叉查找树的左子树若不为空，则左子树上所有结点的值均小于它的根结点的值；
2. 二叉查找树的右子树若不为空，则右子树上所有结点的值均大于它的根结点的值；
3. 二叉查找树的左、右子树也分别为二叉查找树；
4. 没有键值相等的结点。

简述红黑树

红黑树本身是有2-3树发展而来，红黑树是保持黑平衡的二叉树，其查找会比AVL树慢一点，添加和删除元素会比AVL树快一点。增删改查统计性能上讲，红黑树更优。红黑树主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。红黑树保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

设计模式的几大基本原则

开放封闭原则：对扩展开放，对修改关闭。在程序需要进行拓展的时候，不能去修改原有的代码，实现一个热插拔的效果。

单一职责原则：一个类、接口或方法只负责一个职责，降低代码复杂度以及变更引起的风险。

依赖倒置原则：针对接口编程，依赖于抽象类或接口而不依赖于具体实现类。

接口隔离原则：将不同功能定义在不同接口中实现接口隔离。

里氏替换原则：任何基类可以出现的地方，子类一定可以出现。

迪米特原则：每个模块对其他模块都要尽可能少地了解和依赖，降低代码耦合度。

合成复用原则：尽量使用组合(has-a)/聚合(contains-a)而不是继承(is-a)达到软件复用的目的。

说一下你理解的几种设计模式

简单工厂模式指由一个工厂对象来创建实例,适用于工厂类负责创建对象较少的情况。例子：Spring 中的 BeanFactory 使用简单工厂模式，产生 Bean 对象。

代理模式为其他对象提供一种代理以控制对这个对象的访问。优点是可以增强目标对象的功能，降低代码耦合度，扩展性好。缺点是在客户端和目标对象之间增加代理对象会导致请求处理速度变慢，增加系统复杂度。

适配器模式将一个接口转换成客户希望的另一个接口，使接口不兼容的那些类可以一起工作。

MYSQL的事务隔离机制

读未提交：一个事务还没提交，它做的变更就能被别的事务看到。读提交：一个事务提交后，它做的变更才能被别的事务看到。可重复读：一个事务执行过程中看到的数据总是和事务启动时看到的数据是一致的。在这个级别下事务未提交，做出的变更其它事务也看不到。串行化：对于同一行记录进行读写会分别加读写锁，当发生读写锁冲突，后面执行的事务需等前面执行的事务完成才能继续执行。

MYSQL的A C I D怎样实现的

利用undo log保障原子性。该log保存了事务发生之前的数据的一个版本，可以用于回滚，从而保证事务原子性。

利用redo log保证事务的持久性，该log关注于事务的恢复.在重启mysql服务的时候，根据redo log进行重做，从而使事务有持久性。

利用undo log+redo log保障一致性。事务中的执行需要redo log，如果执行失败，需要undo log 回滚。

MVCC原理

MVCC为多版本并发控制，即同一条记录在系统中存在多个版本。其存在目的是在保证数据一致性的前提下提供一种高并发的访问性能。对数据读写在不加读写锁的情况下实现互不干扰,从而实现数据库的隔离性,在事务隔离级别为读提交和可重复读中使用到。

在InnoDB中，事务在开始前会向事务系统申请一个事务ID，该ID是按申请顺序严格递增的。每行数据具有多个版本，每次事务更新数据都会生成新的数据版本，而不会直接覆盖旧的数据版本。数据的行结构中包含多个信息字段。其中实现MVCC的主要涉及最近更改该行数据的事务ID（DBTRXID）和可以找到历史数据版本的指针（DBROLLPTR）。InnoDB在每个事务开启瞬间会为其构造一个记录当前已经开启但未提交的事务ID的视图数组。通过比较链表中的事务ID与该行数据的值与对应的DBTRXID，并通过DBROLLPTR找到历史数据的值以及对应的DBTRXID来决定当前版本的数据是否应该被当前事务所见。最终实现在不加锁的情况下保证数据的一致性

简述redo_log undo_log

redo log: 存储引擎级别的log（InnoDB有，MyISAM没有），该log关注于事务的恢复.在重启mysql服务的时候，根据redo log进行重做，从而使事务有持久性。

undo log：是存储引擎级别的log（InnoDB有，MyISAM没有）保证数据的原子性，该log保存了事务发生之前的数据的一个版本，可以用于回滚，是MVCC的重要实现方法之一。

简述Redis的淘汰机制

1. noeviction：默认禁止驱逐数据。内存不够使用时，对申请内存的命令报错。
2. volatile-lru：从设置了过期时间的数据集中淘汰最近没使用的数据。
3. volatile-ttl：从设置了过期时间的数据集中淘汰即将要过期的数据。
4. volatile-random：从设置了过期时间的数据中随机淘汰数据。
5. allkeys-lru：淘汰最近没使用的数据。
6. allkeys-random：随机淘汰数据。

简述Redis过期策略

1. 定期删除，redis默认是每100ms就随机抽取一些设置了过期时间的key，并检查其是否过期，如果过期就删除。因此该删除策略并不会删除所有的过期key。
2. 惰性删除，在客户端需要获取某个key时，redis将首先进行检查，若该key设置了过期时间并已经过期就会删除。

实际上redis结合上述两种手段结合起来，保证删除过期的key。