技术专栏 第696页

国庆加中秋过去了，大家准备好学习了么？

redis 在项目中用的话，主要就是用作缓存了

既然用作缓存，那就肯定会有 缓存穿透/缓存击穿/缓存雪崩 的问题

这篇文章就来说说，遇到这种情况时，该如何去处理

缓存穿透

首先咱们搞明白什么是缓存穿透？这三个词这么像，得把概念搞清楚不是

其实只是从字面意思上来看的话，大概也能知道一点儿，缓存穿透嘛，就是直接穿过了缓存，将请求打到了数据库上面去

一般情况下，去查询数据的话，缓存里面应该都是有的，但是防不住黑客呀，如果黑客请求查询的是数据库里面根本不存在的数据，数据库里面都没有的数据，缓存里面肯定也不会有了，对吧，那么此时请求就会打到咱们的数据库里面去，这就是缓存穿透

你想啊，黑客想要攻击的话，怎么可能只请求一次呢，肯定是大量的请求过来，因为是拿数据库里面不存在的 id 来请求的，那么这些请求毫无疑问直接打到了数据库上面去，那咱们的数据库可能就会因为这些大量的请求直接宕掉

如何解决呢？

咱们回到产生这个问题的场景中，为什么大量的请求会打到数据库上面来？因为缓存里面没有对应的 key 对吧，所以才会越过缓存直接到数据库

那么问题就好解决了嘛，缓存里面没有对应的 key ？OK ，如果这个 key 数据库里面也没有，那我就在 redis 里面，存上这个 key ，值是 null ，这样如果有查询这个 key 的请求，我直接返回 null 就完事儿了，也就不用打到数据库上面去了

注意一下，要记得设置它的过期时间，一般三到五分钟就够了

但是对方是个黑客呀，可能就用一个 key 去请求么？他可能会在短时间内用大量的 key 来发送请求，那如果一个 key 就在 redis 中存储一个 null 值的话，那么多 key 是不是就会存储那么多个 null 值嘞？

这样的话， redis 里面是不是都是值为 null 的了？

所以有没有更好的解决办法呢？

那必须得有！布隆过滤器，你值得尝试

