Vic's blog
xushengli
2021-06-29

技术面试需要掌握的基础知识整理

# 技术面试知识点整理【目录】

说明：

1. 本文较长共整合27个专题，GitHub用户如果访问的比较慢的话，可以点击下面的链接进群下载本地PDF文件，或者继续在GitHub在线阅读

2. 点击此处进群免费获取PDF版本 (opens new window)

3. 目前还只同步部分内容至GitHub，后续会慢慢同步上来，可放心Ctrl+D

# 一、校招真题题解

# 前言

省略的代码：

import java.util.*;
1
public class Solution {
}
1
2
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
        }
    }
}
1
2
3
4
5
6
7

# 小米-小米Git

  • 重建多叉树
  • 使用 LCA
private class TreeNode {
    int id;
    List<TreeNode> childs = new ArrayList<>();
    TreeNode(int id) {
        this.id = id;
    }
}
public int getSplitNode(String[] matrix, int indexA, int indexB) {
    int n = matrix.length;
    boolean[][] linked = new boolean[n][n]; // 重建邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            linked[i][j] = matrix[i].charAt(j) == '1';
        }
    }
    TreeNode tree = constructTree(linked, 0);
    TreeNode ancestor = LCA(tree, new TreeNode(indexA), new TreeNode(indexB));
    return ancestor.id;
}
private TreeNode constructTree(boolean[][] linked, int root) {
    TreeNode tree = new TreeNode(root);
    for (int i = 0; i < linked[root].length; i++) {
        if (linked[root][i]) {
            linked[i][root] = false; //  因为题目给的邻接矩阵是双向的，在这里需要把它转为单向的
            tree.childs.add(constructTree(links, i));
        }
    }
    return tree;
}
private TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root.id == p.id || root.id == q.id) return root;
    TreeNode ancestor = null;
    int cnt = 0;
    for (int i = 0; i < root.childs.size(); i++) {
        TreeNode tmp = LCA(root.childs.get(i), p, q);
        if (tmp != null) {
            ancestor = tmp;
            cnt++;
        }
    }
    return cnt == 2 ? root : ancestor;
}
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

# 小米-懂二进制

对两个数进行异或，结果的二进制表示为 1 的那一位就是两个数不同的位。

public int countBitDiff(int m, int n) {
    return Integer.bitCount(m ^ n);
}
1
2
3

# 小米-中国牛市

背包问题，可以设一个大小为 2 的背包。

状态转移方程如下：

dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] } = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
1
public int calculateMax(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[3][n];
    for (int i = 1; i <= 2; i++) {
        int localMax = dp[i - 1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], prices[j] + localMax);
            localMax = Math.max(localMax, dp[i - 1][j] - prices[j]);
        }
    }
    return dp[2][n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12

# 微软-LUCKY STRING

  • 斐波那契数列可以预计算；
  • 从头到尾遍历字符串的过程，每一轮循环都使用一个 Set 来保存从 i 到 j 出现的字符，并且 Set 保证了字符都不同，因此 Set 的大小就是不同字符的个数。
Set<Integer> fibSet = new HashSet<>(Arrays.asList(1, 2, 3, 5, 8, 13, 21, 34, 55, 89));
Scanner in = new Scanner(System.in);
String str = in.nextLine();
int n = str.length();
Set<String> ret = new HashSet<>();
for (int i = 0; i < n; i++) {
    Set<Character> set = new HashSet<>();
    for (int j = i; j < n; j++) {
        set.add(str.charAt(j));
        int cnt = set.size();
        if (fibSet.contains(cnt)) {
            ret.add(str.substring(i, j + 1));
        }
    }
}
String[] arr = ret.toArray(new String[ret.size()]);
Arrays.sort(arr);
for (String s : arr) {
    System.out.println(s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 微软-Numeric Keypad

private static int[][] canReach = {
        {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, // 1
        {1, 0, 1, 1, 0, 1, 1, 0, 1, 1}, // 2
        {0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, // 3
        {1, 0, 0, 0, 1, 1, 1, 1, 1, 1}, // 4
        {1, 0, 0, 0, 0, 1, 1, 0, 1, 1}, // 5
        {0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // 6
        {1, 0, 0, 0, 0, 0, 0, 1, 1, 1}, // 7
        {1, 0, 0, 0, 0, 0, 0, 0, 1, 1}, // 8
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}  // 9
};
private static boolean isLegal(char[] chars, int idx) {
    if (idx >= chars.length || idx < 0) return true;
    int cur = chars[idx] - '0';
    int next = chars[idx + 1] - '0';
    return canReach[cur][next] == 1;
}
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = Integer.valueOf(in.nextLine());
    for (int i = 0; i < T; i++) {
        String line = in.nextLine();
        char[] chars = line.toCharArray();
        for (int j = 0; j < chars.length - 1; j++) {
            while (!isLegal(chars, j)) {
                if (--chars[j + 1] < '0') {
                    chars[j--]--;
                }
                for (int k = j + 2; k < chars.length; k++) {
                    chars[k] = '9';
                }
            }
        }
        System.out.println(new String(chars));
    }
}
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

# 微软-Spring Outing

下面以 N = 3，K = 4 来进行讨论。

初始时，令第 0 个地方成为待定地点，也就是呆在家里。

从第 4 个地点开始投票，每个人只需要比较第 4 个地方和第 0 个地方的优先级，里，如果超过半数的人选择了第 4 个地方，那么更新第 4 个地方成为待定地点。

从后往前不断重复以上步骤，不断更新待定地点，直到所有地方都已经投票。

上面的讨论中，先令第 0 个地点成为待定地点，是因为这样的话第 4 个地点就只需要和这个地点进行比较，而不用考虑其它情况。如果最开始先令第 1 个地点成为待定地点，那么在对第 2 个地点进行投票时，每个人不仅要考虑第 2 个地点与第 1 个地点的优先级，也要考虑与其后投票地点的优先级。

int N = in.nextInt();
int K = in.nextInt();
int[][] votes = new int[N][K + 1];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < K + 1; j++) {
        int place = in.nextInt();
        votes[i][place] = j;
    }
}
int ret = 0;
for (int place = K; place > 0; place--) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (votes[i][place] < votes[i][ret]) {
            cnt++;
        }
    }
    if (cnt > N / 2) {
        ret = place;
    }
}
System.out.println(ret == 0 ? "otaku" : ret);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 华为-最高分是多少

int N = in.nextInt();
int M = in.nextInt();
int[] scores = new int[N];
for (int i = 0; i < N; i++) {
    scores[i] = in.nextInt();
}
for (int i = 0; i < M; i++) {
    String str = in.next();
    if (str.equals("U")) {
        int id = in.nextInt() - 1;
        int newScore = in.nextInt();
        scores[id] = newScore;
    } else {
        int idBegin = in.nextInt() - 1;
        int idEnd = in.nextInt() - 1;
        int ret = 0;
        if (idBegin > idEnd) {
            int t = idBegin;
            idBegin = idEnd;
            idEnd = t;
        }
        for (int j = idBegin; j <= idEnd; j++) {
            ret = Math.max(ret, scores[j]);
        }
        System.out.println(ret);
    }
}
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

# 华为-简单错误记录

HashMap<String, Integer> map = new LinkedHashMap<>();
while (in.hasNextLine()) {
    String s = in.nextLine();
    String key = s.substring(s.lastIndexOf('\\') + 1);
    map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
}
List<Map.Entry<String, Integer>> list = new LinkedList<>(map.entrySet());
Collections.sort(list, (o1, o2) -> o2.getValue() - o1.getValue());
for (int i = 0; i < 8 && i < list.size(); i++) {
    String[] token = list.get(i).getKey().split(" ");
    String filename = token[0];
    String line = token[1];
    if (filename.length() > 16) filename = filename.substring(filename.length() - 16);
    System.out.println(filename + " " + line + " " + list.get(i).getValue());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 华为-扑克牌大小

public class Main {
    private Map<String, Integer> map = new HashMap<>();
    public Main() {
        map.put("3", 0);
        map.put("4", 1);
        map.put("5", 2);
        map.put("6", 3);
        map.put("7", 4);
        map.put("8", 5);
        map.put("9", 6);
        map.put("10", 7);
        map.put("J", 8);
        map.put("Q", 9);
        map.put("K", 10);
        map.put("A", 11);
        map.put("2", 12);
        map.put("joker", 13);
        map.put("JOKER ", 14);
    }
    private String play(String s1, String s2) {
        String[] token1 = s1.split(" ");
        String[] token2 = s2.split(" ");
        CardType type1 = computeCardType(token1);
        CardType type2 = computeCardType(token2);
        if (type1 == CardType.DoubleJoker) return s1;
        if (type2 == CardType.DoubleJoker) return s2;
        if (type1 == CardType.Bomb && type2 != CardType.Bomb) return s1;
        if (type2 == CardType.Bomb && type1 != CardType.Bomb) return s2;
        if (type1 != type2 || token1.length != token2.length) return "ERROR";
        for (int i = 0; i < token1.length; i++) {
            int val1 = map.get(token1[i]);
            int val2 = map.get(token2[i]);
            if (val1 != val2) return val1 > val2 ? s1 : s2;
        }
        return "ERROR";
    }
    private CardType computeCardType(String[] token) {
        boolean hasjoker = false, hasJOKER = false;
        for (int i = 0; i < token.length; i++) {
            if (token[i].equals("joker")) hasjoker = true;
            else if (token[i].equals("JOKER")) hasJOKER = true;
        }
        if (hasjoker && hasJOKER) return CardType.DoubleJoker;
        int maxContinueLen = 1;
        int curContinueLen = 1;
        String curValue = token[0];
        for (int i = 1; i < token.length; i++) {
            if (token[i].equals(curValue)) curContinueLen++;
            else {
                curContinueLen = 1;
                curValue = token[i];
            }
            maxContinueLen = Math.max(maxContinueLen, curContinueLen);
        }
        if (maxContinueLen == 4) return CardType.Bomb;
        if (maxContinueLen == 3) return CardType.Triple;
        if (maxContinueLen == 2) return CardType.Double;
        boolean isStraight = true;
        for (int i = 1; i < token.length; i++) {
            if (map.get(token[i]) - map.get(token[i - 1]) != 1) {
                isStraight = false;
                break;
            }
        }
        if (isStraight && token.length == 5) return CardType.Straight;
        return CardType.Sigal;
    }
    private enum CardType {
        DoubleJoker, Bomb, Sigal, Double, Triple, Straight;
    }
    public static void main(String[] args) {
        Main main = new Main();
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String[] token = s.split("-");
            System.out.println(main.play(token[0], token[1]));
        }
    }
}
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

# 去哪儿-二分查找

对于有重复元素的有序数组，二分查找需要注意以下要点：

  • if (val <= A[m]) h = m;
  • 因为 h 的赋值为 m 而不是 m - 1，因此 while 循环的条件也就为 l < h。（如果是 m - 1 循环条件为 l <= h）
public int getPos(int[] A, int n, int val) {
    int l = 0, h = n - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (val <= A[m]) h = m;
        else l = m + 1;
    }
    return A[h] == val ? h : -1;
}
1
2
3
4
5
6
7
8
9

# 去哪儿-首个重复字符

public char findFirstRepeat(String A, int n) {
    boolean[] hasAppear = new boolean[256];
    for (int i = 0; i < n; i++) {
        char c = A.charAt(i);
        if(hasAppear[c]) return c;
        hasAppear[c] = true;
    }
    return ' ';
}
1
2
3
4
5
6
7
8
9

# 去哪儿-寻找Coder

