ARTS

ARTS_WEEK7

ARTS_WEEK7

Posted by CDz on January 19, 2020
  • 这周算法方面主要研究链表知识
  • 加上看的几个专栏的总结知识
    • 多线程视频课
      • 观察者模式实现
      • 线程池参数分析
        • 淘汰策略
    • 数据结构与算法课
      • 数组的删除元素
      • LRU算法实现
        • 顺便把LinkedHashMap复习一遍
    • kafka实战
      • 配置选择
  • 奇思妙想：Redis的key失效实现

    1. although

    1.1. 给定一个链表，判断链表中是否有环

    技巧：想象一个标准操场上，速度快的总会追上速度慢的那个（相遇）

package com.myserious.code.cdz;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-17
 * Time: 下午4:10
 * 给定一个链表，判断链表中是否有环。
 * <p>
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [1,2], pos = 0
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * 输入：head = [1], pos = -1
 * 输出：false
 * 解释：链表中没有环。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week7EHasCycle141 {
    /**
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     *
     * 开辟新的空间，放置之前的内容，通过 hashset的键位判断，找出是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {

        Set<ListNode> set = new HashSet<>();
        while (head!=null){
            if (set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

    /**
     * 快慢变量。
     *
     * 极其巧妙的思路
     *
     * 想象一下两个人在操场上跑步，
     * 快的那个肯定会最终最上慢的那个。
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head) {

        if (head==null||head.next==null) return false;

        ListNode slow = head;
        ListNode fast =head.next;

        while (fast!=slow){
            if (fast==null||fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;

    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

1.2. 请判断一个链表是否为回文链表

技巧：快慢变量，加慢变量反转，最后对比前后两部分

package com.myserious.code.cdz;

/**
 * 请判断一个链表是否为回文链表。
 * 
 * 示例 1:
 * 
 * 输入: 1->2 输出: false 示例 2:
 * 
 * 输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */
public class Week7EIsPalindrome234 {

    /** 
     * 思路：
     * 快慢遍历
     * 慢遍历：一次遍历一个
     * 快遍历：一次遍历两个
     * 
     * 这样的好处是，当快遍历到头时，慢遍历刚好到一半
     * 
     * 慢遍历的同时，反转链表（也就是说前半部分会被反转）
     * 
     * ~这里问题，链表的遍历，并不能随机访问，在这里卡住了。~
     * ~然后再从中间开始，对比前后两部分，只要全部相等就是回文链表~
     * 
     * 找到方法，前半部分前移时，其实记录的有下标，
     * 只需要在长度为奇偶数的时候做一下判断即可
     * 
    */
    public boolean isPalindrome(ListNode head) {
        ListNode pre = null;
        ListNode fast  = head;
        ListNode curr = head;
        while (fast!=null&&fast.next!=null) {
            //这一步还可以放在循环外部 更节省运算——>同时 while语句就需要 多加一个判断 fast.next != null
            //奇数个时，当前指正向前一位
            // if (fast.next==null) {
            //     curr = curr.next;
            //     fast = fast.next;
            //     continue;
            // }
            ListNode tempNext = curr.next;
            fast = fast.next.next;
            curr.next = pre;
            pre = curr;
            curr = tempNext;
        }
        if (fast!=null) {
            curr = curr.next;
        }
        while (pre!=null&&curr!=null) {
            if (pre.val!=curr.val) {
                return false;
            }
            pre = pre.next;
            curr = curr.next;
        }
        return true;
    }
   
    public static void main(String[] args) {
        Week7EIsPalindrome234 main = new Week7EIsPalindrome234();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        System.out.println(main.isPalindrome(head));
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

1.3. 将两个有序链表合并为一个新的有序链表并返回

技巧：1.哨兵头节点 2.递归方式（没有理解真正精髓）

package com.myserious.code.cdz;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-17
 * Time: 上午11:10
 * <p>
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 * 示例：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week7EMergeTwoLists21 {

    /**
     *
     * 时间复杂度O(m+n)
     * 空间复杂度O(1)
     * 迭代方法，关键在于 使用 链表头前置标记量-1记录，因为最后返回只需要返回 preHead.next
     *
     * 接着就是前置游标，
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //使用标记量,哨兵节点
        ListNode preHead = new ListNode(-1);
        //前置指针
        ListNode prev = preHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ?  l2 : l1;
        return preHead.next;
    }

    /**
     * 时间复杂度O(m+n)
     * 空间复杂度O(m+n)
     * 递归方式
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        //任意一个为空，就返回另外一个
        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }

        if (l1.val<l2.val){
            l1.next = mergeTwoLists1(l1.next,l2);//其实是调用拿出最小的一个，赋值给next
            return l1;
        }else {
            l2.next = mergeTwoLists1(l1,l2.next);
            return l2;
        }
    }
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

1.4. 反转一个单链表

技巧：定义好临时节点位置，前置节点，当前节点

package com.myserious.code.cdz;

/**
 * Week7EReverseList206 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * <p>
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week7EReverseList206 {
    /**
     * 重写
     * @param head
     * @return
     */
    public ListNode reverseList3(ListNode head) {

        ListNode pre = null;
        ListNode curr= head;

        while (curr!=null){

            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }

        return pre;
    }
    /**
     * 图解
     * https://pic.leetcode-cn.com/7d8712af4fbb870537607b1dd95d66c248eb178db4319919c32d9304ee85b602-%E8%BF%AD%E4%BB%A3.gif
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;// 前一个节点
        ListNode curr = head;// 当前节点
        while (curr != null) {
            ListNode tempnext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tempnext;
        }
        return prev;
    }

    /**
     * 使用递归的方式
     * https://pic.leetcode-cn.com/dacd1bf55dec5c8b38d0904f26e472e2024fc8bee4ea46e3aa676f340ba1eb9d-%E9%80%92%E5%BD%92.gif
     * <p>
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode curr = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return curr;
    }
    public static void main(String[] args) {
        Week7EReverseList206 main = new Week7EReverseList206();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        main.reverseList2(head);
    }
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

1.5. 链表的中间结点

技术：快慢变量

package com.myserious.code.cdz;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-19
 * Time: 上午10:35
 * <p>
 * 876. 链表的中间结点
 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
 * <p>
 * 如果有两个中间结点，则返回第二个中间结点。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1,2,3,4,5]
 * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
 * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
 * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
 * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
 * 示例 2：
 * <p>
 * 输入：[1,2,3,4,5,6]
 * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
 * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
 *  
 * <p>
 * 提示：
 * <p>
 * 给定链表的结点数介于 1 和 100 之间。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week7EMiddleNode876 {
    /**
     * 快慢变量
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){
            fast= fast.next.next;
            slow = slow.next;
        }

        return slow;

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

1.6. 删除链表的倒数第N个节点(M)

技巧：使用快慢变量变种+前置节点避免链表只有一个元素问题

package com.myserious.code.cdz;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-17
 * Time: 下午5:27
 * <p>
 * 19. 删除链表的倒数第N个节点
 * <p>
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * <p>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 * <p>
 * 给定的 n 保证是有效的。
 * <p>
 * 进阶：
 * <p>
 * 你能尝试使用一趟扫描实现吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Week7MRemoveNthFromEnd19 {

    public ListNode removeNthFromEnd1(ListNode head, int n) {

        //快慢标记量的变种
        //先找到快变量的位置
        //使用前置节点，有效避免当链表只有一个时的问题
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode fast = preHead;
        ListNode slow = preHead;

        // int i = 0;
        // while (n!=i) {
        //     i++;
        //     fast = head.next;
        // }

        for (int i = 1; i <= n+1; i++) {
            fast = fast.next;
        }
        //快慢变量同时前进
        while (fast!=null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return preHead.next;
    }


    public static void main(String[] args) {
        Week7MRemoveNthFromEnd19 week7MRemoveNthFromEnd19 = new Week7MRemoveNthFromEnd19();
        Week7MRemoveNthFromEnd19.ListNode head = new Week7MRemoveNthFromEnd19.ListNode(1);
        head.next = new Week7MRemoveNthFromEnd19.ListNode(2);
        head.next.next = new Week7MRemoveNthFromEnd19.ListNode(3);
        head.next.next.next = new Week7MRemoveNthFromEnd19.ListNode(4);
        head.next.next.next.next = new Week7MRemoveNthFromEnd19.ListNode(5);

        week7MRemoveNthFromEnd19.removeNthFromEnd1(head, 2);


    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

1.7. 平衡树

1.7.1. 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树

思路：中位遍历树

package com.myserious.code.cdz;

/**
 * Week6ESortedArrayToBST108
 * 
 * 
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * 
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 * 
 * 示例:
 * 
 * 给定有序数组: [-10,-3,0,5,9],
 * 
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * 
 * 0 / \ -3 9 / / -10 5
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 技巧
 * 二分查找树
 * 中序遍历
 * 
 */
public class Week7ESortedArrayToBST108 {

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length);
    }

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start==end) {
            return null;
        }
        int mid = start+(end-start)/2;//开始位置 与 结束位置 除以二
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid);
        root.right = sortedArrayToBST(nums, mid+1, end);
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

1.8. 算法衍生

1.8.1. 数组模拟GC垃圾回收核心（改善数组删除慢）

package com.myserious.code.cdz.althoughexpand;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-16
 * Time: 上午11:15
 *
 * 垃圾回收核心思想：
 *
 * 使用数组的形式，
 * 将垃圾回收即为删除下标元素，
 *
 * 设计一个数组包装，能够批量删除连续的元素，
 *
 * **能够批量删除连续的元素**,
 * 删除对象，是随机的，如何将其变成连续的？
 *  根据业务，GC是随机加入，并不需要顺序而言
 *  所以，其实可以先找到对应的删除项
 *  然后将**删除项与数组逻辑第一位换位**,当然同时pos++
 *
 * 并有记录功能（逻辑删除）
 */
public class GCrootRetrieveCore {

    private Object[] GC;

    private int pos;

    private int end;

    public int len(){
        return end-pos;
    }

    public GCrootRetrieveCore(Object[] GC) {
        this.GC = GC;
        this.end = 0;
        this.pos = 0;
    }

    public void add(Object o){
        if (end>GC.length-1) {
            //超过长度
            freeGC();
            if (end>GC.length-1){
                //目前还没有需要删除的
                //扩展数组
                reset();
                return;
            }
        }
        GC[end++] = o;
    }

    public void del(Object o){
        for (int i = pos; i < end; i++) {
            if (GC[i].equals(o)) {
                //找到
                if (pos!=i) {
                    swap(pos++,i);
                }else {
                    //计算是相同位置 pos也要++
                    pos++;
                }
            }
        }
    }

    private void swap(int index1, int index2) {
        Object temp  = GC[index1];
        GC[index1] = GC[index2];
        GC[index2] = temp;
    }

    /**
     * 拓展数组
     * 长度拓展是原来的一半(n+n*50%)
     */
    private void reset() {
        //todo
        System.out.println("需要拓展数组啦");
    }

    /**
     * 删除，标记的垃圾
     */
    public void freeGC() {
        if (pos<5){
            //小于5个不GC
            return;
        }

        int count = 0;
        for (int i = pos; i < end; i++) {
            GC[count++] = GC[i];
            GC[i] = null;
        }
        this.pos = 0;
        this.end = count;

    }


    public static void main(String[] args) {
        GCrootRetrieveCore gc = new GCrootRetrieveCore(new Object[10]);

        System.out.println(gc.len());

        gc.add(1);
        gc.add(2);
        gc.add(3);
        gc.add(4);
        gc.add(5);
        gc.add(6);
        gc.add(7);
        gc.add(8);
        gc.add(9);
        gc.add(10);

        System.out.println(gc.len());


        gc.del(10);
        gc.del(9);
        gc.del(8);
        gc.del(7);
        gc.del(6);
        gc.del(5);

        System.out.println(gc.len());

        gc.freeGC();

        gc.add(11);
        gc.add(12);
        gc.add(13);
        System.out.println(gc.len());
    }
}

1.8.2. LRU淘汰算法

LRU算法：使用LinkedHashMap来实现，很方便。

  • 添加顺序最前（最后）
  • 最近访问放置最前（最后）
  • 达到容量删除最久（最前/最后）没有访问的元素

复习LinkedHashMap的数据结构：

  • 继承HashMap有HashMap的所有特性
  • 内部再讲每个元素使用链表相连
    • 遍历时使用链表拿出顺序链表元素
  • 从源码中学习编码技巧
    • 钩子拓展 ：HashMap实现put时，预留的有钩子去做一些操作
package com.myserious.code.cdz.althoughexpand;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-16
 * Time: 下午2:43
 * LUR淘汰算法
 */
public class LRUAlgorithm {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(4);
        lruCache.put("1", "1");
        lruCache.put("2", "2");
        lruCache.put("3", "3");
        lruCache.put("9", "3");
        lruCache.put("10", "3");
        lruCache.put("11", "3");

        String s = (String) lruCache.get("1");
        String s1 = (String) lruCache.get("3");
        lruCache.forEach((key, value) -> System.out.println(key + ":" + value));
    }
}


