找工作相关知识

找工作相关

算法题

链表相关

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
// 反转链表
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;	// 存储当前节点的前一个节点
        ListNode cur = head;	// 当前节点
        ListNode next = null;	// 存储当前节点的后一个节点
        
        while(cur != null){
            next = cur.next;	// 用next节点存储当前节点的next
            // 反转链表
            cur.next = pre;		// 将当前节点的next指向pre
            // 向后移动
            pre = cur;			// 将当前节点赋给pre
            cur = next;			// 将next赋给当前节点
        }
        return pre;
    }
}

// 合并有序列表（归并排序）
public static ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // 有链表为空则返回另一个链表
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = new ListNode(0);	// 辅助头节点
        ListNode tail = head;				// 当前节点
        while (l1 != null && l2 != null){	// 一个个往tail中加
            if (l1.val <= l2.val){			// 若l1中的当前节点<l2中的
                tail.next = l1;				// 将l1中的当前节点加入tail
                l1 = l1.next;				// l1后移
            } else {						// 若l2中的当前节点<l1中的
                tail.next = l2;				// 将l2中的当前节点加入tail
                l2 = l2.next;				// l2后移
            }
            tail = tail.next;				//tail后移
        }
        tail.next = (l1 == null)?l2:l1;		//l1,l2哪个为空直接另一个其后面的加入tail
        return head.next;					//因为头节点为0，其后面才是l1和l2的值，返回头节点的后一个
    }


// 链表中倒数第k个节点（快慢指针）
public static ListNode FindKthToTail(ListNode head, int k) {
    if (head == null || k <= 0) return null;
    ListNode node1 = head, node2 = head;
    for (int i = 0; i < k; i++) {
        node1 = node1.next;
    }
    while (node1 != null){
        node1 = node1.next;
        node2 = node2.next;
    }
    return node2;
}

//删除链表中倒数第k个节点（快慢指针）
public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode node1 = dummyHead, node2 = dummyHead;
    for (int i = 0 ; i < n + 1 ; i++){   // 先移动n + 1个位置，获取删除节点的前一个节点
        node1 = node1.next;
    }
    while (node1 != null){
        node1 = node1.next;
        node2 = node2.next;
    }
    node2.next = node2.next.next;
    return dummyHead.next;
}

// 判断链表中是否有环
// 快慢指针，快指针每次走两步，慢指针每次一步，每次移动快指针与慢指针之间的距离-1
public static boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode l1 = head, l2 = head;
    while (l1 != null && l2.next != null){
        l1 = l1.next;
        l2 = l2.next.next;
        if (l1 == l2) return true;
    }
    return false;
}

// 获取链表中环的入口结点
public static ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode fast = pHead, slow = pHead;
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    if (fast == null || fast.next == null) return null;
    slow = pHead;
    while (fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

// 单链表排序
public static ListNode sortInList (ListNode head) {
    // write code here
    if (head == null || head.next == null) return head;

    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode sorted = dummy;

    while (sorted.next != null){
        //循环遍历链表，存储当前节点和前一节点
        ListNode pre = sorted;
        ListNode cur = sorted.next;
        //存储最小节点和最小节点前一节点
        ListNode preMin = null;
        ListNode min = null;

        while (cur != null){
            if (min == null || cur.val < min.val){
                preMin = pre;
                min = cur;
            }
            pre = pre.next;
            cur = cur.next;
        }

        preMin.next = min.next;
        min.next = sorted.next;
        sorted.next = min;
        sorted = min;
    }
    return dummy.next;
}

字符串相关

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
// 替换空格（简单）
// 方法1：直接替换
public static String replaceSpace(StringBuffer str) {
    StringBuffer res = new StringBuffer();
    for (int i = 0; i < str.length(); i++) {
        char b = str.charAt(i);
        if (String.valueOf(b).equals(" ")){
            res.append("%20");
        } else {
            res.append(b);
        }
    }
    return res.toString();
}
// 方法2：API
public static String replaceSpace2(StringBuffer str) {
    return str.toString().replaceAll("\\s","%20");   //空格 \\s
}


//匹配括号深度
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    int cnt = 0, max = 0, i;
    for (i = 0; i < s.length(); i++) {
        if (s.charAt(i)== '(')
            cnt++;
        else cnt--;
        max = Math.max(max, cnt);
    }
    sc.close();
    System.out.println(max);
}


//大数加法
public static String solve (String s, String t) {
    StringBuilder stringBuilder = new StringBuilder();
    int i = s.length() - 1, j = t.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry != 0){
        int x = i < 0 ? 0 : s.charAt(i--) - '0';
        int y = j < 0 ? 0 : t.charAt(j--) - '0';
        int sum = x + y + carry;
        stringBuilder.append(sum % 10);
        carry = sum / 10;
    }
    return stringBuilder.reverse().toString();
}


// 括号序列，判断括号序列是否合法
public static boolean isValid (String s) {
    // write code here
    if (s.length() % 2 == 1) return false;  //奇数必不合法
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '['){
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false; // 需要输出但是栈空，不合法
            char pop = stack.pop();
            if (c == ')' && pop != '(') return false;
            else if (c == ']' && pop != '[') return false;
            else if (c == '}' && pop != '{') return false;
        }
    }
    return stack.isEmpty();  //
}


//最长公共前缀  
//排序，然后将第一个和最后一个元素的字符串从前往后比较
public static String replaceSpace(String[] strs) {
    int len = strs.length;
    StringBuilder res = new StringBuilder();
    Arrays.sort(strs);
    int m = strs[0].length();
    int n = strs[len - 1].length();
    int num = Math.min(m, n);

    for (int i = 0; i < num; i++) {
        if (strs[0].charAt(i) == strs[len-1].charAt(i)){
            res.append(strs[0].charAt(i));
        } else
            break;
    }
    return res.toString();
}


// 判断回文串
public static boolean isPalindrome(String s) {
    char[] cs = s.toCharArray();
    if (cs.length == 0) return true;
    int l = 0;
    int r = s.length() - 1;
    while (l < r){
        if (!Character.isLetterOrDigit(cs[l])) l++;
        else if (!Character.isLetterOrDigit(cs[r])) r--;
        else {
            if (Character.toLowerCase(cs[l]) != Character.toLowerCase(cs[r])) 
                return false;
            l++;
            r--;
        }
    }
    return true;
}


// 最长回文子串
// 1.暴力法
private static int index, len;
public static String longestPalindrome (String s){
    if (s.length() < 2)
        return s;
    for (int i = 0 ; i < s.length() - 1 ; i++){
        PalindromeHelper(s, i, i);
        PalindromeHelper(s, i, i + 1);
    }
    return s.substring(index, index + len);
}

private static void PalindromeHelper(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
        l--;r++;
    }
    if (len < r - l - 1) {
        index = l + 1;
        len = r - l - 1;
    }
}

// 2.动态规划
public static int getLongestPalindrome(String A, int n) {
    int[][] dp = new int[n][n];
    int max = 1;
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    char[] chars = A.toCharArray();
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            //长度为2时，需要特殊处理一下
            //dp[i+1][j-1]会访问到数组的左下方，数组的左下方是没有初始化的
            if (len == 2 && chars[i] == chars[j]){
                dp[i][j] = len;
                max = 2;
                continue;
            }
            if (chars[i] == chars[j] && dp[i+1][j-1] != 0){
                dp[i][j] = len;
                max = len;
            }
        }
    }
    return max;
}

// 最长回文子序列
// 与最长回文子串的区别，子串必须是连续的，序列可以不连续，只要求从前到后顺序不变
public static int longestPalindromeSubseq(String s) {
    int len = s.length();
    int[][] dp = new int[len][len];

    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
        for (int j = i - 1 ; j >= 0 ; j--){
            if (s.charAt(i) == s.charAt(j)){
                dp[i][j] = dp[i-1][j+1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j+1]);
            }
        }
    }
    return dp[len-1][0];
}


// 最长公共子串
public static String LCS (String str1, String str2) {
    // write code here
    int maxIndex = 0, maxLength = 0;
    // 存储以str1中str1[i]结尾，最大公共子串的长度
    int[][] dp = new int[str1.length()+1][str2.length()+1];
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            if (str1.charAt(i) == str2.charAt(j)){
                dp[i + 1][j + 1] = dp[i][j] + 1;
                if (dp[i+1][j+1] > maxLength){
                    maxLength = dp[i + 1][j + 1];
                    maxIndex = i;
                }
            } else
                dp[i+1][j+1] = 0;
        }
    }
    return str1.substring(maxIndex - maxLength + 1, maxIndex + 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
//斐波那契数列
public static int Fibonacci(int number) {
    if (number <= 0) return 0;
    if (number == 1 || number == 2) return 1;
    int first = 1, second = 1, third = 0;
    for (int i = 3; i <= number; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}

// 变态跳台阶
// f(n) = f(n-1) + f(n-2) + ... + f(1)
// f(n-1) = f(n-2) + f(n-3) + ... + f(1)
// f(n) = 2*f(n-1)
// f(n) = 2^(number-1)
public static int JumpFloorII(int number) {
    return 1 << --number;
}

//快速幂
public long normalPower(long base,long power){
	long result=1;
	while(power>0){
		if(power%2==0){
			//幂为偶数 直接减半 底数平方
			power/=2;
			base*=base;
		}else{
			//幂为奇数 会多出来一个数 记得存下来
			power/=2;
			result*=base;
			base*=base;
		}
	}
	return result;
}

//快速幂 位运算优化
public long normalPower(long base,long power){
	long result=1;
	while(power>0){
		if(power & 1 ) result*=base;
		power>>=1;
		base*=base;
	}
	return result;
}


//数值的整数次方,求一个double类型数值的整数幂
public static double Power(double base, int exponent){
    if (equal(base, 0.0) && exponent < 0)
        return 0.0;
    int absexponent = Math.abs(exponent);
    double res = getPower(base, absexponent);
    if (exponent < 0) res = 1.0 / res;
    return res;
}
private static double getPower(double base, int e) {
    //快速幂
    if (e == 0) return 1.0;
    if (e == 1) return base;
    double res = getPower(base, e>>1);
    res *= res;
    if ((e & 1) == 1)
        res *= base;
    return res;
}

private static boolean equal(double num1, double num2) {
    // double类型存在精度误差，不能直接用==判断
    if (Math.abs(num1 - num2) <= 0.000001) return true;
    else return false;
}

数组、栈、队列

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
//调整数组顺序使奇数位于偶数前面
public static void reOrderArray(int [] array) {
    if (array.length == 0 || array.length == 1) return;
    int oddCount = 0, oddBegin = 0;
    int[] newArray = new int[array.length];
    for (int i : array) {
        if ((i & 1) == 1) oddCount++;
    }
    for (int i : array) {
        if ((i & 1) == 1)
            newArray[oddBegin++] = i;
        else
            newArray[oddCount++] = i;
    }
    for(int i=0;i<array.length;i++){
        array[i]=newArray[i];
    }
}

// 子数组的最大累加和问题
public static int maxsumofSubarray (int[] arr) {
    int m = Integer.MIN_VALUE;
    // 从第二个位置开始，存储当前位置可能的最大值
    for (int i = 1; i < arr.length; i++) {
        arr[i] = Math.max(arr[i], arr[i - 1] + arr[i]);
        m = Math.max(m, arr[i]);
    }
    return m;
}

//合并两个有序的数组
public static void merge(int A[], int m, int B[], int n) {
    int i = m - 1, j = n - 1, index = m + n - 1;
    // 从后往前遍历
    while (i >= 0 && j >= 0){
        if (A[i] >= B[j]) A[index--] = A[i--];
        else A[index--] = B[j--];
    }
    while (j >= 0)
        A[index--] = B[j--];
}

// 数组中相加和为0的三元组
public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    if (num == null) return lists;
    if (num.length < 3) return lists;
    // 排序
    Arrays.sort(num);
    int sum, left, right;
    // 固定一个数
    for (int i = 0 ; i < num.length - 2 ; i++){
        if (i != 0 && num[i] == num[i - 1]) continue;
        // 双指针，一个指向大的，一个指向小的
        left = i + 1;
        right = num.length - 1;
        while (left < right){
            // 判断三数相加是否为0
            sum = num[left] + num[right];
            if (sum + num[i] == 0){
                ArrayList<Integer> list = new ArrayList<>();
                list.add(num[i]);
                list.add(num[left]);
                list.add(num[right]);
                lists.add(list);
                // 小指针右移，若碰到相同的字符，继续右移
                left++;
                // 大指针左移，若碰到相同的字符，继续左移
                right--;
                while (left < right && num[left] == num[left - 1]) left++;
                while (left < right && num[right] == num[right + 1]) right--;
            } else if (sum + num[i] < 0) left++;
            else right--;
        }
    }
    return lists;
}


// 用两个栈实现队列
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();

public void push(int node){
    stack1.push(node);
}

public int pop(){
    if (stack1.isEmpty() && stack2.isEmpty())
        throw new RuntimeException("Queue is Empty");
    if (stack2.isEmpty()){
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
    }
    return stack2.pop();
}

//栈的压入弹出序列，输入压入序列，判断弹出序列是否合法
public static boolean IsPopOrder(int [] pushA,int [] popA) {
    if (pushA.length == 0 || popA.length == 0) return false;
    Stack<Integer> s = new Stack<>();
    int popIndex = 0;
    for (int i : pushA) {
        s.push(i);
        while (!s.empty() && s.peek() == popA[popIndex]) {
            s.pop();
            popIndex++;
        }
    }
    return s.empty();
}

// 螺旋数组
public static ArrayList<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> list = new ArrayList<>();
    if (matrix.length == 0) return list;
    int lr = 0, lc = 0, rr = matrix.length - 1, rc = matrix[0].length - 1, i;
    while (lr <= rr && lc <= rc){
        for ( i = lc ; i <= rc ; i++){
            list.add(matrix[lr][i]);
        }
        lr++;
        for ( i = lr; i <= rr; i++) {
            list.add(matrix[i][rc]);
        }
        rc--;
        if (lr <= rr){
            for ( i = rc ; i >= lc; i--){
                list.add(matrix[rr][i]);
            }
            rr--;
        }
        if (lc <= rc) {
            for ( i = rr; i >= lr; i--) {
                list.add(matrix[i][lc]);
            }
            lc++;
        }
    }
    return list;
}

二叉树相关

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
// 二叉树的层序遍历
// 按之字形打印二叉树，一层顺序，一层倒序
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    if (pRoot == null) return null;
    Queue<TreeNode> queue = new LinkedList<>();
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    queue.offer(pRoot);
    while (!queue.isEmpty()){
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = queue.size(); i > 0 ; i--) {
            TreeNode t = queue.poll();
            if (ans.size() % 2 != 0) arrayList.add(0, t.val);//根据层数判断是顺序还是倒序
            else arrayList.add(t.val);
            if (t.left != null) queue.offer(t.left);
            if (t.right != null) queue.offer(t.right);
        }
        ans.add(arrayList);
    }
    return ans;
}

// 在二叉树中找到两个节点的最近公共祖先
public static int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    // 当前树为空，返回-1
    if (root == null) return -1;
    // 若这两个节点的值有一个与根节点相同
    // 则这两个节点在当前树的最近公共祖先的值为根节点的值
    if (o1 == root.val || o2 == root.val) return root.val;
    // 如果该节点不是o1,o2, 那么o1,o2必然在该节点的左子树和右子树中
    // 递归，在该节点的左子树和右子树中搜索o1,o2
    int left = lowestCommonAncestor(root.left, o1, o2);
    int right = lowestCommonAncestor(root.right, o1, o2);
    // 若左边为空，返回右节点的值，反之亦然
    if (left == -1) return right;
    if (right == -1) return left;
    return root.val;
}