public String[] findCoder(String[] A, int n) {
    List<Pair<String, Integer>> list = new ArrayList<>();
    for (String s : A) {
        int cnt = 0;
        String t = s.toLowerCase();
        int idx = -1;
        while (true) {
            idx = t.indexOf("coder", idx + 1);
            if (idx == -1) break;
            cnt++;
        }
        if (cnt != 0) {
            list.add(new Pair<>(s, cnt));
        }
    }
    Collections.sort(list, (o1, o2) -> (o2.getValue() - o1.getValue()));
    String[] ret = new String[list.size()];
    for (int i = 0; i < list.size(); i++) {
        ret[i] = list.get(i).getKey();
    }
    return ret;
}
// 牛客网无法导入 javafx.util.Pair，这里就自己实现一下 Pair 类
private class Pair<T, K> {
    T t;
    K k;
    Pair(T t, K k) {
        this.t = t;
        this.k = k;
    }
    T getKey() {
        return t;
    }
    K getValue() {
        return k;
    }
}
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

# 美团-最大差值

贪心策略。

public int getDis(int[] A, int n) {
    int max = 0;
    int soFarMin = A[0];
    for (int i = 1; i < n; i++) {
        if(soFarMin > A[i]) soFarMin = A[i];
        else max = Math.max(max, A[i]- soFarMin);
    }
    return max;
}
1
2
3
4
5
6
7
8
9

# 美团-棋子翻转

public int[][] flipChess(int[][] A, int[][] f) {
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int[] ff : f) {
        for (int[] dd : direction) {
            int r = ff[0] + dd[0] - 1, c = ff[1] + dd[1] - 1;
            if(r < 0 || r > 3 || c < 0 || c > 3) continue;
            A[r][c] ^= 1;
        }
    }
    return A;
}
1
2
3
4
5
6
7
8
9
10
11

# 美团-拜访

private Set<String> paths;
private List<Integer> curPath;
public int countPath(int[][] map, int n, int m) {
    paths = new HashSet<>();
    curPath = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 1) {
                map[i][j] = -1;
                int[][] leftRightDirection = {{1, 0}, {-1, 0}};
                int[][] topDownDirection = {{0, 1}, {0, -1}};
                for (int[] lr : leftRightDirection) {
                    for (int[] td : topDownDirection) {
                        int[][] directions = {lr, td};
                        backtracking(map, n, m, i, j, directions);
                    }
                }
                return paths.size();
            }
        }
    }
    return 0;
}
private void backtracking(int[][] map, int n, int m, int r, int c, int[][] directions) {
    if (map[r][c] == 2) {
        String path = "";
        for (int num : curPath) {
            path += num;
        }
        paths.add(path);
        return;
    }
    for (int i = 0; i < directions.length; i++) {
        int nextR = r + directions[i][0];
        int nextC = c + directions[i][1];
        if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= m || map[nextR][nextC] == -1) continue;
        map[nextR][nextC] = map[nextR][nextC] == 2 ? 2 : -1;
        curPath.add(nextR);
        curPath.add(nextC);
        backtracking(map, n, m, nextR, nextC, directions);
        curPath.remove(curPath.size() - 1);
        curPath.remove(curPath.size() - 1);
        map[nextR][nextC] = map[nextR][nextC] == 2 ? 2 : 0;
    }
}
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

# 美团-直方图内最大矩形

public int countArea(int[] A, int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        int min = A[i];
        for (int j = i; j < n; j++) {
            min = Math.min(min, A[j]);
            max = Math.max(max, min * (j - i + 1));
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11

# 美团-字符串计数

字符串都是小写字符，可以把字符串当成是 26 进制。但是字典序的比较和普通的整数比较不同，是从左往右进行比较，例如 “ac” 和 “abc”，字典序的比较结果为 “ac” > “abc”，如果按照整数方法比较，因为 “abc” 是三位数，显然更大。

由于两个字符串的长度可能不想等，在 s1 空白部分和 s2 对应部分进行比较时，应该把 s1 的空白部分看成是 ‘a’ 字符进行填充的。

还有一点要注意的是，s1 到 s2 长度为 leni 的字符串个数只比较前面 i 个字符。例如 ‘aaa’ 和 ‘bbb’ ，长度为 2 的个数为 ‘aa’ 到 ‘bb’ 的字符串个数，不需要考虑后面部分的字符。

在统计个数时，从 len1 开始一直遍历到最大合法长度，每次循环都统计长度为 i 的子字符串个数。

String s1 = in.next();
String s2 = in.next();
int len1 = in.nextInt();
int len2 = in.nextInt();
int len = Math.min(s2.length(), len2);
int[] subtractArr = new int[len];
for (int i = 0; i < len; i++) {
    char c1 = i < s1.length() ? s1.charAt(i) : 'a';
    char c2 = s2.charAt(i);
    subtractArr[i] = c2 - c1;
}
int ret = 0;
for (int i = len1; i <= len; i++) {
    for (int j = 0; j < i; j++) {
        ret += subtractArr[j] * Math.pow(26, i - j - 1);
    }
}
System.out.println(ret - 1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 美团-平均年龄

int W = in.nextInt();
double Y = in.nextDouble();
double x = in.nextDouble();
int N = in.nextInt();
while (N-- > 0) {
    Y++; // 老员工每年年龄都要加 1
    Y += (21 - Y) * x;
}
System.out.println((int) Math.ceil(Y));
1
2
3
4
5
6
7
8
9

# 百度-罪犯转移

部分和问题，将每次求的部分和缓存起来。

int n = in.nextInt();
int t = in.nextInt();
int c = in.nextInt();
int[] values = new int[n];
for (int i = 0; i < n; i++) {
    values[i] = in.nextInt();
}
int cnt = 0;
int totalValue = 0;
for (int s = 0, e = c - 1; e < n; s++, e++) {
    if (s == 0) {
        for (int j = 0; j < c; j++) totalValue += values[j];
    } else {
        totalValue = totalValue - values[s - 1] + values[e];
    }
    if (totalValue <= t) cnt++;
}
System.out.println(cnt);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 百度-裁减网格纸

int n = in.nextInt();
int minX, minY, maxX, maxY;
minX = minY = Integer.MAX_VALUE;
maxX = maxY = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    int x = in.nextInt();
    int y = in.nextInt();
    minX = Math.min(minX, x);
    minY = Math.min(minY, y);
    maxX = Math.max(maxX, x);
    maxY = Math.max(maxY, y);
}
System.out.println((int) Math.pow(Math.max(maxX - minX, maxY - minY), 2));
1
2
3
4
5
6
7
8
9
10
11
12
13

# 百度-钓鱼比赛

P ( 至少钓一条鱼 ) = 1 - P ( 一条也钓不到 )

坑：读取概率矩阵的时候，需要一行一行进行读取，而不能直接用 in.nextDouble()。

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) {
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        int t = in.nextInt();
        in.nextLine(); // 坑
        double pcc = 0.0;
        double sum = 0.0;
        for (int i = 1; i <= n; i++) {
            String[] token = in.nextLine().split(" "); // 坑
            for (int j = 1; j <= m; j++) {
                double p = Double.parseDouble(token[j - 1]);
                //  double p = in.nextDouble();
                sum += p;
                if (i == x && j == y) {
                    pcc = p;
                }
            }
        }
        double pss = sum / (n * m);
        pcc = computePOfIRT(pcc, t);
        pss = computePOfIRT(pss, t);
        System.out.println(pcc > pss ? "cc" : pss > pcc ? "ss" : "equal");
        System.out.printf("%.2f\n", Math.max(pcc, pss));
    }
}
// compute probability of independent repeated trials
private static double computePOfIRT(double p, int t) {
    return 1 - Math.pow((1 - p), t);
}
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

# 百度-蘑菇阵

这题用回溯会超时，需要用 DP。

dp[i][j] 表示到达 (i,j) 位置不会触碰蘑菇的概率。对于 N*M 矩阵，如果 i == N || j == M，那么 (i,j) 只能有一个移动方向；其它情况下能有两个移动方向。

考虑以下矩阵，其中第 3 行和第 3 列只能往一个方向移动，而其它位置可以有两个方向移动。

int N = in.nextInt();
int M = in.nextInt();
int K = in.nextInt();
boolean[][] mushroom = new boolean[N][M];
while (K-- > 0) {
    int x = in.nextInt();
    int y = in.nextInt();
    mushroom[x - 1][y - 1] = true;
}
double[][] dp = new double[N][M];
dp[0][0] = 1;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (mushroom[i][j]) dp[i][j] = 0;
        else {
            double cur = dp[i][j];
            if (i == N - 1 && j == M - 1) break;
            if (i == N - 1) dp[i][j + 1] += cur;
            else if (j == M - 1) dp[i + 1][j] += cur;
            else {
                dp[i][j + 1] += cur / 2;
                dp[i + 1][j] += cur / 2;
            }
        }
    }
}
System.out.printf("%.2f\n", dp[N - 1][M - 1]);
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

# 二、计算机网络

# （一）、概述

# 网络的网络

网络把主机连接起来，而互联网是把多种不同的网络连接起来，因此互联网是网络的网络。

# ISP

互联网服务提供商 ISP 可以从互联网管理机构获得许多 IP 地址，同时拥有通信线路以及路由器等联网设备，个人或机构向 ISP 缴纳一定的费用就可以接入互联网。

目前的互联网是一种多层次 ISP 结构，ISP 根据覆盖面积的大小分为主干 ISP、地区 ISP 和本地 ISP。

互联网交换点 IXP 允许两个 ISP 直接相连而不用经过第三个 ISP。

# 互联网的组成

  1. 边缘部分：所有连接在互联网上的主机，用户可以直接使用；
  2. 核心部分：由大量的网络和连接这些网络的路由器组成，为边缘部分的主机提供服务。

# 主机之间的通信方式

  1. 客户-服务器（C/S）：客户是服务的请求方，服务器是服务的提供方。
  2. 对等（P2P）：不区分客户和服务器。

# 电路交换与分组交换

###. 电路交换

电路交换用于电话通信系统，两个用户要通信之前需要建立一条专用的物理链路，并且在整个通信过程中始终占用该链路。由于通信的过程中不可能一直在使用传输线路，因此电路交换对线路的利用率很低，往往不到 10%。

###. 报文交换

报文交换用于邮局通信系统，邮局接收到一份报文之后，先存储下来，然后把相同目的地的报文一起转发到下一个目的地，这个过程就是存储转发过程。

###. 分组交换

分组交换也使用了存储转发，但是转发的是分组而不是报文。把整块数据称为一个报文，由于一个报文可能很长，需要先进行切分，来满足分组能处理的大小。在每个切分的数据前面加上首部之后就成为了分组，首部包含了目的地址和源地址等控制信息。

存储转发允许在一条传输线路上传送多个主机的分组，也就是说两个用户之间的通信不需要占用端到端的线路资源。

相比于报文交换，由于分组比报文更小，因此分组交换的存储转发速度更加快速。

# 时延

总时延 = 发送时延 + 传播时延 + 处理时延 + 排队时延

###. 发送时延

主机或路由器发送数据帧所需要的时间。

其中 l 表示数据帧的长度，v 表示发送速率。

###. 传播时延

电磁波在信道中传播一定的距离需要花费的时间，电磁波传播速度接近光速。

其中 l 表示信道长度，v 表示电磁波在信道上的传播速率。

###. 处理时延

主机或路由器收到分组时进行处理所需要的时间，例如分析首部、从分组中提取数据部、进行差错检验或查找适当的路由等。

###. 排队时延

分组在路由器的输入队列和输出队列中排队等待的时间，取决于网络当前的通信量。

# 计算机网络体系结构*

###. 七层协议

如图 a 所示，其中表示层和会话层用途如下：

  • 表示层：信息的语法、语义以及它们的关联，如加密解密、转换翻译、压缩解压缩；
  • 会话层：不同机器上的用户之间建立及管理会话。