/**
 * 封装 linkedhashMap 得到LRU
 * 测试 LinkedHashMap
 * mybatis LRU实现
 * 第三个参数：accessOrder 是否开启排序（每次访问放入链表尾部）
 */
class LRUCache extends LinkedHashMap {
    private int maxElements;

    public LRUCache(int maxElements) {
        super(maxElements, .75F, true);
        this.maxElements = maxElements;
    }

    //钩子设计策略
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > maxElements;
    }
}

2. review

Redis KEY失效策略 轮询删除： Specifically this is what Redis does 10 times per second:

  1. Test 20 random keys from the set of keys with an associated expire.
  2. Delete all the keys found expired.

  3. If more than 25% of keys were expired, start again from step 1.

  4. 从所有Key中，随机拿出20个key
  5. 删除所有过期的key
  6. 如果过期key数，占比在25%，从新第一步 每秒会执行四次

懒删除： 访问时判断是否已过期，如果过期直接删除。

3. tip

3.1. 算法篇

3.1.1. Leetcode刷题技巧

  • 集中精力刷题（一段时间内只刷一类型的题目）
  • 刷题方法（看答案非常的关键，这也是我刷了这几次之后的想法）
    • 看题目想5分钟，大致的思路，如果想不出来就看答案
    • 看懂或者想通思路后，关掉答案，自己做一遍（限时30到60分钟）
      • 超过了就再去看答案
    • 过一段时间再来刷一遍，这次需要能快速的识别关键点，并且能快速写出代码。
      • 如果还是有困难，再看题解
  • 有集中的时间去刷题（每天）
  • 多看别人的题解，理解他人的思路，找出问题或者学习优点
  • 提交答案后去研究中间靠前的答案
    • 这些会相对靠谱，一般排名第一的答案并不是最好的答案

