Java八股文-详细版

发表于

写在最前

现在大三，双非二本，就业压力，内卷左移，我是废物…好久之前，我的朋友们建议我做一个八股文整合，我拒绝了，因为太多了！

于是我们找了一堆八股文提纲，但是每个提纲只是提纲，细致的来说还需要一篇篇介绍，于是有了这个。本文不是八股文背诵讲义，仅仅是我看到的，一些八股文可能会考的，但是讲解比较深入的文章的合计，出处即链接🔗。

本文持续更新…可以收藏或点赞以获取更新状态。

GitHub上的八股文

操作系统

进程/线程

进程是最基本的执行体，它拥有一个执行单元最基本的特征，包括PC，寄存器，堆栈，打开文件集，PID等。一个进程可以fork出子进程，在Linux中，子进程和父进程共享只读空间。写时复制技术用于子进程想写数据时。

每个进程有一个主线程，线程作为进程执行的实体，一个进程可以拥有多个线程，归属于同一个进程的线程共享全部进程资源。对于内核而言，调度线程取决于线程的类型。

首先，线程分为两种：用户线程和内核线程。内核线程由内核进程创建，内核本质是一个进程，它所创建的所有线程都叫内核线程；用户线程由非内核进程创建。对于内核线程，调度单位是线程，对于用户线程，调度单位是它所属的进程，所以同一进程内的用户线程需要自行安排调度规则，如果某个用户进程阻塞，则会阻塞整个进程。

为了把用户线程调度的负担丢给内核，出现了LWP轻量级进程，它只有一个主线程，每次创建线程不是在它内部创建线程，而是创建一个新的LWP。前面说过用户线程调度单位是进程，如果一个线程对应一个进程，那就可以实现每个线程由内核调度了，所以LWP就做到了这件事，同时它的组成相对于普通进程更加轻量级。

Linux和Windows都实现了这种策略，即每个线程对应一个进程，让内核调度线程，这样即不用通过创建内核线程这种高昂的方式实现内核调度，也实现了内核对用户线程的调度。

内存管理

文件系统

I/O

同步和锁

这里只说死锁问题。

死锁产生的四个条件

  • 🤺互斥条件：一个资源要么被占有且不可用，要么可用(有些资源可以同时被多个线程占有，这就不能构成死锁)。
  • ⚾️占有与等待：一个拥有了资源的进程可以继续申请其他资源。
  • 🏓不可抢占：其他进程无法强制抢夺某个进程已经获取的资源。
  • 🏸环路等待：发生死锁的系统，必然存在两个或以上的进程互相等待对象资源的释放。

死锁处理：

  • 死锁预防：在程序运行之前，打破四个条件之一进行预防。
  • 死锁避免：银行家算法确保程序处于安全状态，进而避免进入死锁状态。
  • 死锁检测与恢复：通过有向环路(单个资源)/资源分配图(类似多个资源的银行家算法)进行死锁检测，如果发生了死锁则使用杀死进程/回滚进程/抢占资源三个方式之一进行恢复。

当程序已经开始运行了，检测死锁常用的是有向环路检测，通过A->B来表明A等待B的资源释放，多个进程组成一个有向图，如果出现环，说明出现死锁。

当程序还未开始运行呢，检测死锁常用的就是银行家算法，通过判断系统是否处于安全状态来允许多个进程执行与否。所谓的安全状态指的是，系统从执行第一个线程开始，到所有线程执行结束，都不会发生死锁，那么就成执行前的系统状态未安全状态。

单个资源的银行家算法比较简单，我们直接看多个资源的：

假设有M个进程，N个资源，每种资源的个数为：ResN，每个进程需要的每个资源数为Req[M]N；每个进程已经获得的每个资源数为：Have[M][N]，还需要的资源为：Need[M][N]。

  • 1️⃣找到一个线程i，使它第j个资源得到满足，即Need[i][j] <= Res[j]-(Have[0][j] + … + Have[M-1][j])；即所需资源数<=这种资源剩余数。
  • 2️⃣j = j+1
  • 3️⃣重复1️⃣
  • 4️⃣如果i不满足，i = i+1，重复1️⃣
  • 5️⃣如果j == N，释放i占有的全部资源，继续1️⃣。