###. 五层协议

  • 应用层：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等。数据单位为报文。
  • 运输层：提供的是进程间的通用数据传输服务。由于应用层协议很多，定义通用的运输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服务，数据单位为用户数据报。TCP 主要提供完整性服务，UDP 主要提供及时性服务。
  • 网络层：为主机之间提供数据传输服务，而运输层协议是为主机中的进程提供服务。网络层把运输层传递下来的报文段或者用户数据报封装成分组。
  • 数据链路层：网络层针对的还是主机之间的数据传输服务，而主机之间可以有很多链路，链路层协议就是为同一链路的结点提供服务。数据链路层把网络层传来的分组封装成帧。
  • 物理层：考虑的是怎样在传输媒体上传输数据比特流，而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异，使数据链路层感觉不到这些差异。

###. 数据在各层之间的传递过程

在向下的过程中，需要添加下层协议所需要的首部或者尾部，而在向上的过程中不断拆开首部和尾部。

路由器只有下面三层协议，因为路由器位于网络核心中，不需要为进程或者应用程序提供服务，因此也就不需要运输层和应用层。

###. TCP/IP 体系结构

它只有四层，相当于五层协议中数据链路层和物理层合并为网络接口层。

现在的 TCP/IP 体系结构不严格遵循 OSI 分层概念，应用层可能会直接使用 IP 层或者网络接口层。

TCP/IP 协议族是一种沙漏形状，中间小两边大，IP 协议在其中占用举足轻重的地位。

# （二）、物理层

# 通信方式

  1. 单向通信，又称为单工通信；
  2. 双向交替通信，又称为半双工通信；
  3. 双向同时通信，又称为全双工通信。

# 带通调制

模拟信号是连续的信号，数字信号是离散的信号。带通调制把数字信号转换为模拟信号。

# 信道复用技术

###. 频分复用、时分复用

频分复用的所有用户在相同的时间占用不同的频率带宽资源；时分复用的所有用户在不同的时间占用相同的频率带宽资源。

使用这两种方式进行通信，在通信的过程中用户会一直占用一部分信道资源。但是由于计算机数据的突发性质，通信过程没必要一直占用信道资源而不让出给其它用户使用，因此这两种方式对信道的利用率都不高。

###. 统计时分复用

是对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

###. 波分复用

光的频分复用。由于光的频率很高，因此习惯上用波长而不是频率来表示所使用的光载波。

###. 码分复用

# （三）、数据链路层

# 信道分类

  • 点对点信道：一对一通信方式；
  • 广播信道：一对多通信方式。

# 三个基本问题

###. 封装成帧

将网络层传下来的分组添加首部和尾部，用于标记帧的开始和结束。

###. 透明传输

透明表示一个实际存在的事物看起来好像不存在一样。

帧使用首部和尾部进行定界，如果帧的数据部分含有和首部尾部相同的内容，那么帧的开始和结束位置就会被错误的判定。需要在数据部分出现首部尾部相同的内容前面插入转义字符，如果出现转移字符，那么就在转义字符前面再加个转义字符，在接收端进行处理之后可以还原出原始数据。这个过程透明传输的内容是转义字符，用户察觉不到转义字符的存在。

###. 差错检测

目前数据链路层广泛使用了循环冗余检验（CRC）来检查比特差错。

# 局域网

局域网是典型的一种广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限。

可以按照网络拓扑对局域网进行分类：

# PPP 协议

用于点对点信道中。互联网用户通常需要连接到某个 ISP 之后才能接入到互联网，PPP 协议是用户计算机和 ISP 进行通信时所使用的数据链路层协议。

在 PPP 的帧中：

  • F 字段为帧的定界符
  • A 和 C 字段暂时没有意义
  • FCS 字段是使用 CRC 的检验序列
  • 信息部分的长度不超过 1500

# CSMA/CD 协议*

用于广播信道中。在广播信道上，同一时间只能允许一台计算机发送数据。

CSMA/CD 表示载波监听多点接入 / 碰撞检测。

  • 多点接入 ：说明这是总线型网络，许多计算机以多点的方式连接到总线上。
  • 载波监听 ：每个站都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
  • 碰撞检测 ：在发送中，如果监听到信道已有其它站正在发送数据，就表示发生了碰撞。虽然每一个站在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。

记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为 争用期 。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用 截断二进制指数退避算法 来确定，从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

# 扩展局域网*

###. 在物理层进行扩展

使用集线器进行扩展。

集线器的主要功能是对接收到的信号进行放大，以扩大网络的传输距离。

集线器不能根据 MAC 地址进行转发，而是以广播的方式发送数据帧。

集线器是一种共享式的传输设备，意味着同一时刻只能传输一组数据帧。

###. 在链路层进行扩展

最开始使用的是网桥，它收到一个帧时，根据帧的 MAC 地址，查找网桥中的地址表，确定帧转发的接口。

网桥不是共享式设备，因此性能比集线器这种共享式设备更高。

交换机的问世很快就淘汰了网桥，它实质上是一个多接口网桥，而网桥是两接口。交换机的每个接口都能直接与一个主机或者另一个交换机相连，并且一般都工作在全双工方式。

交换机具有自学习能力，学习的是交换表的内容。交换表中存储着 MAC 地址到接口的映射。下图中，交换机有 4 个接口，主机 A 向主机 B 发送数据帧时，交换机把主机 A 到接口 1 的映射写入交换表中。为了发送数据帧到 B，先查交换表，此时没有主机 B 的表项，那么主机 A 就发送广播帧，主机 C 和主机 D 会丢弃该帧。主机 B 收下之后，查找交换表得到主机 A 映射的接口为 1，就发送数据帧到接口 1，同时交换机添加主机 B 到接口 3 的映射。

###. 虚拟局域网

虚拟局域网可以建立与物理位置无关的逻辑组，只有在同一个虚拟局域网中的成员才会收到链路层广播信息，例如下图中 (A1, A2, A3, A4) 属于一个虚拟局域网，A1 发送的广播会被 A2、A3、A4 收到，而其它站点收不到。

# MAC 层*

MAC 地址是 6 字节（48 位）的地址，用于唯一标识网络适配器（网卡），一台主机拥有多少个适配器就有多少个 MAC 地址，例如笔记本电脑普遍存在无线网络适配器和有线网络适配器。

在 MAC 帧中：

  • 类型 ：标记上层使用的协议；
  • 数据 ：长度在 46-1500 之间，如果太小则需要填充；
  • FCS ：帧检验序列，使用的是 CRC 检验方法；
  • 前同步码 ：只是为了计算 FCS 临时加入的，计算结束之后会丢弃。

# （四）、网络层

# 网际协议 IP 概述

因为网络层是整个互联网的核心，因此应当让网络层尽可能简单。网络层向上只提供简单灵活的、无连接的、尽最大努力交互的数据报服务。

使用 IP 协议，可以把异构的物理网络连接起来，使得在网络层看起来好像是一个统一的网络。

与 IP 协议配套使用的还有三个协议：

  • 地址解析协议 ARP（Address Resolution Protocol）
  • 网际控制报文协议 ICMP（Internet Control Message Protocol）
  • 网际组管理协议 IGMP（Internet Group Management Protocol）

# IP 数据报格式

  • 版本 : 有 4（IPv4）和 6（IPv6）两个值；
  • 首部长度 : 占 4 位，因此最大值为 15。值为 1 表示的是 1 个 32 位字的长度，也就是 4 字节。因为首部固定长度为 20 字节，因此该值最小为 5。如果可选字段的长度不是 4 字节的整数倍，就用尾部的填充部分来填充。
  • 区分服务 : 用来获得更好的服务，一般情况下不使用。
  • 总长度 : 包括首部长度和数据部分长度。
  • 标识 : 在数据报长度过长从而发生分片的情况下，相同数据报的不同分片具有相同的标识符。
  • 片偏移 : 和标识符一起，用于发生分片的情况。片偏移的单位为 8 字节。

  • 生存时间 ：TTL，它的存在是为了防止无法交付的数据报在互联网中不断兜圈子。以路由器跳数为单位，当 TTL 为 0 时就丢弃数据报。
  • 协议 ：指出携带的数据应该上交给哪个协议进行处理，例如 ICMP、TCP、UDP 等。
  • 首部检验和 ：因为数据报每经过一个路由器，都要重新计算检验和，因此检验和不包含数据部分可以减少计算的工作量。

# IP 地址编址方式

IP 地址的编址方式经历了三个历史阶段：

  • 分类
  • 子网划分
  • 无分类

###. 分类

由两部分组成，网络号和主机号，其中不同分类具有不同的网络号长度，并且是固定的。

IP 地址 ::= {< 网络号 >, < 主机号 >}

###. 子网划分

通过在主机号字段中拿一部分作为子网号，把两级 IP 地址划分为三级 IP 地址。注意，外部网络看不到子网的存在。

IP 地址 ::= {< 网络号 >, < 子网号 >, < 主机号 >}

要使用子网，必须配置子网掩码。一个 B 类地址的默认子网掩码为 255.255.0.0，如果 B 类地址的子网占两个比特，那么子网掩码为 11111111 11111111 11000000 00000000，也就是 255.255.192.0。

###. 无分类

无分类编址 CIDR 消除了传统 A 类、B 类和 C 类地址以及划分子网的概念，使用网络前缀和主机号来对 IP 地址进行编码，网络前缀的长度可以根据需要变化。

IP 地址 ::= {< 网络前缀号 >, < 主机号 >}

CIDR 的记法上采用在 IP 地址后面加上网络前缀长度的方法，例如 128.14.35.7/20 表示前 20 位为网络前缀。

CIDR 的地址掩码可以继续称为子网掩码，子网掩码首 1 长度为网络前缀的长度。

一个 CIDR 地址块中有很多地址，一个 CIDR 表示的网络就可以表示原来的很多个网络，并且在路由表中只需要一个路由就可以代替原来的多个路由，减少了路由表项的数量。把这种通过使用网络前缀来减少路由表项的方式称为路由聚合，也称为 构成超网 。

在路由表中的项目由“网络前缀”和“下一跳地址”组成，在查找时可能会得到不止一个匹配结果，应当采用最长前缀匹配来确定应该匹配哪一个。

# IP 地址和 MAC 地址

网络层实现主机之间的通信，而链路层实现具体每段链路之间的通信。因此在通信过程中，IP 数据报的源地址和目的地址始终不变，而 MAC 地址随着链路的改变而改变。

# 地址解析协议 ARP

实现由 IP 地址得到 MAC 地址。

每个主机都有一个 ARP 高速缓存，里面有本局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。

如果主机 A 知道主机 B 的 IP 地址，但是 ARP 高速缓存中没有该 IP 地址到 MAC 地址的映射，此时主机 A 通过广播的方式发送 ARP 请求分组，主机 B 收到该请求后会发送 ARP 响应分组给主机 A 告知其 MAC 地址，随后主机 A 向其高速缓存中写入主机 B 的 IP 地址到硬件地址的映射。

# 路由器的结构

路由器从功能上可以划分为：路由选择和分组转发。

分组转发结构由三个部分组成：交换结构、一组输入端口和一组输出端口。

# 路由器分组转发流程

  1. 从数据报的首部提取目的主机的 IP 地址 D，得到目的网络地址 N。
  2. 若 N 就是与此路由器直接相连的某个网络地址，则进行直接交付；
  3. 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给表中所指明的下一跳路由器；
  4. 若路由表中有到达网络 N 的路由，则把数据报传送给路由表中所指明的下一跳路由器；
  5. 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；
  6. 报告转发分组出错。

# 路由选择协议

互联网使用的路由选择协议都是自适应的，能随着网络通信量和拓扑结构的变化而自适应地进行调整。

互联网可以划分为许多较小的自治系统 AS，一个 AS 可以使用一种和别的 AS 不同的路由选择协议。

可以把路由选择协议划分为两大类：

  • 内部网关协议 IGP（Interior Gateway Protocol）：在 AS 内部使用，如 RIP 和 OSPF。
  • 外部网关协议 EGP（External Gateway Protocol）：在 AS 之间使用，如 BGP。

###. 内部网关协议 RIP

RIP 是一种分布式的基于距离向量的路由选择协议。距离是指跳数，直接相连的路由器跳数为 1，跳数最多为 15，超过 15 表示不可达。

