Nicksxs's Blog

前面写过一系列的 redis 源码分析的，但是实际上很多的问题还是需要结合实际的使用，然后其实就避不开缓存使用的三个著名问题，穿透，击穿和雪崩，这三个概念也是有着千丝万缕的关系，

缓存穿透

缓存穿透是指当数据库中本身就不存在这个数据的时候，使用一般的缓存策略时访问不到缓存后就访问数据库，但是因为数据库也没数据，所以如果不做任何策略优化的话，这类数据就每次都会访问一次数据库，对数据库压力也会比较大。

缓存击穿

缓存击穿跟穿透比较类似的，都是访问缓存不在，然后去访问数据库，与穿透不一样的是击穿是在数据库中存在数据，但是可能由于第一次访问，或者缓存过期了，需要访问到数据库，这对于访问量小的情况其实算是个正常情况，但是随着请求量变高就会引发一些性能隐患。

缓存雪崩

缓存雪崩就是击穿的大规模集群效应，当大量的缓存过期失效的时候，这些请求都是直接访问到数据库了，会对数据库造成很大的压力。

对于以上三种场景也有一些比较常见的解决方案，但也不能说是万无一失的，需要随着业务去寻找合适的方案

解决缓存穿透

对于数据库中就没这个数据的时候，一种是可以对这个 key 设置下空值，即以一个特定的表示是数据库不存在的，这种情况需要合理地调整过期时间，当这个 key 在数据库中有数据了的话，也需要有策略去更新这个值，并且如果这类 key 非常多，这个方法就会不太合适，就可以使用第二种方法，就是布隆过滤器，bloom filter，前置一个布隆过滤器，当这个 key 在数据库不存在的话，先用布隆过滤器挡一道，如果不在的话就直接返回了，当然布隆过滤器不是绝对的准确的

解决缓存击穿

当一个 key 的缓存过期了，如果大量请求过来访问这个 key，请求都会落在数据库里，这个时候就可以使用一些类似于互斥锁的方式去让一个线程去访问数据库，更新缓存，但是这里其实也有个问题，就是如果是热点 key 其实这种方式也比较危险，万一更新失败，或者更新操作的时候耗时比较久，就会有一大堆请求卡在那，这种情况可能需要有一些异步提前刷新缓存，可以结合具体场景选择方式

解决缓存雪崩

雪崩的情况是指大批量的 key 都一起过期了，击穿的放大版，大批量的请求都打到数据库上了，一方面有可能直接缓存不可用了，就需要用集群化高可用的缓存服务，然后对于实际使用中也可以使用本地缓存结合 redis 缓存，去提高可用性，再配合一些限流措施，然后就是缓存使用过程总的过期时间最好能加一些随机值，防止在同一时间过期而导致雪崩，结合互斥锁防止大量请求打到数据库。

题目介绍

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any path.

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和

简要分析

其实这个题目会被误解成比较简单，左子树最大的，或者右子树最大的，或者两边加一下，仔细想想都不对，其实有可能是产生于左子树中，或者右子树中，这两个都是指跟左子树根还有右子树根没关系的，这么说感觉不太容易理解，画个图

可以看到图里，其实最长路径和是左边这个子树组成的，跟根节点还有右子树完全没关系，然后再想一种情况，如果是整棵树就是图中的左子树，那么这个最长路径和就是左子树加右子树加根节点了，所以不是我一开始想得那么简单，在代码实现中也需要一些技巧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int ansNew = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
        maxSumNew(root);
        return ansNew;
    }
    
public int maxSumNew(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 这里是个简单的递归，就是去递归左右子树，但是这里其实有个概念，当这样处理时，其实相当于把子树的内部的最大路径和已经算出来了
    int left = maxSumNew(root.left);
    int right = maxSumNew(root.right);
    // 这里前面我有点没想明白，但是看到 ansNew 的比较，其实相当于，返回的是三种情况里的最大值，一个是左子树+根，一个是右子树+根，一个是单独根节点，
    // 这样这个递归的返回才会有意义，不然像原来的方法，它可能是跳着的，但是这种情况其实是借助于 ansNew 这个全局的最大值，因为原来我觉得要比较的是
    // left, right, left + root , right + root, root, left + right + root 这些的最大值，这里是分成了两个阶段，left 跟 right 的最大值已经在上面的
    // 调用过程中赋值给 ansNew 了    
    int currentSum = Math.max(Math.max(root.val + left , root.val + right), root.val);
    // 这边返回的是 currentSum，然后再用它跟 left + right + root 进行对比，然后再去更新 ans
    // PS: 有个小点也是这边的破局点，就是这个 ansNew
    int res = Math.max(left + right + root.val, currentSum);
    ans = Math.max(res, ans);
    return currentSum;
}

这里非常重要的就是 ansNew 是最后的一个结果，而对于 maxSumNew 这个函数的返回值其实是需要包含了一个连续结果，因为要返回继续去算路径和，所以返回的是 currentSum，最终结果是 ansNew

结果图

难得有个 100%，贴个图哈哈

