面试小札：Java后端闪电五连鞭_11

1. 接口和抽象类的区别
- 定义方式：
- 接口使用 interface 关键字定义，所有方法默认是 public 和 abstract 的，不能有方法体。例如：
interface MyInterface {
    void method1();
    int method2();
}
 
- 抽象类使用 abstract class 关键字定义，它可以有抽象方法（没有方法体的方法，用 abstract 关键字修饰），也可以有非抽象方法。例如：
abstract class MyAbstractClass {
    abstract void abstractMethod();
    void nonAbstractMethod() {
        System.out.println("This is a non - abstract method");
    }
}
 
- 实现方式：
- 一个类可以实现（ implements ）多个接口，以表明该类提供了接口中定义的行为。例如：
class MyClass implements MyInterface {
    @Override
    public void method1() {
        System.out.println("Implementing method1");
    }
    @Override
    public int method2() {
        return 0;
    }
}
 
- 一个类只能继承（ extends ）一个抽象类。例如：
class MySubClass extends MyAbstractClass {
    @Override
    void abstractMethod() {
        System.out.println("Implementing abstract method");
    }
}
 
- 用途差异：
- 接口主要用于定义一组行为规范，通常用于实现多态和松耦合的设计。例如，在Java的 java.util.List 接口，有 ArrayList 、 LinkedList 等不同的实现类，它们都遵循 List 接口的行为规范，用户可以根据具体需求选择不同的实现。
- 抽象类更侧重于提供一个通用的模板，其中可以包含一些通用的方法实现和成员变量，让子类继承并扩展。比如在一个图形绘制系统中， AbstractShape 抽象类可以包含一些通用的图形属性（如颜色、位置等）和通用的方法（如获取面积的抽象方法），具体的图形类（如 Circle 、 Rectangle ）继承它并实现特定的方法。

2. 常见的数据结构
- 数组（Array）
- 是一种线性的数据结构，它在内存中是连续存储的。例如在Java中， int[] array = new int[5]; 就创建了一个可以存储5个整数的数组。可以通过索引快速访问元素，时间复杂度为O(1)，但是插入和删除操作可能比较复杂，在中间插入或删除元素可能需要移动大量元素，时间复杂度为O(n)。
- 链表（Linked List）
- 由一系列节点组成，每个节点包含数据和指向下一个节点的引用。有单向链表、双向链表等类型。插入和删除操作相对灵活，在合适的位置插入或删除节点的时间复杂度为O(1)（如果已经找到插入或删除位置），但访问特定位置的元素需要遍历链表，时间复杂度为O(n)。
- 栈（Stack）
- 是一种后进先出（LIFO）的数据结构。可以想象成一摞盘子，最后放上去的盘子最先被拿走。操作主要有入栈（ push ）和出栈（ pop ），在很多算法中用于函数调用栈、表达式求值等场景。
- 队列（Queue）
- 是一种先进先出（FIFO）的数据结构，就像排队一样，先进入队列的元素先被处理。主要操作有入队（ enqueue ）和出队（ dequeue ），常用于任务调度、广度优先搜索等场景。
- 树（Tree）
- 是一种非线性的数据结构，有根节点、分支和叶子节点。例如二叉树，每个节点最多有两个子节点。二叉搜索树（BST）可以高效地进行插入、删除和查找操作，时间复杂度平均为O(log n)，但在最坏情况下可能退化为链表的性能（O(n)）。还有平衡二叉树（如AVL树、红黑树）来保证树的高度平衡，以维持较好的性能。
- 图（Graph）
- 由顶点（Vertex）和边（Edge）组成，可以表示各种复杂的关系。例如社交网络可以用图来表示，人是顶点，人与人之间的关系是边。图有多种存储方式，如邻接矩阵和邻接表，在图的遍历（广度优先搜索、深度优先搜索）、最短路径算法（如Dijkstra算法、Floyd - Warshall算法）等方面有广泛应用。