RIP 按固定的时间间隔仅和相邻路由器交换自己的路由表，经过若干次交换之后，所有路由器最终会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器地址。

距离向量算法：

  • 对地址为 X 的相邻路由器发来的 RIP 报文，先修改报文中的所有项目，把下一跳字段中的地址改为 X，并把所有的距离字段加 1；
  • 对修改后的 RIP 报文中的每一个项目，进行以下步骤：
    • 若原来的路由表中没有目的网络 N，则把该项目添加到路由表中；
    • 否则：若下一跳路由器地址是 X，则把收到的项目替换原来路由表中的项目；否则：若收到的项目中的距离 d 小于路由表中的距离，则进行更新（例如原始路由表项为 Net2, 5, P，新表项为 Net2, 4, X，则更新）；否则什么也不做。
  • 若 3 分钟还没有收到相邻路由器的更新路由表，则把该相邻路由器标为不可达，即把距离置为 16。

RIP 协议实现简单，开销小，但是 RIP 能使用的最大距离为 15，限制了网络的规模。并且当网络出现故障时，要经过比较长的时间才能将此消息传送到所有路由器。

###. 内部网关协议 OSPF

开放最短路径优先 OSPF，是为了克服 RIP 的缺点而开发出来的。

开放表示 OSPF 不受某一家厂商控制，而是公开发表的；最短路径优先表示使用了 Dijkstra 提出的最短路径算法 SPF。

OSPF 具有以下特点：

  • 向本自治系统中的所有路由器发送信息，这种方法是洪泛法。
  • 发送的信息就是与相邻路由器的链路状态，链路状态包括与哪些路由器相连以及链路的度量，度量用费用、距离、时延、带宽等来表示。
  • 只有当链路状态发生变化时，路由器才会发送信息。

所有路由器都具有全网的拓扑结构图，并且是一致的。相比于 RIP，OSPF 的更新过程收敛的很快。

###. 外部网关协议 BGP

AS 之间的路由选择很困难，主要是互联网规模很大。并且各个 AS 内部使用不同的路由选择协议，就无法准确定义路径的度量。并且 AS 之间的路由选择必须考虑有关的策略，比如有些 AS 不愿意让其它 AS 经过。

BGP 只能寻找一条比较好的路由，而不是最佳路由。它采用路径向量路由选择协议。

每个 AS 都必须配置 BGP 发言人，通过在两个相邻 BGP 发言人之间建立 TCP 连接来交换路由信息。

# 网际控制报文协议 ICMP

ICMP 是为了更有效地转发 IP 数据报和提高交付成功的机会。它封装在 IP 数据报中，但是不属于高层协议。

ICMP 报文分为差错报告报文和询问报文。

# 分组网间探测 PING

PING 是 ICMP 的一个重要应用，主要用来测试两台主机之间的连通性。

Ping 发送的 IP 数据报封装的是无法交付的 UDP 用户数据报。

Ping 的过程：

  1. 源主机向目的主机发送一连串的 IP 数据报。第一个数据报 P1 的生存时间 TTL 设置为 1，但 P1 到达路径上的第一个路由器 R1 时，R1 收下它并把 TTL 减 1，此时 TTL 等于 0，R1 就把 P1 丢弃，并向源主机发送一个 ICMP 时间超过差错报告报文；
  2. 源主机接着发送第二个数据报 P2，并把 TTL 设置为 2。P2 先到达 R1，R1 收下后把 TTl 减 1 再转发给 R2，R2 收下后也把 TTL 减 1，由于此时 TTL 等于 0，R2 就丢弃 P2，并向源主机发送一个 ICMP 时间超过差错报文。
  3. 不断执行这样的步骤，知道最后一个数据报刚刚到达目的主机，主机不转发数据报，也不把 TTL 值减 1。但是因为数据报封装的是无法交付的 UDP，因此目的主机要向源主机发送 ICMP 终点不可达差错报告报文。
  4. 之后源主机知道了到达目的主机所经过的路由器 IP 地址以及到达每个路由器的往返时间。

# 虚拟专用网 VPN

由于 IP 地址的紧缺，一个机构能申请到的 IP 地址数往往远小于本机构所拥有的主机数。并且一个机构并不需要把所有的主机接入到外部的互联网中，机构内的计算机可以使用仅在本机构有效的 IP 地址（专用地址）。

有三个专用地址块：

  • 10.0.0.0 ~ 10.255.255.255
  • 172.16.0.0 ~ 172.31.255.255
  • 192.168.0.0 ~ 192.168.255.255

VPN 使用公用的互联网作为本机构各专用网之间的通信载体。专用指机构内的主机只与本机构内的其它主机通信；虚拟指“好像是”，而实际上并不是，它有经过公用的互联网。

下图中，场所 A 和 B 的通信部经过互联网，如果场所 A 的主机 X 要和另一个场所 B 的主机 Y 通信，IP 数据报的源地址是 10.1.0.1，目的地址是 10.2.0.3。数据报先发送到与互联网相连的路由器 R1，R1 对内部数据进行加密，然后重新加上数据报的首部，源地址是路由器 R1 的全球地址 125.1.2.3，目的地址是路由器 R2 的全球地址 194.4.5.6。路由器 R2 收到数据报后将数据部分进行解密，恢复原来的数据报，此时目的地址为 10.2.0.3，就交付给 Y。

# 网络地址转换 NAT

专用网内部的主机使用本地 IP 地址又想和互联网上的主机通信时，可以使用 NAT 来将本地 IP 转换为全球 IP。

在以前，NAT 将本地 IP 和全球 IP 一一对应，这种方式下拥有 n 个全球 IP 地址的专用网内最多只可以同时有 n 台主机接入互联网。为了更有效地利用全球 IP 地址，现在常用的 NAT 转换表把运输层的端口号也用上了，使得多个专用网内部的主机共用一个全球 IP 地址。使用端口号的 NAT 也叫做网络地址与端口转换 NAPT。

# （五）、传输层

网络层只把分组发送到目的主机，但是真正通信的并不是主机而是主机中的进程。运输层提供了进程间的逻辑通信，运输层向高层用户屏蔽了下面网络层的核心细节，使应用程序看见的好像在两个运输层实体之间有一条端到端的逻辑通信信道。

# UDP 和 TCP 的特点

用户数据报协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部）。

传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块）。

# UDP 首部格式

首部字段只有 8 个字节，包括源端口、目的端口、长度、检验和。12 字节的伪首部是为了计算检验和临时添加的。

# TCP 首部格式

  • 序号 ：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。
  • 确认号 ：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。
  • 数据偏移 ：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。
  • 确认 ACK ：当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。
  • 同步 SYN ：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。
  • 终止 FIN ：用来释放一个连接，当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放运输连接。
  • 窗口 ：窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。

# TCP 的三次握手

假设 A 为客户端，B 为服务器端。

  1. 首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。
  2. A 向 B 发送连接请求报文段，SYN=1，ACK=0，选择一个初始的序号 x。
  3. B 收到连接请求报文段，如果同意建立连接，则向 A 发送连接确认报文段，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。
  4. A 收到 B 的连接确认报文段后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。
  5. B 收到 A 的确认后，连接建立。

三次握手的原因

为了防止失效的连接请求到达服务器，让服务器错误打开连接。

失效的连接请求是指，客户端发送的连接请求在网络中滞留，客户端因为没及时收到服务器端发送的连接确认，因此就重新发送了连接请求。滞留的连接请求并不是丢失，之后还是会到达服务器。如果不进行第三次握手，那么服务器会误认为客户端重新请求连接，然后打开了连接。但是并不是客户端真正打开这个连接，因此客户端不会给服务器发送数据，这个连接就白白浪费了。

# TCP 的四次挥手

以下描述不讨论序号和确认号，因为序号和确认号的规则比较简单。并且不讨论 ACK，因为 ACK 在连接建立之后都为 1。

  1. A 发送连接释放报文段，FIN=1；
  2. B 收到之后发出确认，此时 TCP 属于半关闭状态，B 能向 A 发送数据但是 A 不能向 B 发送数据；
  3. 当 B 要不再需要连接时，发送连接释放请求报文段，FIN=1
  4. A 收到后发出确认，进入 TIME-WAIT 状态，等待 2MSL 时间后释放连接。
  5. B 收到 A 的确认后释放连接。

四次挥手的原因

客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。

TIME_WAIT

客户端接收到服务器端的 FIN 报文后进入此状态，此时并不是直接进入 CLOSED 状态，还需要等待一个时间计时器设置的时间 2MSL。这么做有两个理由：

  1. 确保最后一个确认报文段能够到达。如果 B 没收到 A 发送来的确认报文段，那么就会重新发送连接释放请求报文段，A 等待一段时间就是为了处理这种情况的发生。
  2. 等待一段时间是为了让本连接持续时间内所产生的所有报文段都从网络中消失，使得下一个新的连接不会出现旧的连接请求报文段。

# TCP 滑动窗口

窗口是缓存的一部分，用来暂时存放字节流。发送方和接收方各有一个窗口，接收方通过 TCP 报文段中的窗口字段告诉发送方自己的窗口大小，发送方根据这个值和其它信息设置自己的窗口大小。

发送窗口内的字节都允许被发送，接收窗口内的字节都允许被接收。如果发送窗口左部的字节已经发送并且收到了确认，那么就将发送窗口向右滑动一定距离，直到左部第一个字节不是已发送并且已确认的状态；接收窗口的滑动类似，接收窗口左部字节已经发送确认并交付主机，就向右滑动接收窗口。

接收窗口只会对窗口内最后一个按序到达的字节进行确认，例如接收窗口已经收到的字节为 {31, 32, 34, 35}，其中 {31, 32} 按序到达，而 {34, 35} 就不是，因此只对字节 32 进行确认。发送方得到一个字节的确认之后，就知道这个字节之前的所有字节都已经被接收。

# TCP 可靠传输

TCP 使用超时重传来实现可靠传输：如果一个已经发送的报文段在超时时间内没有收到确认，那么就重传这个报文段。

一个报文段从发送再到接收到确认所经过的时间称为往返时间 RTT，加权平均往返时间 RTTs 计算如下：

超时时间 RTO 应该略大于 RTTs，TCP 使用的超时时间计算如下：

其中 RTTd 为偏差。

# TCP 流量控制

流量控制是为了控制发送方发送速率，保证接收方来得及接收。

接收方发送的确认报文中的窗口字段可以用来控制发送方窗口大小，从而影响发送方的发送速率。将窗口字段设置为 0，则发送方不能发送数据。

# TCP 拥塞控制

如果网络出现拥塞，分组将会丢失，此时发送方会继续重传，从而导致网络拥塞程度更高。因此当出现拥塞时，应当控制发送方的速率。这一点和流量控制很像，但是出发点不同。流量控制是为了让接收方能来得及接受，而拥塞控制是为了降低整个网络的拥塞程度。

TCP 主要通过四种算法来进行拥塞控制：慢开始、拥塞避免、快重传、快恢复。发送方需要维护有一个叫做拥塞窗口（cwnd）的状态变量。注意拥塞窗口与发送方窗口的区别，拥塞窗口只是一个状态变量，实际决定发送方能发送多少数据的是发送方窗口。

为了便于讨论，做如下假设：

  1. 接收方有足够大的接收缓存，因此不会发生流量控制；
  2. 虽然 TCP 的窗口基于字节，但是这里设窗口的大小单位为报文段。

# 慢开始与拥塞避免

发送的最初执行慢开始，令 cwnd=1，发送方只能发送 1 个报文段；当收到确认后，将 cwnd 加倍，因此之后发送方能够发送的报文段数量为：2、4、8 …

注意到慢开始每个轮次都将 cwnd 加倍，这样会让 cwnd 增长速度非常快，从而使得发送方发送的速度增长速度过快，网络拥塞的可能也就更高。设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免，每个轮次只将 cwnd 加 1。

