中气Java开发岗面经

总共两面，问的比较简单，目前已经通过面试。简单记录一下问题：

一面：一面主要就是自我介绍，还有实习时间，还有一些家庭情况，10分钟很快结束了。

二面：先是自我介绍，然后问了一些技术性问题。答案是我面试完查的，可能有不准确的地方。

1.介绍一下链表，栈，队列，树，图的相关知识。

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：

    一个是存储数据元素的数据域 ，另一个是存储下一个节点地址的指针域。

堆是一种是一种特殊的树状结构，其中每个节点都有一个键值，并且满足一定的堆属性。堆常常用于实现优先级队列和排序算法。

在堆中，每个节点的键值必须满足堆属性。具体来说，对于最大堆（大顶堆），每个节点的键值都大于或等于其子节点的键值；而对于最小堆（小顶堆），每个节点的键值都小于或等于其子节点的键值。这个属性使得堆的根节点始终是最大（或最小）的元素。

堆通常使用数组来表示，其中每个元素在数组中的位置与其在树中的位置相关联。为了满足堆属性，通常使用下标从1开始的完全二叉树来表示堆，这样可以通过简单的计算获得节点的父节点和子节点。

堆的常见操作包括：

1. 插入：将一个新元素插入到堆中的适当位置，并调整堆以保持堆属性。
2. 删除根节点：移除堆中的根节点，并调整堆以保持堆属性。
3. 查找根节点：获取堆中的根节点，它是堆中的最大（或最小）元素。
4. 堆化（Heapify）：将一个无序数组转换为堆的过程，通常用于构建堆或恢复堆属性。

堆的一个重要应用是实现优先级队列。优先级队列是一种数据结构，其中每个元素都有一个相关的优先级或权重。通过使用堆，可以在常数时间复杂度内获取具有最高（或最低）优先级的元素，而无需对整个队列进行排序。

此外，堆还可以用于各种排序算法，例如堆排序（Heap Sort）。堆排序利用堆的性质，首先构建一个最大堆（或最小堆），然后反复删除根节点并重新调整堆，最终得到一个有序的数组。

总结：堆是一种树状数据结构，具有堆属性，用于高效地管理和组织数据。它常用于实现优先级队列和排序算法，具有快速获取最大（或最小）元素的特点。

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表， 其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。

栈是限定仅在表尾进行插入或删除操作的线性表。 表尾称为栈顶,表头端称为栈底 。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。

和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一端称为队尾，允许删除的一端则称为队头。

图由节点（也称为顶点）和连接节点的边组成。图可以用于表示各种实际问题，如社交网络、网络拓扑、路线规划等。

根据图的特性，可以将其分类为以下两种常见类型：

1. 无向图：图中的边没有方向。如果两个节点之间存在一条边，则可以沿着该边在两个节点之间进行双向遍历。
2. 有向图：图中的边有方向。如果存在一条从节点 A 到节点 B 的有向边，那么可以从节点 A 沿着该边到达节点 B，但不能反过来。

常见的图遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

3. 深度优先搜索（DFS）： 深度优先搜索从图中的一个节点开始，沿着一条路径尽可能深地访问图的节点，直到到达末端节点，然后回溯到上一个节点，继续访问未被探索的分支。这个过程以递归或栈的方式实现。

DFS的步骤：

4. 选择一个起始节点，并标记为已访问。
5. 访问该节点，并标记为已访问。
6. 递归或使用栈，按照深度优先的原则，访问与当前节点相邻且未被访问的节点。
7. 重复上述步骤，直到所有节点都被访问。

DFS适用于以下情况：

8. 查找路径或连通性：通过遍历可以找到两个节点之间是否存在路径，或者找到图中的连通分量。
9. 拓扑排序：对有向无环图进行拓扑排序，确定节点之间的依赖关系顺序。
10. 广度优先搜索（BFS）： 广度优先搜索从图中的一个节点开始，首先访问该节点，然后依次访问其所有相邻节点，再访问相邻节点的相邻节点，以此类推，直到遍历完所有节点。这个过程使用队列实现。

BFS的步骤：

11. 选择一个起始节点，并标记为已访问。
12. 将起始节点放入队列中。
13. 从队列中取出一个节点，访问该节点，并将其未访问过的相邻节点放入队列中。
14. 重复上述步骤，直到队列为空。

BFS适用于以下情况：

15. 最短路径和最少步骤：BFS可以找到起始节点到目标节点的最短路径，或者在图中找到从起始节点到目标节点的最少步骤。
16. 层级遍历：可以按照层级的方式遍历图，对于具有层次结构的问题很有用，如树的层级遍历。

无论是DFS还是BFS，都需要标记节点是否已经访问过，以避免重复访问，尤其在图中存在环的情况下。这可以通过设置访问标记数组或属性来实现。

总结：图的遍历是按照一定规则访问图中的所有节点和边的过程。深度优先搜索（DFS）按照深度优先的原则遍历图，而广度优先搜索（BFS）按照广度优先的原则遍历图。DFS适用于路径查找和拓扑排序，而BFS适用于最短路径和层级遍历。