3.1.2. 主题训练：链表

总结：

  • 在链表中明白各种指针的指向是最关键的一步
    • 很多其实有头绪该怎么做但是真正到写代码时却被链表各个指针弄的焦头烂额
    • 解决办法
      • 临时变量
      • 画图
  • 技巧：
    • 头部哨兵可以解决很多边界问题
    • 快慢指针遍历方式，可以优化遍历性能
  • 边界考虑项
    • 如果链表为空
    • 链表只有一个
    • 链表只有两个
    • 处理头部与尾部节点是否正常

      3.1.3. 数据结构拓展

      LRU算法：使用LinkedHashMap来实现，很方便。

  • 添加顺序最前（最后）
  • 最近访问放置最前（最后）
  • 达到容量删除最久（最前/最后）没有访问的元素

复习LinkedHashMap的数据结构：

  • 继承HashMap有HashMap的所有特性
  • 内部再讲每个元素使用链表相连
    • 遍历时使用链表拿出顺序链表元素
  • 从源码中学习编码技巧
    • 钩子拓展 ：HashMap实现put时，预留的有钩子去做一些操作

      3.2. 多线程篇

      3.2.1. 线程异常捕获处理器 UncaughtExceptionHandler

  • 可以捕获子线程未知异常

    3.2.2. 线程安全定义

  • 不论遇到多少个线程执行，访问某个对象或方法的情况，在编写业务时，都不需要额外的进行处理（也就是像单线程编程一样）

    4. share