如果出现了超时，则令 ssthresh = cwnd/2，然后重新执行慢开始。

# 快重传与快恢复

在接收方，要求每次接收到报文段都应该发送对已收到有序报文段的确认，例如已经接收到 M1 和 M2，此时收到 M4，应当发送对 M2 的确认。

在发送方，如果收到三个重复确认，那么可以确认下一个报文段丢失，例如收到三个 M2 ，则 M3 丢失。此时执行快重传，立即重传下一个报文段。

在这种情况下，只是丢失个别报文段，而不是网络拥塞，因此执行快恢复，令 ssthresh = cwnd/2 ，cwnd = ssthresh，注意到此时直接进入拥塞避免。

# （六）、应用层

# 域名系统 DNS

把主机名解析为 IP 地址。

被设计成分布式系统。

###. 层次结构

一个域名由多个层次构成，从上层到下层分别为顶级域名、二级域名、三级域名以及四级域名。所有域名可以画成一颗域名树。

域名服务器可以分为以下四类：

  • 根域名服务器：解析顶级域名；
  • 顶级域名服务器：解析二级域名；
  • 权限域名服务器：解析区内的域名；
  • 本地域名服务器：也称为默认域名服务器。可以在其中配置高速缓存。

区和域的概念不同，可以在一个域中划分多个区。图 b 在域 abc.com 中划分了两个区：abc.com 和 y.abc.com

因此就需要两个权限域名服务器：

###. 解析过程

主机向本地域名服务器解析的过程采用递归，而本地域名服务器向其它域名服务器解析可以使用递归和迭代两种方式。

迭代的方式下，本地域名服务器向一个域名服务器解析请求解析之后，结果返回到本地域名服务器，然后本地域名服务器继续向其它域名服务器请求解析；而递归的方式下，结果不是直接返回的，而是继续向前请求解析，最后的结果才会返回。

# 文件传输协议 FTP

FTP 在运输层使用 TCP，并且需要建立两个并行的 TCP 连接：控制连接和数据连接。控制连接在整个会话期间一直保持打开，而数据连接在数据传送完毕之后就关闭。控制连接使用端口号 21，数据连接使用端口号 20。

# 远程终端协议 TELNET

TELNET 用于登录到远程主机上，并且远程主机上的输出也会返回。

TELNET 可以适应许多计算机和操作系统的差异，例如不同操作系统系统的换行符定义。

# 电子邮件协议

一个电子邮件系统由三部分组成：用户代理、邮件服务器以及邮件发送协议和读取协议。其中发送协议常用 SMTP，读取协议常用 POP3 和 IMAP。

###. POP3

POP3 的特点是只要用户从服务器上读取了邮件，就把该邮件删除。

###. IMAP

IMAP 协议中客户端和服务器上的邮件保持同步，如果不去手动删除邮件，那么服务器上的邮件也不会被删除。IMAP 这种做法可以让用户随时随地去访问服务器上的邮件。IMAP 协议也支持创建自定义的文件夹。

###. SMTP

SMTP 只能发送 ASCII 码，而互联网邮件扩充 MIME 可以发送二进制文件。MIME 并没有改动或者取代 SMTP，而是增加邮件主题的结构，定义了非 ASCII 码的编码规则。

# 动态主机配置协议 DHCP

DHCP 提供了即插即用的连网方式，用户不再需要去手动配置 IP 地址等信息。

DHCP 配置的内容不仅是 IP 地址，还包括子网掩码、默认路由器 IP 地址、域名服务器的 IP 地址。

工作方式如下：需要 IP 地址的主机广播发送 DHCP 发现报文（将目的地址置为全 1，即 255.255.255.255:67，源地址设置为全 0，即 0.0.0.0:68），DHCP 服务器收到发现报文之后，则在 IP 地址池中取一个地址，发送 DHCP 提供报文给该主机。

# 点对点传输 P2P

把某个文件分发的所有对等集合称为一个洪流。文件的数据单元称为文件块，它的大小是固定的。一个新的对等方加入某个洪流，一开始并没有文件块，但是能够从其它对等方中逐渐地下载到一些文件块，与此同时，它也为别的对等方上传一些文件块。

每个洪流都有一个基础设施，称为追踪器。当一个对等方加入洪流时，必须向追踪器登记，并周期性地通知追踪器它仍在洪流中。可以在任何时间加入和退出某个洪流。

一个新的对等方加入洪流时，追踪器会随机从洪流中选择若干个对等方，并让新对等方与这些对等方建立连接，把这些对等方称为相邻对等方。接收和发送文件块都是在相邻对等方中进行。

当一个对等方需要很多文件块时，通过使用最稀有优先的策略来取得文件块，也就是一个文件块在相邻对等方中副本最少，那么就优先请求这个文件块。

当很多对等方向同一个对等方请求文件块时，该对等方优先选择以最高速率向其发送文件块的对等方。

P2P 是一个分布式系统，任何时候都有对等方加入或者退出。使用分布式散列表 DHT，可以查找洪流中的资源和 IP 地址映射。

# Web 页面请求过程

###. DHCP 配置主机信息

  • 假设主机最开始没有 IP 地址以及其它信息，那么就需要先使用 DHCP 来获取。
  • 主机生成一个 DHCP 请求报文，并将这个报文放入具有目的端口 67 和源端口 68 的 UDP 报文段中。
  • 该报文段则被放入在一个具有广播 IP 目的地址(255.255.255.255) 和源 IP 地址（0.0.0.0）的 IP 数据报中。
  • 该数据报则被放置在 MAC 帧中，该帧具有目的地址 FF:FF:FF:FF:FF:FF，将广播到与交换机连接的所有设备。
  • 连接在交换机的 DHCP 服务器收到广播帧之后，不断地向上分解得到 IP 数据报、UDP 报文段、DHCP 请求报文，之后生成 DHCP ACK 报文，该报文包含以下信息：IP 地址、DNS 服务器的 IP 地址、默认网关路由器的 IP 地址和子网掩码。该报文被放入 UDP 报文段中，UDP 报文段有被放入 IP 数据报中，最后放入 MAC 帧中。
  • 该帧的目的地址是请求主机的 MAC 地址，因为交换机具有自学习能力，之前主机发送了广播帧之后就记录了 MAC 地址到其转发接口的交换表项，因此现在交换机就可以直接知道应该向哪个接口发送该帧。
  • 主机收到该帧后，不断分解得到 DHCP 报文。之后就配置它的 IP 地址、子网掩码和 DNS 服务器的 IP 地址，并在其 IP 转发表中安装默认网关。

###. ARP 解析 MAC 地址

  • 主机通过浏览器生成一个 TCP 套接字，套接字向 HTTP 服务器发送 HTTP 请求。为了生成该套接字，主机需要知道网站的域名对应的 IP 地址。
  • 主机生成一个 DNS 查询报文，该报文具有 53 号端口，因为 DNS 服务器的端口号是 53。
  • 该 DNS 查询报文被放入目的地址为 DNS 服务器 IP 地址的 IP 数据报中。
  • 该 IP 数据报被放入一个以太网帧中，该帧将发送到网关路由器。
  • DHCP 过程只知道网关路由器的 IP 地址，为了获取网关路由器的 MAC 地址，需要使用 ARP 协议。
  • 主机生成一个包含目的地址为网关路由器 IP 地址的 ARP 查询报文，将该 ARP 查询报文放入一个具有广播目的地址（FF:FF:FF:FF:FF:FF）的以太网帧中，并向交换机发送该以太网帧，交换机将该帧转发给所有的连接设备，包括网关路由器。
  • 网关路由器接收到该帧后，不断向上分解得到 ARP 报文，发现其中的 IP 地址与其接口的 IP 地址匹配，因此就发送一个 ARP 回答报文，包含了它的 MAC 地址，发回给主机。

###. DNS 解析域名

  • 知道了网关路由器的 MAC 地址之后，就可以继续 DNS 的解析过程了。
  • 网关路由器接收到包含 DNS 查询报文的以太网帧后，抽取出 IP 数据报，并根据转发表决定该 IP 数据报应该转发的路由器。
  • 因为路由器具有内部网关协议（RIP、OSPF）和外部网关协议（BGP）这两种路由选择协议，因此路由表中已经配置了网关路由器到达 DNS 服务器的路由表项。
  • 到达 DNS 服务器之后，DNS 服务器抽取出 DNS 查询报文，并在 DNS 数据库中查找待解析的域名。
  • 找到 DNS 记录之后，发送 DNS 回答报文，将该回答报文放入 UDP 报文段中，然后放入 IP 数据报中，通过路由器反向转发回网关路由器，并经过以太网交换机到达主机。

###. HTTP 请求页面

  • 有了 HTTP 服务器的 IP 地址之后，主机就能够生成 TCP 套接字，该套接字将用于向 Web 服务器发送 HTTP GET 报文。
  • 在生成 TCP 套接字之前，必须先与 HTTP 服务器进行三次握手来建立连接。生成一个具有目的端口 80 的 TCP SYN 报文段，并向 HTTP 服务器发送该报文段。
  • HTTP 服务器收到该报文段之后，生成 TCP SYNACK 报文段，发回给主机。
  • 连接建立之后，浏览器生成 HTTP GET 报文，并交付给 HTTP 服务器。
  • HTTP 服务器从 TCP 套接字读取 HTTP GET 报文，生成一个 HTTP 响应报文，将 Web 页面内容放入报文主体中，发回给主机。
  • 浏览器收到 HTTP 响应报文后，抽取出 Web 页面内容，之后进行渲染，显示 Web 页面。

# 常用端口

应用层协议 端口号 运输层协议
DNS 53 UDP
FTP 控制连接 21，数据连接 20 TCP
TELNET 23 TCP
DHCP 67 68 UDP
HTTP 80 TCP
SMTP 25 TCP
POP3 110 TCP
IMAP 143 TCP

# 三、HTTP

# （一）、基本概念

# 1. Web 基础

# 2. URL

# 3. 请求和响应报文

# ⑴. 请求报文

# ⑵. 响应报文

# （二）、HTTP方法

# 1. GET

# 2. POST

# 3. HEAD

# 4. PUT

# 5. PATCH

# 6. DELETE

# 7. OPTIONS

# 8. CONNECT

# 9. TRACE

# （三）、HTTP状态码

# 1. 2XX 成功

# 2. 3XX 重定向

# 3. 4XX 客户端错误

# 4. 5XX 服务器错误

# （四）、HTTP首都

# 1. 通用首部字段

# 2. 请求首部字段

# 3. 响应首部字段

# 4. 实体首部字段

# （五）、具体应用

# 1. Cookie

# ⑴. 创建过程

# ⑵. Set-Cookie

# ⑶. Session 和 Cookie 区别

# ⑷. 浏览器禁用 Cookie 的情况

# ⑸. 使用 Cookie 实现用户名和密码的自动填写

# 2. 缓存

# ⑴. 优点

# ⑵. 实现方法

# ⑶. Cache-Control 字段

# ⑷. no-cache 指令

# ⑸. no-store 指令

# ⑹. max-age 指令

# 3. 持久连接

# 4. 编码

# 5. 分块传输

# 6. 多部分对象集合

# 7. 范围请求

# 8. 内容协商

# 9. 虚拟主机

# 10. 通信数据转发

# ⑴. 代理

# ⑵. 网关

# ⑶. 隧道

# （六）、HTPPs

# 1. 加密

# ⑴. 对称密钥

# ⑵. 公开密钥

# ⑶. HTTPs 采用的加密方式

# 2. 认证

# 3. 完整性

# （七）、Web攻击技术

# 1. 攻击模式

# ⑴. 主动攻击

# ⑵. 被动攻击

# 2. 跨站脚本攻击

# ⑴. 概念

# ⑵. 危害

# ⑶. 防范手段

# 3. SQL 注入攻击

# ⑴. 概念

# ⑵. 攻击原理