// 根据前序和中序序列重建二叉树，找到根节点，然后分别重建左子树和右子树
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    if (pre.length == 0) return null;
    int root = pre[0];
    TreeNode r = new TreeNode(root);
    int index = 0;
    for (int i = 0; i < pre.length; i++) {
        if (vin[i] == root){
            index = i;
            break;
        }
    }
    // Arrays.copyOfRange为[)区间，前闭合，后不闭合
    r.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,index + 1),
                                   Arrays.copyOfRange(vin, 0, index));
    r.right = reConstructBinaryTree(Arrays.copyOfRange(pre,index + 1,pre.length),
                                    Arrays.copyOfRange(vin, index + 1, pre.length));
    return r;
}

图相关

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// 图克隆，深拷贝一个图
// bfs遍历 + HashMap存储遍历过的节点
public Node cloneGraph(Node node) {
    if (node == null) return node;
    HashMap<Node, Node> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    map.put(node, new Node(node.val));
    while (!queue.isEmpty()){
        Node a = queue.poll();
        for (Node neighbor : a.neighbors) {
            if (!map.containsKey(neighbor)){
                map.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            map.get(a).neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}

// 课程表
// 拓扑排序，BFS实现
List<List<Integer>> edges;
int[] indeg;
public boolean canFinish(int numCourses, int[][] prerequisites) {
    edges = new ArrayList<List<Integer>>();
    for (int i = 0; i < numCourses; i++) {
        edges.add(new ArrayList<Integer>());
    }
    indeg = new int[numCourses];
    for (int[] info : prerequisites) {
        edges.get(info[1]).add(info[0]);
        ++indeg[info[0]];
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indeg[i] == 0)
            queue.offer(i);
    }

    int visited = 0;
    while (!queue.isEmpty()){
        ++visited;
        int u = queue.poll();
        for (int v : edges.get(u)) {
            --indeg[v];
            if (indeg[v] == 0)
                queue.offer(v);
        }
    }
    return visited == numCourses;
}

// 最小高度树
// 类似拓扑排序，BFS遍历，从度为1的节点开始，逐步出队，最后出队的必然是最中间的节点，以它为根的树必然是最小高度树
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer> res = new ArrayList<>();
    if (n == 1){
        res.add(0);
        return res;
    }
    int[] degree = new int[n];
    List<List<Integer>> map = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        map.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        degree[edge[0]]++;
        degree[edge[1]]++;
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) queue.offer(i);
    }
    while (!queue.isEmpty()){
        res = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int cur = queue.poll();
            res.add(cur);
            List<Integer> neighbors = map.get(cur);
            for (int neighbor : neighbors) {
                degree[neighbor]--;
                if (degree[neighbor] == 1)
                    queue.offer(neighbor);
            }
        }
    }
    return res;
}

// 阈值距离内邻居最少的城市,两种最短路径算法模板
// 迪杰斯特拉算法（单源最短路径）
public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
    int[][] distances = new int[n][n];
    int INF = 0x3f3f3f3f;
    // 初始化邻接矩阵
    for (int[] distance : distances) {
        Arrays.fill(distance, INF);
    }
    for (int i = 0; i < n; i++) {
        distances[i][i] = 0;
    }
    for (int[] edge : edges) {
        distances[edge[0]][edge[1]] = distances[edge[1]][edge[0]] = edge[2];
    }
    int res = 0;
    int MIN = n + 1;
    // n次迪杰斯特拉
    for (int i = 0; i < n; i++) {
        int[] dist = new int[n];
        boolean[] set = new boolean[n];
        // 初始化距离
        for (int v = 0; v < n; v++) {
            dist[v] = distances[i][v];
        }
        // 与自己的距离为0
        dist[i] = 0;
        set[i] = true;
        // n个顶点逐个加入
        for (int j = 0; j < n; j++) {
            int min = INF;  // 暂存i到j的最小值
            int start = i;  // 获取出发节点i
            for (int k = 0; k < n; k++) {       // 寻找节点j到其他节点距离最小的节点
                if (!set[k] && dist[k] < min){  // 没访问过k，且到k距离小，start=k
                    min = dist[k];
                    start = k;
                }
            }
            set[start] = true;                  // 将start加入已访问集合
            for (int k = 0; k < n; k++) {       // 搜索以k为中间节点，到其他点的最小值
                if (!set[k] && dist[k] > dist[start] + distances[start][k])
                    dist[k] = dist[start] + distances[start][k];
            }
        }

        int temp = 0;
        for (int j = 0; j < dist.length; j++) {
            if (dist[j] <= distanceThreshold)
                temp++;
        }
        if (temp <= MIN){
            MIN = temp;
            res = i;
        }
    }
    return res;
}

// 弗洛伊德算法（全源最短路径）
public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
    // 初始化邻接矩阵
    int[][] distances = new int[n][n]
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                distances[i][j] = 0;
            }
            else {
                distances[i][j] = Integer.MAX_VALUE;
            }
        }
    }
    for (int[] edge : edges) {
        distances[edge[0]][edge[1]] = distances[edge[1]][edge[0]] = edge[2];
    }
	// 弗洛伊德算法
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != k && j != k && distances[i][k] != Integer.MAX_VALUE
                    && distances[k][j] != Integer.MAX_VALUE){
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }
        }
    }
    int res = -1, min = n + 1;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (i != j && distances[i][j] <= distanceThreshold)
                count++;
        }
        if (min >= count){
            min = count;
            res = i;
        }
    }
    return res;
}

动态规划

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
148
149
150
151
152
153
154
155
156
157
158
159
160
// 01背包
// 采药
public class 采药 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();   	// 总体力
        int n = sc.nextInt();		// n种药
        int dp[] = new int[t+1];
        int c[] = new int[n];		// 采每种药消耗的体力
        int v[] = new int[n];		// 采每种药获取的价值
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        sc.close();
        for (int i = 0; i < n; i++) {			// 循环遍历每种药
            for (int j = t; j >= c[i]; j--) {	// 查看加入每种药之后的最大价值
                dp[j] = Math.max(dp[j], dp[j-c[i]] + v[i]);
            }
        }
        System.out.println(dp[t]);
    }
}

// 完全背包
// 疯狂的采药
public class 疯狂的采药 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int n = sc.nextInt();
        int dp[] = new int[t+1];
        int c[] = new int[n];
        int v[] = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        sc.close();
        for (int i = 0; i < n; i++) {		  // 循环遍历每种药
            for (int j = c[i]; j <= t; j++) { // 只要还能往里加，一直加
                dp[j] = Math.max(dp[j], dp[j-c[i]]+v[i]);
            }
        }
        System.out.println(dp[t]);
    }
}

//最长上升子串/子序列
public class 最长上升子串 {
    static int a[],dp[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new int[n];
        dp = new int[n+1];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            dp[i] = 1;
        }
        sc.close();
        // 最长上升子序列
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (a[j] < a[i])
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//            }
//        }
//        int ans = 0;
//        for (int i = 0; i < n; i++) {
//            ans = Math.max(ans, dp[i]);
//        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (a[i-1]<a[i]) dp[i] = Math.max(dp[i-1]+1, dp[i]);
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}

// 最长公共子串/子序列
public class 最长公共子串 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        int ans = 0;
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        // 最长公共子序列
//        for (int i = 1; i <= s1.length(); i++) {
//            for (int j = 1; j <= s2.length(); j++) {
//                if (s1.charAt(i-1) == s2.charAt(j-1)){
//                    dp[i][j] = dp[i-1][j-1] + 1;
//                } else {
//                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
//                }
//            }
//        }
//        System.out.println(dp[s1.length()][s2.length()]);
        System.out.println(ans);
    }
}

//扩展：打印最长公共子序列
public class 最长公共子串 {
    static int[][] dp;
    static int[][] b;
    static String s1;
    static String s2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s1 = sc.nextLine();
        s2 = sc.nextLine();
        dp = new int[s1.length()+1][s2.length()+1];
        b = new int[s1.length()+1][s2.length()+1];
        int ans = 0;
        // 最长公共子序列
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    b[i][j] = 1;        // 来自左上方
                } else {
                    if (dp[i-1][j] > dp[i][j-1]){
                        dp[i][j] = dp[i-1][j];
                        b[i][j] = 2;    // 来自左方
                    } else {
                        dp[i][j] = dp[i][j-1];
                        b[i][j] = 3;    // 来自上方
                    }
                }
            }
        }
        System.out.println(dp[s1.length()][s2.length()]);
        Print(s1.length(), s2.length());
    }

    private static void Print(int i, int j) {
        if (i == 0 || j == 0) return;
        if (b[i][j] == 1){
            Print(i-1,j-1);
            System.out.print(s1.charAt(i-1));
        } else if(b[i][j] == 2){
            Print(i-1, j);
        } else if (b[i][j] == 3){
            Print(i, j-1);
        }
    }
}

数据结构

红黑树的五个特点

  1. 每个节点非红即黑；
  2. 根节点总是黑色的；
  3. 每个叶子节点都是黑色的空节点（NIL节点）；
  4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
  5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

红黑树的应用： TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。

B树，B+树，B*树

B树

B树（B-树）是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。

B树的每个节点包括：

  1. 本节点所含的关键字个数
  2. 指向父节点的指针
  3. 关键字
  4. 指向子节点的指针数组

B树的特点：

  • B-tree是一种多路搜索树（并不是二叉的），对于一棵M阶树：
  • 定义任意非叶子结点最多只有M个孩子；且M>2；
  • 根结点的孩子数为[2, M]，除非根结点为叶子节点；
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  • 非叶子结点的关键字个数=指向儿子的指针个数-1；
  • 每个非叶子结点存放至少M/2-1（取上整）和至多M-1个关键字；
  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 所有叶子结点位于同一层；

B+树

B+树是应文件系统所需而产生的一种B-tree的变形树。 相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

B+树特点

  1. B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
  2. B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
  3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
  4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B*树

B*树是B+树的变种，相对于B+树他们的不同之处如下：

  1. 首先是关键字个数限制问题，B+树初始化的关键字初始化个数是ceil(m/2)，b树的初始化个数为（ceil(2/3m)）
  2. B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

B*树特点： 在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B树额分解次数变得更少；

堆排序

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
public class 堆排序 {
    public static void main(String[] args) {
        int[] arr = {16, 7, 3, 20, 17, 8};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void heapSort(int[] arr) {
        //创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    private static void adjustHeap(int[] arr, int parent, int length) {
        //将temp作为父节点
        int temp = arr[parent];
        //左孩子
        int lChild = 2 * parent + 1;
        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[lChild]) {
                break;
            }
            // 把孩子结点的值赋给父结点
            arr[parent] = arr[lChild];
            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }
}

操作系统

死锁的四个条件

  • 互斥条件：该资源任意一个时刻只由一个线程占用

  • 请求与保持条件：一个进程因请求资源而阻塞时，对以获得的资源保持不放。

  • 不剥夺条件：线程以获得的资源在未使用完之前不能被其他线程强行剥夺，只有自己使用完才释放资源

  • 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

    如何避免死锁

  1. 互斥条件：该条件无法破坏，因为我们用锁本来就是想让他们互斥
  2. 请求与保持条件：一次性申请所有的资源
  3. 不剥夺条件：占用部分资源的线程进一步申请其他资源时，如果申请不到可主动释放它占有的资源。
  4. 循环等待条件：靠按序申请资源来预防。

计算机网络

三次握手和四次挥手

SYN标志位：发起一个新的连接

ACK标志位：确认标志位，1位，表示确认序号是否有效

FIN标志位：结束一个连接

三次握手：

第一次握手：客户端发送，SYN位置1，生成序号（连接后，序号递增）

第二次握手：服务器发送，SYN位置1，生成序号（连接后，序号递增），ACK位置1，确认序号=客户端序号+1

第三次握手：客户端发送，ACK位置1，确认序号=服务器序号+1

四次挥手：

第一次挥手：客户端发送，FIN位置1，发送序号

第二次挥手：服务器发送，ACK位置1，确认序号=客户端序号+1

第三次挥手：服务器发送，FIN位置1，发送序号

第四次挥手：客户端发送，ACK位置1，确认序号=服务器序号+1

问：是否了解TCP/IP中三次握手和四次挥手机制吗？

答：TCP/IP协议是传输层的一个面向连接的安全可靠的传输协议

三次握手：

三次握手的机制是为了保证能建立一个安全可靠的连接。

第一次握手是由客户端发起，客户端会向服务端发送一个报文，在报文里面：SYN标志位置为1，表示发起新的连接。

当服务器收到这个报文之后就知道客户端要和我建立一个新的连接，于是服务端就向客户端发送一个确认消息包，在这个消息包里面：ACK标志位置1，表示确认客户端发起的第一次连接请求。

以上两次握手之后，对客户端而言：已经明确了我既能给服务端成功发送消息，也能收到服务端的响应，但对服务端而言：服务端只知道客户端给我发送的消息我能收到，但我相应给客户端的消息，客户端能否收到我是不知道的。所以还需要第三次握手。

第三次握手就是当客户端收到服务端发送的确认响应报文之后，还要继续给服务端进行回应，也是一个ACK标志位置1的确认消息。经过这三次连接，客户端和服务端都能确认我既能给对方发消息，也能收到对方发送的消息。那么这个连接就被安全的建立了。

四次挥手：

四挥挥手的机制是为了保证能安全的结束连接。

第一次挥手是客户端发起，客户端会向服务器端发送一个报文，在报文中：FIN标志位置1，表示客户端已准备结束当前连接。

第二次挥手是服务器发起，服务器会向客户端发送一个确认消息包，在这个消息包中，ACK标志位置1，表示确认接收到了客户端的请求。

第三次挥手是服务器发起，服务器会向客户端发送一个报文，报文中FIN标志位置1，表示服务器已准备结束当前连接。

第四次挥手是客户端发起，客户端会向服务器发送一个确认消息包，其中ACK标志位置1，表示确认收到了服务器的消息。

问：为什么是四次挥手，不能是三次？

答：第二次挥手后，服务器虽然收到了客户端的断开连接的请求，但是其仍可能需要向客户端发送一些消息，在这些消息发完之后才会断开连接，执行第三次挥手。所以接收断开连接请求和断开连接要分两次发送，第一次是确认收到消息，第二次才是执行断开连接，中间可能会继续向客户端发送一些消息。

Java基础面试题

接口和抽象类的区别

答：对成员函数而言，抽象类中可以存在普通的成员函数，而接口中只能存在public abstract final类型的。

对成员变量而言，抽象类中的成员变量可以是各种类型的，而接口中成员变量只能是public static final类型的。

抽象类只能继承一个，接口可以实现多个。

补充：

抽象类是对类本质的抽象，相当于包含并实现所有子类的通用特性。

接口是对行为的抽象，即实现类可以做什么，对于实现类主体是谁并不关心。

使用场景：关注一个事物的本质的时候，用抽象类；关注一个操作的时候，用接口。

抽象类的功能要远超过接口，但是定义抽象类的代价高，Java每个类只能继承一个类，在这个类中，必须继承或编写出其所有子类的所有共性。虽然接口在功能上会弱化许多，但是只是针对一个动作的描述，而且一个类中可以同时实现多个接口，在设计阶段会降低难度。

List和Set的区别

  • List：有序，按对象进入的顺序保存对象，可重复，允许多个null元素对象，可用迭代器取出所有元素，再逐一遍历，还可以用get(index)获取指定下标的元素。
  • Set：无序，不可重复，最多允许一个null对象，取元素时只能用Iterator接口取得所有元素，然后再逐一遍历元素。

