Algorithm

题目

题目描述

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。 239 sliding-window-maximum

题目解答

一般与滑动窗口有关的问题都可以使用双端队列来处理。

 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

import java.util.ArrayDeque;
import java.util.List;
import java.util.ArrayList;

public class MaxSlidingWindow {

    private ArrayDeque<Integer> window = new ArrayDeque<>();
    public int[] slidingWindowMax(int[] nums, int k) {
        if(nums.length == 0) {
            return new int[0];
        }

        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++) {
            if(i >= k && window.getFirst() <= i - k) {
                window.pollFirst();
            }

            while(!window.isEmpty() && nums[window.getLast()] < nums[i]) {
                window.pollLast();
            }

            window.add(i);

            if(i >= k - 1) {
                res.add(nums[window.getFirst()]);
            }
        }

        return res.stream().mapToInt(i->i).toArray();
    }
}

Review

Consistent_hashing一致性Hash算法。

一致性Hash算法是什么？

一致性Hash算法是一种特殊的Hash算法，当需要对Hash表进行重新映射调整大小时，平均情况下只需要处理(nums_keys/nums_slots)个key。一致性Hash算法的主要思想是将每个缓存与一个或者多个散列值关联起来，其中间隔边界是通过计算每个缓存标识符的散列来确定的。如果移除了缓存，其间隔将由相邻间隔的缓存接管，而其余的缓存保持不变。

一致性Hash是怎么实现的？

一致Hash是基于将每个对象映射到一个圆上的一个点，系统将个可用的存储映射到同一个圆上的许多伪随机点。

查找操作

当进行查找时，系统会找到该物体的键在圆圈上的位置，然后绕着圆圈顺时针走，直到掉进它遇到的第一个存储桶中。

删除操作

如果有存储变得不可用，它映射到的点将被删除，这样被删除存储的key会被映射到顺时针的下个节点，这样只有这个新的被映射的存储桶（一般这个桶会有多个虚拟的节点）需要重新分配，而其它的存储桶则不需要进行改变。

增加存储

增加存储桶时，就把先两桶之间的存储进行分隔，这样将新桶点与前一桶点之间元素映射到新桶，这些新映射的点在查询时不会被 老的桶点查到。

为什么要使用一致性Hash？

在运行缓存的机器集合时，一般情况下会对机器号进行Hash进行映射。但是在对机器进行修改（增加，删除）时，整个集群的存储都要进行重新Hash，这样会使整个缓存失效，大量流量进入DB层，造成雪崩。为了避免出现这种情况，需要使用一致性Hash。因为在修改时一致性Hash只会使一部分存储失效。还有一种处理方式，就是扩容冗余算法，再对新的N未取到值再对老的M进行Hash取值。

一致性Hash的注意点

一般在使用一致性Hash时会根据实际存储点来映射出多个虚拟节点，这样可以保证节点数据的均衡性。

一致性Hash的时间复杂度

经典Hash 一致性Hash
添加一个节点 O(K) O(K/N + log(N))
移除一个节点 O(K) O(K/N + log(N))
添加一个Key O(1) O(log(N))
删除一个Key O(1) O(log(N))

由于要使用二分查找法来找到下一下节点，所以时间复杂度为O(log(N))

更多示例说明

这里只列出了JAVA语言的示例说明，参见这里

Tip

Idea的条件断点调试很好用，尤其是在要调试的系统有多个后台子线程运行时，可以过滤掉这些后台运行线程而只专注关心业务线程了。BreakPoints

Share

luruke/browser-2020，2020年，浏览器都可以用来做什么。这是一个github仓库，这个仓库给了一个列表，展示了浏览器那些不为人知的特性，如付款申请，网络分享，离线浏览，运行VR，使蓝牙和系统剪切板等。