# ⑶. 危害

# ⑷. 防范手段

# 4. 跨站点请求伪造

# ⑴. 概念

# ⑵. 防范手段

# 5. 拒绝服务攻击

# ⑴. 概念

# （八）、各版本比较

# 1. HTTP/1.0 与 HTTP/1.1 的区别

# 2. HTTP/1.1 与 HTTP/2.0 的区别

# ⑴. 多路复用

# ⑵. 首部压缩

# ⑶. 服务端推送

# ⑷. 二进制格式

# 四、操作系统

# （一）、概述

# 1. 操作系统基本特征

# ⑴. 并发

# ⑵. 共享

# ⑶. 虚拟

# ⑷. 异步

# 2. 操作系统基本功能

# ⑴. 进程管理

# ⑵. 内存管理

# ⑶. 文件管理

# ⑷. 设备管理

# 3. 系统调用

# 4. 大内核和微内核

# ⑴. 大内核

# ⑵. 微内核

# 5. 中断分类

# 6. 外中断

# 7. 异常

# 8. 陷入

# （二）、进程管理

# 1. 进程与线程

# ⑴. 进程

# ⑵. 线程

# ⑶. 区别

# 2. 进程状态的切换

# 3. 调度算法

# ⑴. 批处理系统中的调度

# ①. 先来先服务
# ②. 短作业优先
# ③. 最短剩余时间优先

# ⑵. 交互式系统中的调度

# ①. 优先级调度
# ②. 时间片轮转
# ③. 多级反馈队列

# ⑶. 实时系统中的调度

# 4. 进程同步

# ⑴. 临界区

# ⑵. 同步与互斥

# ⑶. 信号量

# ⑷. 管程

# 5. 经典同步问题

# ⑴. 读者-写者问题

# ⑵. 哲学家进餐问题

# 6. 进程通信

# ⑴. 进程同步与进程通信的区别

# ⑵. 进程通信方式

# ①. 消息传递
# ②. 共享内存

# （三）、死锁

# 1. 死锁的必要条件

# 2. 死锁的处理方法

# ⑴. 鸵鸟策略

# ⑵. 死锁检测与死锁恢复

# ⑶. 死锁预防

# ⑷. 死锁避免

# （四）、内存管理

# 1. 虚拟内存

# 2. 分页与分段

# ⑴. 分页

# ⑵. 分段

# ⑶. 段页式

# ⑷. 分页与分段区别

# 3. 分页系统地址映射

# 4. 页面置换算法

# ⑴. 最佳

# ⑵. 先进先出

# ⑶. 最近最久未使用

# ⑷. 时钟

# （五）、设备管理

# 1. 磁盘调度算法

# ⑴. 先来先服务

# ⑵. 最短寻道时间优先

# ⑶. 扫描算法

# ⑷. 循环扫描算法

# （六）、链接

# 1. 编译系统

# 2. 目标文件

# 3. 静态链接

# 4. 动态链接

# 五、Linux

# （一）、常用操作以及概念

# 1. 求助

# ⑴. help

# ⑵. man

# ⑶. info

# 2. 关机

# ⑴. sync

# ⑵. shutdown

# ⑶. 其它关机指令

# 3. PATH

# 4. 运行等级

# 5. sudo

# 6. GNU

# 7. 包管理工具

# 8. 发行版

# 9. VIM 三个模式

# （二）、分区

# 1. 磁盘的文件名

# 2. 分区表

# ⑴. MBR

# ⑵. GPT

# 3. 开机检测程序

# ⑴. BIOS

# ⑵. UEFI

# 4. 挂载

# （三）、文件

# 1. 文件权限概念

# 2. 文件属性以及权限的修改

# ⑴. 修改文件所属群组

# ⑵. 修改文件拥有者

# ⑶. 修改权限

# 3. 目录的权限

# 4. 文件默认权限

# 5. 目录配置

# 6. 文件时间

# 7. 文件与目录的基本操作

# ⑴. ls

# ⑵. cp

# ⑶. rm

# ⑷. mv

# 8. 获取文件内容

# ⑴. cat

# ⑵. tac

# ⑶. more

# ⑷. less

# ⑸. head

# ⑹. tail

# ⑺. od

# ⑻. touch

# 9. 指令与文件搜索

# ⑴. which

# ⑵. whereis

# ⑶. locate

# ⑷. find

# （四）、磁盘与文件系统

# 1. 文件系统的组成

# 2. inode

# 3. 目录的 inode 与 block

# . 实体链接与符号链接

# ⑴. 实体链接

# ⑵. 符号链接

# （五）、压缩与打包

# 1. 压缩

# ⑴. gzip

# ⑵. bzip2

# ⑶. xz

# 2. 打包

# （六）、Bash

# 1. 特性

# 2. 变量操作

# 3. 指令搜索顺序

# 4. 数据流重定向

# （七）、管线指令

# 1. 提取指令

# 2. 排序指令

# 3. 双向输出重定向

# 4. 字符转换指令

# 5. 分区指令

# （八）、正则表达式

# 1. grep

# 2. printf

# 3. awk

# （九）、进程管理

# 1. 查看进程

# ⑴. ps

# ⑵. top

# ⑶. pstree

# ⑷. netstat

# 2. 进程状态

# 3. SIGCHILD

# 4. 孤儿进程和僵死进程

# ⑴. 孤儿进程

# ⑵. 僵死进程

# （十）、I/O复用

# 1. 概念理解

# 2. I/O 模型

# ⑴. 同步-阻塞

# ⑵. 同步-非阻塞

# ⑶. 异步-阻塞

# ⑷. 异步-非阻塞

# 3. select poll epoll

# ⑴. select

# ⑵. poll

# ⑶. epoll

# 4. select 和 poll 比较

# ⑴. 功能

# ⑵. 速度

# ⑶. 可移植性

# 5. eopll 工作模式

# ⑴. LT 模式

# ⑵. ET 模式

# 6. select poll epoll 应用场景

# ⑴. select 应用场景

# ⑵. poll 应用场景

# ⑶. epoll 应用场景

# ⑷. 性能对比

# 六、算法

# （一）、算法分析

# 1. 数学模型

# ⑴. 近似

# ⑵. 增长数量级

# ⑶. 内循环

# ⑷. 成本模型

# 2. ThreeSum

# 3. 倍率实验

# 4. 注意事项

# ⑴. 大常数

# ⑵. 缓存

# ⑶. 对最坏情况下的性能的保证

# ⑷. 随机化算法

# ⑸. 均摊分析

# （二）、栈和队列

# 1. 栈

# 2. 队列

# （三）、union-find

# 1. quick-find

# 2. quick-union

# 3. 加权 quick-union

# 4. 路径压缩的加权 quick-union

# 5. 各种 union-find 算法的比较

# （四）、排序

# 1. 选择排序

# 2. 插入排序

# 3. 希尔排序

# 4. 归并排序

# ⑴. 归并方法

# ⑵. 自顶向下归并排序

# ⑶. 自底向上归并排序

# 5. 快速排序

# ⑴. 基本算法

# ⑵. 切分

# ⑶. 性能分析

# ⑷. 算法改进

# 6. 优先队列

# ⑴. 堆

# ⑵. 上浮和下沉

# ⑶. 插入元素

# ⑷. 删除最大元素

# ⑸. 堆排序

# ⑹. 分析

# 7. 应用

# ⑴. 排序算法的比较

# ⑵. Java 的排序算法实现

# ⑶. 基于切分的快速选择算法

# （五）、查找

# 1. 符号表

# ⑴. 无序符号表

# ⑵. 有序符号表

# ⑶. 二分查找实现有序符号表

# 2. 二叉查找树

# ⑴. get()

# ⑵. put()

# ⑶. 分析

# ⑷. floor()

# ⑸. rank()

# ⑹. min()

# ⑺. deleteMin()

# ⑻. delete()

# ⑼. keys()

# ⑽. 性能分析

# 3. 2-3 查找树

# ⑴. 插入操作

# ⑵. 性质

# 3. 红黑二叉查找树

# ⑴. 左旋转

# ⑵. 右旋转

# ⑶. 颜色转换

# ⑷. 插入

# ⑸. 删除最小键

# ⑹. 分析

# 4. 散列表

# ⑴. 散列函数

# ⑵. 基于拉链法的散列表

# ⑶. 基于线性探测法的散列表

# 5. 应用

# ⑴. 各种符号表实现的比较

# ⑵. Java 的符号表实现

# ⑶. 集合类型

# ⑷. 稀疏向量乘法

# 七、剑指 Offer 题解

# 1. 前言

# 2. 实现 Singleton

# 3. 数组中重复的数字

# 4. 二维数组中的查找

# 5. 替换空格

# 6. 从尾到头打印链表

# 7. 重建二叉树

# 8. 二叉树的下一个结点

# 9. 用两个栈实现队列

# 10.1 斐波那契数列

# 10.2 跳台阶

# 10.3 变态跳台阶

# 10.4 矩形覆盖

# 11. 旋转数组的最小数字

# 12. 矩阵中的路径

# 13. 机器人的运动范围

# 14. 剪绳子

# 15. 二进制中 1 的个数

# 16. 数值的整数次方

# 17. 打印从 1 到最大的 n 位数

# 18.1 在 O(1) 时间内删除链表节点

# 18.2 删除链表中重复的结点

# 19. 正则表达式匹配

# 20. 表示数值的字符串

# 21. 调整数组顺序使奇数位于偶数前面

# 22. 链表中倒数第 K 个结点

# 23. 链表中环的入口结点

# 24. 反转链表

# 25. 合并两个排序的链表

# 26. 树的子结构

# 27. 二叉树的镜像

# 28. 对称的二叉树

# 29. 顺时针打印矩阵

# 30. 包含 min 函数的栈

# 31. 栈的压入、弹出序列

# 32.1 从上往下打印二叉树

# 32.2 把二叉树打印成多行

# 32.3 按之字形顺序打印二叉树

# 33. 二叉搜索树的后序遍历序列

# 34. 二叉树中和为某一值的路径

# 35. 复杂链表的复制

# 36. 二叉搜索树与双向链表

# 37. 序列化二叉树

# 38. 字符串的排列

# 39. 数组中出现次数超过一半的数字

# 40. 最小的 K 个数

# 41.1 数据流中的中位数

# 41.2 字符流中第一个不重复的字符

# 42. 连续子数组的最大和

# 43. 从 1 到 n 整数中 1 出现的次数

# 44. 数字序列中的某一位数字

# 45. 把数组排成最小的数

# 46. 把数字翻译成字符串

# 47. 礼物的最大价值

# 48. 最长不含重复字符的子字符串

# 49. 丑数

# 50. 第一个只出现一次的字符位置

# 51. 数组中的逆序对

# 52. 两个链表的第一个公共结点

# 53 数字在排序数组中出现的次数

# 54. 二叉搜索树的第 K 个结点

# 55.1 二叉树的深度

# 55.2 平衡二叉树

# 56. 数组中只出现一次的数字

# 57.1 和为 S 的两个数字

# 57.2 和为 S 的连续正数序列

# 58.1 翻转单词顺序列

# 58.2 左旋转字符串

# 59. 滑动窗口的最大值

# 60. n 个骰子的点数

# 61. 扑克牌顺子

# 62. 圆圈中最后剩下的数

# 63. 股票的最大利润

# 64. 求 1+2+3+…+n

# 65. 不用加减乘除做加法

# 66. 构建乘积数组

# 67. 把字符串转换成整数

# 68. 树中两个节点的最低公共祖先

# 八、Leetcode 题解

# （一）、算法思想

# 1. 二分查找

# 2. 贪心思想

# 3. 双指针

# 4. 排序

# ⑴. 快速选择

# ⑵. 堆排序

# ⑶. 桶排序

# 5. 搜索

# ⑴. BFS

# ⑵. DFS

# ⑶. Backtracking

# 6. 分治

# 7. 动态规划