3. 红黑树的原理
- 红黑树的性质
- 红黑树是一种自平衡二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。它有以下性质：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点，空节点）都是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 插入操作原理
- 当插入一个新节点时，默认将其颜色设为红色。插入后可能会破坏红黑树的性质，需要通过一系列的调整操作来恢复平衡。例如，如果插入节点的父节点是红色，就可能出现违反性质的情况，此时可能需要进行变色和旋转操作。旋转操作分为左旋和右旋，左旋是将一个节点提升为其父节点的位置，右旋则相反。通过这些操作来调整树的结构，使得红黑树重新满足其性质。
- 删除操作原理
- 删除节点时，首先要找到要删除的节点。如果删除的节点是红色，一般不会破坏红黑树的性质。如果删除的节点是黑色，可能会导致从根到叶子的某条路径上的黑色节点数减少，这时需要通过一些复杂的调整操作来恢复平衡，比如将其兄弟节点的颜色和结构进行调整，可能涉及变色和旋转操作，以保证红黑树的性质仍然成立。红黑树的插入和删除操作的时间复杂度在最坏情况下都是O(log n)。

4. MySQL的存储引擎
- InnoDB
- 是MySQL默认的存储引擎，支持事务处理，具有ACID特性（原子性、一致性、隔离性、持久性）。它采用了行级锁，可以提高并发性能，适用于高并发的事务处理场景，如电商系统中的订单处理、金融系统中的交易记录等。它通过聚集索引（主键索引）来存储数据，数据和索引存储在一起，非主键索引存储的是主键值，这样可以减少数据冗余。
- MyISAM
- 不支持事务，但是它的存储结构相对简单，在早期的MySQL应用中比较常用。它采用表级锁，在并发写入操作较多的情况下性能不如InnoDB，但在以读操作为主的场景下可以有较好的性能。它的索引和数据是分开存储的，有三个文件，分别是 .frm （表结构定义文件）、 .MYD （数据文件）和 .MYI （索引文件）。
- Memory（HEAP）
- 数据存储在内存中，读写速度非常快，但是数据在服务器重启后会丢失。适用于存储临时数据、缓存等场景，例如在一些需要快速查询的统计结果缓存场景中可以使用。
- CSV
- 存储数据的格式是CSV（逗号分隔值）格式，数据以文本文件形式存储。它可以方便地与其他程序进行数据交换，例如可以用电子表格软件直接打开和编辑CSV文件，但是它不支持索引，在大数据量和复杂查询场景下性能较差。

5. Innodb存储引擎和MyISAM存储引擎的区别

- 事务支持
- Innodb支持事务，符合ACID特性，可以保证数据的一致性和完整性。例如在一个银行转账系统中，从一个账户扣款和向另一个账户存款这两个操作可以作为一个事务来处理，要么全部成功，要么全部失败。而MyISAM不支持事务。
- 锁机制
- Innodb采用行级锁，在高并发场景下，多个事务可以同时对不同行进行操作，减少了锁冲突，提高了并发性能。例如在一个电商系统中，多个用户同时购买不同商品时，行级锁可以让这些操作并发执行。MyISAM采用表级锁，当一个事务对表进行写操作时，整个表都会被锁定，其他事务不能对该表进行写操作，在并发写入较多的场景下性能较差，但在以读为主的场景下，表级锁的开销相对较小。
- 存储结构
- Innodb通过聚集索引（主键索引）存储数据，数据和索引存储在一起，非主键索引存储的是主键值。MyISAM的索引和数据是分开存储的，它有单独的数据文件和索引文件，这种存储方式在一些以读为主的简单应用场景下可能会有一定的性能优势。
- 数据恢复
- Innodb支持崩溃后的自动恢复，因为它有日志文件（如redo log和undo log）来记录事务操作，在数据库崩溃后可以根据日志文件进行数据恢复。MyISAM在出现故障后恢复相对复杂，可能需要借助备份和手动修复等方式。