ArrayList和LinkedList的区别

  • ArrayList： 基于动态数组，连续内存存储，适合下标访问（随机访问）

    扩容机制：因为数组的长度固定，超出长度存数据时需要新建数组，然后将老数组的数据拷贝到新数组。

    如果不是尾部插入数据，会涉及到元素的移动，使用尾插法并指定初始容量（不用扩容，浪费时间）可以极大提升性能，甚至超过LinkedList（需要创建大量node对象）。

  • LinkedList：基于链表，可以存储在分散的内存，适合做数据的插入和删除，不适合查询。

    遍历LinkedList必须使用iterator，不适合使用for循环，因为每次for循环体内通过get(i)取得某一元素时都要对list重新进行遍历，性能消耗极大。

    不要试图使用indexOf返回元素索引，并利用其进行遍历，使用indexOf对list进行了遍历，而且结果为空时遍历了整个列表。

HashMap和HashTable的区别及其底层实现

区别：

  • HashMap方法没有用synchronized修饰，线程非安全，HashTable线程安全
  • HashMap允许key和value为null，HashTable不允许

底层实现：数组+链表实现

jdk8开始链表高度到8、数组长度超过64，链表转变为红黑树，元素以内部类Node节点存在

  • 计算key的hash值，二次hash然后对数组长度取模，对应到数组下标
  • 如果没有产生hash冲突，直接创建Node存入数组
  • 如果产生hash冲突，先进行equal比较，相同则替换，不同而判断链表高度插入链表，链表高度达到8，且数组长度达到64则转变为红黑树，长度低于6则将红黑树转回链表
  • key为null，存在下标0的位置

数组扩容同ArrayList。

什么是字节码，采用字节码的好处

  • Java程序通过编译器将程序编译为字节码文件，也就是.class文件。
  • 采用字节码最大的好处：可以实现一次编译，到处运行，与平台无关。
  • JVM通过解释器将字节码文件转为机器可执行的二进制机器码。
  • Java源代码 -> 编译器 -> JVM可执行的Java字节码 -> JVM -> JVM中的解释器 -> 机器可执行的二进制文件 -> 程序运行

双亲委派模型

每个类加载器都有自己的缓存，会将自己加载过的类放到缓存中。Main方法所在的类由AppClassLoader加载。

  • 向上委派：实际上就是查找缓存，是否加载了该类，有则直接返回，没有继续向上。委派到顶层之后，缓存中还是没有，则到加载路径中查找，有则加载返回，没有就向下查找。
  • 向下查找：查找加载路径，有则加载返回，没有就向下查找。

好处：

  • 主要是为了安全性，避免用户自己编写的类动态替换了Java的一些核心类，如：String。
  • 同时也避免了类的重复加载，因为JVM中区分不同类，不仅仅是根据类名，相同的class文件被不同的ClassLoader加载就是不同的两个类。

GC如何判断对象可以被回收

  • 引用计数法：每个对象有一个引用计数器属性，新增一个引用计数器+1，引用释放引用计数器-1，计数器为0时，可回收。

    缺点：可能出现A引用B，B引用A，这时候就算他们都不再使用了，但因为相互引用，计数器一直为1，无法回收。

    有点：效率高。

  • 可达性分析法：从GC Roots开始向下搜索，搜索走过的路径成为引用链。当一个对象到GC Roots没有任何引用链相连时，证明此对象是不可用的，那么虚拟机就判断可回收对象。

    GC Roots的对象有：

    • 虚拟机栈（栈帧中的本地变量表）中引用的对象
    • 方法去中类静态属性引用的对象
    • 方法区中常量引用的对象
    • 本地方法栈中JNI（即一般说的Native方法）引用的对象

可达性算法中的不可达对象并不是立即死亡的，对象拥有一次自我拯救的机会。对象被系统宣告死亡至少经历两次标记过程：第一次是经过可达性分析发现没有与GCRoots相连接的引用链，第二次是由虚拟机自动建立的Finalizer队列中判断是否需要执行finalize()方法。

当对象变成(GC Roots)不可达时，GC会判断该对象是否覆盖了finalize方法，若未覆盖，则直接将其回收。否则，若对象未执行过finalize方法，将其放入F-Queue队列，由一低优先级线程执行该队列中对象的finalize方法。执行finalize方法完毕后，GC会再次判断该对象是否可达，若不可达，则进行回收，否则，对象“复活”。

sleep,wait,join,yield的区别

  1. 锁池

    所以需要竞争同步锁的线程都会被放到锁池中，若当前对象的锁已被其中一个线程得到，其他线程需要在锁池中等待，当前面的线程释放同步锁之后锁池中的线程去竞争同步锁，得到锁之后会进入就绪队列等待cpu的分配。

  2. 等待池

    当我们掉用wait方法后，线程会放到等待池中，等待池的线程不会去竞争同步锁。只有调用了notify后等待池的线程才会开始去竞争锁，notify是随机从等待池选出一个线程放到锁池，而notifyAll是将等待池的所有线程放到锁池中。

sleep和wait的区别：

  • sleep是Thread类的静态本地方法，wait则是Object类的本地方法。
  • sleep方法不会释放lock，但是wait方法会释放，而且会加入到等待队列中。
  • sleep方法不依赖于同步器synchronized，但是wait需要依赖synchronized关键字。
  • sleep不需要被唤醒（休眠之后退出阻塞），而wait需要（不指定时间，需要被别人中断）。
  • sleep一般用于当前线程休眠，或者轮询暂停操作，wait多用于多线程之间的通信。
  • sleep会让出CPU执行时间且强制上下文切换，而wait不一定，notify后可能还是有机会重新竞争到锁继续执行的。

yield执行后，线程直接进入就绪状态，马上释放了cpu的执行权，但是依然保留cpu的执行资格，所以有可能cpu下次进行线程调度还是会让这个线程获取到执行权继续执行。

join执行后，线程进入阻塞状态。例如：线程B中调用线程A的join，那么B线程会进入到阻塞队列，直到线程A结束或中断线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) throws InterruptedException {
    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("222222");
        }
    });
    t1.start();
    t1.join();
    System.out.println("1111");
}

//输出：
222222
1111

对线程安全的理解

堆：堆是进程和线程共有的空间，分全局堆和局部堆。全局堆就是所有没有分配的空间，局部堆就是用户分配的空间。堆在操作系统对进程初始化的时候分配，运行过程中也可以向系统要额外的堆，但是用完要还给操作系统，不然就是内存泄漏。堆是线程安全问题发生的位置。

Java中，堆是Java虚拟机所管理的内存中最大的一块，是所有线程共享的一块内存区域，在虚拟机启动的时候创建。堆所存在的内存区域的唯一目的就是存放对象实例，几乎所有的对象实例以及数组都在这里分配内存。

栈：栈是每个线程独有的，保存其运行状态和局部变量的。栈在线程开始的时候初始化，每个线程的栈相互独立，因此，栈是线程安全的。操作系统在切换线程的时候会自动切换栈。栈空间不需要再高级语言里面显示的分配和释放。

对守护线程的理解

守护线程：为所有非守护线程提供服务的线程；任何一个守护线程都是整个JVM中所有非守护线程的保姆；

守护线程依赖于整个进程而运行；哪天其他线程都结束了，程序就结束了，会直接结束守护线程。因此不要把IO、File等重要操作逻辑分配给守护线程。

守护线程的作用：

举例：GC垃圾回收线程:就是一个经典的守护线程，当我们的程序不再有任何运行的Thread，程序就不会在产生垃圾，垃圾回收器就无事可做，所以当垃圾回收线程是JVM上仅剩的线程时，垃圾回收线程会自动离开。它始终在低级别的状态中进行，用于实时监控和管理系统中的可回收资源。

应用场景：

  1. 来为其他线程提供服务支持的情况。

  2. 在任何情况下，程序结束时，这个线程必须正常且立即关闭；

    反之，若一个正在执行某个操作的线程必须要正确地关闭掉否则会出现不好的后果的话，那么这个线程就不能是守护线程，而是用户线程。

设置：thread.setDeamon(true)， 必须要在start之前设置。

在守护线程中产生的线程也是守护线程。

守护线程不能用于访问固有资源，比如读写操作或者计算逻辑。因为它会在任何时候甚至一个操作的中间发生中断。

Java自带的多线程框架，如ExecutorService，会将守护线程转换为用户线程，所有如果要使用后台线程就不能用java的线程池。

ThreadLocal的原理和使用场景

每一个Thread对象都有一个ThreadLocalMap类型的成员变量threadLocal，它存储本线程中所有ThreadLocal对象以及其对应的值。

ThreadLocalMap由一个个Entry对象构成。

Entry继承自WeakReference<ThreadLocal<?>>，一个Entry由ThreadLocal对象和Object构成。由此可见，Entry的key是ThreadLocal对象，并且是一个弱引用。当没有指向key的强引用后，该key就会被垃圾回收器回收。

当执行set方法时，ThreadLocal首先会获取当前线程对象，然后获取当前线程的ThreadLocalMap对象。再将ThreadLocal对象为key，将值存储进ThreadLocalMap对象中。

get类似。

由于每一条线程均含有各自私有的ThreadLocalMap容器，这些容器相互独立不影响，因此不会存在线程安全问题，从而也无需使用同步机制来保证多条线程访问容器的互斥性。

使用场景：

  1. 再进行对象跨层传递的时候，使用ThreadLocal可以避免多次传递，打破层次间的约束。

  2. 线程间数据隔离。

  3. 使用事务操作，用于存储线程事务信息。

  4. 数据库连接，Session会话管理。

1
Spring框架在事务开始时会给当前线程绑定一个Jdbc Connection，在整个事务过程都是使用该线程绑定的connection来进行数据库操作，实现了事务的隔离性，Spring框架里面就是用的ThreadLcoal来实现这种隔离

ThreadLocal内存泄漏原因，如何避免

内存泄漏：为程序在申请内存后，无法释放已申请的内存空间，一次内存泄漏危害可以忽略，但内存泄漏堆积后果很严重。

不再会被使用的对象或者变量占用的内存不能被回收，就是内存泄漏。

强引用：使用最普遍的引用(new、反射)，一个对象具有强引用，不会被垃圾回收器回收。当内存空间不足时，java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不回收这种对象。

如果想取消强引用和某个对象之间的关联，可以显式地将引用赋值为null，这样可以使JVM在合适的时间就回收该对象。

弱引用：JVM进行垃圾回收时，无论内存是否充足，都会回收被弱引用关联的对象。在java中，用java.lang.WeakReference类表示。可以在缓存中使用弱引用。

ThreadLocal的实现原理，每一个Thread维护一个ThreadLocalMap，key为使用弱引用的ThreadLocal实例，value为线程变量的副本

实线为强引用，虚线为弱引用。

ThreadLocalMap使用ThreadLocal的弱引用作为key，如果一个ThreadLocal不存在外部强引用时，Key势必会被GC回收，这样就导致ThreadLocalMap中key为null，而value还存在着强引用，只有线程退出之后，value的强引用链条才会断掉，但如果线程迟迟不结束的话，这些key为null的Entry的value就会一直存在一条强引用链。

key使用强引用

当ThreadLocalMap的key为强引用回收ThreadLocal时，因为ThreadLocalMap还持有ThreadLocal的强引用，如果没有手动删除，ThreadLocal不会被回收，导致Entry内存泄漏。

key使用弱引用

当ThreadLocalMap的key为弱引用回收ThreadLocal时，由于ThreadLocalMap持有ThreadLocal的弱引用，即使没有手动删除，ThreadLocal也会被回收。当key为null时，在下一次ThreadLocalMap掉用set，get，remove方法的时候会被清除value值。

因此，ThreadLocal内存泄漏的根源是：由于ThreadLocalMap的生命周期和Thread一样长，如果没有手动删除对应key就会导致内存泄漏，而不是因为弱引用。

ThreadLocal正确的使用方法

  • 每次使用完ThreadLocal都调用它的remove方法清除数据。
  • 将ThreadLocal变量定义成private static，这样就一直存在ThreadLocal的强引用，也就能保证任何时候通过ThreadLocal的弱引用访问到Entry的value值，进而清除掉。

并发的三大特性

  • 原子性

  • 可见性

    总线Lock：总线锁定协议

    MESI：缓存一致性协议

  • 有序性（禁止指令重排）

synchronized：同时保证三大特性

volatile：可见性+有序性，final可见性

原子性+可见性来保证线程安全，如：AtomicInteger：volatile（可见）+cas（原子）

为什么用线程池，解释下线程池参数

1、 降低资源消耗：提高线程利用率，降低创建和销毁线程的消耗。

2、提高相应速度：任务来了，直接有线程可用可执行，而不是先创建线程在执行。

3、提高线程的可管理性：线程是稀缺资源，使用线程池可以统一分配调优监控。

  • corePoolSize：核心线程数，也就是正常情况下创建工作的线程数，这些线程创建后并不会消除，而是一种常驻线程。

  • maxinumPoolSize：最大线程数，表示最大允许被创建的线程数。当任务很多，将核心线程数用完了，还是无法满足需求时，此时就会创建新的线程，但是线程池内线程总数不会超过最大线程数。

  • keepAliveTime：超出核心线程数之外的线程的空闲存活时间。

  • workQueue：用来存放待执行的任务，假设核心线程都已被使用，还有任务进来则全部放入队列，直到整个队列被放满但任务还再持续进入则会创建新的线程

  • ThreadFactory：线程工厂，用来生产线程执行任务。可以使用默认的创建工厂，产生的线程都在一个组内，拥有相同的优先级，且都不是守护线程。也可以选择自定义线程工厂，一般根据业务置定不同工厂。

    一个创建线程的接口，里面只有一个创建线程的方法，设置名字，设置线程参数。

  • Handler：任务拒绝策略。两种情况，第一种是掉用shutdown等方法关闭线程池后，这时候即使线程池内部还有没执行完的任务正在执行，由于线程池已经关闭，我们再继续向线程池提交任务就会被拒绝。另一种是达到最大线程数，线程池已经没有能力处理新提交的任务时，拒绝。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /**
     * 四种拒绝策略：
     *
     * new ThreadPoolExecutor.AbortPolicy() 
     * 银行满了，还有人进来，不处理这个人的，抛出异常
     *
     * new ThreadPoolExecutor.CallerRunsPolicy() 
     * 哪来的去哪里！比如你爸爸 让你去通知妈妈洗衣服，妈妈拒绝，让你回去通知爸爸洗
     *
     * new ThreadPoolExecutor.DiscardPolicy() 
     * 队列满了，丢掉任务，不会抛出异常！
     *
     * new ThreadPoolExecutor.DiscardOldestPolicy() 
     * 队列满了，尝试去和最早的竞争，也不会抛出异常！
     */

线程池中阻塞队列的作用

1、 一般的队列只能保证作为一个有限长度的缓冲区，如果超出了缓冲长度，就无法保留当前的任务了，阻塞队列可以保留住当前想要继续入队的任务。

阻塞队列可以保证任务队列中没有任务时阻塞获取任务的线程，使线程进入wait状态，释放cpu资源。

阻塞队列自带阻塞和唤醒的功能，不需要额外处理，无任务执行时，线程池利用阻塞队列的take方法挂起，从而维持核心线程的存活、不至于一直占用cpu资源。

问：为什么先添加到阻塞队列，而不是创建新线程。

答：消耗资源、影响效率。在创建新线程的时候，是要获取全局锁的，这个时候其它的就得阻塞，影响了整体效率。

线程池中线程复用原理

线程池将线程和任务进行解耦，线程是线程、任务是任务，拜托了之前通过Thread创建线程时的一个线程必须对应一个任务的限制。

在线程池中，同一个线程可以从阻塞队列中不断获取新任务来执行，其核心原理在于线程池对Thread进行了封装，并不是每次执行任务都会调用Thread.start()来创建新线程，而实让每个线程去执行一个“循环任务”，在这个“循环任务”中不停检查是否有新的任务需要被执行，如果有则直接执行，也就是掉用任务中的run方法，将run方法当成一个普通的方法执行，通过这种方式只是用固定的线程就将所有任务的run方法串联起来。

框架相关问题

Spring

1. Spring是什么