# ⑴. 斐波那契数列

# ⑵. 最长递增子序列

# ⑶. 最长公共子系列

# ⑷. 0-1 背包

# ⑸. 数组区间

# ⑹. 字符串编辑

# ⑺. 分割整数

# ⑻. 矩阵路径

# ⑼. 其它问题

# 8. 数学

# ⑴. 素数

# ⑵. 最大公约数

# ⑶. 进制转换

# ⑷. 阶乘

# ⑸. 字符串加法减法

# ⑹. 相遇问题

# ⑺. 多数投票问题

# ⑻. 其它

# （二）、数据结构

# 1. 栈和队列

# 2. 哈希表

# 3. 字符串

# 4. 数组与矩阵

# ⑴. 1-n 分布

# ⑵. 有序矩阵

# 5. 链表

# 6. 树

# ⑴. 递归

# ⑵. 层次遍历

# ⑶. 前中后序遍历

# ⑷. BST

# ⑸. Trie

# 7. 图

# 8. 位运算

# 九、设计模式

# （一）、前言

# （二）、设计模式概念

# （三）、单例模式

# 1. 意图

# 2. 类图

# 3. 使用场景

# 4. JDK 的使用

# 5. 实现

# ⑴. 懒汉式-线程不安全

# ⑵. 懒汉式-线程安全

# ⑶. 饿汉式-线程安全

# ⑷. 双重校验锁-线程安全

# （四）、简单工厂

# 1. 意图

# 2. 类图

# 3. 实现

# （五）、工厂方法模式

# 1. 意图

# 2. 类图

# 3. 实现

# （六）、抽象工厂模式

# 1. 意图

# 2. 类图

# 3. 代码实现

# 十、面向对象思想

# （一）、设计原则

# 1. S.O.L.I.D

# ⑴. 单一责任原则

# ⑵. 开放封闭原则

# ⑶. 里氏替换原则

# ⑷. 接口分离原则

# ⑸. 依赖倒置原则

# 2. 其他常见原则

# ⑴. 迪米特法则

# ⑵. 合成复用原则

# ⑶. 共同封闭原则

# ⑷. 稳定抽象原则

# ⑸. 稳定依赖原则

# （二）、三大特性

# 1. 封装

# 2. 继承

# 3. 多态

# （三）、UML

# 1. 类图

# ⑴. 继承相关

# ⑵. 泛化关系 (Generalize)

# ⑶. 实现关系 (Realize)

# ⑷. 整体和部分

# ⑸. 聚合关系 (Aggregation)

# ⑹. 组合关系 (Composition)

# ⑺. 相互联系

# ⑻. 关联关系 (Association)

# ⑼. 依赖关系 (Dependency)

# 2. 时序图

# ⑴. 定义

# ⑵. 赤壁之战时序图

# ⑶. 活动图、时序图之间的关系

# ⑷. 类图与时序图的关系

# ⑸. 时序图的组成

# ⑹. 对象

# ⑺. 生命线

# ⑻. 消息

# ⑼. 激活

# 十一、数据库系统原理

# （一）、事务

# 1. 概念

# 2. 四大特性

. 原子性（Atomicity）

. 一致性（Consistency）

. 隔离性（Isolation）

. 持久性（Durability）

# （二）、并发一致性问题

# 1. 问题

# ⑴. 丢失修改

# ⑵. 读脏数据

# ⑶. 不可重复读

# ⑷. 幻影读

# 2. 解决方法

# （三）、封锁

# 1. 封锁粒度

# 2. 封锁类型

# ⑴. 排它锁与共享锁

# ⑵. 意向锁

# 3. 封锁协议

# ⑴. 三级封锁协议

# ⑵. 两段锁协议

# （四）、隔离级别

# （五）、多版本并发控制

# 1. 版本号

# 2. Undo 日志

# 3. 实现过程

# ⑴. SELECT

# ⑵. INSERT

# ⑶. DELETE

# ⑷. UPDATE

# 4. 快照读与当前读

# （六）、Next-Key Locks

# 1. Record Locks

# 2. Grap Locks

# 3. Next-Key Locks

# （七）、关系数据库设计理论

# 1. 函数依赖

# 2. 异常

# 3. 范式

# ⑴. 第一范式 (1NF)

# ⑵. 第二范式 (2NF)

# ⑶. 第三范式 (3NF)

# ⑷. BC 范式（BCNF）

# （八）、数据库系统概述

# 1. 基本术语

# ⑴. 数据模型

# ⑵. 数据库系统

# 2. 数据库的三层模式和两层映像

# ⑴. 外模式

# ⑵. 模式

# ⑶. 内模式

# ⑷. 外模式/模式映像

# ⑸. 模式/内模式映像

# （九）、关系数据库建模

# 1. ER 图

# ⑴. 实体的三种联系

# ⑵. 表示出现多次的关系

# ⑶. 联系的多向性

# ⑷. 表示子类

# （十）、约束

# 1. 键码

# 2. 单值约束

# 3. 引用完整性约束

# 4. 域约束

# 5. 一般约束

# 十二、SQL

# （一）、基础

# （二）、创建表

# （三）、修改表

# （四）、插入

# （五）、更新

# （六）、删除

# （七）、查询

# 1. DISTINCT

# 2. LIMIT

# （八）、排序

# （九）、过滤

# （十）、通配符

# （十一）、计算字段

# （十二）、函数

# 1. 文本处理

# 2. 日期和时间处理

# 3. 数值处理

# 4. 汇总

# （十三）、分组

# （十四）、子查询

# （十五）、连接

# 1. 内连接

# 2. 自连接

# 3. 自然连接

# 4. 外连接

# （十六）、组合查询

# （十七）、视图

# （十八）、存储过程

# 1. 使用存储过程的好处

# 2. 创建存储过程

# （十九）、游标

# （二十）、触发器

# （二十一）、事务处理

# （二十二）、字符集

# （二十三）、权限管理

# 1. 创建账户

# 2. 修改账户名

# 3. 删除账户

# 4. 查看权限

# 5. 授予权限

# 6. 删除权限

# 7. 更改密码

# 十三、MySQL

# （一）、储存引擎

# 1. InnoDB

# 2. MyISAM

# 3. 比较

# （二）、数据类型

# 1. 整型

# 2. 浮点数

# 3. 字符串

# 4. 时间和日期

# ⑴. DATATIME

# ⑵. TIMESTAMP

# （三）、索引

# 1. 索引分类

# ⑴. B+Tree 索引

# ⑵. 哈希索引

# ⑶. 空间索引（R-Tree）

# ⑷. 全文索引

# 2. 索引的优点

# 3. 索引优化

# ⑴. 独立的列

# ⑵. 前缀索引

# ⑶. 多列索引

# ⑷. 索引列的顺序

# ⑸. 聚簇索引

# ⑹. 覆盖索引

# 4. B-Tree 和 B+Tree 原理

# ⑴. B-Tree

# ⑵. B+Tree

# ⑶. 带有顺序访问指针的 B+Tree

# ⑷. 为什么使用 B-Tree 和 B+Tree

# （四）、查询性能优化

# 1. Explain

# 2. 减少返回的列

# 3. 减少返回的行

# 4. 拆分大的 DELETE 或 INSERT 语句

# （五）、切分

# 1. 垂直切分

# 2. 水平切分

# 3. 切分的选择

# 4. 存在的问题

# ⑴. 事务问题

# ⑵. 跨库跨表连接问题

# ⑶. 额外的数据管理负担和数据运算压力

# （六）、数据转移和故障恢复

# 1. 提升备库或切换角色

# 2. 虚拟 IP 地址和 IP 托管

# 3. 中间件解决方案

# 4. 在应用中处理故障转移

# 十四、Redis

# （一）、Redis是什么

# （二）、五种基本类型

# 1. STRING

# 2. LIST

# 3. SET

# 4. HASH

# 5. ZSET

# （三）、键的过期时间

# （四）、发布与订阅

# （五）、事务

# （六）、持久化

# 1. 快照持久化

# 2. AOF 持久化

# （七）、复制

# 1. 从服务器连接主服务器的过程

# 2. 主从链

# （八）、处理故障

# （九）、分片

# 1. 客户端分片

# 2. 代理分片

# 3. 服务器分片

# （十）、事件

# 1. 事件类型

# ⑴. 文件事件

# ⑵. 时间事件

# 2. 事件的调度与执行

# （十一）、Redis 与 Memcached 的区别

# 1. 数据类型

# 2. 数据持久化

# 3. 分布式

# 4. 内存管理机制

# （十二）、Redis 适用场景

# 1. 缓存

# 2. 消息队列

# 3. 计数器

# 4. 好友关系

# （十三）、数据淘汰策略

# （十四）、一个简单的论坛系统分析

# 1. 文章信息

# 2. 点赞功能

# 3. 对文章进行排序

# 十五、Java 虚拟机

# （一）、运行时数据区域

# 1. 程序计数器

# 2. Java 虚拟机栈

# 3. 本地方法栈

# 4. Java 堆

# 5. 方法区

# 6. 运行时常量池

# 7. 直接内存

# （二）、垃圾收集

# 1. 判断一个对象是否可回收

# ⑴. 引用计数

# ⑵. 可达性

# ⑶. 引用类型

# ⑷. 方法区的回收

# ⑸. finalize()

# 2. 垃圾收集算法

# ⑴. 标记 - 清除

# ⑵. 复制

# ⑶. 标记 - 整理

# ⑷. 分代收集

# 3. 垃圾收集器

# ⑴. Serial 收集器

# ⑵. ParNew 收集器

# ⑶. Parallel Scavenge 收集器

# ⑷. Serial Old 收集器

# ⑸. Parallel Old 收集器

# ⑹. CMS 收集器

# ⑺. G1 收集器

# ⑻. 七种垃圾收集器的比较

# 4. 内存分配与回收策略

# ⑴. 优先在 Eden 分配

# ⑵. 大对象直接进入老年代

# ⑶. 长期存活的对象进入老年代

# ⑷. 动态对象年龄判定

# ⑸. 空间分配担保

# 5. Full GC 的触发条件

# ⑴. 调用 System.gc()

# ⑵. 老年代空间不足

# ⑶. 空间分配担保失败

# ⑷. JDK 1.7 及以前的永久代空间不足

# ⑸. Concurrent Mode Failure

# （三）、类加载机制

# 1. 类的生命周期

# 2. 类初始化时机

# 3. 类加载过程

# ⑴. 加载

# ⑵. 验证

# ⑶. 准备

# ⑷. 解析

# ⑸. 初始化

# 4. 类加载器

# ⑴. 类与类加载器

# ⑵. 类加载器分类

# ⑶. 双亲委派模型

# （四）、JVM参数

# 1. GC 优化配置

# 2. GC 类型设置

# 十六、Java 并发

# （一）、使用线程

# 1. 实现 Runnable 接口

# 2. 实现 Callable 接口

# 3. 继承 Thread 类

# 4. 实现接口 VS 继承 Thread

# （二）、基础线程机制

# 1. sleep()

# 2. yield()

# 3. join()

# 4. deamon

# （三）、结束线程

# 1. 阻塞

# 2. 中断

# （四）、线程之间的协作

# 1. 同步与通信的概念理解

# 2. 线程同步

# ⑴. synchronized

# ⑵. ReentrantLock

# 3. 线程通信

# ⑴. wait() notify() notifyAll()

# ⑵. BlockingQueue

# （五）、线程状态转换

# （六）、Executor

# （七）、内存模型

# 1. 主内存与工作内存

# 2. 内存模型三大特性

# ⑴. 原子性

# ⑵. 可见性

# ⑶. 有序性

# 3. 先行发生原则

# ⑴. 单一线程原则

# ⑵. 管程锁定规则

# ⑶. volatile 变量规则

# ⑷. 线程启动规则

# ⑸. 线程加入规则

# ⑹. 线程中断规则

# ⑺. 对象终结规则

# ⑻. 传递性