什么是布隆过滤器呢？就是它能告诉你，某个值一定不存在或者可能存在( emmmm ，也不知道我有没有说清楚

所以可以将数据库的内容缓存一份到布隆过滤器，这样的话，当大量的请求过来的时候， redis 里面没有，没关系，再去布隆过滤器过滤一下，这样请求不用打到数据库上面去，就能确定这个 key 数据库中有没有

这样不就降低了数据库的压力么，可真是个天才~

缓存击穿

缓存击穿说的是，在高并发情况下，如果好多个请求都在查询一个 key ，好巧不巧的是，这个 key 因为某些原因失效了（比如设置的过期时间到了，缓存服务器宕机了），这样就会导致那么多的请求都直接打到数据库上面去了

那如果这些请求的数量足够大的话，可能直接把数据库就干掉了

知道了造成结果的原因，那么寻找解决方案也就好办了

不是因为好多个请求打到了数据库嘛，但是它们请求的都只是一个 key ，所以这里可以使用排斥锁来实现，第一个请求达到请求 key 发现缓存里面没有，允许它去数据库查询，同时加锁，这样第二个请求，第三个请求…都会被锁阻塞到当前，不会再打到数据库，这样就减少了数据库的并发压力

缓存雪崩

缓存雪崩，雪崩雪崩嘛，就比较严重，击穿说的是一个 key 失效的情况，雪崩指的是大规模的缓存失效情况的发生，这是有可能发生的，比如说我的缓存服务器宕机了，那是不是直接就大规模的缓存失效了;或者说，我当时为了图省事，好多个 key 设置的过期时间都是一样的，然后刚好在缓存都失效的时候，好多请求不同的 key 过来了

解决方案的话，其实就不适合使用加锁的方式去解决了，因为这是好多请求不同的 key ，它不是一个嘛

而且嘞，咱们是因为好多个 key 设置的过期时间都是一样的，所以解决方案就是，咱们不设置同样的时间让缓存失效了，咱们给一个随机时间，让缓存随机失效，这样的话，大规模的缓存失效情况就减少很多了

那还要一种情况呢，就是如果我的缓存服务器直接宕机了，这怎么办？也好弄，来个集群就解决了，这里只是一个解决方案，它的落地实现不是本文重点哈~

再谈 布隆过滤器

OK ，你如果看到这里的话，其实这篇文章的内容就说完了

但是我感觉布隆过滤器那块，我没有说清楚，所以在这里拿出来详细说一说（我知道你一定又在默默夸阿粉是个暖男了，乖，知道就好了，不要真说出来，我会害羞的

布隆过滤器是一种数据结构，它是一种概率型的数据结构，就是它能告诉你“某样东西一定不存在或者可能存在”

你可能会说，这话刚刚不是说过了嘛，本来就挺拗口的，你咋还说

还不是因为这句话比较重要，我觉得把这句话理解透彻了，那么对布隆过滤器理解的应该也就到位了

来，为了形象生动一些，咱们举个例子~ 布隆过滤器是一个 bit 向量或者说 bit 数组，大概长这样：

现在，我们需要把 “AliPay” 这个字段给存储进去 大概的存储过程就是:将要映射的值，使用多个不同的哈希函数生成多个哈希值，然后每个生成的哈希值指向的 bit 置为 1

以给的为例，我们现在将 “AliPay” 这个值，通过三个不同的哈希函数进行映射，那么大概就是这样了：

同样，现在我要存储另外一个值 “WechatPay” ，那么可能映射之后就是下面这样：

细心的你可能就会发现， 4 号位置的值，刚开始不是给 “AliPay” 了么，后来 “WechatPay” 也在那里，这样的话，值不就给覆盖掉了嘛

嗯，没错，是被覆盖掉了

接下来，我们查询 “Ali” 那么查询之后，布隆过滤器可能会给你 “0，1，2” 的值， 结果呢 “2” 的位置是 0 ，说明没有任何值映射到这个位置上来，所以我们就可以判定数据库里面没有 “Ali” 这个值

那我查询 “AliPay” 的话，毫无疑问，肯定会返回给我 “1，4，6” ，那我们能说数据库里面一定有 “AliPay” 么？不能，因为 “1，4，6” 的值有可能被其他的值给覆盖到了，所以我们只能说，数据库里可能存在 “AliPay”

这就是布隆过滤器说的”某个值一定不存在或者可能存在”

乖，你懂了吗?

文章来源于公众号：Java极客技术 作者：鸭血粉丝

以上就是W3Cschool编程狮关于关于 缓存穿透/缓存击穿/缓存雪崩 看这篇文章就够了的相关介绍了，希望对大家有所帮助。

前面我们学习了很多关于栈的知识，比如《动图演示：手撸堆栈的两种实现方法！》和《JDK 竟然是这样实现栈的？》，那么接下来我们再来刷一些关于栈的经典面试题以巩固学过的知识。

我们今天的面试题是这样的…

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.min(); –> 返回 -3.

minStack.pop();

minStack.top(); –> 返回 0.

minStack.min(); –> 返回 -2.

LeetCode 地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

思考

首先来说这道题目本身很好理解，它的实现难点在于以下两个方面：

• 当我们进行 pop（移除栈顶元素）操作时如果删除的是当前最小值，那么我们如何寻找下一个最小值？
• 要保证调用 min、push 及 pop 的时间复杂度都是 O(1)。

也就是说，在我们执行了 pop 时如果移除的栈中最小的值，那么如何寻找栈中的下一个最小元素？并且要保证操作的时间复杂度为 O(1)。这个时间复杂度制约了我们在移除了最小值之后不能通过遍历查找下一个最小值，所以这就成为了这道题的难点。

比如当我们移除以下栈顶元素值：

因为最小值就是 1，因此在移除之后最小值也被移除了，如下图所示：

那么接下来，让我们一起思考 3 分钟，想一想应该如何处理这个问题~

解题思路

其实我们可以在每次入栈时，判断当前元素是否小于最小值，如果小于则将原最小值和最新的最小值相继入栈，这样在调用 pop 时即使移除的是最小值，我们也能通过获取下一个元素得到一个新的最小值，执行流程如下所示。

操作步骤1

入栈第一个元素，因为是第一个元素，因此最小值就是此元素的值。

操作步骤2

入栈第二个元素，如下图所示：

因为入栈的元素 3 比 8 小，所以先将栈中的原最小值 8 存入栈中，再将 3 入栈。

操作步骤3

入栈第三个元素，如下图所示：

因为入栈元素 5 大于 3，因此栈中的最小值不变，直接将元素 5 入栈。

操作步骤4

继续入栈，如下图所示：

入栈元素 1 小于于 3，因此先将原最小值 3 入栈，再将 1 入栈，栈中的最小值更改为 1。

操作步骤5

执行出栈操作，如下图所示：

元素 1 出栈，判断当前元素就是栈的最小值，因此将栈顶元素 3 设置为最小值，并移除元素 3，如下图所示：

操作步骤6

继续出栈，如下图所示：

因为元素 5 不是当前最小值，因此直接出栈。

操作步骤7

继续出栈，如下图所示：

因为出栈元素 3 为最小值，因此继续将最小值设置为栈顶元素 8，并将栈顶元素出栈，如下图所示：

这样就剩下最后一个元素了，最后一个元素出栈之后就成空栈了，整个流程就执行完了。

实现代码1

接下来我们将上面的思路用代码实现一下，我们用数组实现的栈来实现相关的功能，代码如下：

class MinStack {
    private int[] data; // 栈数据
    private int maxSize; // 最大长度
    private int top; // 栈顶指针（下标）
    private int min; // 最小值


    // 构造函数
    public MinStack() {
        // 设置默认值
        maxSize = 10000;
        data = new int[maxSize];
        top = -1;
        min = Integer.MAX_VALUE;
    }


    // 入栈（添加元素）
    public void push(int x) {
        if (min >= x) {
            // 遇到了更小的值，记录原最小值（入栈）
            data[++top] = min;
            min = x;
        }
        // 当前值入栈
        data[++top] = x;
    }


    // 出栈（移除栈顶元素）
    public void pop() {
        if (min == data[top]) {
            min = data[--top]; // 拿到原最小值，并（将原最小值）出栈
        }
        --top; // 出栈
    }


    // 查找栈顶元素
    public int top() {
        return data[top];
    }

 
    // 查询最小值
    public int min() {
        return min;
    }
}

上述代码在 LeetCode 的执行结果如下：

可以看出性能还是很高的，超越了 99.92% 的用户，内存消耗也不大。它的核心代码在 push 方法内，先将原最小值和最新最小值相继入栈，在 pop 出栈时判断出栈元素是否为最小值，如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈，这样就得到了下一个新的最小值了。

实现代码2

如果我们不想使用数组的自定义栈来实现，还可以使用 Java 中自带的栈 Stack 来实现此功能，代码如下：

class MinStack {
    private Stack stack = new Stack();
    private int min = Integer.MAX_VALUE;


    public MinStack() { }


    // 入栈（添加元素）
    public void push(int x) {
        if (x  这种实现代码的方式（使用 Java API），在刷题或者实际面试中如果没有特殊说明是可以直接用的。


### 总结


本文我们通过两种方式：自定义数组栈和 Java API 中的 `Stack` 来实现了栈中最小值的功能，保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1)。两种实现方式的代码虽然略不相同，但实现思路都是一样的，都是**在元素入栈时判断当前元素是否小于最小元素，如果小于最小元素则先将原最小值入栈，再将当前最小元素入栈，这样当调用 pop 方法时，即使移除的是最小值，只需要将下一个元素取出即为新的最小值了**，这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。


>文章来源于公众号：Java中文社群 作者：磊哥


以上就是`W3Cschool编程狮`关于**算法图解：如何找出栈中的最小值？**的相关介绍了，希望对大家有所帮助。

  DDPM
^[3]是一个双向马尔可夫模型，其分为扩散过程和采样过程。

通过
JWT 为每个用户生成一个唯一且有期限的
Token，用户每次请求都会重新生成过期时间，在规定的时间内，用户未进行操作
Token 就会过期，当用户再次请求时则会再次执行登录流程，而
Token 的过期时间应根据实际的业务场景规定。

DeepSeek问答结果：

创新点：

下面是两条提示词的对比：

准备开始学习java了。

今天学习的第五天，每天都会发文章，我要卷起来。

请小伙伴们监督我，奥利给

分布式事务的核心目标是确保 
跨服务/数据库的操作要么全部成功，要么全部回滚。

翻译 | 郑子铭