轻量级的开源J2EE框架。它是一个容器框架，用来装JavaBean(java对象)，中间层框架可以起一个连接作用，可以让我们的企业开发更快更简洁。

Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器框架。

  • 从大小和开销两方面而言，Spring都是轻量级的。（侵入性低）
  • 通过IoC达到松耦合的目的
  • 提供了面向切面编程的丰富支持，允许通过分离应用的业务逻辑与系统级服务进行内聚性的开发（如专门开发一个打日志的切面）
  • 包含并管理应用对象(Bean)的配置和生命周期，这个意义上是一个容器
  • 将简单的组合配置、组合成复杂的应用，这个意义上是一个框架

2. 对AOP的理解

系统是由许多不同的组件所组成的，每个组件各负责一块特定功能。除了实现自身核心功能之外，这些组件还经常承担着额外的职责。例如日志，事务管理和安全这样的核心业务经常融入到自身具有核心业务逻辑的组件中去。这些系统服务经常被称为横切关注点，因为他们会跨越系统的多个组件。

当我们需要为分散的对象引入公共行为的时候，OOP（面向对象）显得无能为力，OOP允许定义从上到下的关系，但并不合适定义从左到右的关系。如日志功能。

在OOP设计中，它导致大量代码的复用，而不利于各个模块的重用。

AOP：将程序中的交叉业务逻辑（如安全、日志、事务）,封装成一个切面，然后注入到目标对象（具体的业务逻辑）中。AOP可以对某个对象或某些对象的功能进行增强，比如对象中的方法进行增强，可以在执行某个方法之前、之后额外做一些事情。

3. 对IoC的理解

三个方面：容器概念、控制反转、依赖注入

IoC容器：实际上就是一个map(key, value)，里面存放的是各种对象（在xml里配置的bean节点、@repository、@service、@controller、@component），在项目启动的时候会读取配置文件中的bean节点，根据全限定类名使用反射创建对象放到map里，扫描到带以上注解的类还是通过反射将对象放到map里。

这时候map里面就有各种对象了，接下来在代码里需要用到里面的对象时，再通过依赖注入(autowired, resource等注解，xml里bean节点的ref属性，项目启动的时候就会读取xml节点的ref属性根据id注入，也会扫描这些注解，根据类型或id注入，id就是对象名)。

控制反转：没有引入IoC容器之前，对象A依赖于对象B，那么对象A在初始化或者运行到某一点的时候，自己需要主要去创建对象B或者使用已经创建的对象B。无论是创建还是使用对象B，控制权都在自己手上。

引入IoC容器之后，对象A与对象B之间失去了直接联系，当对象A运行到需要对象B的时候，IoC容器会主动创建一个对象B注入到对象A需要的地方。

通过前后的对比，不难看出：对象A获得依赖对象B的过程，有主动行为变为了被动行为，控制权颠倒过来了，这就是“控制反转”。

全部对象的控制权全部上缴给“第三方”IoC容器，所以IoC容器成了整个系统的关键核心，它起到了一种类似“粘合剂”的作用，把系统中的所有对象粘合在一起发挥作用，如果没有这个“粘合剂”，对象与对象之间会彼此失去联系。

依赖注入：控制被反转之后，获得依赖对象的过程由自身管理变为了由IoC容器自动注入。依赖注入是实现IoC的方法，就是由IoC容器在运行期间，动态地将某种依赖注入到对象之中。

4. BeanFactory与ApplicationContext的区别

ApplicationContext是BeanFactory的子接口。

ApplicationContext提供了更完整的功能：

  1. 继承MessageSource（其中 getMessage(String code, Object[] obj, Locale locale) 方法用于对国际化的支持），因此支持国际化。

  2. 统一的资源文件访问方式。（Resources接口，通过不同的实现访问不同的资源 URLResource 、 ClassPathResource 、 FileSystemResource ）

  3. 提供监听器中注册bean的事件。

  4. 同时加载多个配置文件。

  5. 载入多个（有继承关系）上下文，使每一个上下文都专注于一个特定的层次，如应用的web层。

  • BeanFactory采用的是延迟加载的形式来注入Bean，即只有在使用到某个Bean的时候才对该Bean进行加载实例化。这样我们就不能发现一些存在的Spring配置问题，如果Bean的某一个属性没有注入，BeanFactory加载后，直至第一次使用调用getBean方法才会抛出异常。

    ApplicationContext是在容器启动的时候一次性创建了所有的Bean。这样，容器启动时，我们就可以发现Spring中存在的配置错误，这样有利于检查所依赖属性是否注入。ApplicationContext启动后预载入所有的单例Bean，通过预载入单例Bean，确保当你需要的时候不用等待。

    ApplicationContext唯一的不足是占用内存空间，当应用程序配置Bean较多时，程序启动较慢。

  • BeanFactory通常以编程的方式被创建，ApplicationContext还能以声明的方式创建，如使用ContextLoader。

    BeanFactory和ApplicationContext都支持BeanPostProcessor、BeanFactoryPostProcessor的使用，但两者的区别是：BeanFactory需要手动注册，而ApplicaitonContext则是自动注册。

5. SpringBean的生命周期

  1. 解析类得到BeanDefinition（所有Bean的抽象，存放 class名，bean工厂的名称，依赖的bean等等…）。
  2. 通过反射创建一个Bean实例
  3. 对对象中的加了@Autowired注解的属性进行属性填充
  4. 回调Aware方法，获取容器中的一些组件，如BeanNameAware（获取bean在IoC的注册名称），BeanFactoryAware（获取当前BeanFactory，可以调用容器服务）
  5. 调用BeanPostProcessor的初始化前的方法
  6. 调用初始化方法
  7. 调用BeanPostProcessor的初始化后的方法，在这里会进行AOP
  8. 如果当前创建的bean是单例的则会把bean放入单例池
  9. 使用bean
  10. Spring容器关闭时调用DisposableBean的destory()方法

6. 解释Spring支持的Bean的作用域

  • singeton：默认，每个容器中只有一个bean的实例，单例模式由BeanFactory自身来维护。该对象的生命周期是与SpringIOC容器一致的（单子第一次被注入的时候才会创建）。
  • prorotype：为每一个bean请求提供一个实例。在每次注入时都会创建一个新的对象
  • request：bean被定义为在每个HTTP请求中创建一个单例对象，也就是说单个请求中都会复用这个对象。
  • session：与request范围类似，确保每个session中有一个bean实例，在session过期后，bean会随之失效。
  • application：bean被定义为ServletContext（跨IoC容器）的生命周期中复用一个单例对象。
  • websocket：websocket被定义为websocket的生命周期中复用一个单例对象。

7. Spring框架中的单例Bean是线程安全的吗

Spring中的Bean默认是单例模式的，框架并没有对Bean进行多线程的封装处理。实际上，大部分Bean 是无状态的，在某种程度上说Bean也是安全的，但如果Bean有状态的话，就要开发者自己去保证线程安全了，最简单的就是改变bean的作用域，把“singleton”改为“prototype”，这样请求bean相当于new Bean()了，保证了线程安全。

  • 有状态就是有数据存储的功能。
  • 无状态就是不会保存数据。

问：Spring如何处理线程并发问题？

答：一般只有无状态的Bean蔡可以在多线程下共享，大部分是无状态的Bean。当存在有状态的Bean时，spring一般是用ThreadLocal进行处理，解决线程安全问题。

ThreadLocal会为每一个线程提供一个独立的变量副本，从而隔离了多个线程对数据的访问冲突。因为每一个线程都拥有自己的变量副本，所以没有相同变量的访问冲突问题，所以可以把不安全的变量封装进ThreadLocal。

8. Spring框架中用到了哪些设计模式

简单工厂：有工厂类根据传入的参数，动态决定应该创建哪一类产品类。

Spring中的BeanFactory就是简单工厂模式的体现，根据传入一个唯一的标识来获得Bean对象，会调用该Bean的getObject方法，所以返回的不是factory这个bean，而是bean.getObject()方法的返回值。

工厂方法：

实现了FactoryBean接口的bean是一类叫做factory的bean。其特点是，spring会在使用getBean调用该bean时，会自动调用该bean的getObject方法，所以返回的不是factory这个bean，而实bean。getObject返回值。

单例模式：保证一个类仅有一个实例，并提供一个访问它的全局访问点。

spring中的单例模式完成了后半句话，即提供了全局的访问点BeanFactory。但没有从构造器级别去控制单例，这是因为spring管理的是任意的java对象。

适配器模式：

Spring定义了一个适配接口，使得每一种Controller有一种对应的适配器实现类，让适配器代替Controller执行相应的方法。这样在扩展Controller时，只需要增加一个适配器类就完成了SpringMVC的扩展了。

装饰器模式：动态地给一个对象添加一些额外的职责。就添加功能来说，Decorator模式比生成子类更灵活。

Spring中用到装饰器模式在类名上有两种表现：一种含Wrapper，另一种含Decorator。

动态代理：

切面在应用运行的时刻被织入。一般情况下，在织入切面时，AOP容器会为目标对象动态的创建一个代理对象。SpringAOP就是以这种方式织入切面的。

织入：把切面应用到目标对象并创建新的代理对象的过程。

观察者模式：

Spring事务驱动模型使用的是观察者模式，Soring中Observer模式常用的地方是listener的实现。

策略模式:

Spring框架的资源访问Resource接口。该接口提供了更强的资源访问能力，Spring框架本身大量使用了Resource接口访问底层资源。

9. Spring事务的实现方法、隔离级别

事务这个概念是数据库层面的，Spring只是基于数据库中的事务进行了扩展，以及提供了一些能让程序员更加方便操作事务的方式。

实现方式：

  1. 编程式：自己编写相关sql。
  2. 声明式：@Transactional

可以在某个方法上加上@Transactional开启事务，这个方法的所有sql都会在一个事务中执行，统一成功或失败。

在一个方法上加了@Transactional注解之后，Spring会基于这个类生成一个代理对象，将这个代理对象作为bean，当在使用这个代理对象的方法时，如果这个方法上存在@Transactional注解，那么代理逻辑会把事务的自动提交设置为false，然后再去执行原本的业务逻辑方法，如果执行业务逻辑方法没有出现异常，那么代理逻辑中就会将事务提交，若出现异常，则回滚。默认会对RuntimeException和Error进行回滚，可以利用rollbackFor属性进行配置。

隔离级别：

spring事务隔离级别就是数据库的隔离级别：外加一个默认级别

  • read uncommitted（未提交读）
  • read committed（提交读、不可重复读）
  • repeatable read（可重复读，Spring，Mysql默认）
  • serializable（可串行化）

最终配置的隔离级别以Spring的配置为准，若数据库不支持Spring配置的隔离级别，效果取决于数据库。

10. Spring事务传播机制

多个事务相互调用时，事务如何在这些方法间传播。

如：方法A是一个有事务的方法，方法A执行的过程中调用了方法B，那么方法B有无事务对事务的要求不同都会对方法A的事务具体执行造成影响，同时方法A的事务对方法B的事务执行影响，

REQUIRED：Spring默认的事务传播类型， 当前没有事务，则自己新建一个事务，若当前存在事务，则加入这个事务。

SUPPORTS：当前存在事务，则加入当前事务，若没有事务，就以非事务方法执行。

MANDATORY：当前存在事务，则加入当前事务，当前事务不存在，则抛出异常。

REQUIRES_NEW：创建一个新事物，如果存在当前事务，则挂起该事务。

NOT_SUPPORTED: 以非事务方法执行，如果当前存在事务，则挂起当前事务。

NEVER：不使用事务，如果当前事务存在，则抛出异常。

NESTED：如果当前事务存在，则在嵌套事务中执行，否则REQUIRED的操作一样。

NESTED与REQUIRES_NEW的区别

REQUIRES_NEW是创建一个事务并且新开启的这个事务与原有事务无关，而NESTED则是当前存在事务时，会开启一个嵌套事务。在NESTED情况下，父事务回滚时，子事务也会回滚，而在REQUIRES_NEW情况下，不会影响新开启的事务。

NESTED与REQUIRED的区别

REQUIRED情况下，调用方存在事务时，则被调用方和调用方使用同一事务，那么被调用方出现异常时，由于共用一个事务，所以无论调用方是否catch其异常，事务都会回滚。而在NESTED情况下，被调用方发生异常时，调用方可以用catch捕获其异常。

11. Spring事务什么时候会失效

Spring事务的原理是AOP，进行了切面增强，那么失效的原因是这个AOP不起作用了！常用情况如下几种：

  1. 发生自调用，类里面使用this调用本类的方法，此时这个this不是代理类，而实UserService对象本身。

    解决方法：不要用this去调本类方法，将this改为UserService。

  2. 方法不是public的

    @Transaction只能用于public的方法上，否则事务不会失效，如果要用在非public方法上，可以开启AspectJ代理模式。

  3. 数据库不支持事务

  4. 没有被spring管理

  5. 异常被吃掉，事务不会滚（或抛出的异常没有被定义，默认为RuntimeException）

12. Bean的自动装配

开启自动装配： 在中定义“autowired”

autowired属性的五种装配方式：

  • no - 缺省情况下，自动装配是通过“ref”属性手动设定

  • byName - 根据bean的id通过setter进行自动装配

  • byType - 根据bean的类型进行自动装配

    找到多个bean，报错，可以使用@Qualified指定

  • constructor - 类似byType，不过是应用于构造器的参数。如果一个bean与构造器参数的类型相同，则自动装配，否则导致异常。

    构造函数中存在需要装配的类则进行自动装配

  • autodetect - 如果有构造器，则通过constructor进行装配，否则使用byType进行装配。

@Autowired自动装配bean，可以在字段、setter方法，构造函数中的使用。

13. Spring、SpringMVC、SpringBoot之间的区别

Spring是一个IOC容器，用来管理Bean，使用依赖注入实现控制反转，可以很方便的整合各种框架，提供AOP机制弥补OOP的代码重复问题，更方便将不同类不同方法的共同处理抽取成切面、自动注入给方法执行，比如日志、异常等。

SpringMVC是Spring对web框架的一个解决方案，提供了一个总的前端控制器Servlet，用来接收请求，然后定义了一套路由策略（url到handle的映射）及适配执行handle，将handle结果使用视图解析技术生成视图展现给前端。

SpringBoot是Spring提供的一个快速开发工具包，让程序员能更方便、更快速开发Spring+SpringMVC应用，简化了配置（约定大于配置），整合了一系列的解决方案(starter机制)，redis，mongodb，es可以开箱即用。

SpringMVC

1. SpringMVC的工作流程

  1. 用法发送请求至前端控制器DispatcherServlet

  2. DispatcherServlet收到请求调用HandlerMapping处理器映射器。

    HandlerMapping维护url到Handler的映射。

  3. 处理器映射器找到具体的处理器，生成处理器及处理器拦截器（如果有则生成）并返回给DispatcherServlet。

  4. DispatcherServlet调用HandlerAdapter处理器适配器。

    处理器可能是Controller、@RequestMapping、Servlet，需要通过适配器适配。

  5. HandlerAdapter经过设配器调用具体的处理器。

  6. Controller执行完成，返回ModelAndView。

  7. HandlerAdapter将controller执行结果ModelAndView返回给DispatcherServlet。

  8. DispatcherServlet将ModelAndView传给ViewReslover试图解析器。

  9. ViewResolver解析后返回具体View。

  10. DispatcherServlet根据View进行渲染视图。（即将模型数据填充至视图中）

  11. DispatcherServlet响应用户。

SpringMVC的九大组件