4.1. 算法篇

4.1.1. 数据结构

4.1.1.1. 数组的下标为什么是从零开始？

很神奇的问题。

  • 数组算是最基础的数据结构
  • 所有图灵完备的编程语言都有此结构
  • 并且通常是最底层的数据结构
  • 编程语言会在此基础上再分装一个更易用的结构

而数组，在计算机中，更底层其实是开辟的，相同类型的连续的内存空间。

数组的随机访问能做到O(1)的速度就是源于此。

数组内存占用图：

  • 相同类型（int 在Java中为4字节）
  • 连续的空间（1000-1039） 以此使用公式就能轻易的推算出个index的下标的内存地址：
a[I]_address = base_address+i*data_type_size;

纠正：数组并不是查询时间复杂度O(1)，这样描述不够准确，更准确的是随机查询的时间复杂度为O(1)。

衍生问题：

1.数组越界

在C中因为内存是可以被程序所访问的（没有学过C不清楚，但是大致可以这么理解）

所以当数组越界时，很有可能读到了其他内存地址的内容，导致程序错误，且难以察觉。

而Java中，在JVM层面讲数组所分配的内存地址，做了屏障（个人理解，没有看实际理论，暂时存疑），当数组越界时会报错异常。

2.增删问题

数组内存成块，方便了随机查询，但是带来的缺点增删的时间复杂度为O(n)，也就是说不适合增删操作。