其他比如两阶段锁和通信锁，活锁解决均比较简单。

处理器架构(偏底层)

程序优化(偏底层)

计算机网络

DNS解析

查询过程：浏览器缓存=>操作系统缓存=>本地域名解析器缓存(比如路由器缓存)=>本地域名服务器=>根域名服务器=>一级域名服务器=>权限域名服务器=>IP地址。

HTTP

关于HTTP1.0的“一问一答”和HTTP1.1的“流水线”以及HTTP2的“多路复用”。

版本 技术 意义
HTTP1.0 一问一答式 早期内存金贵的很，所以对于连接(大约占用8KB)要尽快关闭好，这也造就了早期HTTP是一问一答，一次请求一次应答，然后结束
HTTP1.1 流水线式 一问一答每次都要开启一次TCP连接，代价太大，于是一次连接发送多个请求变成一种方案，但是响应必须按照请求顺序，否则会乱序，这就有可能造成队头阻塞，即前一个请求的响应阻塞会影响后面的请求的响应
HTTP2.0 多路复用 此时的HTTP基于二进制传输，每次传输单位为流，流由多个帧组成，每个帧指出它属于谁(头部有唯一标识)，接收端不停地接收帧，根据所属流进行聚合，以此保证不会发生队头阻塞

WebSocket

Java

MySQL

MySQL中的redolog主要通过记录修改前的数据来实现回滚操作，undolog只要用于持久化修改，因为数据修改需要先把数据加载到buffer中再修改，然后写回磁盘，undolog是追加写的方式，属于顺序I/O，更快一些。具体操作是：写buffer=>写undolog=>异步刷新磁盘(通过定时刷新等手段)。

MySQL为了防止死锁，除了InnoDB提供的资源申请图死锁检测之外，还有一次性锁，就是一口气把所有需要的资源全部加锁。

与之对应的是MySQL提供的两阶段锁，本意就是把所有的加锁操作放到一起，加锁阶段只加不释放，之后就是解锁阶段，只释放不加。两阶段锁的引入是为了解决事务可串行化问题；这样虽然提升了并发度，但是引入了死锁问题。

NoSQL

在这里简述一下Redis集群：

主从集群很简单，从服务器申请同步(发送SYNC)，主服务器发送快照文件以及生成快照期间发生的写命令给从服务器，从服务器利用快照文件和写命令初始化数据库，然后主服务器每次有写命令，都同步给从服务器。

哨兵集群实现了故障转移：

  • 哨兵只会监控主服务器，并且会发送INFO指令获取主服务器的信息，这些信息包括监控这台主服务器的其他哨兵，和主服务器的从服务器。
  • 如果发现了主服务器的从服务器，哨兵会建立与从服务器的连接；如果发现了其他哨兵，则会建立与其他哨兵的连接。
  • 与从服务器的连接是为了实现故障转移，与其他哨兵的连接是为了实现投票机制等。
  • 当主服务器挂了，哨兵会经历主观下线，客观下线，投票选出主哨兵，并由主哨兵发起故障转移。

Spring

分布式

Kafka

其他

集群

Zookeeper

在这里我总结一下分布式系统的一致性问题：

分布式系统的一致性分为两种：强一致性和弱一致性。

  • 强一致性：指的是主库(主服务)同步对从库(从服务)写入数据，每次写入需要等待从库给予响应才算结束，可以保证主从库绝对的一致，但是缺点就是响应时间过久，因为写入从库涉及到很多的网络I/O。
  • 弱一致性：指的是主库异步对从库写入数据，每次发起对从库的写，但是不会等待回应，因此整个请求只需要等待主库完成即可。