Handler：处理器，它直接应对MVC中的Controller层，它的具体表现形式有很多，可以是类，也可以是方法。如Controller层中@RequestMapping标注的所有方法。只要可以实际处理请求就可以是Handler。

  1. HandlerMapping

    处理器映射器，类似于一个Map，存储url->handler的映射。在SpringMVC中会有很多请求，每个请求都需要一个Handler处理，具体接收到一个请求之后使用哪个Handler进行，这就是HandlerMapping需要做的事。

  2. HandlerAdapter

    处理器适配器，因为SpringMVC中的Handler可以是任意的形式，只要能处理请求就ok，但是Servlet需要的处理方法的结构却是固定的，都是以request和response为参数的方法。如何让固定的Servlet处理方法调用灵活的Handler来尽心处理就是HandlerAdapter要做的事情。

    类比：HandlerMapping用于根据需要干的活找到相应的工具；HandlerAdapter是使用工具

  3. HandlerExceptionResolver

    其他组件都是用来干活的，其过程中难免会出现异常。HandlerExceptionResolver根据异常设置ModelAndView，之后再交给render方法进行渲染。

  4. ViewResolver

    ViewResolver用来将String类型的视图名解析为View类型的视图。View是用来渲染页面的，也就是将程序返回的参数填入模板里，生成html(或其他类型)文件。两个关键问题：使用哪个模板、使用什么技术？这是ViewResolver主要要做的工作，ViewResolver需要找到渲染所用的模板和所用的技术进行渲染，具体的渲染过程则交由不同的试图自己完成。

  5. RequestToViewNameTranslator

    ViewResoler根据ViewName查找View。如果Handler返回void，就需要从request获取ViewName。

  6. LocaleResolver

    解析试图需要两个参数，一个是视图名，一个是Locale。LocaleResolver从request解析出Locale，Locale就是zh-cn之类的，表示一个区域，有了这个就可以对不同区域的用户显示不同的结果。

    两个作用：1.ViewResolver视图解析的时候。2. 用到国际化资源或主题的时候。

  7. ThemeResolver

    用于解析主题，SpringMVC中一个主题对应一个properties文件，里面存放着跟当前主题相关的资源（图片，css样式）。

  8. MultipartResolver

    处理上传请求。将request包装成MultipartHttpServletRequest，后者可以直接调用getFile方法获取File，如果上传多个文件，还可以调用getFileMap得到FileName->File结构的Map。

  9. FlashMapManager

    用于管理FlashMap，用于再redirect中传递参数

SpringBoot

1. SpringBoot自动配置原理

@SpringBootApplication三个主要的注解：

  1. @SpringBootConfiguration：标记当前类为配置类
  2. @EnableAutoConfiguration：开启自动配置
  3. @ComponentScan：扫描主类所在的同级包以及下级包里的Bean

其中最主要的是@EnableAutoConfiguration：

1）SpringBoot启动的时候加载了主配置类，开了自动配置@EnableAutoConfiguration

2）@EnableAutoConfiguration作用：

  • 利用EnableAutoConfigurationImportSelector给容器导入一些组件

  • 可以查看selectImports方法的内容：

  • List configurations = getCandidateConfigurations(annotationMetadata,attributes);获取候选的配置

    • SpringFactoriesLoader.loadFactoryNames();