删除：

但是在删除时，其实可以进行优化，一定空间的数组，当还没有存满时，需要删除连续位置的元素时，其实可以将其标记（逻辑删除），等到积累到一定程度时一起删除，这样就可以将几次O(n)操作转化为一次O(n)操作。这也是JVM垃圾回收的核心思想。

4.2. 设计模式篇

4.2.1. 观察者模式实现

package com.myserious.code.cdz.designpattern;


import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-16
 * Time: 上午10:29
 *
 * 观察者模式
 */
public class SubjectObserverModel {

    public static void main(String[] args){

        //被观察对象
        ConcreteSubject concreteSubject = new ConcreteSubject();
        concreteSubject.setStatus("吵架");


        //观察者
        ConcreteObserver observer1 = new ConcreteObserver("出瓜群众",concreteSubject.getStatus());
        ConcreteObserver observer2 = new ConcreteObserver("警察",concreteSubject.getStatus());


        //注册到被观察者对象上
        concreteSubject.attach(observer1);
        concreteSubject.attach(observer2);

        //当事件发生变化时,需要主动调用 notify所有的观察者
        //状态改变
        concreteSubject.setStatus("打架");
        System.out.println("--------------");
        concreteSubject.setStatus("打架");
        System.out.println("--------------");
        concreteSubject.setStatus("医院");

    }

}


/**
 * 目标对象
 */
abstract class Subject {

    //保存注册的 观察者对象
    List<Observer> observers = new LinkedList<>();

    //添加观察者
    public void attach(Observer observer){
        observers.add(observer);
    }

    public void detach(Observer observer){
        //ArrayList 方法remove方法，性能较差，先要for找出元素，然后再删除，修改底层数组
        //使用linkedList比较好
        observers.remove(observer);
    }

    abstract String getStatus();

    abstract void setStatus(String status);

    //通知需要通知的目标对象
    abstract void notifyObservers();
}


class ConcreteSubject extends Subject{

    private String status;

    @Override
    public String getStatus() {
        return status;
    }
    @Override
    public void setStatus(String status) {
        this.status = status;
        this.notifyObservers();
    }

    @Override
    void notifyObservers() {
        for (Observer observer : observers) {
            observer.update(this);
        }
    }
}

/**
 * 观察者 接口
 */
interface  Observer{
    void update(Subject subject);
}

/**
 * 观察者 实现
 */
class ConcreteObserver implements Observer{

    private String status;

    private String name;

    public ConcreteObserver(String name,String status) {
        this.status = status;
        this.name = name;
    }


    @Override
    public void update(Subject subject) {

        String status = subject.getStatus();
        if (this.status.equals(status)){
            //相同
            System.out.println(this.name+":相同状态("+this.status+")，不需要通知");
        }else {
            System.out.println(this.name+":原来是："+ this.status +",通知修改为："+status);
            this.status = status;
        }
    }
}

4.3. 多线程篇