今天真的是被气得不轻，情况是碰到一个有 70 多秒的直行红灯，然后直行就排了很长的队，但是左转车道没车，就有好几辆车占着左转车道，准备往直行车道插队加塞，一般这种加塞的，会挑个不太计较的，如果前面一辆不让的话就再等等，我因为赶着回家，就不想让，结果那辆车几次车头直接往里冲，当时怒气值基本已经蓄满了，我真的是分毫都不想让，如果路上都是让着这种人的，那么这种情况只会越来越严重，我理解的这种心态，就赌你怕麻烦，多一事不如少一事，结果就是每次都能顺利插队加塞，其实延伸到我们社会中的种种实质性的排队或者等同于排队的情况，都已经有这种惯有思维，一方面这种不符合规则，可能在严重程度上容易被很多人所忽视，基本上已经被很多人当成是“合理”行为，另一方面，对于这些“微小”的违规行为，本身管理层面也基本没有想要管的意思，就更多的成为了纵容这些行为的导火索，并且大多数人都是想着如果不让，发生点小剐小蹭的要浪费很多时间精力来处理，甚至会觉得会被别人觉得自己太小气等等，诸多内外成本结合起来，会真的去硬刚的可能少之又少了，这样也就让更多的人觉得这种行为是被默许的，再举个非常小的例子，以我们公司疫情期间的盒饭发放为例，有两个比较“有意思”的事情，第一个就是因为疫情，本来是让排队要间隔一米，但是可能除了我比较怕死会跟前面的人保持点距离基本没别人会不挨着前面的人，甚至我跟我前面的人保持点距离，后面的同学会推着我让我上去；第二个是关于拿饭，这么多人排着队拿饭，然后有部分同学，一个人拿好几份，帮组里其他人的都拿了，有些甚至一个人拿十份，假如这个盒饭发放是说明了可以按部门直接全领了那就没啥问题，但是当时的状况是个人排队领自己的那一份，如果一个同学直接帮着组里十几个人都拿了，后面排队的人是什么感受呢，甚至有些是看到队伍排长了，就找队伍里自己认识的比较靠前的人说你帮我也拿一份，其实作为我这个比较按规矩办事的“愣头青”来说，我是比较不能接受这两件小事里的行为的，再往下说可能就有点偏激了，先说到这~

题目介绍

写一个程序找出两个单向链表的交叉起始点，可能是我英语不好，图里画的其实还有一点是交叉以后所有节点都是相同的
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

1
2
3

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

分析题解

一开始没什么头绪，感觉只能最原始的遍历，后来看了一些文章，发现比较简单的方式就是先找两个链表的长度差，因为从相交点开始肯定是长度一致的，这是个很好的解题突破口，找到长度差以后就是先跳过长链表的较长部分，然后开始同步遍历比较 A，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

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 算 A 的长度
        int countA = 0;
        ListNode tailA = headA;
        while (tailA != null) {
            tailA = tailA.next;
            countA++;
        }
        // 算 B 的长度
        int countB = 0;
        ListNode tailB = headB;
        while (tailB != null) {
            tailB = tailB.next;
            countB++;
        }
        tailA = headA;
        tailB = headB;
        // 依据长度差，先让长的链表 tail 指针往后移
        if (countA > countB) {
            while (countA > countB) {
                tailA = tailA.next;
                countA--;
            }
        } else if (countA < countB) {
            while (countA < countB) {
                tailB = tailB.next;
                countB--;
            }
        }
        // 然后以相同速度遍历两个链表比较
        while (tailA != null) {
            if (tailA == tailB) {
                return tailA;
            } else {
                tailA = tailA.next;
                tailB = tailB.next;
            }
        }
        return null;
    }

总结

可能缺少这种思维，做的还是比较少，所以没法一下子反应过来，需要锻炼，我的第一反应是两重遍历，不过那样复杂度就高了，这里应该是只有 O(N) 的复杂度。

Java 中的这个话题也是比较常遇到的，关于这块原先也是比较忽略的，但是仔细想想又有点遗忘了就在这里记一下
简单看下代码
java.lang.Object#equals

1
2
3

public boolean equals(Object obj) {
        return (this == obj);
    }

对于所有对象的父类，equals 方法其实对比的就是对象的地址，也就是是否是同一个对象，试想如果像 Integer 或者 String 这种，我们没有重写 equals，那其实就等于是在用==，可能就没法达到我们的目的，所以像 String 这种常用的 jdk 类都是默认重写了
java.lang.String#equals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

然后呢就是为啥一些书或者 effective java 中写了 equals 跟 hashCode 要一起重写，这里涉及到当对象作为 HashMap 的 key 的时候
首先 HashMap 会使用 hashCode 去判断是否在同一个槽里，然后在通过 equals 去判断是否是同一个 key，是的话就替换，不是的话就链表接下去，如果不重写 hashCode 的话，默认的 object 的hashCode 是 native 方法，根据对象的地址生成的，这样其实对象的值相同的话，因为地址不同，HashMap 也会出现异常，所以需要重写，同时也需要重写 equals 方法，才能确认是同一个 key，而不是落在同一个槽的不同 key.