扫描所有jar包类路径  META-INF/spring.factories
把扫描到的这些文件的内容包装成Properties对象
从properties中获取到EnableAutoConfiguration.class类（类名）对应的值，然后把他们添加在容器中

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

        将类路径下META-INF/spring.factories里面配置的所有EnableAutoConfiguration的值加入到了容器中。

      3）每一个自动配置类进行自动配置功能

      4）以 HttpEncodingAutoConfiguration配置为例：

      ```java
      @Configuration
      @EnableConfigurationProperties(HttpEncodingProperties.class)
      @ConditionalOnWebApplication(type = ConditionalOnWebApplication.Type.SERVLET)
      @ConditionalOnClass(CharacterEncodingFilter.class)
      @ConditionalOnProperty(prefix = "spring.http.encoding", value = "enabled", matchIfMissing = true)
      public class HttpEncodingAutoConfiguration {

@Configuration：标明为配置类
@EnableConfigurationProperties(HttpEncodingProperties.class)声明开启属性注入
@ConditionalOnClass(CharacterEncodingFilter.class)当CharacterEncodingFilter在类路径的条件下
@ConditionalOnProperty(prefix = “spring.http.encoding”, value = “enabled”, matchIfMissing = true)当spring.http.encoding=enabled的情况下，如果没有设置则默认为true，即条件符合
@ConditionalOnMissingBean当容器中没有这个Bean时新建Bean

mybatis-spring-boot-starter、spring-boot-starter-web等组件的META-INF文件下均含有spring.factories文件，自动配置模块中，SpringFactoriesLoader收集到文件中的类全名并返回一个全类名的数组，返回的全类名通过反射被实例化，就形成了具体的工厂实例，工厂实例来生成组件具体需要的bean。

2. 如何理解SpringBoot中的Starter

使用Spring+SpringMVC时，如果需要引入Mybatis等框架，需要到xml中定义mybatis需要的bean。

starter就是定义一个starter的jar包，写一个@Configuration配置类，将这些bean定义在里面，然后再starter包的META-INF/spring.factories中写入该配置类，springboot会按照约定来加载配置类

开发人员只需要将对应的starter包依赖进应用，进行相应的属性配置（使用默认配置时，不需要配置），就可以直接进行代码开发，使用对应的功能了。

3.嵌入式服务器

节省了下载安装tomcat，应用也不需要再打war包，然后放到webapp目录下运行

只需要安装了java虚拟机，就可以直接在上面部署应用程序了

springboot已经内置了tomcat.jar，运行main方法时会去启动tomcat，并利用tomcat的spi机制加载SpringMVC。

Mybatis

1. MyBatis的优缺点

优点：

1、基于SQL语句编程，相当灵活，不会对应用程序或者数据库的现有设计造成任何影响，SQL写在XML里，解除sql与程序代码的耦合，便于统一管理；提供XML标签，支持编写动态SQL语句，并可重用。

2、与JDBC相比，减少了50%以上的代码量，消除了JDBC大量冗余的代码，不需要手动开关连接；

3、很好地与各种数据库兼容（因为Mybatis使用JDBC来连接数据库，所以只要JDBC支持的数据库MyBatis都支持）。

4、能与Spring很好的集成；

5、提供映射标签，支持对象与数据库的ORM字段关系映射，提供对象关系映射标签，支持对象关系组件维护。

缺点：

1、SQL语句的编写工作量比较大，尤其当字段多、关联表多时，对开发人员编写SQL语句功底有一定的要求。

2、SQL语句依赖于数据库，导致数据库移植性差，不能随意更换数据库。

2. #{}和${}的区别是什么

#{}是预编译处理、是占位符

${}是字符串替换、是拼接符

Mybatis在处理#{}时，会将sql中的#{}替换为？，调用PreparedStatement来赋值

Mybatis在处理${}时，就是把${}替换为变量的值，调用Statement来赋值

#{}的变量替换是在DBMS中，变量替换后自动加上单引号

${}的变量替换是发生在DBMS外，不加单引号

使用#{}可以有效地防止SQL注入。

3. 最佳实践相关

问：最佳实践中，通常一个 Xml 映射文件，都会写一个 Dao 接口与之对应，请问，这个 Dao 接口的工作原理是什么？Dao 接口里的方法，参数不同时，方法能重载吗？

答：Mapper接口是没有实现类的，当调用接口方法时，接口全限名+方法名拼接字符串作为 key 值，可唯一定位一个MappedStatement。举例：com.mybatis3.mappers.StudentDao.findStudentById，可以唯一找到 namespace 为com.mybatis3.mappers.StudentDao下面id = findStudentById的MappedStatement。在 MyBatis 中，每一个<select>、<insert>、<update>、<delete>标签，都会被解析为一个MappedStatement对象。

Dao 接口里的方法可以重载，但是Mybatis的XML里面的ID不允许重复。

4. Mybatis插件运行原理

Mybatis的插件，指的就是拦截器。Mabatis只支持对ParameterHandler、ResultSetHandler、StatementHandler、Executor这4种接口的插件，Mybatis使用JDK的动态代理，为需要拦截的接口生成代理对象以实现接口方法拦截功能，每当执行这4种接口对象的方法时，就会进入拦截方法，具体就是invocationHandler的invoke()方法，拦截那些你指定需要拦截的方法。

插件编写：实现MyBatis的Interceptor接口并复写intercept()方法，然后再给插件编写注解，指定要拦截哪一个接口的哪些方法即可，在配置文件中编写配置编写的插件。

数据库

索引的基本原理

索引用来快速地寻找那些具有特定值的记录。如果没有索引，一般来说执行查询时遍历整张表。

索引的原理：

  • 把创建了索引的列的内容进行排序
  • 对排序结果生成倒排序
  • 在倒排序内容上拼上数据地址链
  • 在查询的时候，先拿到倒排序表内容，再取出数据地址链，从而拿到具体数据

MySQL聚簇和非聚簇索引

聚簇和非聚簇都是用的B+数。

  • 聚簇索引：将数据存储和索引放到一块、并且是按照一定的顺序组织的，找到索引也就找到了数据，数据的物理存放顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻的存放在磁盘上的。适合范围查询。
  • 非聚簇索引：叶子节点不存储数据、存储的是数据行地址，也就是说根据索引查找数据行的位置再取磁盘查找数据，则就有点类似一本书的目录，根据目录的对应页码再去对应的页码看文章。

优势：

  • 查询通过聚簇索引可以直接获取数据，相比非聚簇索引需要第二次查询（非覆盖索引的情况下）效率更高

    覆盖索引：只查索引，不查数据

    非覆盖索引：需要查找索引之外的其他数据

  • 聚簇索引对于范围查询的效率很高，因为其数据是按照大小排列的

  • 聚簇索引适合用在排序的场合，非聚簇索引不合适

劣势：

  • 维护索引很昂贵，特别是插入新行或者主键被更新导致要（操作系统）分页的时候。建议在大量插入新行后，选在负载较低的时间段，通过OPTIMIZE TABLE优化表，因为必须被移动的行数据可能造成碎片。使用独享表空间可以弱化碎片。
  • 表因为使用UUID（随机ID）作为主键，是数据存储稀疏（无序），这就会出现聚簇索引有可能有比全表扫描更慢，索引建议使用int的auto_increment作为主键。
  • 如果主键比较大的话，那么辅助索引（id）将会变得更大，因为辅助索引的叶子存储的是主键值：过长的主键值，会导致非叶子节点占用更多的物理空间。

InnoDB一定有主键，主键一定是聚簇索引，不手动设置、则会使用unique索引，没有unique索引，则会使用数据库内部的一个行的隐藏id来作为主键索引。在聚簇索引之上创建的索引称之为辅助索引，辅助索引访问数据总是需要两次查找，非聚簇索引都是辅助索引，像复合索引、前缀索引、唯一索引，辅助索引叶子节点存储的不在是行的物理位置，而是主键值。

MyISAM使用的是非聚簇索引，没有聚簇索引，非聚簇索引的两颗B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。

mysql索引的数据结构

索引的数据结构和具体存储引擎的实现相关。在MySQL中使用较多的索引有Hash索引，B+树索引等，InnoDB存储引擎的默认索引实现有：B+树索引。对于哈希索引来说，底层的数据结构是哈希表，因此在绝大多数需求为单条记录查询的时候，可以选择哈希索引，查询性能最快；其余大部分场景，建议选择B+Tree索引。

B+树：

B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互连接。在B+树上的常规检索，从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速左右移动，效率非常高。因此，B+树索引被广泛应用于数据库、文件系统等场景。

哈希索引：

哈希索引就是采用哈希算法，把键值换算成新的哈希值，检索时只需要一次哈希算法即可立即定位到相应的位置，速度非常快。

如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值：前提是键值都是唯一的。如果键值不是唯一的，就需要找到该键所在的位置，然后再根据链表往后扫描，直到找到相应的数据。

如果是范围查询检索，这是哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，可能变成不在连续的了，就没办法再利用索引完成范围查询检索。同理，哈希索引也没办法利用索引完成排序，也不支持多列联合索引的最左匹配规则。

索引设计的原则

查询更快、占用空间更小

1、适合索引的列是出现在where子句中的列，或者连接子句中指定的列

2、基数较小的表（数据量少），索引效果较差，没必要再此列建立索引

3、使用短索引，如果对长字符串进行索引，对应指定一个前缀长度，这样能够节省大量索引空间，如果搜索词超过索引前缀长度，则使用索引排除不匹配的行，然后检查其余行是否可能匹配。

4、不要过度索引。索引需要额外的磁盘空间，并降低写操作的性能。在修改表内容的时候，索引会进行更新甚至重构，索引列越多，这个时间越长，所以只保持需要的索引有利于查询即可。

5、定义有外键的数据列一定要建立索引。

6、更新频繁字段不适合创建索引。

7、若是不能有效区分数据的列不适合做列索引（如：性别，就两种：男、女，区分度低）

8、尽量的扩展索引，不要新建索引。如：标中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。

9、对于那些查询中很少涉及的列，重复值比较多的列不要建立索引表。

10、对于定义为text、image和bit的数据类型的列不要建立索引。

MySQL锁的类型有哪些

基于锁的属性分类：共享锁、排它锁

基于锁的粒度分类：行级锁(InnoDB)、表级锁(InnoDB、MYISAM)、页级锁(BDB引擎)、记录锁、间隙锁、临键锁。

基于所得状态分类：意向共享锁、意向排他锁

  • 共享锁：又称读锁：当一个事务为数据加上读锁之后，其他事务只能对该数据加读锁，而不能对数据加写锁，直到所有的读锁释放之后其他事务才能对其进行加持写锁。

    共享锁的特性主要是为了支持并发的读取数据，读取数据的时候不支持修改，避免出现重复读的问题。

  • 排他锁：又称写锁：当一个事务为数据加上写锁时，其他请求将不能为数据加任何锁，直到该锁释放之后，其他事务才能对数据进行加锁。排它锁的目的是在数据库修改时，不允许其他人同时修改，也不允许其他人读取，避免出现脏数据和脏读的问题。

  • 表锁：表锁是指上锁的时候锁住的是整个表，当下一个事务访问该表的时候，必须等前一个事务放了锁才能进行访问。

    特点：粒度大，加锁简单，容易冲突。

  • 行锁：行锁是指上锁的时候锁住的是表的某一行或多行记录，其他事务访问同一张表时，只有被锁住的记录不能被访问，其他记录可正常访问。

    特点：粒度小，加锁比表锁麻烦，不容易冲突，相比表锁支持的并发要高

  • 记录锁：行锁的一种，记录锁只是表中的某一条记录。精准条件命中，并且命中的条件字段是唯一索引。

    加了记录锁之后数据可以避免在查询的时候被修改的重复读问题，也避免了在修改的事务未提交前被其他事务读取的脏读问题。

  • 页锁：粒度介于行锁和表锁之间的一种锁，一次锁定相邻的一组记录。

    开销在表锁与行锁之间；会出现死锁

  • 间隙锁：行锁的一种，锁定的是表记录的某一个区间，遵循左开右闭 (]

  • 临键锁：行锁的一种，是InnoDB的行锁默认算法，总给来说它就是记录锁和间隙锁的组合，临键锁会把查询出来的记录锁住，同时也会把该范围查询内的所有空隙空间也锁住。

如果当事务A加锁成功之后就设置一个状态告诉后面的人，已经有人对表里的行加了一个排它锁了，你们不能对整个表加共享锁或排它锁了，那么后面需要对整个表加锁的人只需要获取这个状态就知道自己是不是可以对表加锁，便面了整个索引树的每个节点扫描是否加锁，而这个状态就是意向锁。

  • 意向共享锁：当一个事务试图对整个表进行加共享锁之前，首先需要获得这个表的意向共享锁。
  • 意向排它锁：当一个事务试图对整个表进行加排他锁之前，首先需要获得这个表的意向排他锁。

MySQL执行计划

事务的基本特性和隔离级别

基本特性：ACID，分别是：

原子性：一个事务中的操作要么全部成功，要么全部失败

一致性：数据库总是从一个一致性的状态转换到另一个一致性的状态。如A给B转账100元，假设A只有90元，支付之前我们数据库里的数据都是符合约束的，但是如果事务执行成功了，我们的数据库就破坏约束了，因此事务不能成功，这里我们说事务提供了一致性的保证。

隔离性：一个事务的修改在最终提交之前，对其他事务是不可见的。

持久性：事务一旦提交，所做的修改就会永久保存到数据库中。

隔离性的4个隔离级别：

  • read uncommit: 读未提交，可能会督导其他事务未提交的数据，也叫脏读。

  • read commit：读已提交，两次读取的结果不一致，叫不可重复读。

    不可重复读解决了脏读的问题，他只会读取已经提交的事务。

  • repeatable read: 可重复读，mysql默认，每次读取结果都一样，可能产生幻读。

  • serializable： 串行，一般是不会使用的，给每一行读取的数据加锁，会导致大量超时和锁竞争问题。

脏读：某个事务已更新一份数据，另一个事务在此时读取了同一份数据，由于某些原因，前一个RollBack了操作，则后一个事务所读取的数据就会是不正确的。

不可重复读：在一个事务的两次查询之中数据不一致，这可能是两次查询过程中插入了一个事务更新的原有的数据。

幻读：在一个事务的两次查询中数据不一致，例如有一个事务查询了几列数据，而另一个事务却在此时插入了新的几列数据，先前的事务在接下来的查询中，就会发现有几列数据是它先前没有的。

怎么优化慢查询

在业务系统中，除了使用主键进行的查询，其他的都会在测试库上测试其耗时。

查询慢的原因：1.是查询条件没有命中索引？2.是load了不需要的数据列？3.是数据量太大？

优化：

  • 首先分析语句，看看是否load了额外的数据列，可能是查询了多余的行并且丢弃掉了，可能是加载了许多结果中不需要的列，对sql语句分析以及重写。
  • 分析语句的执行计划，然后获得其使用索引的情况，之后修改语句或者修改索引，使得语句可以尽可能的命中索引。
  • 如果对语句的优化已经无法进行，可以考虑表中的数据量是否太大，如果是的话可以进行横向或者纵向的分表。

ACID靠什么保证的

A原子性由undo log日志保证，它记录了需要回滚的日志信息，事务回滚时撤销已经执行成功的sql。

C一致性由其他三大特性保证，程序代码要保证业务上的一致性

I隔离性由MVCC保证

D持久性由内存+redo log来保证，mysql修改数据同时在内存和redo log记录这次操作，宕机的时候可以从redo log恢复。redo log 记录的是物理层面的数据页、偏移量。应对的问题是：MySQL异常宕机后，如何将没来得及提交的事物数据重作出来。

InnoDB redo log 写盘， InnoDB事务进入prepare状态
如果前面prepare成功，bin log写盘，再继续将事务日志持久化到bin log，如果持久化成功，那么InnoDB事务则进入commit状态(在redo log里面写一个commit记录)

redo log的刷盘会在系统空闲时进行

MVCC

MVCC：多版本并发控制：读取数据时通过一种类似快照的方式将数据保存下来，这样读锁就和写锁不冲突了，不同的事务session会看到自己特定版本的数据，版本链

MVCC只在READ COMMITTED和REPEATABLE READ两个隔离级别下工作。其他两个隔离级别和MVCC不兼容，因为READ UNCOMMITTED总是读取最新的数据行，而不是符合当前事务版本的数据行。而SERIALIZABLE则会对所有读取的行都加锁。

聚簇索引记录中有两个必要的隐藏列：

trx_id: 用来存储每次对某条聚簇索引记录进行修改的时候的事务id。

roll_pointer：每次对哪条聚簇索引记录有修改的时候，都会把老版本写入undo日志中。这个roll_pointer就是存了一个指针，它指向这条聚簇索引记录的上一个版本的位置，通过它来获得上一个版本的记录信息。（注意插入操作的undo日志没有这个属性，因为它没有老版本）

已提交读和可重复读的区别就在于他们生成的ReadView的策略不同

开启事务时会创建ReadView，ReadView维护当前事务的事务id，即未提交的事务id，排序生成一个数组

访问数据，获取数据中的事务id（获取的是事务id最大的记录），对比readview

如果在ReadView的左边（比ReadView都小），可以访问（意味着该事务已经提交）

如果在ReadView的右边（比ReadView都大）或者就在ReadView中，不可以访问，获取roll_pointer，取上一个版本重新对比(在右边意味着，该事务在ReadView生成之后出现，在ReadView中意味着该事务还未提交)

已提交读隔离级别下的事务在每次查询的开始都会生成一个独立的ReadView。

可重复读隔离级别则是在第一次读的时候生成一个ReadView，之后的读都复用之前的ReadView。

MySQL主从同步原理

MySQL的主从复制中主要有三个线程：master(binlog dump thread)、salve(I/O thread, SQL thread)，Master一条线程和slave中的两条线程。

  • 主节点binlog，主从复制的基础是主库记录数据库的所有变更记录到binlog。binlog是数据库服务器启动的那一刻起，保存所有数据库结构或内容的一个文件。
  • 主节点log dump线程，当binlog有变动时，log dump线程读取其内容并发送给从节点。
  • 从节点I/O线程接收binlog内容，并将其写入到relay log文件中。
  • 从节点的SQL线程读取relay log文件内容对数据更新进行重放，最终保证主从数据库的一致性。

注：主从节点使用binlog文件+position偏移量来定位主从同步的位置，从节点会保存其已收到的偏移量，如果从节点发生宕机重启，则会自动从position的位置发起同步。

由于mysql默认的复制方式是异步的，主库把日志发送给从库后不关心从库是否已经处理，这样会产生一个问题就是假设主库挂了，从库处理失败了，这时候从库升为主库后，日志就丢失了。由此产生两个概念：

全同步复制

主库写入binlog后强制同步日志到从库，所有的从库都执行完后才返回给客户端，但是很显然这个方式的话性能会受到严重影响。

半同步复制

和全同步不同的是，半同步复制的逻辑是这样，从库写入日志成功后返回ACK确认给主库，主库收到至少一个从库的确认就认为写操作完成。

简述MyISAM和InnoDB的区别

MyISAM：

不支持事务，但是每次查询都是原子的。

支持表级锁，每次操作都会对整个表加锁。

存储表的总行数

一个MYISAM表有三个文件：索引文件、表结构文件、数据文件

采用非聚簇索引，索引文件的数据域存储指向数据文件的指针。辅索引与主索引基本一致，但是辅索引不用保证唯一性。

InnoDB

支持ACID的事务，支持事务的四种隔离级别

支持行级锁以及外键约束：因此可以支持写并发

不存储总行数

一个InnoDB引擎存储在一个文件空间(共享表空间，表大小不受操作系统控制，一个表可能分布在多个文件里)，也有可能为多个(设置为独立表空间，表大小受操作系统文件大小限制，一般为2G)，受操作系统文件大小的限制。

主键索引采用聚簇索引(索引的数据域存储数据文件本身)，辅索引的数据域存储主键的值；因此从辅索引找数据，需要先通过辅索引找到主键值，再访问主索引；最好使用自增主键，防止插入数据时，为维持B+数结构，文件的大调整。

索引类型对数据库性能的影响

普通索引：允许被索引的数据列包含重复的值。

唯一索引：可以保证数据记录的唯一性。

主键：是一种特殊的唯一索引，在一张表中只能定义一个主键索引，主键用于唯一标识一条记录，使用关键字PRIMARY KEY来创建。

联合索引：索引可以覆盖多个数据列，如INDEX（columnA， columnB）索引。

全文索引：通过建立倒排索引，可以极大的提升检索效率，解决判断字段是否包含的问题，是目前搜索引擎使用的一种关键技术。可以通过ALTER TABLE table_name ADD FULLTEXT(column);来创建全文索引。

索引可以极大的提高数据的查询速度。

通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

但是会降低插入、删除、更新表的速度，因为在执行这些写操作时，还要操作索引文件。

索引需要占物理空间，除了数据表空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大，如果非聚簇索引很多，一旦聚簇索引改变，那么所有非聚簇索引都会跟着变。

Redis事务实现

Redis单条命令保证原子性，但是无rollback机制，所以Redis的命令保证原子性，但是事务不保证原子性，Redis事务可以一次执行多个命令，并且带有以下三个重要保证：

  • 批量操作在发送 EXEC 命令前被放入队列缓存（顺序性）。
  • 收到 EXEC 命令后进入事务执行，事务中任意命令执行失败，其余的命令依然被执行 （一次性）
  • 在事务执行过程，其他客户端提交的命令请求不会插入到事务执行命令序列中（排他性）

一个事务从开始到执行会经历三个阶段：

  • 开启事务(multi)
  • 命令入队
  • 执行事务(exec, 放弃事务 discard)

异常的种类

  • 编译异常，就是代码错误，没有这命令，这个事务会全部失败
  • 运行时异常，语法没错误，但执行时出错，除了有异常的语句，其他的都可以继续执行。

Redis实现乐观锁

WATCH key [key …]监视一个（或多个）key，如果在事务执行之前这个key被其他命令改动，那么事务将被打断，整个事务都会失败。如果修改失败，使用UNWATCH取消监视，然后再使用watch获得最新的数据，再执行事务。

Redis内存淘汰机制

Redis 提供 6 种数据淘汰策略：

  • volatile-lru（least recently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
  • volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
  • volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
  • allkeys-lru（least recently used）：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）
  • allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
  • no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧！

Redis持久化

RDB（Redis DataBase）

redis是内存型数据库，如果不持久化，根据内存断电即失的特点，我们就会失去我们保存好的数据

在指定的时间间隔内将内存中的数据集快照写入磁盘，也就是行话讲的Snapshot快照，它恢复时是将快 照文件直接读到内存里。 Redis会单独创建（fork）一个子进程来进行持久化，会先将数据写入到一个临时文件中，待持久化过程 都结束了，再用这个临时文件替换上次持久化好的文件。整个过程中，主进程是不进行任何IO操作的。 这就确保了极高的性能。如果需要进行大规模数据的恢复，且对于数据恢复的完整性不是非常敏感，那 RDB方式要比AOF方式更加的高效。RDB的缺点是最后一次持久化后的数据可能丢失。

如何触发RDB快照：

1、配置文件中默认的快照配置，建议多用一台机子作为备份，复制一份dump.rdb

2、save和bgsave

  • Save 命令执行一个同步保存操作，将当前 Redis 实例的所有数据快照(snapshot)以 RDB 文件的形式保存到硬盘。保存成功时返回 OK 。

  • BGSAVE 命令执行之后立即返回 OK ， 然后 Redis fork 出一个新子进程，原来的 Redis 进程(父进程)继续处理客户端请求，而子进程则负责将数据保存到磁盘，然后退出。

    客户端可以通过 LASTSAVE 命令查看相关信息，判断 BGSAVE 命令是否执行成功。

3、执行flushall命令，也会产生dump.rdb文件，但里面是空的，无意义

4、退出的时候也会产生dump.rdb文件

如何恢复

1、将备份文件移动到redis安装目录并启动服务即可

2、CONFIG GET dir获取目录

优点

1、适合大规模的数据恢复

2、对数据完整性和一致性要求不高

缺点

1、在一定间隔时间做一次备份，所以如果redis意外down掉的话，就会丢失最后一次快照后所有的修改

2、Fork的时候，内存中的数据被克隆了一份，大致2倍的膨胀性需要考虑。

AOF（Append Only File）

以日志的形式来记录每个写操作，将Redis执行过的所有指令记录下来（读操作不记录），只许追加文件 但不可以改写文件，redis启动之初会读取该文件重新构建数据，换言之，redis重启的话就根据日志文件的内容将写指令从前到后执行一次以完成数据的恢复工作

恢复步骤

正常恢复：启动：设置yes，修改默认的appendonly no，改为yes，将有数据的aof文件复制一份保存到对应目录，恢复：重新启动redis然后重新加载。

异常恢复：启动：设置yes，故意破坏 appendonly.aof 文件！ 修复：redis-check-aof –fix appendonly.aof进行修改恢复：重启redis然后重新加载

重写机制

AOF 文件持续增长而过大时，会fork出一条新进程来将文件重写（也是先写临时文件最后再 rename），遍历新进程的内存中数据，每条记录有一条的Set语句。重写aof文件的操作，并没有读取旧的aof文件，这点和快照有点类似！ Redis会启动AOF文件的内容压缩，只保留可以恢复数据的最小指令集。

触发机制

1、手动触发： 执行bgrewriteaof命令。

2、配置自动触发

auto-aof-rewrite-min-size 表示运行AOF重写是文件最小的大小。默认64M，小于64M就会不自动重写了。

auto-aof-rewrite-percentage 表示（aof_current_size- aof_base_size） / aof_base_size 的比值。 aof文件重写之后当前文件大小增长多少就触发重写

优缺点

优点：

1、每修改同步：appendfsync always 同步持久化，每次发生数据变更会被立即记录到磁盘，性能较差 但数据完整性比较好

2、每秒同步： appendfsync everysec 异步操作，每秒记录 ，如果一秒内宕机，有数据丢失

3、不同步： appendfsync no 从不同步

缺点：

1、相同数据集的数据而言，aof 文件要远大于 rdb文件，恢复速度慢于 rdb。

2、Aof 运行效率要慢于 rdb，每秒同步策略效率较好，不同步效率和rdb相同。

持久化总结

1、RDB 持久化方式能够在指定的时间间隔内对你的数据进行快照存储

2、AOF 持久化方式记录每次对服务器写的操作，当服务器重启的时候会重新执行这些命令来恢复原始 的数据，AOF命令以Redis 协议追加保存每次写的操作到文件末尾，Redis还能对AOF文件进行后台重 写，使得AOF文件的体积不至于过大。

3、只做缓存，如果你只希望你的数据在服务器运行的时候存在，你也可以不使用任何持久化

4、同时开启两种持久化方式 在这种情况下，当redis重启的时候会优先载入AOF文件来恢复原始的数据，因为在通常情况下AOF 文件保存的数据集要比RDB文件保存的数据集要完整。 RDB 的数据不实时，同时使用两者时服务器重启也只会找AOF文件，那要不要只使用AOF呢？作者建议不要，因为RDB更适合用于备份数据库（AOF在不断变化不好备份），快速重启，而且不会有AOF可能潜在的Bug，留着作为一个万一的手段。

5、性能建议 因为RDB文件只用作后备用途，建议只在Slave上持久化RDB文件，而且只要15分钟备份一次就够 了，只保留 save 900 1 这条规则。 如果Enable AOF ，好处是在最恶劣情况下也只会丢失不超过两秒数据，启动脚本较简单只load自己的AOF文件就可以了，代价一是带来了持续的IO，二是AOF rewrite的最后将rewrite过程中产 生的新数据写到新文件造成的阻塞几乎是不可避免的。只要硬盘许可，应该尽量减少AOF rewrite 的频率，AOF重写的基础大小默认值64M太小了，可以设到5G以上，默认超过原大小100%大小重 写可以改到适当的数值。 如果不Enable AOF ，仅靠 Master-Slave Repllcation 实现高可用性也可以，能省掉一大笔IO，也 减少了rewrite时带来的系统波动。代价是如果Master/Slave 同时倒掉，会丢失十几分钟的数据， 启动脚本也要比较两个 Master/Slave 中的 RDB文件，载入较新的那个，微博就是这种架构。

Redis发布和订阅

Redis 发布订阅 (pub/sub) 是一种消息通信模式：发送者 (pub) 发送消息，订阅者 (sub) 接收消息。

Redis 客户端可以订阅任意数量的频道。

下表列出了 redis 发布订阅常用命令：

序号 命令及描述
1 PSUBSCRIBE pattern [pattern …] 订阅一个或多个符合给定模式的频道。
2 [PUBSUB subcommand [argument [argument …]]]( 查看订阅与发布系统状态。
3 [PUBLISH channel message] 将信息发送到指定的频道。
4 [PUNSUBSCRIBE [pattern [pattern …]]] 退订所有给定模式的频道。
5 [SUBSCRIBE channel [channel …]] 订阅给定的一个或多个频道的信息。
6 [UNSUBSCRIBE [channel [channel …]]] 指退订给定的频道。

Redis主从复制

主从复制,读写分离! 80% 的情况下都是在进行读操作!减缓服务器的压力! 架构中经常使用! |

默认情况下,每台Redis服务器都是主节点;且一个主节点可以有多个从节点(或没有从节点) ,但一个从节点只能有一个主节点。

作用：

1、 数据冗余： 主从复制实现了数据的热备份，是持久化之外的一种数据冗余方式。

2、故障恢复： 当主节点出现问题时，可以由从节点提供服务，实现快速的故障恢复；实际上是一种服务的冗余。

3、负载均衡： 在主从复制的基础上，配合读写分离，可以由主节点提供写服务，由从节点提供读服务（即写Redis数据时应用连接主节点，读Redis数据时应用连接从节点）

分担服务器负载；尤其是在写少读多的场景下，通过多个从节点分担读负载，可以大大提高Redis服务器的并发量。

4、高可用基石： 除了上述作用以外，主从复制还是哨兵和集群能够实施的基础，因此说主从复制是Redis高可用的基础。

复制原理

  • Slave启动成功连接到master后会发送一个sync同步命令，Master接到命令,启动后台的存盘进程,同时收集所有接收到的用于修改数据集命令,在后台进程执行完毕之后, master将传送整个数据文件到slave ,并完成一次完全同步。
  • 全量复制：而slave服务在接收到数据库文件数据后, 将其存盘并加载到内存中。
  • 增量复制：Master继续将新的所有收集到的修改命令依次传给slave ,完成同步
  • 但是只要是重新连接master , 一次完全同步(全量复制)将被自动执行!我们的数据-定可以在从机中看到!

哨兵模式

哨兵模式是一种特殊的模式，首先Redis提供了哨兵的命令，哨兵是一个独立的进程，作为进程，它会独立运行。其原理是哨兵通过发送命令，等待Redis服务器响应，从而监控运行的多个Redis实例。

  • 通过发送命令，让Redis服务器返回监控其运行状态，包括主服务器和从服务器。
  • 当哨兵监测到master宕机，会自动将slave切换成master，然后通过发布订阅模式通知其他的从服务器，修改配置文件，让它们切换主机。

故障切换(failover)的过程

  • 假设主服务器宕机，哨兵1先检测到这个结果，系统并不会马上进行failover过程，仅仅是哨兵1主观的认为主服务器不可用，这个现象成为主观下线。
  • 当后面的哨兵也检测到主服务器不可用，并且数量达到一定值时，那么哨兵之间就会进行一次投票，投票的结果由一个哨兵发起，进行failover操作。
  • 切换成功后，就会通过发布订阅模式，让各个哨兵把自己监控的从服务器实现切换主机，这个过程称为客观下线。这样对于客户端而言，一切都是透明的。

优点

1、 哨兵集群,基于主从复制模式,所有的主从配置优点,它全有

2、 主从可以切换,故障可以转移,系统的可用性就会更好

3、 哨兵模式就是主从模式的升级,手动到自动,更加健壮!

缺点

1、 Redis不好在线扩容的,集群容量一旦到达上限,在线扩容就很麻烦

2、 实现哨兵模式的配置其实是很麻烦的,里面有很多选择!

缓存穿透和雪崩

概念：

  • 缓存穿透：key对应的数据在数据源并不存在，每次针对此key的请求从缓存获取不到，请求都会到数据源，从而可能压垮数据源。比如用一个不存在的用户id获取用户信息，不论缓存还是数据库都没有，若黑客利用此漏洞进行攻击可能压垮数据库。
  • 缓存击穿：key对应的数据存在，但在redis中过期，此时若有大量并发请求过来，这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端DB压垮。
  • 缓存雪崩：当缓存服务器重启或者大量缓存集中在某一个时间段失效，这样在失效的时候，大量的请求就会集中到数据库里面这样就会造成数据库压力过大。

缓存击穿和缓存穿透的区别：

  • 缓存击穿：指一个key是热点数据，在不停的扛着大并发，在这个key失效的瞬间，持续的大并发就击穿缓存，直接请求数据库，数据库扛不住这么大并发量，可能会崩溃。
  • 缓存穿透：key不存在，大量的请求在缓存中获取不到，数据库也获取不到，但请求都回到数据库，从而可能压垮数据库。

解决方案：

1、Redis高可用： 这个思想的含义是，既然redis有可能挂掉，那我多增设几台redis，这样一台挂掉之后其他的还可以继续工作，其实就是搭建的集群。

2、限流降级： 这个解决方案的思想是，在缓存失效后，通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个key只允许一个线程查询数据和写缓存，其他线程等待。

3、数据预热： 数据加热的含义就是在正式部署之前，我先把可能的数据先预先访问一遍，这样部分可能大量访问的数据就会加载到缓存中。在即将发生大并发访问前手动触发加载缓存不同的key，设置不同的过期时间，让缓存失效的时间点尽量均匀。

设计模式

单例模式

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
// 懒汉式单例模式
// 缺点：如果类中由一些很占用资源的对象，每次构造需要初始化这些对象很费资源
public class Hungry {
	// 私有化构造
    private Hungry(){}
	
    private final static Hungry HUNGRY = new Hungry();

    public static Hungry getInstance(){
        return HUNGRY;
    }
}


// DCL（双重检测锁）饿汉式
// 缺点：可用reflect对其进行破坏
public class LazyMan {

    private LazyMan(){

    }

    // volatile关键字
    // 1. 可见性：保证了不同线程中对这个变量进行操作时的可见性，某线程修改这一变量，其他线程立即可见
    // 2. 不保证原子性
    // 3. 禁止进行指令重排
    private volatile static LazyMan lazyMan;

    // 双重检测锁模式的  懒汉式单例  DCL
    public static LazyMan getInstance(){
        if (lazyMan == null){
            // 为了避免多线程下懒汉式出现问题，加锁
            synchronized (LazyMan.class){
                if (lazyMan == null){
                    lazyMan = new LazyMan(); // 不是原子性操作
                    /**
                     * 1. 分配内存空间
                     * 2. 执行构造方法，初始化对象
                     * 3. 把这个对象指向这个空间
                     *
                     *  CPU执行时，可能会出现指令重排
                     *  123
                     *  132
                     */
                }
            }
        }
        return lazyMan;
    }
}

// 静态内部类
public class Holder {

    private Holder(){}

    public static Holder getInstance(){
        return InnerClass.HOLDER;
    }

    private static class InnerClass{
        private static final Holder HOLDER = new Holder();

    }
}

// 枚举（无法通过反射破坏）
public enum  EnumSingle {
    INSTANCE;

    public EnumSingle getInstance(){
        return INSTANCE;
    }
}

工厂模式

简单工厂模式

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
// 简单工厂：
// 创建Car接口
// 在静态工厂中实现不同品牌的Car 

// 定义一个接口
public interface Car
{
    void name();
}

// 接口的实现类
public class WuLing implements Car
{
    @Override
    public void name()
    {
        System.out.println("五菱宏光！");
    }
}
public class Model implements Car
{
    @Override
    public void name()
    {
        System.out.println("特斯拉！");
    }
}

// 简单工厂
// 静态工厂模式
public class CarFactory
{
    // 方法一  违反了开闭原则
    public static Car getCar(String car)
    {
        if ("五菱".equals(car))
        {
            return new WuLing();
        }
        else if ("特斯拉".equals(car))
        {
            return new Model();
        }
        else
        {
            return null;
        }
    }
    // 方法二
    public static Car getWuLing()
    {
        return new WuLing();
    }
    public static Car getModel()
    {
        return new Model();
    }
}

//输出
public class Consumer
{
    public static void main(String[] args)
    {
        // 正常方法
        WuLing wuLing = new WuLing();
        Model model = new Model();
        wuLing.name();
        model.name();
        // 使用工厂创建 方法一
        Car wuLingF = CarFactory.getCar("五菱");
        wuLingF.name();
        Car modelF = CarFactory.getCar("特斯拉");
        modelF.name();
        // 方法二
        Car wuLing2 = CarFactory.getWuLing();
        Car model2 = CarFactory.getModel();
        wuLing2.name();
        model2.name();
    }
}

工厂方法模式

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
// 工厂方法模式
// 1. 创建CarFactory接口
// 2. 让不同的品牌实现CarFactory
// 3. 在CarFactory中生产Car
public interface CarFactory
{
    Car getCar();
}
public class WuLingFactory implements CarFactory
{
    @Override
    public Car getCar()
    {
        return new WuLing();
    }
}
public class ModelFactory implements CarFactory
{
    @Override
    public Car getCar()
    {
        return new Model();
    }
}

// 输出
public class Consumer
{
    public static void main(String[] args)
    {
        Car car_WuLing = new WuLingFactory().getCar();
        Car car_Model = new ModelFactory().getCar();
        car_WuLing.name();
        car_Model.name();
        Car car_xiaoPeng = new XiaoPengFactory().getCar();
        car_xiaoPeng.name();
    }
}

简单工厂与工厂方法结论

结构复杂度: simple

代码复杂度: simple

编程复杂度: simple

管理上的复杂度: simple

根据设计原则: 工厂方法模式
根据实际业务: 简单工厂模式

抽象工厂模式

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
// 1. 定义产品接口
// 2. 定义抽象产品工厂，生产产品
// 3. 定义不同品牌的不同产品
// 4. 定义不同品牌的产品工厂，用于生产该品牌产品

// 定义产品接口
// 手机接口
public interface PhoneProduct
{
    void start();
    void shutdown();
    void callup();
    void sendSMS();
}
// 路由器产品接口
public interface RouterProduct
{
    void start();
    void shutdown();
    void openWifi();
    void setting();
}


// 抽象产品工厂
public interface IProductFactory
{
    // 生产手机
    PhoneProduct phoneProduct();
    // 生产路由器
    RouterProduct routerProduct();
}


// 华为手机
public class HuaweiPhone implements PhoneProduct
{
    @Override
    public void start()
    {
        System.out.println("打开华为手机");
    }
    @Override
    public void shutdown()
    {
        System.out.println("关闭华为手机");
    }
    @Override
    public void callup()
    {
        System.out.println("使用华为手机打电话");
    }
    @Override
    public void sendSMS()
    {
        System.out.println("使用华为手机发消息");
    }
}
// 华为路由器
public class HuaweiRouter implements RouterProduct
{
    @Override
    public void start()
    {
        System.out.println("打开华为路由器");
    }
    @Override
    public void shutdown()
    {
        System.out.println("关闭华为路由器");
    }
    @Override
    public void openWifi()
    {
        System.out.println("打开华为wifi");
    }
    @Override
    public void setting()
    {
        System.out.println("设置华为WiFi");
    }
}
// 小米手机和小米路由器与华为一致
// 省略

// 创建产品工厂
// 华为工厂实现产品工厂接口，生产华为手机和华为路由器
public class HuaweiFactory implements IProductFactory
{
    @Override
    public PhoneProduct phoneProduct()
    {
        return new HuaweiPhone();
    }
    @Override
    public RouterProduct routerProduct()
    {
        return new HuaweiRouter();
    }
}
public class XiaomiFactory implements IProductFactory
{
    @Override
    public PhoneProduct phoneProduct()
    {
        return new XiaomiPhone();
    }
    @Override
    public RouterProduct routerProduct()
    {
        return new XiaomiRouter();
    }
}

// 输出
public class Client
{
    public static void main(String[] args)
    {
        System.out.println("====================华为产品====================");
        HuaweiFactory huaweiFactory = new HuaweiFactory();
        PhoneProduct huaweiPhone = huaweiFactory.phoneProduct();
        huaweiPhone.start();
        huaweiPhone.callup();
        huaweiPhone.sendSMS();
        huaweiPhone.shutdown();
        RouterProduct huaweiRouter = huaweiFactory.routerProduct();
        huaweiRouter.start();
        huaweiRouter.openWifi();
        System.out.println("====================小米产品====================");
        XiaomiFactory xiaomiFactory = new XiaomiFactory();
        PhoneProduct xiaomiPhone = xiaomiFactory.phoneProduct();
        xiaomiPhone.start();
        xiaomiPhone.callup();
        xiaomiPhone.sendSMS();
        xiaomiPhone.shutdown();
        RouterProduct xiaomiRouter = xiaomiFactory.routerProduct();
        xiaomiRouter.start();
        xiaomiRouter.openWifi();
    }
}

抽象工厂模式：提供了一个创建一些列相关或者相互依赖对象的接口，无需指定他们的实现类。

适用场景：

  • 客户端（应用层）不依赖与产品类实例如何被创建、实现等细节
  • 强调一系列相关的产品对象（属于同一产品簇）一起使用创建对象需要大量的重复代码
  • 提供一个产品类的库，所有的产品以同样的接口出现，从而使得客户端不依赖具体的实现。

优点：

  • 具体产品在应用层的代码隔离，无需关心创建的细节
  • 将一个系列的产品统一到一起创建。

缺点：

  • 规定了所有可能被创建的产品集合，产品簇中扩展新的产品困难（如加一个生产笔记本电脑，需要改动大量代码）
  • 增加了系统的抽象性和理解难度

三种工厂模式比较

  • 简单工厂模式（静态工厂模式）：
    • 虽然某种程度上不符合设计原则，但实际使用最多。
    • 优点：解耦，能应对需求变更
    • 缺点：扩展时需要修改工厂类，不符合开闭原则
  • 工厂方法模式
    • 不修改已有类的前提下，通过增加新的工厂类实现扩展
    • 优点：解耦，能应对需求变更，扩展不需要修改旧的类
    • 缺点：每次扩展的编码量提升，需要对应多写一个工厂类
  • 抽象工厂模式
    • 不可以增加产品，可以增加产品簇
    • 优点：解耦，在现有系列之间切换灵活
    • 缺点：扩展产品时很麻烦，修改从头到尾

建造者模式

  • 介绍
    • 使用多个简单的对象一步一步构建成一个复杂的对象，将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。
    • 允许用户只通过指定复杂对象的类型和内容就可以构建它们，不需要知道内部的具体构建细节
  • 场景举例
    • KFC创建套餐：套餐是一个复杂对象，它一般包含主食如汉堡、烤翅等和饮料 如果汁、 可乐等组成部分，不同的套餐有不同的组合，而KFC的服务员可以根据顾客的要求，一步一步装配这些组成部分，构造一份完整的套餐
    • 电脑有低配、高配，组装需要CPU、内存、电源、硬盘、主板等
  • 核心组成
    • Builder：抽象建造者，定义多个通用方法和构建方法
    • ConcreteBuilder：具体建造者，可以有多个
    • Director：指挥者，控制整个组合过程，将需求交给建造者，由建造者去创建对象
    • Product：产品角色
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
// 案例
/**
 * @Auther: csp1999
 * @Date: 2020/11/08/10:35
 * @Description: 产品类 Computer
 */
public class Computer {
    private String cpu;
    private String memory;
    private String mainboard;
    private String disk;
    private String power;
    //get set toString
}

//创建抽象建造者接口Builder
public interface Builder {
    /**
     * 接口方法
     */
    void buildCpu();
    void buildMainBoard();
    void buildDisk();
    void buildPower();
    void buildMemory();
    Computer createComputer();
}

//创建具体建造者类A (高配电脑建造者)HighComputerBuilder
//具体建造者类B(低配电脑建造者) LowComputerBuilder
public class HighComputerBuilder implements Builder {
    private Computer computer = new Computer();
    @Override
    public void buildCpu() {
        computer.setCpu("高配 CPU");
    }
    @Override
    public void buildMainBoard() {
        computer.setMainboard("高配 主板");
    }
    @Override
    public void buildDisk() {
        computer.setDisk("高配 磁盘");
    }
    @Override
    public void buildPower() {
        computer.setPower("高配 电源");
    }
    @Override
    public void buildMemory() {
        computer.setMemory("高配 内存");
    }
    @Override
    public Computer createComputer() {
        return computer;// 返回computer对象
    }
}
// 低配一样


//最后是指挥者类Director控制产品生产过程
public class Director {
    public Computer create(Builder builder){
        builder.buildCpu();
        builder.buildDisk();
        builder.buildMainBoard();
        builder.buildMemory();
        builder.buildPower();
        return builder.createComputer();
    }
}

//测试：
public void testBuilder(){
    Director director = new Director();// 声明指挥者
    // 指挥者指挥构建低配电脑
    Computer low_computer = director.create(new LowComputerBuilder());
    // 指挥者指挥构建高配电脑
    Computer high_computer = director.create(new HighComputerBuilder());
    System.out.println(low_computer);
    System.out.println(high_computer);
}
  • 建造者模式优点
    • 客户端不必知道产品内部组成的细节，将产品本身与产品的创建过程解耦
    • 每一个具体建造者都相对独立，而与其他的具体建造者无关，更加精细地控制产品地创建过程
    • 增加新的具体建造者无需修改原有库类的代码，符合开闭原则
    • 建造者模式结合链式编程来使用，代码上更加美观
  • 建造者模式缺点
    • 建造者模式所创建的产品一般具有较多的共同点，如果产品差异大则不建议使用
  • JDK中的使用
    • tcp传输协议protobuf生成的api、java中的StringBuilder(不完全一样，思想一样)
  • 建造者模式与抽象工厂模式的比较
    • 建造者模式返回一个组装好的完整产品 ， 抽象工厂模式返回一系列相关的产品，这些产品位于不同的产品等级结构，构成了一个产品族
    • 建造者模式是把对象的创建分散开来，每个抽象方法负责其中的一部分。抽象工厂是每个方法负责一个产品族。
    • 建造者模式所有函数加到一起才能生成一个对象。抽象工厂一个函数生成一个对象。

原型模式

  • 介绍
    • 是一种对象创建型模式，使用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象，主要用于创建重复的对象，同时又能保证性能
    • 工作原理是将一个原型对象传给那个要发动创建的对象，这个要发动创建的对象通过请求原型对象拷贝自己来实现创建过程
    • 应该是最简单的设计模式了，实现一个接口，重写一个方法即完成了原型模式
  • 核心组成
    • Prototype: 声明克隆方法的接口，是所有具体原型类的公共父类，Cloneable接口
    • ConcretePrototype : 具体原型类
    • Client: 让一个原型对象克隆自身从而创建一个新的对象
  • 应用场景
    • 创建新对象成本较大，新的对象可以通过原型模式对已有对象进行复制来获得
    • 如果系统要保存对象的状态，做备份使用
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
// 案例
public class Person implements Cloneable{
    private String name;
    private int age;
    public Person(){
        System.out.println("空参构造函数调用...");
    }
    
    // get set toString
    
    /**
     * 重写克隆方法，返回Person对象类型
     *
     * 注意：权限改成public，方便调用
     * @return
     * @throws CloneNotSupportedException
     */
    @Override
    public Person clone() throws CloneNotSupportedException {
        return (Person) super.clone();
    }
}

// 测试
@Test
public void testPropotype() throws CloneNotSupportedException {
    Person person1 = new Person();
    person1.setAge(22);
    person1.setName("csp");
    System.out.println(person1);
    Person person2 = person1.clone();
    person2.setName("hzw");
    System.out.println(person2);
}

注意：

  • 当克隆执行完成后，实际上相当于新 new一个Person 对象并为其分配了新的存储地址及引用，因此person1 和 person2 的地址引用不同；
  • 对于复杂对象，当进行克隆时，实际上是从被拷贝对象中拷贝了其引用地址，并非new一个出来
  • 因此，二者是共享一个相同地址引用的复杂对象，这种情况被称为浅拷贝。

浅拷贝

  • 如果原型对象的成员变量是基本数据类型，将复制一份给克隆对象。
  • 如果原型对象的成员变量是引用类型，将引用对象的地址复制一份给克隆对象
  • 也就是说 原型对象和克隆对象的成员变量指向相同的内存地址
  • 通过覆盖Object类的clone()方法可以实现浅克隆

深拷贝

  • 无论原型对象的成员变量是基本数据类型还是引用类型，都将复制一份给克隆对象，如果需要实现深克隆，可以通过序列化(Serializable)等方式来实现

原型模式优点

  • 当创建新的对象实例较为复杂时，使用原型模式可以简化对象的创建过程，可以提高新实例的创建效率
  • 可辅助实现撤销操作，使用深克隆的方式保存对象的状态，使用原型模式将对象复制一份并将其状态保存起来，以便在需要的时候使用恢复到历史状态

原型模式缺点

  • 需要为每一个类配备一个克隆方法，对已有的类进行改造时，需要修改源代码，违背了“开闭原则”
  • 在实现深克隆时需要编写较为复杂的代码，且当对象之间存在多重的嵌套引用时，需要对每一层对象对应的类都必须支持深拷贝

深拷贝的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//首先Person对象实现Serializable接口，然后自定义深拷贝方法 deepClone()：

/**
* 深拷贝
 * 注意：要实现序列化接口
 * @return
 */
public Person deepClone() {
    try {
        // 输出 (序列化)
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(baos);
        oos.writeObject(this);
        // 输入 (反序列化)
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
        ObjectInputStream ois = new ObjectInputStream(bais);
        Person person = (Person) ois.readObject();
        return person;
    } catch (Exception e) {
        e.printStackTrace();
        return null;
    }
}

适配器模式

  • 介绍
    • 见名知意，是作为两个不兼容的接⼝之间的桥梁，属于结构型模式
    • 适配器模式使得原本由于接⼝不兼容⽽不能⼀起⼯作的那些类可以⼀起⼯作
    • 常见的几种适配器
      • 类的适配器模式：想将一个类转换成满足另一个新接口的类时，剋使用类的适配器模式，创建一个新类， 继承原有的类，实现新的接⼝即可
      • 对象的适配器模式：想将一个对象转换成满足另一个新接口的对象时，可以创建一个适配器类，持有原类的一个实例， 在适配器类的⽅法中，调⽤实例的⽅法就⾏
      • 接口的适配器模式：不想实现一个接口中所有的方法时，可以创建一个Adapter，实现所有方法，在写别的类的时候，继承Adapter方法即可。
  • 应用场景
    • 电脑需要读取内存卡的数据，读卡器就是适配器
    • 系统需要使⽤现有的类，⽽这些类的接⼝不符合系统的需要
    • JDBC就是我们⽤的最多的适配器模式
      • JDBC给出⼀个客户端通⽤的抽象接⼝，每⼀个具体数据库⼚商
      • 如 SQL Server、Oracle、MySQL等，就会开发JDBC驱动
      • 就是⼀个介于JDBC接⼝和数据库引擎接⼝之间的适配器软件

桥接模式

  • 介绍
    • 适配器模式类似，包括以后经常会遇到意思接近⼀样的设计模式，因为⼤神往往就是多个模式混⽤，且根据不 同的场景进⾏搭配，桥接设计模式也是结构型模式
    • 将抽象部分与实现部分分离，使它们都可以独⽴的变化
    • 通俗来说，是通过组合来桥接其它的⾏为/维度
  • 应用场景
    • 系统需要在构件的抽象化⻆⾊和具体化⻆⾊之间增加更多的灵活性
    • 不想使⽤继承导致系统类的个数急剧增加的系统
    • 有时候⼀个类，可能会拥有多个变化维度，⽐如啤酒， 有不同的容量和品牌，可以使⽤继承组合的⽅式进⾏开 发，假如维度很多，就容易出现类的膨胀，使⽤桥接模式就可以解决这个问题，且解耦

代理模式

  • 代理模式：为一个对象提供一个替身，以控制对这个对象的访问。即通过代理对象访问目标对象.这样做的好处 是:可以在目标对象实现的基础上,增强额外的功能操作,即扩展目标对象的功能。
  • 被代理的对象可以是远程对象、创建开销大的对象或需要安全控制的对象
  • 代理模式有不同的形式, 主要有三种 静态代理、理 动态代理 (JDK 代理、接口代理)和 Cglib 理 代理 (可以在内存动态的创建对象，而不需要实现接口， 他是属于动态代理的范畴) 。

静态代理

静态代理在使用时,需要定义接口或者父类,被代理对象(即目标对象)与代理对象一起实现相同的接口或者是继承相同父类。 

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
// 定义手机的规则，不能你说是手机就是手机。
/**
 * 接口的出现是为了定义规则用的
 */
public interface Phone {
    //打电话
    public void call();
    //玩游戏
    public void play();
    //拍照片
    public void photo();
}


// 定义商店的规则，不可能谁都可以卖iPhone，要进行授权
public interface Store {
    public Phone selliPhone();
}


//具体手机实现类，iPhone
public class iPhone implements Phone{
    //描述属性
    private String name;
    private String color;
    //构造方法
    public iPhone(){}
    public iPhone(String name,String color){
        this.name=name;
        this.color=color;
    }
    //打电话
    public void call(){
        System.out.println("真的iPhone 打电话很流畅");
    }
    //玩游戏
    public void play(){
        System.out.println("真的iPhone 玩游戏不卡顿");
    }
    //拍照片
    public void photo(){
        System.out.println("真的iPhone 拍照片很清晰");
    }
}

//具体iPhone专卖店
public class AppleStore implements Store{
    private iPhone productPhone(){//可以理解为这个方法是工厂店自己的
        //创建一台手机
        iPhone iPhone = new iPhone("iPhone7","black");
        //将生出来的手机返回出去
        return iPhone;
    }
    //卖手机
    //  做事情之前是否需要条件---参数
    //  做事情之后是否需要结果---返回值
    public Phone selliPhone(){
        //找自己的工厂生产一台手机
        iPhone iPhone = this.productPhone();
        //将工厂方法生产的手机返回出去
        return iPhone;
    }
}


//提供具体代理类帮我们干活，苹果专卖店可能太多人了，我找人帮我卖
//代理类不仅能去专卖店拿手机卖而且还能造假货。
public class ProxyStore implements Store{
    //聚合关系  代理店--工厂店
    private AppleStore store = new AppleStore();
    //如果想要造假    自己在山沟沟里造一个山寨工厂
    private lPhone productlPhone(){
        lPhone lPhone = new lPhone();
        return lPhone;
    }
    //代购  代理------卖手机
    public Phone selliPhone(){//可以在真正用户不知情的情况下修改执行的过程
        //1.有一台手机????  真机  找工厂店
        Phone iPhone = this.store.selliPhone();
        //2.有一个山寨工厂     山寨手机
        Phone lPhone = this.productlPhone();
        //3.手机卖出去
//        return iPhone;
        return iPhone;
    }
}

//客户端测试
public class TestMain {
    public static void main(String[] args) {
        //1.有一个代理店
        Store store = new ProxyStore();
        //2.代理店卖手机
        Phone iPhone = store.selliPhone();
        //3.用户使用
        iPhone.call();
        iPhone.play();
        iPhone.photo();
    }
}

静态代理优缺点：

优点： 被代理对象只要和代理类实现了同一接口即可，代理类无须知道被代理对象具体是什么类、怎么做的， 而客户端只需知道代理即可，实现了类之间的解耦合。

缺点：

  • 代理类和被代理类实现了相同的接口，代理类通过被代理类实现了相同的方法，这样就出现了大量的代码重复。 如果接口增加一个方法，除了所有实现类需要实现这个方法外，所有代理类也需要实现此方法，增加了代码维护的复杂度。
  • 每个代理类只能为一个接口服务，如果程序开发中要使用代理的接口很多的话，必然会产生许多的代理类，造成类膨胀。

动态代理

介绍：

  • 代理对象,不需要实现接口，但是目标对象要实现接口，否则不能用动态代理
  • 代理对象的生成，是由java内部的反射机制来实现的。
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
// 定义手机规则
public interface Phone {
    //描述一下手机的功能
     void call();
     void play();
     void photo();
}

// 手机具体实现类
public class iPhone implements Phone {
    @Override
    public void call() {
        System.out.println("iPhone12打电话真好用");
    }
    @Override
    public void play() {
        System.out.println("iPhone12玩王者真好用");
    }
    @Override
    public void photo() {
        System.out.println("iPhone12照相真好用");
    }
}
// 华为手机
public class Mate40 implements Phone {
    @Override
    public void call() {
        System.out.println("华为Mate40打电话带劲");
    }
    @Override
    public void play() {
        System.out.println("华为Mate40打吃鸡带劲");
    }
    @Override
    public void photo() {
        System.out.println("华为Mate40照相带劲");
    }
}


// 华为生产线
public interface HuaweiStore {
    Mate40 salePhone();
}
// 苹果生产线
public interface AppleStore{
    // 苹果专卖店只负责卖，找代工厂负责生产
    iPhone salePhone();
}


public class ProxyStore {
    //描述一个方法 通过Proxy这个类获取一个代理对象(代工商店)
    //  1.方法是一件事情  做事情之前是否需要条件---参数   代理谁? AppleStore
    //  2.方法是一件事情  做事情之后是否需要结果---返回值  代理对象--利用泛型
    public static <T> T getStore(Class clazz) {
        //分析创建proxy代理对象需要的条件
        //0.类加载器---目的是把需要代理的AppleStore这个类加载进来
        ClassLoader classLoader = clazz.getClassLoader();
        //1.代理谁 AppleStore(传递的参数clazz)  下面第二个问号需要数组
        Class[] classes = new Class[]{clazz};
        //2.代理他之后 具体该做什么事情---原来真正店做的事情 卖手机
        InvocationHandler handler = new InvocationHandler() {
            public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
                //内部类中方法的三个参数含义
                //1.proxy代理对象  2.method代理的那个方法  3.args代理方法传递的参数
                // 想让这个工厂根据传递的参数，代工不同的产品
                // 1、获取需要被代工的类
                Class clazz = method.getDeclaringClass();
                // 2、判断clazz从而执行不同的代工
                if (clazz == AppleStore.class) {
                    return new iPhone();
                } else if (clazz == HuaweiStore.class) {
                    return new Mate40();
                } else {
                    return null;
                }
            }
        };
        //1.通过Proxy类帮我们创建一个代理对象
        T proxy = (T) Proxy.newProxyInstance(classLoader, classes, handler);
        //2.将这个proxy代理对象返回
        return proxy;
    }
}


//测试
public class TestMain {
    //动态代理
    //  可以理解为是一个代工厂
    //  富士康公司(代工 什么品牌都代工  好多生产线  做苹果 做华硕 做索尼)
    //  可以理解为  可以出了苹果之外还能卖别的品牌手机
    //  由于这个对象什么都可以做    我们不自己创建---找人帮忙(创建一个这个代理商店)
    //  Proxy类  Java给我们提供的 Math String ArrayList
    //  Proxy类可以帮我们创建一个代理对象(这个对象就是动态代理的对象 什么都能做)
    public static void main(String[] args) {
        //1.需要有一个店----可以找代理店(代理店不是new 是通过自己写的类方法创建出来)
        AppleStore store = ProxyStore.getStore(AppleStore.class);
//        HuaweiStore store = ProxyStore.getStore(HuaweiStore.class);
        //2.商店做事情----卖手机
        Phone phone = store.salePhone();
//        Phone phone = store.saleiPhone();
        //3.拿去使用
        phone.call();
        phone.play();
        phone.photo();
    }
}
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一个辣鸡小破站