4.3.1. 线程属性

  • 线程ID： 线程ID，是不可修改的，自增 源码： 
          /* For generating thread ID */
      private static long threadSeqNumber;
      private static synchronized long nextThreadID() {
          return ++threadSeqNumber;
      }

    说明id不是从0开始，而是从1开始。 通过，主线与子线程打印情况看， Java启动时，JVM会帮我们启动很多线程

    • 线程name
    • 是否是守护线程
      • 守护线程与普通线程：
        • 相同：守护线程与普通线程没有本质上的区别都是线程
        • 不同：守护线程不会影响JVM的退出
        • 用不应该自定义设置守护线程
    • 优先级

      4.3.2. 写出一个必然死锁的程序

package com.virgocx.scheduled;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-01-15
 * Time: 上午10:14
 *
 * 必然死锁程序
 *
 */
public class MultiThreadError implements Runnable{
    private int flag = 0;
    //锁对象一定不能是成员变量，
    //静态变量才会导致死锁，因为静态变量会类中唯一，也就是说new出来时，只有一个实例，所以两个线程的锁对象相同
    static Object o1 = new Object();
    static Object o2 = new Object();
    public static void main(String[] args) {
        MultiThreadError m1 = new MultiThreadError();
        MultiThreadError m2 = new MultiThreadError();
        m1.flag = 0;
        m1.flag = 1;
        new Thread(m1).start();
        new Thread(m2).start();
    }

    @Override
    public void run() {
        if (flag==0){
            System.out.println("0");
            synchronized (o1){
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (o2){
                    System.out.println("1");
                }
            }
        }else {
            System.out.println("1");
            synchronized (o2){
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (o1){
                    System.out.println("0");
                }
            }
        }


    }
}

4.3.3. 线程池ThreadPoolExecutor类

构造函数： //最终调用

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler)
  • corePoolSize：核心线程数量，会一直尽量维持在这个数量
  • maximumPoolSize：最大线程数量，线程数量的最大容量
  • keepAliveTime：空闲线程的存活时间
  • workQueue：缓存任务执行队列
  • threadFactory：线程池创建工厂
  • RejectedExecutionHandler handler：淘汰策略
    • CallerRunsPolicy，当拒绝时，将线程直接运行
    • AbortPolicy，抛出异常
    • DiscardPolicy，直接抛弃
    • DiscardOldestPolicy，抛弃执行实现最长的，并重新执行此任务

      4.4. 问题驱动

      4.4.1. Redis的定时失效Key是如何实现的？

      一般失效方式有三种：

  • 立即删除——事件回调，当到期时间后回调一个事件，然后自动调用删除方法
  • 懒删除——到期后不删除，当查询时，判断是否已过期，过期就删除且返回null
  • 轮询——一个定时任务，每过一段时间进行轮询删除已过期的key Redis使用的后两者结合。

4.5. kafka学习

4.5.1. 系统选择：Linux为主

原因：

  • 社区支持
  • IO模型
    • kafka底层是使用Java的NIO，在Linux在Java默认是用的epoll实现相比select更高效
  • 数据传输
    • Linux环境下JavaNIO使用零拷贝技术（zero copy）
    • Win环境下只有在Java8 后面版本才支持

4.5.2. 磁盘：

4.5.2.1. 使用机械硬盘还是SSD？

因为kafka更多的是顺序读写，很大程度上避免了机械硬盘的随机读写慢问题。所以在数据量不多的情况下，使用机械硬盘物美价廉

机械硬盘是否需要RAID?

综合考虑，数据量并不是特别大的情况下，并不需要，因为kafka本身有集群备份的功能。

4.5.2.2. 磁盘容量需要多大？

一般默认消息保存两周，根据自己的实际每天消息数量，进行换算。换算时留出10%的磁盘空间即可。

考虑点：

  • 每日消息量、消息大小
  • 保存时间
  • 备份数量
  • 是否开启压缩（消耗CPU）

4.5.3. 宽带：网络宽带单位与磁盘存储单位是什么关系？

存储单位一般使用的字节(Byte)为基本单位，数据传输大多使用的是“位”(bit)

1Byte = 8bit

所以换算下来，平时说的1Gbps的网络实际速度为：

1Gbps = 1024Mb(位)/8=128MB(字节)/s;

Over;

CATALOG
    FEATURED TAGS
    算法 Java 随想 个人笔记 zookeeper 中间件 Golang 测试 ARTS JVM 总结 通信协议
    FRIENDS