树形结构是一类重要的非线性数据结构，树中结点之间具有明确的层次关系，并且结点之间有分支，非常类似于真正的树。树形结构在客观世界中大量存在，如行政组织机构和人类社会家谱等都可以用树形结构形象表示。

(1)结点的度：结点所拥有的子树的个数。

(2)树的度：树中结点度的最大值。

(3)叶子：度为0的结点

(4)分支结点：度不为0的结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点

(5)孩子：结点的直接后继（结点的子树的根）

(6)双亲：结点直接前趋

(7)兄弟：同一双亲的孩子互为兄弟

(8)子孙：一颗树上的任何结点称为根的子孙

(9)祖先：从根结点开始到该及诶点连线上的所有结点都是该结点的祖先

(10)路径：树中存在一个结点序列k1，k2…ki，使得ki是ki+1的双亲（1《i<j）,则称该及诶点序列是从k1到kj的一条路径或道路即链接两个结点的线段的数目等于j-1;

注意：

若一个结点序列是路径，则在树的树形图表示中，该结点序列’自上而下‘地通过路径上的每条边。

(11)结点的层：设跟结点的层数为1，其余结点的层数等于双亲结点的层数加1。

(12)输的高度（或深度）：树中所有结点层数的最大值。

(13)有序树和无序树：将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。

(14)森林：是m(m>=0)棵互不相交的树的集合。树和森林的概念相近，删去一棵树的根，就得到一个森林；反之加上一个节点做为根，森林变成一棵树。

性质一： 非空树中的结点总数等于树中所有结点的度之和加1.

性质二：度为k的非空树的第i层最多有k的（i-1）次方个结点（i>=1）；

性质三：深度为h的k叉树最多有k^h - 1/k-1个结点。

2.MySQL中如何提高多表查询的效率？

索引优化：为联查中使用的关联字段创建合适的索引。确保每个表的关联字段都有索引，这样MySQL可以更快地定位到匹配的行。考虑创建组合索引以覆盖多个关联字段，避免使用过多或不必要的索引，因为索引的维护也需要额外的开销。

索引的优点：可以大大的加快数据的检索速度。在查询的过程中，使用优化隐藏器，提高系统性能。

缺点：时间：创建维护索引要耗费时间。空间：索引需要占物理空间

避免使用子查询，使用缓存。

3.如何防止库存超卖？

乐观锁，悲观锁，版本号，CAS。

在程序世界中，乐观锁和悲观锁的最终目的都是为了保证线程安全，避免在并发场景下的资源竞争问题。但是，相比于乐观锁，悲观锁对性能的影响更大！

悲观锁总是假设最坏的情况，认为共享资源每次被访问的时候就会出现问题(比如共享数据被修改)，所以每次在获取资源操作的时候都会上锁，这样其他线程想拿到这个资源就会阻塞直到锁被上一个持有者释放。也就是说，共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程。

 Java 中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现。

高并发的场景下，激烈的锁竞争会造成线程阻塞，大量阻塞线程会导致系统的上下文切换，增加系统的性能开销。并且，悲观锁还可能会存在死锁问题，影响代码的正常运行。

乐观锁总是假设最好的情况，认为共享资源每次被访问的时候不会出现问题，线程可以不停地执行，无需加锁也无需等待，只是在提交修改的时候去验证对应的资源（也就是数据）是否被其它线程修改了（具体方法可以使用版本号机制或 CAS 算法）。高并发的场景下，乐观锁相比悲观锁来说，不存在锁竞争造成线程阻塞，也不会有死锁的问题，在性能上往往会更胜一筹。但是，如果冲突频繁发生（写占比非常多的情况），会频繁失败和重试（悲观锁的开销是固定的），这样同样会非常影响性能，导致 CPU 飙升。

乐观锁一般会使用版本号机制或 CAS 算法实现，CAS 算法相对来说更多一些，这里需要格外注意。

版本号机制

一般是在数据表中加上一个数据版本号 version 字段，表示数据被修改的次数。当数据被修改时，version 值会加一。当线程 A 要更新数据值时，在读取数据的同时也会读取 version 值，在提交更新时，若刚才读取到的 version 值为当前数据库中的 version 值相等时才更新，否则重试更新操作，直到更新成功。

举一个简单的例子 ：假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。

操作员 A 此时将其读出（ version=1 ），并从其帐户余额中扣除 $50（ $100-$50 ）。

在操作员 A 操作的过程中，操作员 B 也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。

操作员 A 完成了修改工作，将数据版本号（ version=1 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本等于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。

操作员 B 完成了操作，也将版本号（ version=1 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 1 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须等于当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。

这样就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员 A 的操作结果的可能。

CAS 算法

CAS 的全称是 Compare And Swap（比较与交换） ，用于实现乐观锁，被广泛应用于各大框架中。CAS 的思想很简单，就是用一个预期值和要更新的变量值进行比较，两值相等才会进行更新。

