1105--面试代码题
请编写一个Java类（Singleton），实现单例模式，获取实例的方法为getInstance()
public class Singleton {
// 使用 volatile 关键字确保在多线程环境下的可见性
private static volatile Singleton instance;
// 私有构造函数，防止外部实例化
private Singleton() {
// 防止反射破坏单例
if (instance != null) {
throw new IllegalStateException("Instance already created.");
}
}
// 公共的静态方法获取实例
public static Singleton getInstance() {
// 第一次检查，如果实例为 null，则进入同步块
if (instance == null) {
synchronized (Singleton.class) {
// 第二次检查，确保实例仍然为 null
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
}
Java中volatile关键字的作用
在 Java 中，volatile 关键字主要用于保证变量的可见性和防止指令重排序，特别适用于并发环境下共享变量的控制。
1. 可见性
当一个变量被声明为 volatile，意味着该变量在被修改后，会立即刷新到主内存中，而不是仅仅停留在线程的工作内存。这样，其他线程在读取这个变量时，总是能看到最新的值。换句话说，volatile 变量的读写操作直接在主内存中进行，保证了线程间的可见性。
示例：
public class Example {
private volatile boolean flag = true;
public void stop() {
flag = false;
}
public void run() {
while (flag) {
// 执行一些操作
}
}
}
在这个示例中，当一个线程调用 stop() 方法将 flag 设置为 false 后，其他线程在 run() 中读取到的 flag 值会立即变成 false，从而终止循环。
2. 防止指令重排序
在编译和执行过程中，Java 可能会优化代码顺序以提高效率，即所谓的指令重排序。但在并发场景下，这种重排序可能导致线程看到不同步的变量状态。通过 volatile，可以防止某些重排序，以保证代码按照预期顺序执行。
示例：
public class Singleton {
private static volatile Singleton instance;
public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
}
在双重检查锁定的单例模式中，instance 被声明为 volatile，确保在初始化时不会发生重排序，从而避免线程安全问题。
注意事项
volatile适用于状态简单的变量（如布尔值、计数器等）。对于复杂操作或依赖先后关系的代码（如i++），需要使用synchronized来确保原子性。volatile不保证原子性（不能用来保证复杂操作的线程安全）。
简述分布式系统中的cap定理，并解释其对系统设计的影响
CAP定理概述
CAP定理（CAP Theorem）也被称作布鲁尔定理（Brewer’s theorem），它指出在一个分布式系统中，最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三个属性中的两个。
一致性（Consistency）
- 含义：在分布式系统中的所有数据备份，在同一时刻是否具有相同的值。例如，在一个分布式数据库系统中，当一个数据项被更新后，后续的所有对该数据项的读取操作都应该返回最新的值。
- 示例：在一个多节点的分布式缓存系统中，如果一个节点更新了某个缓存键的值，那么在更新操作完成后，其他节点对该缓存键的读取都应该立即返回更新后的值。
可用性（Availability）
- 含义：系统在面对各种情况（包括网络故障、节点故障等）时，是否能够持续对外提供服务，并且在合理的时间内返回响应。也就是说，系统中的每个请求都应该能够在有限的时间内得到响应，而不会一直处于等待状态。
- 示例：一个在线电商系统，在双十一购物高峰期，即使部分服务器负载很高或者存在网络波动，用户的商品浏览、下单等操作依然能够得到及时响应，系统不会出现长时间的无响应状态。
分区容错性（Partition tolerance）
- 含义：分布式系统在遇到网络分区（节点之间的网络通信出现故障，导致部分节点之间无法通信）时，系统仍然能够正常工作，对外提供服务。在实际的分布式系统中，网络分区是不可避免的，比如网络故障、节点故障等原因都可能导致网络分区的出现。
- 示例：一个分布式存储系统横跨多个数据中心，当两个数据中心之间的网络连接中断（网络分区发生）时，每个数据中心内的节点仍然能够继续处理读写请求，系统整体依然保持可用状态。
CAP定理对系统设计的影响
选择CA放弃P（一致性和可用性优先，放弃分区容错性）
- 适用场景：在对一致性和可用性要求极高的场景下，例如金融交易系统中的核心交易处理环节，如银行转账操作。如果出现数据不一致可能导致严重的财务问题，同时系统需要随时可用以处理大量实时交易。
- 系统设计特点：通常需要采用强一致性的分布式算法，如两阶段提交（2PC）或三阶段提交（3PC）协议，来确保所有节点在事务处理过程中的数据一致性。但这种设计在网络分区发生时，系统可能会因为无法满足分区容错性而停止服务。例如，在一个数据中心内部署的高可用集群，通过高速网络连接各个节点，尽量避免网络分区的发生，以保证CA特性。
选择CP放弃A（一致性和分区容错性优先，放弃可用性）
- 适用场景：适用于对数据一致性要求极高且能容忍一定时间内系统不可用的场景，比如分布式数据库中的主从复制模式下的数据同步过程。在主节点数据更新时，需要确保从节点数据的一致性，在同步过程中从节点可能会暂时不可用，但数据的准确性得到了保证。
- 系统设计特点：系统会在网络分区发生时，优先保证数据的一致性，可能会牺牲部分节点的可用性。例如，在一个分布式文件系统中，当网络分区出现时，系统会暂停部分节点的写入操作，直到网络分区恢复，确保数据在各个分区内的一致性。这种情况下，系统在分区期间对部分客户端请求可能无法及时响应，但数据不会出现不一致的情况。
选择AP放弃C（可用性和分区容错性优先，放弃一致性）
- 适用场景：在对可用性要求很高且允许一定程度的数据不一致的场景中，如社交网络系统中的用户状态更新、实时消息推送等功能。用户能够快速获取信息并进行操作比看到的数据完全一致更为重要，偶尔的数据不一致不会对用户体验造成严重影响。
- 系统设计特点：系统会在网络分区时，继续提供服务，可能会导致不同节点之间的数据在短期内不一致。例如，在一个分布式缓存系统中，当网络分区发生时，各个节点可以继续响应读请求，即使数据可能不是最新的。这种设计通过牺牲数据的强一致性来换取系统的高可用性，在网络分区恢复后，再通过异步方式进行数据的同步和修复。
总结
CAP定理为分布式系统设计提供了重要的理论指导，系统设计者需要根据具体的业务需求和场景特点，权衡一致性、可用性和分区容错性这三个属性，选择最适合的系统设计方案。在实际应用中，大多数分布式系统会在AP或CP之间
为什么最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三个属性中的两个
理解CAP定理中的三个属性
- 一致性（Consistency）
- 要求在分布式系统中的所有数据副本在同一时刻都具有相同的值。这意味着无论客户端向哪个节点发起读取操作，都应该获取到最新的、一致的数据。例如，在一个分布式数据库中，对于同一条记录的多次读取，无论在哪个节点上进行，结果都应该相同。
- 可用性（Availability）
- 系统必须能够在合理的时间内对每个请求做出响应，保证系统随时可用，不会出现长时间的无响应或拒绝服务情况。即使在部分节点出现故障或网络出现问题时，系统整体仍应能正常工作，持续为客户端提供服务。
- 分区容错性（Partition tolerance）
- 分布式系统在网络分区（节点之间的网络通信出现故障，导致部分节点之间无法通信）的情况下仍能继续正常工作，对外提供服务。由于网络故障在分布式环境中难以避免，所以分区容错性是分布式系统必须具备的特性。
为什么只能同时满足两个属性
- 假设满足CAP中的三个属性
- 考虑一个分布式系统，它有多个节点，并且节点之间通过网络进行通信和数据同步。假设在某个时刻，系统处于一致状态，所有节点的数据副本都是相同的。
- 现在发生了网络分区，将系统分为两个或多个分区（例如，节点A、B在一个分区，节点C、D在另一个分区，两个分区之间无法通信）。
- 分析一致性与可用性的矛盾
- 如果要保证一致性，当节点A收到更新数据的请求时，它需要将更新操作同步到其他节点（包括分区中的节点B以及其他分区的节点C、D等），以确保所有节点的数据一致。然而，由于网络分区的存在，节点A无法与节点C、D通信，无法完成数据同步。为了保证一致性，系统可能会选择等待网络恢复后再进行更新操作，这样在等待期间，节点A、B所在分区无法响应其他客户端的读取请求（因为数据不一致），系统的可用性就受到了影响。
- 反之，如果要保证可用性，节点A在收到更新请求后，即使无法与其他分区的节点通信，也立即响应客户端并执行更新操作，那么节点A、B所在分区的数据就与节点C、D所在分区的数据不一致了，从而破坏了一致性。
- 分析一致性与分区容错性的矛盾
- 在网络分区存在的情况下，要保证一致性，就需要节点之间进行频繁的数据同步和协调，以确保所有副本数据一致。但网络分区可能导致部分节点之间无法通信，使得数据同步无法完成，这与分区容错性要求系统在网络分区时仍能正常工作相冲突。例如，为了保证一致性，系统可能会在网络分区时停止部分节点的服务，等待网络恢复后再进行数据同步和服务恢复，这就违背了分区容错性的原则。
- 分析可用性与分区容错性的矛盾
- 为了保证可用性，系统在网络分区时需要各个节点能够独立处理请求，即使节点之间的数据不一致。但这样就无法保证所有节点的数据在同一时刻是一致的，即牺牲了一致性。例如，在网络分区期间，不同分区的节点可能会处理不同的请求，导致数据状态发生变化，而无法保证整个系统的数据一致性。
结论
由于在分布式系统中网络分区难以避免，当网络分区发生时，要同时保证一致性和可用性是非常困难的，往往会顾此失彼。因此，在设计分布式系统时，需要根据具体的业务需求和场景，权衡CAP三个属性，选择优先满足其中两个属性，从而确定最适合的系统架构和设计方案。例如，在一些对数据一致性要求极高的金融交易系统中，可能会牺牲一定的可用性来保证一致性和分区容错性；而在一些社交网络等对实时性和可用性要求较高的系统中，可能会适当放宽一致性要求，优先保证可用性和分区容错性。
多线程交替打印奇数和偶数
class Solution {
private final int maxCount; // 最大数字
private int currentNumber = 1; // 当前打印的数字
private final Object lock = new Object(); // 锁对象
public Solution(int maxCount) {
this.maxCount = maxCount;
}
// 开启两个线程分别打印奇数和偶数
public void start() throws InterruptedException {
// 线程 OddThread 调用 printOdd();
Thread oddThread = new Thread(() -> {
try {
printOdd();
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "OddThread");
// 线程 EvenThread 调用 printEven();
Thread evenThread = new Thread(() -> {
try {
printEven();
} catch (InterruptedException e) {
e.printStackTrace();
}
}, "EvenThread");
// 启动两个线程
oddThread.start();
evenThread.start();
// 等待子线程执行完成
oddThread.join();
evenThread.join();
}
public void printOdd() throws InterruptedException {
while (currentNumber <= maxCount) {
synchronized (lock) {
// 检查当前数字是否为奇数
if (currentNumber % 2 != 0) {
System.out.println(currentNumber++);
lock.notify(); // 唤醒偶数线程
} else {
lock.wait(); // 如果不是奇数，等待
}
}
}
}
public void printEven() throws InterruptedException {
while (currentNumber <= maxCount) {
synchronized (lock) {
// 检查当前数字是否为偶数
if (currentNumber % 2 == 0) {
System.out.println(currentNumber++);
lock.notify(); // 唤醒奇数线程
} else {
lock.wait(); // 如果不是偶数，等待
}
}
}
}
public static void main(String[] args) throws InterruptedException {
Solution solution = new Solution(10); // 设定最大数字为 10
solution.start();
}
}
找出数组中唯一重复的数
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param nums int整型ArrayList
* @return int整型
*/
public int findRepeatNum(ArrayList<Integer> nums) {
// 创建一个 HashSet 用于存储已经见过的数字
Set<Integer> seenNumbers = new HashSet<>();
// 遍历数组
for (int num : nums) {
// 如果当前数字已经在 HashSet 中，说明它是重复的
if (seenNumbers.contains(num)) {
return num; // 返回找到的重复数字
}
// 否则，将当前数字添加到 HashSet 中
seenNumbers.add(num);
}
// 如果没有找到重复的数字，返回 -1（根据需求可以修改）
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
ArrayList<Integer> nums = new ArrayList<>(Arrays.asList(1, 3, 4, 2, 2));
int result = solution.findRepeatNum(nums);
System.out.println("重复的数字是: " + result); // 输出 2
}
}