# （八）、线程安全

# 1. 线程安全分类

# ⑴. 不可变

# ⑵. 绝对线程安全

# ⑶. 相对线程安全

# ⑷. 线程兼容

# ⑸. 线程对立

# 2. 线程安全的实现方法

# ⑴. 互斥同步

# ⑵. 非阻塞同步

# ⑶. 无同步方案

# 3. 锁优化

# ⑴. 自旋锁与自适应自旋

# ⑵. 锁消除

# ⑶. 锁粗化

# ⑷. 轻量级锁

# ⑸. 偏向锁

# （九）、多线程开发良好的实践

# 十七、Java 容器

# （一）、概览

# 1. Collection

# ⑴. Set

# ⑵. List

# ⑶. Queue

# 2. Map

# （二）、容器中的设计模式

# 1. 迭代器模式

# 2. 适配器模式

# （三）、散列

# （四）、源码分析

# 1. ArrayList

# ⑴. 概览

# ⑵. Fail-Fast

# ⑶. 和 Vector 的区别

# ⑷. 和 LinkedList 的区别

# 2. Vector

# 3. LinkedList

# 4. TreeMap

# 5. HashMap

# ⑴. 存储结构

# ⑵. 拉链法的工作原理

# ⑶. 链表转红黑树

# ⑷. 扩容

# ⑸. 确定桶下标

# ⑹. 扩容-重新计算桶下标

# ⑺. 扩容-计算数组容量

# ⑻. null 值

# ⑼. 与 HashTable 的区别

# 6. LinkedHashMap

# 7. ConcurrentHashMap - JDK 1.7

# ⑴. 存储结构

# ⑵. HashEntery 的不可变性

# ⑶. Volatile 变量

# ⑷. 小结

# 8. ConcurrentHashMap - JDK 1.8

# 十八、Java IO

# （一）、概览

# （二）、磁盘操作

# （三）、字节操作

# （四）、字符操作

# （五）、对象操作

# （六）、网络操作

# 1. InetAddress

# 2. URL

# 3. Sockets

# 4. Datagram

# （七）、NIO

# 1. 流与块

# 2. 通道与缓冲区

# ⑴. 通道

# ⑵. 缓冲区

# 3. 缓冲区状态变量

# 4. 文件 NIO 实例

# 5. 套接字 NIO 实例

# ⑴. ServerSocketChannel

# ⑵. Selectors

# ⑶. 主循环

# ⑷. 监听新连接

# ⑸. 接受新的连接

# ⑹. 删除处理过的 SelectionKey

# ⑺. 传入的 I/O

# 6. 内存映射文件

# 7. 对比

# 十九、Java 基础

# （一）、关键字

# 1. final

# 2. static

# （二）、Object 通用方法

# 1. 概览

# 2. clone()

# 3. equals()

# （三）、继承

# 1. 访问权限

# 2. 抽象类与接口

# 3. super

# 4. 重载与重写

# （四）、String

# 1. String, StringBuffer and StringBuilder

# 2. String 不可变的原因

# 3. String.intern()

# （五）、基本类型与运算

# 1. 包装类型

# 2. switch

# （六）、反射

# （七）、异常

# （八）、泛型

# （九）、注解

# （十）、特性

# 1. 面向对象三大特性

# 2. Java 各版本的新特性

# 3. Java 与 C++ 的区别

# 4. JRE or JDK

# 二十、JDK 中的设计模式

# （一）、创建型

# 1. 单例模式

# 2. 简单工厂模式

# 3. 工厂方法模式

# 4. 抽象工厂

# 5. 生成器模式

# 6. 原型模式

# （二）、行为型

# 1. 责任链

# 2. 命令模式

# 3. 解释器模式

# 4. 迭代器

# 5. 中间人模式

# 6. 备忘录模式

# 7. 观察者模式

# 8. 策略模式

# 9. 模板方法

# 10. 访问者模式

# 11. 空对象模式

# （三）、结构型

# 1. 适配器

# 2. 桥接模式

# 3. 组合模式

# 4. 装饰者模式

# 5. 蝇量模式

# 6. 动态代理

# 二十一、分布式基础

# （一）、基本概念

# 1. 异常

# ⑴. 服务器宕机

# ⑵. 网络异常

# ⑶. 磁盘故障

# 2. 超时

# 3. 衡量指标

# ⑴. 性能

# ⑵. 可用性

# ⑶. 一致性

# ⑷. 可扩展性

# （二）、数据分布

# 1. 哈希分布

# 2. 顺序分布

# （三）、负载均衡

# （四）、复制

# 1. 强同步复制协议

# 2. 异步复制协议

# （五）、CAP

# （六）、BASE

# 1. 基本可用

# 2. 软状态

# 3. 最终一致性

# （七）、容错

# 1. 故障检测

# 2. 故障恢复

# （八）、CDN 架构

# 二十二、一致性协议

# （一）、两阶段提交协议

# 1. 运行过程

# 2. 存在的问题

# （二）、Paxos 协议

# 1. 执行过程

# 2. 约束条件

# ⑴. 正确性

# ⑵. 可终止性

# （三）、Raft 协议

# 1. 单个 Candidate 的竞选

# 2. 多个 Candidate 竞选

# 3. 日志复制

# （四）、拜占庭将军问题

# 二十三、分布式问题分析

# （一）、谈谈业务中使用分布式的场景

# （二）、分布式事务

# 1. 产生原因

# 2. 应用场景

# 3. 解决方案

# ⑴. 两阶段提交协议

# ⑵. 消息中间件

# ①. 消息处理模型
# ②. 消息的可靠性

# （三）、负载均衡的算法与实现

# 1. 算法

# ⑴. 轮询（Round Robin）

# ⑵. 加权轮询（Weighted Round Robbin）

# ⑶. 最少连接（least Connections）

# ⑷. 加权最小连接（Weighted LeastConnection）

# ⑸. 随机算法（Random）

# 2. 实现

# ⑴. HTTP 重定向

# ⑵. DNS 重定向

# ⑶. 修改 MAC 地址

# ⑷. 修改 IP 地址

# ⑸. 代理自动配置

# （四）、分布式锁

# 1. 使用场景

# 2. 实现方式

# ⑴. 数据库分布式锁

# ⑵. Redis 分布式锁

# ⑶. Zookeeper 分布式锁

# （五）、分布式 Session

# 1. Sticky Sessions

# 2. Session Replication

# 3. Persistent DataStore

# 4. In-Memory DataStore

# （六）、分库与分表带来的分布式困境与应对之策

# 1. 事务问题

# 2. 查询问题

# 3. ID 唯一性

# 二十四、Git

# 1. 学习资料

# 2. 集中式与分布式

# 3. Git 的中心服务器

# 4. Git 工作流

# 5. 分支实现

# 6. 冲突

# 7. Fast forward

# 8. 分支管理策略

# 9. 储藏（Stashing）

# 10. SSH 传输设置

# 11. .gitignore 文件

# 12. Git 命令一览

# 二十五、正则表达式

# （一）、概述

# （二）、匹配单个字符

# （三）、匹配一组字符

# （四）、使用元字符

# 1. 匹配空白字符

# 2. 匹配特定的字符类别

# ⑴. 数字元字符

# ⑵. 字母数字元字符

# ⑶. 空白字符元字符

# （五）、重复匹配

# （六）、位置匹配

# 1. 单词边界

# 2. 字符串边界

# （七）、使用子表达式

# （八）、回溯引用

# 1. 替换

# 2. 大小写转换

# （九）、前后查找

# （十）、嵌入条件

# 1. 回溯引用条件

# 2. 前后查找条件

# 二十六、重构

# （一）、第一个案例

# （二）、重构原则

# 1. 定义

# 2. 为何重构

# 3. 三次法则

# 4. 间接层与重构

# 5. 修改接口

# 6. 何时不该重构

# 7. 重构与设计

# 8. 重构与性能

# （三）、代码的坏味道

# 1. 重复代码

# 2. 过长函数

# 3. 过大的类

# 4. 过长的参数列表

# 5. 发散式变化

# 6. 散弹式修改

# 7. 依恋情结

# 8. 数据泥团

# 9. 基本类型偏执

# 10. switch 惊悚现身

# 11. 平行继承体系

# 12. 冗余类

# 13. 夸夸其谈未来性

# 14. 令人迷惑的暂时字段

# 15. 过度耦合的消息链

# 16. 中间人

# 17. 狎昵关系

# 18. 异曲同工的类

# 19. 不完美的类库

# 20. 幼稚的数据类

# 21. 被拒绝的馈赠

# 22. 过多的注释

# （四）、构筑测试体系

# （五）、重新组织函数

# 1. 提炼函数

# 2. 内联函数

# 3. 内联临时变量

# 4. 以查询取代临时变量

# 5. 引起解释变量

# 6. 分解临时变量

# 7. 移除对参数的赋值

# 8. 以函数对象取代函数

# 9. 替换算法

# （六）、在对象之间搬移特性

# 1. 搬移函数

# 2. 搬移字段

# 3. 提炼类

# 4. 将类内联化

# 5. 隐藏委托关系

# 6. 移除中间人

# 7. 引入外加函数

# 8. 引入本地扩展

# （七）、重新组织数据

# 1. 自封装字段

# 2. 以对象取代数据值

# 3. 将值对象改成引用对象

# 4. 将引用对象改为值对象

# 5. 以对象取代数组

# 6. 赋值被监视数据

# 7. 将单向关联改为双向关联

# 8. 将双向关联改为单向关联

# 9. 以字面常量取代魔法数

# 10. 封装字段

# 11. 封装集合

# 12. 以数据类取代记录

# 13. 以类取代类型码

# 14. 以子类取代类型码

# 15. 以 State/Strategy 取代类型码

# 16. 以字段取代子类

# （八）、简化条件表达式

# 1. 分解条件表达式

# 2. 合并条件表达式

# 3. 合并重复的条件片段

# 4. 移除控制标记

# 5. 以卫语句取代嵌套条件表达式

# 6. 以多态取代条件表达式

# 7. 引入 Null 对象

# 8. 引入断言

# （九）、简化函数调用

# 1. 函数改名

# 2. 添加参数

# 3. 移除参数

# 4. 将查询函数和修改函数分离

# 5. 令函数携带参数

# 6. 以明确函数取代参数

# 7. 保持对象完整

# 8. 以函数取代参数

# 9. 引入参数对象

# 10. 移除设值函数

# 11. 隐藏函数

# 12. 以工厂函数取代构造函数

# 13. 封装向下转型

# 14. 以异常取代错误码

# 15. 以测试取代异常

# （十）、处理概括关系

# 1. 字段上移

# 2. 函数上移

# 3. 构造函数本体上移

# 4. 函数下移

# 5. 字段下移

# 6. 提炼子类

# 7. 提炼超类

# 8. 提炼接口

# 9. 折叠继承体系

# 10. 塑造模板函数

# 11. 以委托取代继承

# 12. 以继承取代委托

# 二十七、代码可读性

# 1. 可读性的重要性

# 2. 用名字表达代码含义

# 3. 名字不能带来歧义

# 4. 良好的代码风格

# 5. 编写注释

# 6. 如何编写注释

# 7. 提高控制流的可读性

# 8. 拆分长表达式

# 9. 变量与可读性

# 10. 抽取函数

# 11. 一次只做一件事

# 12. 用自然语言表述代码

# 13. 减少代码量

编辑 (opens new window)
上次更新: 2021/11/16, 23:47:58
我凭这三招轻松拿到offer
程序员面试攻略：面试中的技巧

← 程序员面试攻略：面试中的技巧→

最近更新
01
万字长文：选 Redis 还是 MQ，终于说明白了！
 10-11
02
Typora+gitee+自定义命令实现图床
 09-13
03
字节终面：两个文件的公共url怎么找？
 09-09
更多文章>
Theme by Vdoing | Copyright © 2019-2022 Vic | MIT License
×