CAS 是一个原子操作，底层依赖于一条 CPU 的原子指令。

原子操作 即最小不可拆分的操作，也就是说操作一旦开始，就不能被打断，直到操作完成。

CAS 涉及到三个操作数：

V ：要更新的变量值(Var)

E ：预期值(Expected)

N ：拟写入的新值(New)

当且仅当 V 的值等于 E 时，CAS 通过原子方式用新值 N 来更新 V 的值。如果不等，说明已经有其它线程更新了 V，则当前线程放弃更新。

举一个简单的例子 ：线程 A 要修改变量 i 的值为 6，i 原值为 1（V = 1，E=1，N=6，假设不存在 ABA 问题）。

i 与 1 进行比较，如果相等， 则说明没被其他线程修改，可以被设置为 6 。

i 与 1 进行比较，如果不相等，则说明被其他线程修改，当前线程放弃更新，CAS 操作失败。

当多个线程同时使用 CAS 操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。

4.如何提高系统并发性能？

使用线程池：合理使用线程池可以有效管理线程的创建和销毁，减少线程创建的开销。通过线程池可以重用线程，并控制线程的数量，避免过多的线程竞争资源导致性能下降。

减少锁竞争：使用细粒度的锁和锁分离技术可以减少线程之间的竞争，提高并发性能。考虑使用读写锁（ReentrantReadWriteLock）或无锁的并发数据结构（如ConcurrentHashMap）来替代全局锁，以实现更好的并发性能。

并发数据结构：选择适当的并发数据结构可以提高并发性能。Java中提供了许多并发安全的数据结构，如ConcurrentHashMap、ConcurrentLinkedQueue等。使用这些数据结构可以避免手动处理同步和锁带来的开销。

合理的任务拆分：将大任务拆分为多个小任务，并行处理可以提高并发性能。可以使用Java并发框架（如Executor框架）或并发工具类（如CountDownLatch、CyclicBarrier等）来实现任务的拆分和并发执行。

使用非阻塞IO：在处理高并发的网络请求时，可以考虑使用非阻塞IO（NIO）来提高系统的并发性能。NIO利用事件驱动模型和选择器（Selector）机制，可以较少线程数目，提高处理并发请求的能力。

缓存优化：合理使用缓存可以减少对底层资源的访问，提高系统的响应速度和并发性能。可以使用内存缓存（如Redis、Memcached）或者本地缓存（如Caffeine、Ehcache）来存储频繁访问的数据，避免重复计算或查询数据库。

并行算法和数据结构：选择适当的并行算法和数据结构可以充分利用多核处理器的能力，提高系统的并发性能。例如，使用并行排序算法（如Fork/Join框架）或并行集合（如并行流Stream）来处理大规模数据。

JVM调优：通过调整JVM参数可以提高系统的并发性能。例如，调整堆内存大小、垃圾回收策略和线程栈大小等参数，以适应系统的并发负载。

分布式部署：如果系统需要处理非常高的并发请求，可以考虑将系统部署为分布式架构，通过横向扩展来提高系统的并发性能。

5.redis如何提高系统性能？

Redis（Remote Dictionary Server）通过以下几个方面来提高系统性能：

内存存储：Redis将数据存储在内存中，这使得它能够快速读取和写入数据。相比于磁盘存储的数据库系统，Redis能够提供更高的数据访问速度。

单线程模型：Redis采用单线程模型，避免了多线程的锁竞争和上下文切换开销。在高并发场景下，单线程的Redis能够更好地利用CPU的缓存和计算资源，提供更高的响应速度。

非阻塞IO：Redis使用非阻塞IO模型，通过事件驱动的方式处理客户端请求。它利用事件循环机制（Event Loop）和多路复用技术，可以高效地处理大量并发请求，减少线程开销和上下文切换。

内置数据结构和操作：Redis提供了丰富的数据结构（如字符串、哈希、列表、集合、有序集合等）和对应的操作命令。这些内置的数据结构和操作能够在服务端完成，避免了网络传输和客户端计算的开销，提高了数据操作的效率。

缓存机制：Redis可以作为缓存层，将经常访问的数据存储在内存中，并设置过期时间。通过缓存机制，可以避免频繁访问磁盘或数据库，提高数据的访问速度。

发布/订阅和消息队列：Redis提供了发布/订阅（Pub/Sub）和消息队列（Message Queue）功能。这使得它可以处理实时的消息推送和异步任务处理，提高系统的并发性能和可扩展性。

持久化：Redis支持数据持久化，可以将数据保存到磁盘中，以防止数据丢失。它提供了两种持久化方式：RDB（快照）和AOF（追加日志），可以根据需求选择适合的方式进行数据持久化。

集群和分片：Redis提供了集群和分片的功能，可以将数据分布在多个节点上，实现横向扩展和负载均衡。通过分布式部署，Redis可以处理更大规模的数据和更高的并发请求，提高系统的性能和可用性。

#我发现了面试通关密码#