关于弱一致性，分为很多变种：最终一致性，读写一致性，单调读，因果一致性等。

  • 最终一致性：系统保证在一定的时间之后，主从一致，也就是让数据写入“飞一会儿”。我们不能保证立刻看到一致性，但是可以在几秒或者几分钟后，整个分布式系统达到一致性状态。
  • 读写一致性：对于某些特定的读，从主库完成，其余从库读取。比如我在知乎回答了一个问题，我发布完就想立刻看到，此时针对我的回答，我自己去看，可以从主库去读，这样可以读到最新的，但是其他人查看我的问题，则可以通过从库去读，这样实现了分布式读，同时又实现了我想立刻看到我的回答的效果。
  • 单调读：使用映射的方式，把针对某一特定记录的读全部请求到同一数据库。如果我们跨库读取，可能读到历史数据；比如我在A库读到了今天的数据，但是由于数据同步有延迟，下一次我在B库刷新数据时反而看到了昨天的，这样我刷新读取最新的反而读到了旧数据，这就像发生了时光倒流一样。而如果我们读的是同一个数据库，这个问题就迎刃而解了。
  • 因果一致性：详见向量时钟。

网络

首先我们需要明确，TCP的是发送一个请求，得到一个接收确认。如果某次请求之后，未获得接收方的ACK确认，那我们可以认为出了问题，这个问题成为超时。这个问题包括两个原因：一个是丢包，一个是网络阻塞(堵车了)。

为什么TCP的拥塞控制算法至今还在完善？很大一部分原因是因为我们不知道当发生超时了，到底是因为简单的丢包还是因为发生了网络阻塞，前者简单重发即可，后者设计网络阻塞的恢复。所以目前的算法都在根据网络带宽，流量，时延，ACK回复来判断到底是哪种，以此来完善算法。

如果发生了超时，需要进行重传。超时的原因有两个：发送丢包，返回的ACK丢包，无论是哪个都需要进行重新发送，这涉及超时时间的判定，表现为RTO时间，RTO又和RTT有关，Linux中对于RTO的计算有自己的方式，且每次RTO=之前的二倍。

此外，如果某一次发送丢包了，接收端发现这个包后面的包都收到了，唯独这个包没有收到，那就可以每次接收新的包，发送丢失的包的前一个包的ACK来实现对发送端的通知；如果发送端发现出现了连续三次相同的ACK，那就是发生了丢包，需要涉及到重传，这就是快速重传。

为了知道快速重传是重传全部还是某一包需要依赖SACK，它里面有一个数据段指出了接收端接受了哪些数据，这样发送者就可以选择数据重传了。

但是SACK无法处理ACK丢失引起的重传，它只能处理发送时包丢失的问题，如果发送成功，但是回复ACK丢失，就只能通过D-SACK(Duplicate-SACK)来解决。此外，它还能解决因为网络延迟导致的问题，如果某个包因为网络延迟而未到达，触发快速重传，发送第二个包，而后被延迟的包到达，便可以通过DSACK通知发送者引起重传的原因不是丢包，而是网络延迟。

如果每一次请求都要等待回复，那通信效率就会变得非常低效，此时我们需要通过窗口来解决。发送窗口维护了四个部分：

  • 1️⃣已发送且已确认
  • 2️⃣已发送但未确认
  • 3️⃣未发送但可发送
  • 4️⃣未发送且不可发送

同样的，接收窗口也维护了四个部分：

  • 1️⃣已使用
  • 2️⃣已接收且已确认
  • 3️⃣未接收但可接收
  • 4️⃣未接收且不可接收

通过这两个窗口，我们可以知道如何规划发送数据和接收数据。发送窗口的大小约等于接收窗口的大小，通过响应数据的windows参数指明接收端窗口的大小。

每次把发送端把ACK中指明的位置标记为已接收，同时右滑窗口；接收端对于接收到的数据同样右滑窗口来实现。

Netty

I/O

设计模式

常见的设计模式

算法与数据结构

排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
Java复制代码    public static void insertSort(int[] nums) {
        // [0, i]是有序的
        for (int i = 0; i < nums.length - 1; ++i) {
            int j = i + 1;
            int tmp = nums[i + 1];
            // 帮i+1找到一个合适的位置，并插入
            for (; j - 1 >= 0 && tmp < nums[j - 1]; --j) {
                nums[j] = nums[j - 1];
            }
            nums[j] = tmp;
        }
    }

    public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            int min = nums[i];
            int minIdx = i;
            // 在[i+1, nums.length-1]中找到小于nums[i]且最小的元素进行交换
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] < min) {
                    min = nums[j];
                    minIdx = j;
                }
            }
            nums[minIdx] = nums[i];
            nums[i] = min;
        }
    }

    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            // 不停地暴力交换
            for (int j = 0; j < nums.length - 1; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    public static void shellSort(int[] nums) {
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            // 同插入排序，但是每次处理的数据间隙是逐步减小的
            for (int i = 0; i + gap < nums.length; i += gap) {
                int tmp = nums[i + gap];
                int j = i + gap;
                for (; j - gap >= 0 && tmp < nums[j - gap]; j -= gap) {
                    nums[j] = nums[j - gap];
                }
                nums[j] = tmp;
            }
        }
    }

    public static void mergeSort(int[] nums) {
        mergeSort0(nums, 0, nums.length-1);
    }

    // [from, to]
    private static void mergeSort0(int[] nums, int from, int to) {
        if (from >= to) {
            return ;
        }
        int mid = (from + to) / 2;
        mergeSort0(nums, from, mid);
        mergeSort0(nums, mid+1, to);
        int[] tmp = new int[to-from+1];
        int idxA = from, idxB = mid+1, idx = 0;
        while (idxA <= mid && idxB <= to) {
            if (nums[idxA] < nums[idxB]) {
                tmp[idx++] = nums[idxA++];
            } else {
                tmp[idx++] = nums[idxB++];
            }
        }
        while (idxA <= mid) {
            tmp[idx++] = nums[idxA++];
        }
        while (idxB <= to) {
            tmp[idx++] = nums[idxB++];
        }
        System.arraycopy(tmp, 0, nums, from, tmp.length);
    }

    public static void quickSort(int[] nums) {
        quickSort0(nums, 0, nums.length-1);
    }

    // [from, to]
    private static void quickSort0(int[] nums, int from, int to) {
        if (from >= to) {
            return ;
        }
        int cmp = nums[from];
        int l = from, r = to;
        while (l < r) {
            while (l <= r && nums[l] <= cmp) {
                ++l;
            }
            while (l <= r && nums[r] > cmp) {
                --r;
            }
            if (l < r) {
                swap(nums, l, r);
            }
        }
        swap(nums, from, r);
        quickSort0(nums, from, r-1);
        quickSort0(nums, r+1, to);
    }

    public void add(int[] nums, int i, int val){
        nums[i] = val;
        int curIndex = i;
        while (curIndex > 0) {
            int parentIndex = (curIndex - 1) / 2;
            if (nums[parentIndex] < nums[curIndex])
                swap(nums, parentIndex, curIndex);
            else break;
            curIndex = parentIndex;
        }
    }

    public int remove(int[] nums, int size){
        int result = nums[0];
        nums[0] = nums[size - 1];
        int curIndex = 0;
        while (true) {
            int leftIndex = curIndex * 2 + 1;
            int rightIndex = curIndex * 2 + 2;
            if (leftIndex >= size) break;
            int maxIndex = leftIndex;
            if (rightIndex < size && nums[maxIndex] < nums[rightIndex])
                maxIndex = rightIndex;
            if (nums[curIndex] < nums[maxIndex])
                swap(nums, curIndex, maxIndex);
            else break;
            curIndex = maxIndex;
        }
        return result;
    }

    private static void swap(int[] nums, int idxA, int idxB) {
        int tmp = nums[idxA];
        nums[idxA] = nums[idxB];
        nums[idxB] = tmp;
    }

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%