关于算法:敲黑板鹅厂程序员面试也考了这些算法知识

腾小云导读

开发者在程序设计时，擅于使用优良正当的算法相较于被动陷入逻辑之沼潭，是更被举荐的上上之策。算法的思维精华是值得每个开发者深入研究和细细品味。本文总结腾讯游戏、微信红包等腾讯王牌的后盾开发在设计过程中波及到的一些罕用算法，试图尽量以简洁的文字和图表来解释和阐明其中的思维原理，心愿能给大家带来一些思考和启发。

目录

1 调度算法

2 不放回随机抽样算法

3 排序算法

4 限流与过载爱护

5 序列化与编码

6 加密与校验

7 缓存淘汰策略

8 基数集与基数统计

9 其余罕用算法

10 总结

孙子云：“上兵伐谋，其次伐交，其次伐兵，其下攻城”，最上乘行军打仗的形式是使用谋略，下乘的形式才是与敌人进行惨烈的厮杀。同样的，在程序设计中，解决问题的方法有很多种，陷入到与逻辑进行贴身肉搏的境况实属下下之策，而能使用优良正当的算法才是“伐谋”的上上之策。

接下来，我将为各位介绍后盾开发设计罕用到的算法如缓存淘汰、排序、限流与过载爱护等，较为实用。文章整体较长但皆是我从业十年所积淀，此处先为各位整顿了全文要点的思维导图，各位能够珍藏文章和思维导图，后续继续消化内容。

01、调度算法

在服务器逻辑开发设计中，调度算法随处可见，资源的调度、申请的调配、负载平衡的策略等等都与调度算法相干。调度算法没有好坏之分，最适宜业务场景的才是最好的。

1.1 轮询

轮询是非常简单且罕用的一种调度算法，轮询行将申请顺次调配到各个服务节点，从第一个节点开始，顺次将申请调配到最初一个节点，而后从新开始下一轮循环。最终所有的申请会均摊调配在每个节点上，假如每个申请的耗费是一样的，那么轮询调度是最均衡的调度（负载平衡）算法。

1.2 加权轮询

有些时候服务节点的性能配置各不相同，解决能力不一样，针对这种的状况，能够依据节点解决能力的强弱配置不同的的权重值，采纳加权轮询的形式进行调度。

加权轮询能够形容为：

最终所有申请会依照各节点的权重值成比例的调配到服务节点上。假如有三个服务节点{a,b,c}，它们的权重配置别离为{2,3,4}，那么申请的调配秩序将是{c,b,c,a,b,c,a,b,c}，如下所示：

1.3 平滑权重轮询

加权轮询算法比拟容易造成某个服务节点短时间内被集中调用，导致刹时压力过大，权重高的节点会先被选中直至达到权重次数才会抉择下一个节点，申请间断的调配在同一个节点上的状况，例如假如三个服务节点{a,b,c}，权重配置别离是{5,1,1}，那么加权轮询调度申请的调配秩序将是{a,a,a,a,a,b,c}，很显著节点 a 有间断的多个申请被调配。

为了应答这种问题，平滑权重轮询实现了基于权重的平滑轮询算法。所谓平滑，就是在一段时间内，不仅服务节点被抉择次数的散布和它们的权重统一，而且调度算法还能比拟平均的抉择节点，不会在一段时间之内集中只抉择某一个权重较高的服务节点。

平滑权重轮询算法能够形容为：

同样假如三个服务节点{a,b,c}，权重别离是{5,1,1}，那么平滑权重轮询每一轮的调配过程如下表所示：

最终申请调配的秩序将是{a, a, b, a, c, a, a}，绝对于一般权重轮询算法会更平滑一些。

1.4 随机

随机即每次将申请随机地调配到服务节点上，随机的长处是齐全无状态的调度，调度节点不须要记录过往申请分配情况的数据。实践上申请量足够大的状况下，随机算法会趋近于齐全均衡的负载平衡调度算法。

1.5 加权随机

相似于加权轮询，加权随机反对依据服务节点解决能力的大小配置不同的的权重值，当有申请须要调度时，每次依据节点的权重值做一次加权随机调配，服务节点权重越大，随机到的概率就越大。最终所有申请调配到各服务节点的数量与节点配置的权重值成正比关系。

1.6 最小负载

理论利用中，各个申请很有可能是异构的，不同的申请对服务器的耗费各不相同，无论是应用轮询还是随机的形式，都可能无奈精确的做到齐全的负载平衡。最小负载算法是依据各服务节点以后的实在负载能力进行申请调配的，以后负载最小的节点会被优先选择。

最小负载算法能够形容为：

负载状况能够统计节点正在解决的申请量，服务器的 CPU 及内存使用率，过往申请的响应提早状况等数据，综合这些数据以正当的计算公式进行负载打分。

1.7 两次随机抉择策略

最小负载算法能够在申请异构状况下做到更好的均衡性。然而个别状况下服务节点的负载数据都是定时同步到调度节点，存在肯定的滞后性，而应用滞后的负载数据进行调度会导致产生“群居”行为，在这种行为中，申请将批量地发送到以后某个低负载的节点，而当下一次同步更新负载数据时，该节点又有可能处于较高地位，而后不会被调配任何申请。再下一次又变成低负载节点被调配了更多的申请，始终处于这种很忙和很闲的循环状态，不利于服务器的稳固。

为应答这种状况，两次随机抉择策略算法做了一些改良，该算法能够形容为：

两次随机抉择策略联合了随机和最小负载这两种算法的长处，应用负载信息来抉择节点的同时，防止了可能的“群居”行为。

1.8 一致性哈希

为了保序回归和充分利用缓存，咱们通常心愿雷同申请 key 的申请总是会被调配到同一个服务节点上，以放弃申请的一致性，既有了一致性哈希的调度形式。

1.8.1 划段

最简略的一致性哈希计划就是划段，即当时布局好资源段，依据申请的 key 值映射找到所属段，比方通过配置的形式，配置 id 为 [1-10000] 的申请映射到服务节点 1，配置 id 为 [10001-20000] 的申请映射到节点 2 等等，但这种形式存在很大的利用局限性，对于平衡性和稳定性也都不太现实，理论业务利用中根本不会采纳。

1.8.2 割环法

割环法的实现有很多种，原理都相似。割环法将 N 台服务节点地址哈希成 N 组整型值，该组整型即为该服务节点的所有虚构节点，将所有虚构节点打散在一个环上。

申请调配过程中，对于给定的对象 key 也哈希映射成整型值，在环上搜寻大于该值的第一个虚构节点，虚构节点对应的理论节点即为该对象须要映射到的服务节点。

如下图所示，对象 K1 映射到了节点 2，对象 K2 映射到节点 3。

![]()

割环法实现复杂度略高，工夫复杂度为 O(log(vn)),（其中，n 是服务节点个数，v 是每个节点领有的虚构节点数），它具备很好的枯燥性，而平衡性和稳定性次要取决于虚构节点的个数和虚构节点生成规定，例如 ketama hash 割环法采纳的是通过服务节点 ip 和端口组成的字符串的 MD5 值，来生成 160 组虚构节点。

1.8.3 二次取模

取模哈希映射是一种简略的一致性哈希形式，然而简略的一次性取模哈希枯燥性很差，对于故障容灾十分不好，一旦某台服务节点不可用，会导致大部分的申请被重新分配到新的节点，造成缓存的大面积迁徙，因而有了二次取模的一致性哈希形式。

二次取模算法即调度节点保护两张服务节点表：涣散表（所有节点表）和紧实表（可用节点表）。申请调配过程中，先对涣散表取模运算，若后果节点可用，则间接选取；若后果节点已不可用，再对紧实表做第二次取模运算，失去最终节点。如下图示：

二次取模算法实现简略，工夫复杂度为 O(1)，具备较好的枯燥性，能很好地解决缩容和节点故障的状况。平衡性和稳定性也比拟好，次要取决于对象 key 的散布是否足够散列（若不够散列，也能够加一层散列函数将 key 打散）。

1.8.4 最高随机权重

最高随机权重算法是以申请 key 和节点标识为参数进行一轮散列运算（如 MurmurHash 算法），得出所有节点的权重值进行比照，最终取最大权重值对应的节点为指标映射节点。能够形容为如下公式：

散列运算也能够认为是一种放弃一致性伪随机的形式，相似于后面讲到的一般随机的调度形式，通过随机比拟每个对象的随机值进行抉择。

这种形式须要 O(n) 的工夫复杂度，但换来的是十分好的枯燥性和平衡性，在节点数量变动时，只有当对象的最大权重值落在变动的节点上时才受影响，也就是说只会影响变动的节点上的对象的从新映射、因而无论扩容、缩容和节点故障都能以最小的代价转移对象，在节点数较少而对于枯燥性要求十分高的场景能够采纳这种形式。

1.8.5 Jump consistent hash

Jump consistent hash 通过一种非常简单的跳跃算法对给定的对象 key 算出该对象被映射的服务节点，算法如下：

int JumpConsistentHash(unsigned long long key, int num_buckets) {
    long long  b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;}

这个算法乍一看难以了解，它其实是上面这个算法的一个变种，只是将随机函数通过线性同余的形式革新而来的。

int ch(int key, int num_buckets) {random.seed(key) ;
    int b = -1; // bucket number before the previous jump
    int j = 0; // bucket number before the current jump
    while(j < num_buckets){
        b = j;
        double r = random.next(); // 0<r<1.0
        j = floor((b+1) / r);
    }
    return b;}

它也是一种伪随机的形式，通过随机保障了平衡性，而这里随机函数用到的种子是各个申请的 key 值，因而保障了一致性。它与最高随机权重的差异是这里的随机不须要对所有节点都进行一次随机，而是通过随机值跳跃了局部节点的比拟。

Jump consistent hash 实现简略，零内存耗费，工夫复杂度为 O(log(n))。具备很高的平衡性，在枯燥性方面，扩容和缩容体现较好，但对于两头节点故障，现实状况下须要将故障节点与最初一个节点调换，须要将故障节点和最初的节点共两个节点的对象进行转移。

1.8.6 小结

一致性哈希形式还有很多品种，通常联合不同的散列函实现。也有些或为了更简略的应用，或为了更好的枯燥性，或为了更好的平衡性等而对以上这些形式进行的革新等，如二次 Jump consistent hash 等形式。另外也有联合最小负载形式等的变种，如无限负载一致性哈希会依据以后负载状况对所有节点限度一个最大负载，在一致性哈希中对 hash 进行映射时跳过已达到最大负载限度的节点，理论利用过程中可依据业务状况自行做更好地调整和联合。

02、不放回随机抽样算法

2.1 Knuth 洗牌抽样

不放回随机抽样能够当成是一次洗牌算法的过程，利用洗牌算法来对序列进行随机排列，而后选取前 m 个序列作为抽样后果。

Knuth 洗牌算法是在 Fisher-Yates 洗牌算法中改良而来的，通过地位替换的形式代替了删除操作，将每个被删除的数字替换为最初一个未删除的数字（或最前一个未删除的数字）。

Knuth 洗牌算法能够形容为：

使用 Knuth 洗牌算法进行的随机抽样的形式称为 Knuth 洗牌随机抽样算法，因为随机抽样只须要抽取 m 个序列，因而洗牌流程只需洗到前 m 个数据即可。

2.2 占位洗牌随机抽样

Knuth 洗牌算法是一种 in-place 的洗牌，即在原有的数组间接洗牌，只管保留了原数组的所有元素，但它还是毁坏了元素之间的前后程序，有些时候咱们心愿原数组仅是可读的（如全局配置表），不会因为一次抽样受到毁坏，以满足能够对同一原始数组屡次抽样的需要，如若应用 Knuth 抽样算法，必须对原数组先做一次拷贝操作，但这显然不是最好的做法，更好的方法在 Knuth 洗牌算法的根底上，不对原数组进行替换操作，而是通过一个额定的 map 来记录元素间的替换关系，咱们称为占位洗牌算法。

占位洗牌算法过程演示如下：

最终，洗牌的后果为 3，5，2，4，1。

使用占位洗牌算法实现的随机抽样的形式称为占位洗牌随机抽样，同样的，咱们仍然能够只抽取到前 m 个数据即可。这种算法对原数组不做任何批改，代价是减少不大于

的长期空间。

2.3 抉择抽样技术抽样

洗牌算法是对一个曾经预初始化好的数据列表进行洗牌，须要在内存中全量缓存数据列表，如果数据总量 n 很大，并且单条记录的数据也很大，那么在内存中缓存所有数据记录的做法会显得十分的蠢笨。而抉择抉择抽样技术算法，它不须要事后全量缓存数据列表，从而能够反对流式解决。

抉择抽样技术算法能够形容为：

抉择抽样技术算法过程演示如下：

最终，抽样的后果为 2，5。

能够证实，抉择抉择抽样技术算法对于每个数被选取的概率都是

。

抉择抽样技术算法尽管不须要将数据流全量缓存到内存中，但他依然须要事后精确的晓得数据量的总大小即 n 值。它的长处是能放弃输入程序与输出程序不变，且单个元素是否被抽中能够提前晓得。

2.4 蓄水池抽样

很多时候咱们依然不晓得数据总量 n，上述的抉择抽样技术算法就须要扫描数据两次，第一次先统计 n 值，第二次再进行抽样，这在流解决场景中依然有很大的局限性。

Alan G. Waterman 给出了一种叫蓄水池抽样（Reservoir Sampling）的算法，能够在无需提前晓得数据总量 n 的状况下依然反对流解决场景。

蓄水池抽样算法能够形容为：

最终，抽样的后果为 1，5。

能够证实，每个数据被选中且留在蓄水池中的概率为

。

2.5 随机分值排序抽样

洗牌算法也能够认为就是将数据按随机的形式做一个排序，从 n 个元素汇合中随机抽取 m 个元素的问题就相当于是随机排序之后取前 m 排名的元素，基于这个原理，咱们能够设计一种通过随机分值排序的形式来解决随机抽样问题。

随机分值排序算法能够形容为：

只管随机分值排序抽样算法相比于蓄水池抽样算法并没有什么益处，反而须要减少额定的排序耗费，但接下来的带权重随机抽样将利用到它的算法思维。

2.6 奢侈的带权重抽样

很多需要场景数据元素都须要带有权重，每个元素被抽取的概率是由元素自身的权重决定的，诸如全服生产抽奖类流动，须要以玩家在肯定时间段内的总生产额度为权重进行抽奖，生产越高，最初中奖的机会就越大，这就波及到了带权重的抽样算法。

奢侈的带权重随机算法也称为轮盘赌抉择法，将数据搁置在一个假想的轮盘上，元素个体的权重越高，在轮盘上占据的空间就越多，因而就更有可能被选中。

假如下面轮盘一到四等奖和侥幸奖的权重值别离为 5,10,15,30,40，所有元素权重之和为 100，咱们能够从[1, 100] 中随机失去一个值，假如为 45，而后从第一个元素开始，一直累加它们的权重，直到有一个元素的累加权重蕴含 45，则选取该元素。如下所示：

因为权重 45 处于四等奖的累加权重值当中，因而最初抽样后果为四等奖。

若要不放回的选取 m 个元素，则须要先选取一个，并将该元素从汇合中踢除，再重复按同样的办法抽取其余元素。

这种抽样算法的复杂度是

并且将元素从汇合中删除毁坏了原数据的可读属性，更重要的是这个算法须要屡次遍历数据，不适宜在流解决的场景中利用。

2.7 带权重的 A-Res 算法蓄水池抽样

奢侈的带权重抽样算法须要内存足够包容所有数据，毁坏了原数据的可读属性，工夫复杂度低等毛病，而经典的蓄水池算法高效的实现了流解决场景的大数据不放回随机抽样，但对于带权重的状况，就不能实用了。

A-Res（Algorithm A With a Reservoir）是蓄水池抽样算法的带权重版本，算法主体思维与经典蓄水池算法一样都是保护含有 m 个元素的后果集，对每个新元素尝试去替换后果集中的元素。同时它奇妙的利用了随机分值排序算法抽样的思维，在对数据做随机分值的时候联合数据的权重大小生成排名分数，以满足分值与权重之间的正相关性，而这个 A-Res 算法生成随机分值的公式就是：

其中

为第 i 个数据的权重值，

是从（0,1]之间的一个随机值。

A-Res 算法能够形容为：

该算法的工夫复杂度为

且能够完满的使用在流式解决场景中。

2.8 带权重的 A-ExpJ 算法蓄水池抽样

A-Res 须要对每个元素产生一个随机数，而生成高质量的随机数有可能会有较大的性能开销，《Weighted random sampling with a reservoir》论文中给出了一种更为优化的指数跳跃的算法 A-ExpJ 抽样（Algorithm A with exponential jumps），它能将随机数的生成量从

少到

，原理相似于通过一次额定的随机来跳过一段元素的特征值

的计算。

A-ExpJ 算法蓄水池抽样能够形容为：

对于前 m 个数，计算特征值

其中

为第 i 个数据的权重值，

是从（0,1]之间的一个随机值，间接放入蓄水池中；

对于从 m+1,m+2,…,n 的第 i 个数，执行以下步骤；

计算阈值

，其中 r 为（0,1]之间的一个随机值，

为蓄水池中的最小特征值；

跳过局部元素并累加这些元素权重值

，直到第 i 个元素满足

；

计算以后元素特征值

，其中

为(

,1]之间的一个随机值，

为蓄水池中的最小特征值，

为以后元素权重值；

应用以后元素替换蓄水池中最小特征值的元素；

更新阈值

。

有点不好了解，show you the code:

function aexpj_weight_sampling(data_array, weight_array, n, m)
    local result, rank = {}, {}
    for i=1, m do
        local rand_score = math.random() ^ (1 / weight_array[i])
        local idx = binary_search(rank, rand_score)
        table.insert(rank, idx, {score = rand_score, data = data_array[i]})
    end

    local weight_sum, xw = 0, math.log(math.random()) / math.log(rank[m].score)
    for i=m+1, n do
        weight_sum = weight_sum + weight_array[i]
        if weight_sum >= xw then
            local tw = rank[m].score ^ weight_array[i]
            local rand_score = (math.random()*(1-tw) + tw) ^ (1 / weight_array[i])
            local idx = binary_search(rank, rand_score)
            table.insert(rank, idx, {score = rand_score, data = data_array[i]})
            table.remove(rank)
            weight_sum = 0
            xw = math.log(math.random()) / math.log(rank[m].score)
        end
    end

    for i=1, m do
        result[i] = rank[i].data
    end

    return resultend

03、排序算法

3.1 根底排序

根底排序是建设在对元素排序码进行比拟的根底上进行的排序算法。

3.1.1 冒泡排序

冒泡排序是一种简略直观的排序算法。它每轮对每一对相邻元素进行比拟，如果相邻元素程序不合乎规定，则替换他们的程序，每轮将有一个最小 / 大的元素浮上来。当所有轮完结之后，就是一个有序的序列。

过程演示如下：

3.1.2 插入排序

插入排序通过构建有序序列，初始将第一个元素看做是一个有序序列，前面所有元素看作未排序序列，从头到尾顺次扫描未排序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。

过程演示如下：

3.1.3 抉择排序

抉择排序首先在未排序序列中找到最小 / 大元素，寄存到已排序序列的起始地位。再从残余未排序元素中持续寻找最小 / 大元素，而后放到已排序序列的开端。直到所有元素处理完毕。

过程演示如下：

插入排序是每轮会解决好第一个未排序序列的地位，而抉择排序是每轮固定好一个已排序序列的地位。冒泡排序也是每轮固定好一个已排序序列地位，它与抉择排序之间的不同是抉择排序间接选一个最小 / 大的元素进去，而冒泡排序通过顺次相邻替换的形式抉择出最小 / 大元素。

3.1.4 疾速排序

疾速排序应用分治法策略来把一串序列分为两个子串序列。疾速排序是一种分而治之的思维在排序算法上的典型利用。实质上来看，疾速排序应该算是在冒泡排序根底上的递归分治法。

疾速排序从数列中挑出一个元素，称为 ” 基准 ”，所有元素比基准值小的摆放在基准后面，比基准值大的摆在基准的前面。一轮之后该基准就处于数列的两头地位。并递归地把小于基准值元素的子数列和大于基准值元素的子数列进行排序。

过程演示如下：

3.1.5 归并排序

归并排序是建设在归并操作上的一种无效的排序算法，也是采纳分治法的一个十分典型的利用。归并排序首先将序列二分成最小单元，而后通过归并的形式将两两曾经有序的序列合并成一个有序序列，直到最初合并为一个最终有序序列。

过程演示如下：

3.1.6 堆排序

堆排序（Heapsort）是利用堆这种数据结构所设计的一种排序算法。堆是一个近似齐全二叉树的构造，并同时满足堆的性质：子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序首先创立一个堆，每轮将堆顶元素弹出，而后进行堆调整，放弃堆的个性。所有被弹出的元素序列即是最终排序序列。

过程演示如下：

3.1.7 希尔排序

希尔排序，也称递加增量排序算法，是插入排序的一种更高效的改良版本，但希尔排序是非稳固排序算法。

插入排序在对简直曾经排好序的数据操作时，效率高，即能够达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据挪动一位。

希尔排序通过将比拟的全副元素分为几个区域来晋升插入排序的性能。这样能够让一个元素能够一次性地朝最终地位后退一大步。而后算法再取越来越小的步长进行排序，算法的最初一步就是一般的插入排序，然而到了这步，需排序的数据简直是已排好的了（此时插入排序较快）。

过程演示如下：

3.2 调配排序

根底排序是建设在对元素排序码进行比拟的根底上，而调配排序是采纳“调配”与“收集”的方法。

3.2.1 计数排序

计数排序的外围在于将输出的数据值转化为键存储在额定开拓的数组空间中。作为一种线性工夫复杂度的排序，计数排序要求输出的数据必须是有确定范畴的整数。

计数排序的特色：当输出的元素是 n 个 0 到 k 之间的整数时，它的运行工夫是

。计数排序不是比拟排序，排序的速度快于任何比拟排序算法。

因为用来计数的数组的长度取决于待排序数组中数据的范畴（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范畴很大的数组，须要大量工夫和空间。

过程演示如下：

3.2.2 桶排序

桶排序是计数排序的升级版，它利用了函数的映射关系，桶排序高效与否的要害就在于这个映射函数的确定。比方咱们能够将排序数据进行除 10 运算，运算后果中具备雷同的商值放入雷同的桶中，即每十个数会放入雷同的桶中。

过程演示如下：

为了使桶排序更加高效，咱们须要做到这两点：

计数排序实质上是一种非凡的桶排序，当桶的个数取最大值 (max-min+1) 的时候，桶排序就变成了计数排序。

3.2.3 基数排序

基数排序的原理是将整数按位数切割成不同的数字，而后对每个位数别离比拟。基数排序首先按最低有效位数字进行排序，将雷同值放入同一个桶中，并按最低位值程序叠放，而后再按次低无效位排序，反复这个过程直到所有位都进行了排序，最终即是一个有序序列。

过程演示如下：

基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分，基数排序能够看做是多轮桶排序，每个数位上都进行一轮桶排序。

3.3 多路归并排序

多路归并排序算法是将多个曾经有序的列表进行归并排序，合成为一组有序的列表的排序过程。

k 路归并排序能够形容为：

每次在比拟池中取最小 / 大的元素时，须要进行一次 k 个数据的比拟操作，当 k 值较大时，会重大影响多路归并的效率，为提高效率，能够应用“败者树”来实现这样的比拟过程。

败者树是齐全二叉树，败者树绝对的是胜者树，胜者树每个非终端结点（除叶子结点之外的其它结点）中的值都示意的是左右孩子相比拟后的胜者。

如下图所示是一棵胜者树：

而败者树双亲结点示意的是左右孩子比拟之后的失败者，但在上一层的比拟过程中，依然是拿前一次的胜者去比拟。

如下图所示是一颗败者树：

叶子节点的值是：{7,4,8,2,3,5,6,1}，7 与 4 比拟，7 是败者，4 是胜者，因而他们的双亲节点是 7，同样 8 与 2 比拟，8 是败者，示意在他们双亲节点上，而 7 与 8 的双亲节点须要用他们的胜者去比拟，即用 4 与 2 比拟，4 是败者，因而 7 与 8 的双亲节点记录的是 4，依此类推。

假如 k=8，败者树归并排序的过程演示如下所示：

首先构建起败者数，最初的胜者是 1，第二次将 1 弹出，取 1 所在的第 8 列的第二个数 15 放入 1 所在的叶子节点地位，并进行败者树调整，此时只需调整原 1 所在分支的先人节点，最初胜者为 2，后续过程依此类推。最初每轮的最终胜者序列即是最初的归并有序序列。

胜者树和败者树的实质是利用空间换工夫的做法，通过辅助节点记录两两节点的比拟后果来达到新插入节点后的比拟和调整性能。

3.4 跳跃表排序

跳跃表（Skip Lists）是一种有序的数据结构，它通过在每个节点中随机的建设下层辅助查找节点，从而达到快速访问节点的目标（与败者树的多路归并排序有殊途同归之妙）。

跳跃列表按层建造，底层是一个一般的有序链表，蕴含所有元素。每个更高层都充当上面列表的“快速通道”，第 i 层中的元素按某个固定的概率 p（通常为 1 / 2 或 1 /4）随机呈现在第 i+ 1 层中。每个元素均匀呈现在 1 /(1-p)个列表中，而最高层的元素在

个列表中呈现。

如下是四层跳跃表构造的示意：

在查找指标元素时，从顶层列表、头元素起步，沿着每层链表搜寻，直至找到一个大于或等于指标的元素，或者达到以后层列表开端。如果该元素等于指标元素，则表明该元素已被找到；如果该元素大于指标元素或已达到链表开端，则退回到以后层的上一个元素，而后转入下一层进行搜寻。顺次类推，最终找到该元素或在最底层底仍未找到（不存在）。

当 p 值越大，快速通道就越稠密，占用空间越小，但查找速度越慢，反之，则占用空间大查找速度快，通过抉择不同 p 值，就能够在查找代价和存储代价之间获取均衡。

因为跳跃表应用的是链表，加上减少了近似于以二分形式的辅助节点，因而查问，插入和删除的性能都很现实。在大部分状况下，跳跃表的效率能够和均衡树相媲美，它是一种随机化的均衡计划，在实现上比均衡树要更为简略，因此失去了宽泛的利用，如 redis 的 zset，leveldb，我司的 apollo 排行榜等都应用了跳跃表排序计划。

3.5 百分比近似排序

在流解决场景中，针对大容量的排序榜单，全量存储和排序须要耗费的空间及工夫都很高，不太事实。理论利用中，对于长尾数据的排序，个别也只须要显示百分比近似排名，通过就义肯定的精确度来换取高性能和高实时性。

3.5.1 HdrHistogram 算法

HdrHistogram 应用的是直方图统计算法，直方图算法相似于桶排序，原理就是创立一个直方图，以肯定的区间距离记录每个区间上的数据总量，预测排名时只需统计以后值所在区间及之前区间的所有数量之和与总数据量之间的比率。

区间宰割形式能够采纳线性宰割和指数宰割形式：

HdrHistogram 为了兼顾内存和估算的准确度，同时采纳了线性宰割和指数宰割的形式，相当于两层的直方图算法，第一层应用指数宰割形式，能够粗略的估算数据的排名范畴地位，第二层应用线性宰割形式，更加准确的估算出数据的排名地位。线性区间划分越小后果越准确，但须要的内存越多，能够依据业务精确度需要管制线性区间的大小。

直方图算法须要事后晓得数据的最大值，超过最大值的数据将存不进来。HdrHistogram 提供了一个主动扩容的性能，以解决数据超过预估值的问题，然而这个主动扩容形式存在一个很高的拷贝老本。

3.5.2 CKMS 算法

HdrHistogram 是一种动态分桶的算法，当数据序列是均匀分布的状况下，有比拟好的预测成果，然而理论利用中数据有可能并不平均，很有可能集中在某几个区间上，CKMS 采纳的是动静分桶的形式，在数据处理过程中一直调整桶的区间距离和数量。

CKMS 同时引入一个可配置的错误率的概念，在抉择是否开拓新桶时，依据用户设置的错误率进行计算断定。断定公式为：区间距离 = 错误率 * 数据总量。

下图是一个桶合并的例子：

如上所示，假如错误率设置为 0.1，当数据总量大于 10 个时，通过断定公式计算出区间距离为 1，因而将会对区间距离小于等于 1 的相邻桶进行合并。

CKMS 算法不须要预知数据的范畴，用户能够依据数据的性质设置适合的错误率，以管制桶的空间占用和精确度之间的均衡关系。

3.5.3 TDigest 算法

Tdigest 算法的思维是近似算法罕用的素描法（Sketch），用一部分数据来刻画整体数据集的特色，就像咱们日常的素描画一样，尽管和实物有差距，然而却看着和实物很像，可能展示实物的特色。它实质上也是一种动静分桶的形式。

TDigest 算法预计具体的百分位数时，都是依据百分位数对应的两个质心去线性插值计算的，和精准百分位数的计算形式一样。首先咱们依据百分位 q 和所有质心的总权重计算出索引值；其次找出和对应索引相邻的两个质心；最终能够依据两个质心的均值和权重用插值的办法计算出对应的百分位数。（理论的计算方法就是加权均匀）。

由此咱们能够晓得，百分位数 q 的计算误差要越小，其对应的两个质心的均值应该越靠近。TDigest 算法的要害就是如何管制质心的数量，质心的数量越多，显然预计的精度就会越高，然而须要的内存就会越多，计算效率也越低；然而质心数量越少，预计的精度就很低，所以就须要一个衡量。

一种 TDigest 构建算法 buffer-and-merge 能够形容为：

假如咱们有 200 个质心，那么咱们就能够将 0 到 1 拆分 200 等份，则每个质心就对应 0.5 个百分位。如果当初有 10000 个数据点，即总权重是 10000，咱们依照大小对 10000 个点排序后，就能够确定每个质心的权重（相当于质心代表的数据点的个数）应该在 10000/200 = 500 左右，所以说当每个质心的权重小于 500 时，咱们就能够将以后数据点退出以后的质心，否则就新建一个质心。

理论利用中，咱们可能更加关怀 90%，95%，99% 等极其的百分位数，所以 TDigest 算法特意优化了 q= 0 和 q= 1 左近的百分位精度，通过专门的映射函数 K 保障了 q= 0 和 q= 1 左近的质心权重较小，数量较多。

另外一种 TDigest 构建算法是 AVL 树的聚类算法，与 buffer-and-merge 算法相比，它通过应用 AVL 二叉均衡树的形式来搜寻数据点最靠近的质心数，找到最靠近的质心数后，将二者进行合并。

04、限流与过载爱护

简单的业务场景中，常常容易遇到刹时申请量的突增，很有可能会导致服务器占用过多资源，产生了大量的重试和资源竞争，导致响应速度升高、超时乃至宕机，甚至引发雪崩造成整个零碎不可用的状况。

为应答这种状况，通常须要零碎具备牢靠的限流和过载爱护的能力，对于超出零碎承载能力的局部的申请作出疾速回绝、抛弃解决，以保障本服务或上游服务零碎的稳固。

4.1 计数器

计数器算法是限流算法里最简略也是最容易实现的一种算法。计数器算法能够针对某个用户的申请，或某类接口申请，或全局总申请量进行限度。

比方咱们设定针对单个玩家的登录协定，每 3 秒能力申请一次，服务器能够在玩家数据上记录玩家上一次的登录工夫，通过与本次登录工夫进行比照，判断是否曾经超过了 3 秒钟来决定本次申请是否须要持续解决。

又如针对某类协定，假如咱们设定服务器同一秒内总登录协定申请次数不超过 100 条，咱们能够设置一个计数器，每当一个登录申请过去的时候，计数器加 1，如果计数器值大于 100 且以后申请与第一个申请间隔时间还在 1 秒内，那么就断定为达到申请下限，拒绝服务，如果该申请与第一个申请距离曾经超过 1 秒钟，则重置计数器的值为 0，并从新计数。

计数器算法存在刹时流量的临界问题，即在工夫窗口切换时，前一个窗口和后一个窗口的申请量都集中在工夫窗口切换的前后，在最坏的状况下，可能会产生两倍于阈值流量的申请。

为此也能够应用多个不同距离的计数器相结合的形式进行限频，如能够限度登录申请 1 秒内不超过 100 的同时 1 分钟内不超过 1000 次。

4.2 漏桶

漏桶算法原理很简略，假如有一个水桶，所有水（申请）都会先丢进漏桶中，漏桶则以固定的速率出水（解决申请），当申请量速率过大，水桶中的水则会溢出（申请被抛弃）。漏桶算法能保证系统整体按固定的速率解决申请。

如下图所示：

4.3 令牌桶

对于很多利用场景来说，除了要求可能限度申请的固定解决速率外，还要求容许某种程度的突发申请量，这时候漏桶算法可能就不适合了。

令牌桶算法的原理是零碎会以一个恒定的速度往桶里放入令牌，而如果申请须要被解决，则须要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

令牌桶算法大略形容如下：

如下图所示：

4.4 滑动窗口

计数器，漏桶和令牌桶算法是在上游节点做的限流，通过配置零碎参数做限度，不依赖于上游服务的反馈数据，对于异构的申请不太实用，且须要预估上游节点的解决能力。

滑动窗口限频相似于 TCP 的滑动窗口协定，设置一个窗口大小，这个大小即以后最大在解决中的申请量，同时记录滑动窗口的左右端点，每次发送一个申请时滑动窗口右端点往前移一格，每次收到申请处理完毕响应后窗口左端点往前移一格，当右端点与左端点的差值超过最大窗口大小时，期待发送或拒绝服务。

如下图所示：

4.5 SRE 自适应限流

滑动窗口是以固定的窗口大小限度申请，而 Google 的 SRE 自适应限流相当于是一个动静的窗口，它依据过往申请的成功率动静调整向后端发送申请的速率，当成功率越高申请被回绝的概率就越小；反之，当成功率越低申请被回绝的概率就相应越大。

SRE 自适应限流算法须要在应用层记录过来两分钟内的两个数据信息：

申请被回绝的概率 p 的计算公式如下：

咱们能够针对不同场景中解决更多申请带来的危险老本与回绝更多申请带来的服务损失老本之间进行衡量，调整 K 值大小：

如对于某些解决该申请的老本与回绝该申请的老本的靠近场景，零碎高负荷运行造成很多申请解决超时，理论已无意义，然而却还是一样会耗费系统资源的状况下，能够调小 K 值。

4.6 熔断

熔断算法原理是零碎统计并定时查看过往申请的失败（超时）比率，当失败（超时）率达到肯定阈值之后，熔断器开启，并休眠一段时间，当休眠期完结后，熔断器敞开，从新往后端节点发送申请，并从新统计失败率。如此周而复始。

如下图所示：

4.7 Hystrix 半开熔断器

Hystrix 中的半开熔断器绝对于简略熔断减少了一种半开状态，Hystrix 在运行过程中会向每个申请对应的节点报告胜利、失败、超时和回绝的状态，熔断器保护计算统计的数据，依据这些统计的信息来确定熔断器是否关上。如果关上，后续的申请都会被截断。而后会隔一段时间，尝试半开状态，即放入一部分申请过来，相当于对服务进行一次健康检查，如果服务复原，熔断器敞开，随后完全恢复调用，如果失败，则从新关上熔断器，持续进入熔断期待状态。

如下图所示：

05、序列化与编码

数据结构序列化是指将数据结构或对象状态转换成可取用格局（例如存成文件，存于缓冲，或经由网络传输），以留待后续在雷同或另一台计算机环境中，能复原原先状态的过程。通过按照序列化格局从新获取字节的后果时，能够利用它来产生与原始对象雷同语义的正本。

5.1 标记语言

标记语言是一种将文本（Text）以及文本相干的其余信息联合起来，展现出对于文档构造和数据处理细节的计算机文字编码。

5.1.1 超文本标记语言（HTML）

HTML 是一种用于创立网页的规范标记语言。HTML 是一种根底技术，常与 CSS、JavaScript 一起被泛滥网站用于设计网页、网页应用程序以及挪动应用程序的用户界面。网页浏览器能够读取 HTML 文件，并将其渲染成可视化网页。HTML 形容了一个网站的构造语义随着线索的出现，使之成为一种标记语言而非编程语言。

5.1.2 可扩大标记语言（XML）

XML 是一种标记语言，设计用来传送及携带数据信息。每个 XML 文档都由 XML 申明开始，在后面的代码中的第一行就是 XML 申明 <?xml version=”1.0″?>。这一行代码会通知解析器或浏览器这个文件应该依照 XML 规定进行解析。

XML 文档的字符分为标记（Markup）与内容（content）两类。标记通常以 < 结尾，以 > 结尾；或者以字符 & 结尾，以; 结尾。不是标记的字符就是内容。一个 tag 属于标记构造，以 < 结尾，以 > 结尾。

元素是文档逻辑组成，或者在 start-tag 与匹配的 end-tag 之间，或者仅作为一个 empty-element tag。

属性是一种标记构造，在 start-tag 或 empty-element tag 外部的“名字 - 值对”。例如：<img src=”madonna.jpg” alt=”Madonna” />。每个元素中，一个属性最多呈现一次，一个属性只能有一个值。

5.1.3 Markdown

Markdown 是一种轻量级标记语言，创始人为约翰·格鲁伯。它容许人们应用易读易写的纯文本格式编写文档，而后转换成无效的 XHTML（或者 HTML）文档。这种语言排汇了很多在电子邮件中已有的纯文本标记的个性。

因为 Markdown 的轻量化、易读易写个性，并且对于图片，图表、数学式都有反对，目前许多网站都宽泛应用 Markdown 来撰写帮忙文档或是用于论坛上发表音讯。如 GitHub、Reddit、Diaspora、Stack Exchange、OpenStreetMap、SourceForge、简书等，甚至还能被用来撰写电子书。

Markdown 语法格局如下：

5.1.4 JSON

JSON 是以数据线性化为指标的轻量级标记语言，相比于 XML，JSON 更加简洁、轻量和具备更好的可读性。

JSON 的根本数据类型和编码规定：

5.2 TLV 二进制序列化

很多高效的数据序列化形式都是采纳类 TLV（Tag+Length+Value）的形式对数据进行序列化和反序列化，每块数据以 Tag 开始，Tag 即数据标签，标识接下来的数据类型是什么，Length 即长度，标识接下来的数据总长，Value 即数据的理论内容，联合 Tag 和 Length 的大小即可获取以后这块数据内容。

5.2.1 Protocol Buffers

Protocol Buffers（简称：ProtoBuf）是一种开源跨平台的序列化数据结构的协定，它是一种灵便、高效、自动化的构造数据序列化办法，相比 XML 和 JSON 更小、更快、更为简略。

Protocol Buffers 蕴含一个接口描述语言 .proto 文件，形容须要定义的一些数据结构，通过程序工具依据这些形容产生 .cc 和 .h 文件代码，这些代码将用来生成或解析代表这些数据结构的字节流。

Protocol Buffers 编码后的音讯都是 Key-Value 模式，Key 的值由 field_number（字段标号）和 wire_type（编码类型）组合而成，规定为：key = field_number << 3 | wire type。

field_number 局部批示了以后是哪个数据成员，通过它将 cc 和 h 文件中的数据成员与以后的 key-value 对应起来。

wire type 为字段编码类型，有以下几类：

Protocol Buffers 编码特色：

5.2.2 TDR

TDR 是腾讯自研跨平台多语言数据表示组件，次要用于数据的序列化反序列化以及数据的存储。TDR 通过 XML 文件来定义接口和构造的形容，通过程序工具依据这些形容产生 .tdr 和 .h 文件代码，用于序列化和反序列化这些数据结构。

TDR1.0 的版本是通过版本剪裁形式来序列化反序列化，须要当时保护好字段版本号，序列化反序列化时通过剪裁版本号来实现兼容的形式，只反对单向的高版本兼容低版本数据。

TDR2.0 整体上与 Protocol Buffers 类似，TDR2.0 反对音讯协定的前后双向兼容，整型数据同样反对 varint 编码和 zigzag 调整的形式，在对 TLV 中 Length 局部进行解决时，采纳定长编解码形式，以节约序列化空间的代价来获取更高性能，防止了相似 Protocol Buffers 中不必要的内存拷贝（或者是事后计算大小）的过程。

Protocol Buffers 和 TDR 都有接口描述语言，这使得它们的序列化更高效，数据序列化后也更加紧凑。

5.2.3 Luna 序列化

luna 库是开源的基于 C++17 的 lua/C++ 绑定库，它同时也实现了针对 lua 数据结构的序列化和反序列化性能，用于 lua 构造数据的传输和存储。

Lua 语言中须要传输和存储的数据类型次要有：nil，boolean，number，string，table。因而在序列化过程中，luna 将类型定义为以下九种类型。

序列化形式如下：

整体上也是相似于 Protocol Buffers 和 TDR 的 TLV 编码方式，同时针对 lua 类型构造的个性做了一些效率上的优化。

次要个性如下：

5.2.4 Skynet 序列化

Skynet 是一个为在线游戏服务器打造的轻量级框架，其利用较为宽泛。但实际上它也不仅仅应用在游戏服务器畛域 Skynet 的外围是由 C 语言编写，但大多数 Skynet 服务应用 lua 编写，因而它也实现了针对 lua 数据结构的序列化和反序列化性能。

序列化形式如下：

次要个性如下：

5.3 压缩编码

压缩算法从对数据的完整性角度分有损压缩和无损压缩。

有损压缩算法通过移除在保真前提下须要的必要数据之外的其小细节，从而使文件变小。在有损压缩里，因局部无效数据的移除，复原原文件是不可能的。有损压缩次要用来存储图像和音频文件，通过移除数据达到比拟高的压缩率。

无损压缩，也能使文件变小，但对应的解压缩性能能够准确地复原原文件，不失落任何数据。无损数据压缩被宽泛的利用于计算机领域，数据的传输和存储系统中均应用无损压缩算法。

接下来咱们次要是介绍几种无损压缩编码算法。

5.3.1 熵编码法

一种次要类型的熵编码方式是对输出的每一个符号，创立并调配一个惟一的前缀码，而后，通过将每个固定长度的输出符号替换成相应的可变长度前缀无关（prefix-free）输入码字替换，从而达到压缩数据的目标。每个码字的长度近似与概率的负对数成比例。因而，最常见的符号应用最短的码。

霍夫曼编码和算术编码是两种最常见的熵编码技术。如果事后已知数据流的近似熵个性（尤其是对于信号压缩），能够应用简略的动态码。

5.3.2 游程编码

又称行程长度编码或变动长度编码法，是一种与材料性质无关的无损数据压缩技术，基于“应用变动长度的码来取代间断反复呈现的原始材料”来实现压缩。举例来说，一组材料串 ”AAAABBBCCDEEEE”，由 4 个 A、3 个 B、2 个 C、1 个 D、4 个 E 组成，通过变动长度编码法可将材料压缩为 4A3B2C1D4E（由 14 个单位转成 10 个单位）。

5.3.3 MTF 变换

MTF（Move-To-Front）是一种数据编码形式，作为一个额定的步骤，用于进步数据压缩技术成果。MTF 次要应用的是数据“空间局部性”，也就是最近呈现过的字符很可能在接下来的文本左近再次出现。

过程能够形容为：

5.3.4 块排序压缩

当一个字符串用该算法转换时，算法只扭转这个字符串中字符的程序而并不扭转其字符。如果原字符串有几个呈现屡次的子串，那么转换过的字符串上就会有一些间断反复的字符，这对压缩是很有用的。

块排序变换（Burrows-Wheeler Transform）算法能使得基于解决字符串中间断反复字符的技术（如 MTF 变换和游程编码）的编码更容易被压缩。

块排序变换算法将输出字符串的所有循环字符串依照字典序排序，并以排序后字符串造成的矩阵的最初一列为其输入。

5.3.5 字典编码法

由 Abraham Lempel 和 Jacob Ziv 独创性的应用字典编码器的 LZ77/78 算法及其 LZ 系列变种利用宽泛。

LZ77 算法通过应用编码器或者解码器中曾经呈现过的相应匹配数据信息替换以后数据从而实现压缩性能。这个匹配信息应用称为长度 - 间隔对的一对数据进行编码，它等同于“每个给定长度个字符都等于前面特定间隔字符地位上的未压缩数据流。”编码器和解码器都必须保留肯定数量的缓存数据。保留这些数据的构造叫作滑动窗口，因为这样所以 LZ77 有时也称作滑动窗口压缩。编码器须要保留这个数据查找匹配数据，解码器保留这个数据解析编码器所指代的匹配数据。

LZ77 算法针对过来的数据进行解决，而 LZ78 算法却是针对起初的数据进行解决。LZ78 通过对输出缓存数据进行事后扫描与它保护的字典中的数据进行匹配来实现这个性能，在找到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输入数据在字典中的地位、匹配的长度以及找不到匹配的数据，并且将后果数据增加到字典中。

5.3.6 霍夫曼（Huffman）编码

霍夫曼编码把文件中肯定位长的值看作是符号，比方把 8 位长的 256 种值，也就是字节的 256 种值看作是符号。依据这些符号在文件中呈现的频率，对这些符号从新编码。对于呈现次数十分多的，用较少的位来示意，对于呈现次数非常少的，用较多的位来示意。这样一来，文件的一些局部位数变少了，一些局部位数变多了，因为变小的局部比变大的局部多，所以整个文件的大小还是会减小，所以文件失去了压缩。

要进行霍夫曼编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（咱们把字节的 256 种值看作是 256 种符号）的呈现次数。而后依据符号的呈现次数，建设霍夫曼树，通过霍夫曼树失去每个符号的新的编码。对于文件中呈现次数较多的符号，它的霍夫曼编码的位数比拟少。对于文件中呈现次数较少的符号，它的霍夫曼编码的位数比拟多。而后把文件中的每个字节替换成他们新的编码。

5.3.7 其余压缩编码

以下数据起源网络：

5.4 其余编码

5.4.1 Varint

前文所提到的 Varint 整型压缩编码方式，它应用一个或多个字节序列化整数的办法，把整数编码为变长字节。

Varint 编码将每个字节的低 7bit 位用于示意数据，最高 bit 位示意前面是否还有字节，其中 1 示意还有后续字节，0 示意以后是最初一个字节。当整型数值很小时，只须要极少数的字节进行编码，如数值 9，它的编码就是 00001001，只需一个字节。

如上图所示，假如要编码的数据 123456，二进制为：11110001001000000，按 7bit 划分后，每 7bit 增加高 1 位的是否有后续字节标识，编码为 110000001100010000000111，占用 3 个字节。

对于 32 位整型数据通过 Varint 编码后须要 1~5 个字节，小的数字应用 1 个字节，大的数字应用 5 个字节。64 位整型数据编码后占用 1~10 个字节。在理论场景中小数字的使用率远远多于大数字，因而通过 Varint 编码对于大部分场景都能够起到很好的压缩成果。

5.4.2 ZigZag

zigzag 编码的呈现是为了解决 varint 对正数编码效率低的问题。对于有符号整型，如果数值为正数，二进制就会十分大，例如 - 1 的 16 进制：0xffff ffff ffff ffff，对应的二进制位全副是 1，应用 varint 编码须要 10 个字节，十分不划算。

zigzag 编码的原理是将有符号整数映射为无符号整数，使得正数的二进制数值也能用较少的 bit 位示意。它通过移位来实现映射。

因为补码的符号位在最高位，对于正数，符号位为 1，这导致 varint 压缩编码无奈压缩，须要最大变长字节来存储，因而首先将数据位整体循环左移 1 位，最低位空出留给符号位应用，另外，对于理论应用中，绝对值小的正数利用场景比绝对值大的正数利用场景大的多，但绝对值小的正数的前导 1 更多（如 -1，全是 1），因而对于负整数，再把数据位按取反规定操作，将前导 1 置换为 0，以达到能够通过 varint 编码能无效压缩的目标。

最终通过 zigzag 编码后绝对值小的正负整数都能编码为绝对值绝对小的正整数，编码成果如下：

5.4.3 Base 系列

有的字符在一些环境中是不能显示或应用的，比方 &, = 等字符在 URL 被保留为特殊作用的字符，比方一些二进制码如果转成对应的字符的话，会有很多不可见字符和控制符（如换行、回车之类），这时就须要对数据进行编码。Base 系列的就是用来将字节编码为 ASCII 中的可见字符的，以便能进行网络传输和打印等。

Base 系列编码的原理是将字节流按固定步长切片，而后通过映射表为每个切片找一个对应的、可见的 ASCII 字符，最终重组为新的可见字符流。

Base16 也称 hex，它应用 16 个可见字符来示意二进制字符串，1 个字符应用 2 个可见字符来示意，因而编码后数据大小将翻倍。

Base32 应用 32 个可见字符来示意二进制字符串，5 个字符应用 8 个可见字符示意，最初如果有余 8 个字符，将用“=”来补充，编码后数据大小变成原来的 8 /5。

Base64 应用 64 个可见字符来示意二进制字符串，3 个字符应用 4 个可见字符来示意，编码后数据大小变成原来的 4 /3。

Base64 索引表如下：

5.4.4 百分号编码

百分号编码又称 URL 编码（URL encoding），是特定上下文的对立资源定位符（URL）的编码机制，实际上也实用于对立资源标志符（URI）的编码。

百分号编码同样也是为了使 URL 具备可传输性，可显示性以及应答二进制数据的完整性而进行的一种编码规定。

百分号编码规定为把字符的 ASCII 的值示意为两个 16 进制的数字，而后在其后面搁置转义字符百分号“%”。

URI 所容许的字符分作保留与未保留。保留字符是那些具备非凡含意的字符，例如：斜线字符用于 URL（或 URI）不同局部的分界符；未保留字符没有这些非凡含意。

以下是 RFC3986 中对保留字符和未保留字符的定义：

百分号编码可形容为：

06、加密与校验

6.1 CRC

CRC 循环冗余校验（Cyclic redundancy check）是一种依据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，次要用来检测或校验数据传输或者保留后可能呈现的谬误。生成的数字在传输或者存储之前计算出来并且附加到数据前面，而后接管方进行测验确定数据是否发生变化。它是一类重要的线性分组码，编码和解码办法简略，检错和纠错能力强，在通信畛域宽泛地用于实现差错控制。

CRC 是两个字节数据流采纳二进制除法（没有进位，应用 XOR 来代替减法）相除所失去的余数。其中被除数是须要计算校验和的信息数据流的二进制示意；除数是一个长度为（n+1）的预约义（短）的二进制数，通常用多项式的系数来示意。在做除法之前，要在信息数据之后先加上 n 个 0。CRC 是基于无限域 GF（2）（即除以 2 的同余）的多项式环。简略来说，就是所有系数都为 0 或 1（又叫做二进制）的多项式系数的汇合，并且汇合对于所有的代数操作都是关闭的。

6.2 奇偶校验

奇偶校验 (Parity Check) 是一种校验代码传输正确性的办法。依据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采纳奇数的称为奇校验，反之，称为偶校验。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。

以偶校验位来说，如果一组给定数据位中 1 的个数是奇数，补一个 bit 为 1，使得总的 1 的个数是偶数。例：0000001, 补一个 bit 为 1 即 00000011。

以奇校验位来说，如果给定一组数据位中 1 的个数是奇数，补一个 bit 为 0，使得总的 1 的个数是奇数。例：0000001, 补一个 bit 为 0 即 00000010。

偶校验实际上是循环冗余校验的一个特例，通过多项式 x + 1 失去 1 位 CRC。

6.3 MD 系列

MD 系列算法（Message-Digest Algorithm）用于生成信息摘要特色码，具备不可逆性和高度的离散性，能够看成是一种非凡的散列函数（见 8.1 节），个别认为能够惟一地代表原信息的特色，通常用于明码的加密存储，数字签名，文件完整性验证等。

MD4 是麻省理工学院传授 Ronald Rivest 于 1990 年设计的一种信息摘要算法，它是一种用来测试信息完整性的明码散列函数的实现，其摘要长度为 128 位。它是基于 32 位操作数的位操作来实现的。这个算法影响了起初的算法如 MD5、SHA 家族和 RIPEMD 等。

MD5 音讯摘要算法是一种被宽泛应用的明码散列函数，能够产生出一个 128 位（16 个字符）的散列值，用于确保信息传输残缺统一。MD5 由美国明码学家罗纳德·李维斯特（Ronald Linn Rivest）设计，于 1992 年公开，用以取代 MD4 算法。MD5 是输出不定长度信息，输入固定长度 128-bits 的算法。通过程序流程，生成四个 32 位数据，最初联结起来成为一个 128-bits 散列。根本形式为，求余、取余、调整长度、与链接变量进行循环运算，得出后果。

MD6 音讯摘要算法应用默克尔树模式的构造，容许对很长的输出并行进行大量散列计算。该算法的 Block size 为 512 bytes(MD5 的 Block Size 是 512 bits), Chaining value 长度为 1024 bits, 算法减少了并行 机制，适宜于多核 CPU。相较于 MD5，其安全性大大改良，加密构造更为欠缺，但其有证实的版本速度太慢，而效率高的版本并不能给出相似的证实。

6.4 SHA 系列

SHA（Secure Hash Algorithm）是一个明码散列函数家族，是 FIPS 所认证的平安散列算法。

SHA1 是由 NISTNSA 设计为同 DSA 一起应用的，它对长度小于 264 的输出，产生长度为 160bit 的散列值，因而抗穷举性更好。SHA-1 设计时基于和 MD4 雷同原理，并且模拟了该算法。SHA-1 的安全性在 2010 年当前曾经不被大多数的加密场景所承受。2017 年荷兰密码学钻研小组 CWI 和 Google 正式发表攻破了 SHA-1。

SHA-2 由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在 2001 年公布。属于 SHA 算法之一，是 SHA- 1 的后继者。包含 SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-256 和 SHA-512 是很新的杂凑函数，前者以定义一个 word 为 32 位元，后者则定义一个 word 为 64 位元。它们别离应用了不同的偏移量，或用不同的常数，然而，实际上二者构造是雷同的，只在循环执行的次数上有所差别。SHA-224 以及 SHA-384 则是前述二种杂凑函数的截短版，利用不同的初始值做计算。

SHA-3 第三代平安散列算法之前名为 Keccak 算法，Keccak 应用海绵函数，此函数会将材料与初始的外部状态做 XOR 运算，这是无可避免可置换的（inevitably permuted）。在最大的版本，算法应用的内存状态是应用一个 5×5 的二维数组，材料类型是 64 位的字节，总计 1600 比特。缩版的算法应用比拟小的，以 2 为幂次的字节大小 w 为 1 比特，总计应用 25 比特。除了应用较小的版本来钻研加密分析攻击，比拟适中的大小（例如从 w = 4 应用 100 比特，到 w =32 应用 800 比特）则提供了比拟理论且轻量的代替计划。

6.5 对称密钥算法

对称密钥算法（Symmetric-key algorithm）又称为对称加密、私钥加密、共享密钥加密，是密码学中的一类加密算法。这类算法在加密和解密时应用雷同的密钥，或是应用两个能够简略地互相推算的密钥。事实上，这组密钥成为在两个或多个成员间的独特机密，以便维持专属的通信联系。与公开密钥加密相比，要求单方获取雷同的密钥是对称密钥加密的次要毛病之一。

常见的对称加密算法有 AES、ChaCha20、3DES、Salsa20、DES、Blowfish、IDEA、RC5、RC6、Camellia 等。

对称加密的速度比公钥加密快很多，在很多场合都须要对称加密。

6.6 非对称加密算法

非对称式密码学（Asymmetric cryptography）也称公开密钥密码学（Public-key cryptography），是密码学的另一类加密算法，它须要两个密钥，一个是公开密钥，另一个是公有密钥。公钥用作加密，私钥则用作解密。应用公钥把明文加密后所得的密文，只能用绝对应的私钥能力解密并失去本来的明文，最后用来加密的公钥不能用作解密。因为加密和解密须要两个不同的密钥，故被称为非对称加密，不同于加密和解密都应用同一个密钥的对称加密。

公钥能够公开，可任意向外公布，私钥不能够公开，必须由用户自行严格机密保存，绝不透过任何路径向任何人提供，也不会走漏给被信赖的要通信的另一方。

罕用的非对称加密算法是 RSA 算法。

6.7 哈希链

哈希链是一种由单个密钥或明码生成多个一次性密钥或明码的一种办法。哈希链是将密码学中的哈希函数

循环地用于一个字符串。（行将所得哈希值再次传递给哈希函数得至其哈希值）。

例：

，是一个长度为 4 哈希链，记为：

。

相比较而言，一个提供身份验证的服务器贮存哈希字符串，比贮存纯文本明码，更能避免明码在传输或贮存时被泄露。举例来说，一个服务器一开始存储了一个由用户提供的哈希值

。进行身份验证时，用户提供给服务器

。服务器计算

即

，并与已贮存的哈希值

进行比拟。而后服务器将存储

以用来对用户进行下次验证。

窃听者即便嗅探到

送交服务器，也无奈将

用来认证，因为当初服务器验证算法传入的参数是

。因为平安的哈希函数有一种单向的加密属性，对于想要算出前一次哈希值的窃听者来说它的值是不可逆的。在本例中，用户在整个哈希链用完前能够验证 1000 次之多。每次哈希值是不同的，不能被攻击者再次应用。

07、缓存淘汰策略

服务器罕用缓存晋升数据拜访性能，但因为缓存容量无限，当缓存容量达到下限，就须要淘汰局部缓存数据挪出空间，这样新数据才能够增加进来。好的缓存应该是在无限的内存空间内尽量放弃最热门的数据在缓存中，以进步缓存的命中率，因而如何淘汰数据有必要进行一番讲究。缓存淘汰有多种策略，能够依据不同的业务场景抉择不同淘汰的策略。

7.1 FIFO

FIFO（First In First Out）是一种先进先出的数据缓存器，先进先出队列很好了解，当拜访的数据节点不在缓存中时，从后端拉取节点数据并插入在队列头，如果队列已满，则淘汰最先插入队列的数据。

假如缓存队列长度为 6，过程演示如下：

7.2 LRU

LRU（Least recently used）是最近起码应用缓存淘汰算法，可它依据数据的历史拜访记录来进行淘汰数据，其核心思想认为最近应用的数据是热门数据，下一次很大概率将会再次被应用。而最近很少被应用的数据，很大概率下一次不再用到。因而当缓存容量的满时候，优先淘汰最近很少应用的数据。因而它与 FIFO 的区别是在拜访数据节点时，会将被拜访的数据移到头结点。

假如缓存队列长度为 6，过程演示如下：

LRU 算法有个缺点在于对于偶发的拜访操作，比如说批量查问某些数据，可能使缓存中热门数据被这些偶发应用的数据代替，造成缓存净化，导致缓存命中率降落。

7.3 LFU

LFU 是最不常常应用淘汰算法，其核心思想认为如果数据过来被拜访屡次，那么未来被拜访的频率也更高。LRU 的淘汰规定是基于拜访工夫，而 LFU 是基于拜访次数。LFU 缓存算法应用一个计数器来记录数据被拜访的次数，最低拜访数的条目首先被移除。

假如缓存队列长度为 4，过程演示如下：

LFU 可能防止偶发性的操作导致缓存命中率降落的问题，但它也有缺点，比方对于一开始有高访问率而之后长时间没有被拜访的数据，它会始终占用缓存空间，因而一旦数据拜访模式扭转，LFU 可能须要长时间来实用新的拜访模式，即 LFU 存在历史数据影响未来数据的 ” 缓存净化 ” 问题。另外对于对于交替呈现的数据，缓存命中不高。

7.4 LRU-K

无论是 LRU 还是 LFU 都有各自的缺点，LRU-K 算法更像是联合了 LRU 基于拜访工夫和 LFU 基于拜访次数的思维，它将 LRU 最近应用过 1 次的判断规范扩大为最近应用过 K 次，以进步缓存队列淘汰置换的门槛。LRU-K 算法须要保护两个队列：拜访列表和缓存列表。LRU 能够认为是 LRU-K 中 K 等于 1 的特化版。

LRU-K 算法实现能够形容为：

假如拜访列表长度和缓存列表长度都为 4，K=2，过程演示如下：

LRU-K 具备 LRU 的长处，同时可能升高缓存数据被净化的水平，理论利用可依据业务场景抉择不同的 K 值，K 值越大，缓存列表中数据置换的门槛越高。

7.5 Two queues

Two queues 算法能够看做是 LRU-K 算法中 K=2，同时拜访列表应用 FIFO 淘汰算法的一个特例。如下图所示：

7.6 LIRS

LIRS（Low Inter-reference Recency Set）算法将缓存分为两局部区域：热数据区与冷数据区。LIRS 算法利用冷数据区做了一层隔离，目标是即便在有偶发性的拜访操作时，爱护热数据区的数据不会被频繁地被置换，以进步缓存的命中。

LIRS 继承了 LRU 依据工夫局部性对冷热数据进行预测的思维，并在此之上 LIRS 引入了两个掂量数据块的指标：

如下图，从左往右通过以下 8 次访问后，A 节点此时的 IRR 值为 3，R 值为 1。

IRR 能够由 R 值计算而来，具体公式为：IRR= 上一时刻的 R- 以后时刻的 R，如上图以后时刻拜访的节点是 F，那么以后时刻 F 的 R 值为 0，而上一个 F 节点的 R 值为 2，因而 F 节点的 IRR 值为 2。

LIRS 动静保护两个汇合：

LIR 汇合所有数据都在缓存中，而 HIR 汇合中有局部数据不在缓存中，但记录了它们的历史信息并标记为未驻留在缓存中，称这部分数据块为 nonresident-HIR，另外一部分驻留在缓存中的数据块称为 resident-HIR。

LIR 汇合在缓存中，所以拜访 LIR 汇合的数据是百分百会命中缓存的。而 HIR 汇合分为 resident-HIR 和 nonresident-HIR 两局部，所以会遇到未命中状况。当产生缓存未命中须要置换缓存块时，会抉择优先淘汰置换 resident-HIR。如果 HIR 汇合中数据的 IRR 通过更新比 LIR 汇合中的小，那么 LIR 汇合数据块就会被 HIR 汇合中 IRR 小的数据块挤出并转换为 HIR。

LIRS 通过限度 LIR 汇合的长度和 resident-HIR 汇合长度来限度整体大小，假如设定 LIR 长度为 2，resident-HIR 长度为 1 的 LIRS 算法过程演示如下：

解释一下当栈 S 中的一个 HIR 数据被拜访时，它为什么肯定会变成一个 LIR 数据：这个数据被拜访时，须要更新 IRR 值（即为以后的 R 值），应用这个新的 IRR 与 LIR 汇合数据中最大的 R 值进行比拟（即栈 S 最底部的 LIR 数据），新的 IRR 肯定会比栈 S 最底部的 LIR 数据的 IRR 小（因为栈 S 最底部的数据肯定是 LIR 数据，步骤 2 曾经保障了），所以它肯定会变成一个 LIR 数据。

7.7 MySQL InnoDB LRU

MySQL InnoDB 中的 LRU 淘汰算法采纳了相似的 LIRS 的分级思维，它的置换数据形式更加简略，通过判断冷数据在缓存中存在的工夫是否足够长（即还没有被 LRU 淘汰）来实现。数据首先进入冷数据区，如果数据在较短的工夫内被拜访两次或者以上，则成为热点数据进入热数据区，冷数据和热数据局部区域外部各自还是采纳 LRU 替换算法。

MySQL InnoDB LRU 算法流程能够形容为：

08、基数集与基数统计

基数集即不反复元素的汇合，基数统计即统计基数集中元素的个数。比如说 18 号晚微信视频号西城男孩直播夜的累积观看人数统计就是一个基数统计的利用场景。

8.1 哈希表

哈希表是依据关键码（Key）而间接进行拜访的数据结构，它把关键码映射到一个无限的地址区间上寄存在哈希表中，这个映射函数叫做散列函数。哈希表的设计最要害的是应用正当的散列函数和抵触解决算法。

好的散列函数应该在输出域中较少呈现散列抵触，数据元素能被更快地插入和查找。常见的散列函数算法有：间接寻址法，数字分析法，平方取中法，折叠法，随机数法，除留余数法等。

然而即便再好的散列函数，也不能百分百保障没有抵触，因而必须要有抵触的应答办法，常见的抵触解决算法有：

应用哈希表统计基数值行将所有元素存储在一个哈希表中，利用哈希表对元素进行去重，并统计元素的个数，这种办法能够准确的计算出不反复元素的数量。

但应用哈希表进行基数统计，须要存储理论的元素数据，在数据量较少时还算可行，然而当数据量达到百万、千万甚至上亿时，应用哈希表统计会占用大量的内存，同时它的查找过滤老本也很高。如 18 号晚微信视频号西城男孩直播夜有 2000 万多的用户观看，假如记录用户的 id 大小须要 8 字节，那么应用哈希表构造至多须要 152.6M 内存，而为了升高哈希抵触率，进步查找性能，理论须要开拓更大的内存空间。

8.2 位图（Bitmap）

位图就是用每一比特位来寄存真和假状态的一种数据结构，应用位图进行基数统计不须要去存储理论元素信息，只须要用相应地位的 1bit 来标识某个元素是否呈现过，这样可能极大地节俭内存。

如下图所示，假如要存储的数据范畴是 0 -15，咱们只须要应用 2 个字节组建一个领有 16bit 位的比特数组，所有 bit 位的值初始化为 0，须要存储某个值时只须要将相应地位的的 bit 位设置为 1，如下图存储了 {2,5,6,9,11,14} 六个数据。

假如观看西城男孩直播的微信 id 值域是[0-2000 万]，采纳位图统计观看人数所须要的内存就只需 2.38M 了。

位图统计形式内存占用的确大大减少了，但位图占用的内存和元素的值域无关，因为咱们须要把值域映射到这个间断的大比特数组上。实际上观看西城男孩直播的微信 id 不可能是间断的 2000 万个 id 值，而应该按微信的注册量级开拓长度，可能至多须要 20 亿的 bit 位（238M 内存）。

8.3 布隆过滤器

位图的形式有个很大的局限性就是要求值域范畴无限，比方咱们统计观看西城男孩直播的微信 id 总计 2000 万个，但理论却须要依照微信 id 范畴下限 20 亿来开拓空间，如果有一个完满散列函数，能正好将观看了直播的这 2000 万个微信 id 映射成 [0-2000 万] 的不反复散列值，而其余没有观看直播的 19.8 亿微信 id 都被映射为超过 2000 万的散列值，那事件就好办了，但事实是咱们无奈提前晓得哪 2000 万的微信号会观看直播，因而这样的散列函数是不可能存在的。

但这个思维是对的，布隆过滤器就是相似这样的思维，它能将 20 亿的 id 值映射到更小数值范畴内，而后应用位图来记录元素是否存在，因为值域范畴被压缩了，必然会存在大面积的抵触，为了升高抵触导致的统计错误率，它通过 K 个不同的散列函数将元素映射成一个位图中的 K 个 bit 位，并把它们都置为 1，只有当某个元素对应的这 K 个 bit 位同时为 1，才认为这个元素曾经存在过。

假如 K=3，3 个哈希函数将数据映射到 0 -15 的位图中存储，过程演示如下：

相似百分比近似排序，布隆过滤器也是就义肯定的精确度来换取高性能的做法。它依然存在肯定的错误率，不能保障齐全精确，比方上图示例中，假如接下来要插入数据 123，它通过 3 个哈希函数别离被映射为：{2,3,6}，此时会误判为 123 曾经存在了，将过滤掉该数据的统计。

但实际上只有 K 值和位图数组空间设置正当，就能保障错误率在肯定范畴，这对于大数据量的基数统计，齐全能承受这样的统计误差。

8.4 布谷鸟过滤器

布谷鸟过滤器是另外一种通过就义肯定的精确度来换取高性能的做法，也是十分之奇妙。在解释布谷鸟过滤器之前咱们先来看下布谷鸟哈希算法。

布谷鸟哈希算法是 8.1 节中讲到的解决哈希抵触的另一种算法，它的思维来源于布谷鸟“鸠占鹊巢”的生存习性。布谷鸟哈希算法会有两个散列函数将元素映射到哈希表的两个不同地位。如果两个地位中有一个地位为空，那么就能够将元素间接放进去。然而如果这两个地位都满了，它就随机踢走一个，而后本人霸占了这个地位。被踢走的那个元素会去查看它的另外一个散列值的地位是否是空位，如果是空位就霸占它，如果不是空位，那就把受害者的角色转移进来，挤走对方，让对方再去找安身之处，如此循环直到某个元素找到空位为止。

布谷鸟哈希算法有个毛病是当空间自身很拥挤时，呈现“鸠占鹊巢”的景象会很频繁，插入效率很低，一种改进的优化计划是让每个散列值对应的地位上能够搁置多个元素。

8.1 节讲到，哈希表能够用来做基数统计，因而布谷鸟哈希表当然也能够用来基数统计，而布谷鸟过滤器基于布谷鸟哈希算法来实现基数统计，布谷鸟哈希算法须要存储数据的整个元素信息，而布谷鸟过滤器为了缩小内存，将存储的元素信息映射为一个简略的指纹信息，例如微信的用户 id 大小须要 8 字节，咱们能够将它映射为 1 个字节甚至几个 bit 的指纹信息来进行存储。

因为只存储了指纹信息，因而谷鸟过滤器的两个散列函数的抉择比拟非凡，当一个地位上的元素被挤走之后，它须要通过指纹信息计算出另一个对偶地位（布谷鸟哈希存储的是元素的残缺信息，必然能找到另一个散列值地位），因而它采纳异或的形式达到目标，公式如下：

h1(x) = hash(x)
h2(x) = h1(x) ⊕ hash(x 的指纹)

地位 h2 能够通过地位 h1 和 h1 中存储的指纹信息计算出来，同样的地位 h1 也能够通过 h2 和指纹信息计算出来。

布谷鸟过滤器实现了哈希表过滤和基数统计的能力，同时存储元素信息改为存储更轻量指纹信息节约了内存，但它损失了一些精确度，比方会呈现两个元素的散列地位雷同，指纹也正好雷同的状况，那么插入查看会认为它们是相等的，只会统计一次。但同样这个误差率是能够承受的。

8.4 HyperLogLog

说到基数统计，就不得不提 Redis 外面的 HyperLogLog 算法了，前文所说的哈希表，位图，布隆过滤器和布谷鸟过滤器都是基于记录元素的信息并通过过滤（或近似过滤）雷同元素的思维来进行基数统计的。

而 HyperLogLog 算法的思维不太一样，它的根底是察看到能够通过计算汇合中每个数字的二进制示意中的前导零的最大数目来预计均匀分布的随机数的多重集的基数。如果察看到的前导零的最大数目是 n，则汇合中不同元素的数量的预计是

。

怎么了解呢？其实就是使用了数学概率论的实践，以抛硬币的伯努利试验为例，假如始终尝试抛硬币，直到它呈现侧面为止，同时记录第一次呈现侧面时共尝试的抛掷次数 k，作为一次残缺的伯努利试验。那么对于 n 次伯努利试验，假如其中最大的那次抛掷次数为

。联合极大似然估算的办法，n 和

中存在估算关联关系即：

。

对应于基数统计的场景，HyperLogLog 算法通过散列函数，将数据转为二进制比特串，从低位往高位看，第一次呈现 1 的时候认为是抛硬币的侧面，因而比特串中前导零的数目即是抛硬币的抛掷次数。因而能够依据存入数据中，转化后的二进制串集中最大的首次呈现 1 的地位

来估算存入了多少不同的数据。

这种估算形式存在肯定的必然性，比方当某次抛硬币特地可怜时，抛出了很大的值，数据会偏差的厉害，为了升高这种极其必然性带来的误差影响，在 HyperLogLog 算法中，会将汇合分成多个子集（分桶计算），别离计算这些子集中的数字中的前导零的最大数量，最初应用和谐平均数的计算形式将所有子集的这些估计值计算为选集的基数。例如 redis 会分为 16384 个子集进行分桶求均匀统计。

09、其余罕用算法

9.1 工夫轮定时器

定时器的实现形式有很多，比方用有序链表或堆都能够实现，然而他们或插入或运行或删除的性能不太好。工夫轮定时器是一种插入，运行和删除都比拟现实的定时器。

工夫轮定时器将依照到期工夫分桶放入缓存队列中，零碎只需依照每个桶到期程序顺次执行到期的工夫桶节点中的所有定时工作。

如下图所示：

而针对定时工作时间跨度大，且精度要求较高的场景，应用单层工夫轮耗费的内存可能比拟大，因而还能够进一步优化为采纳层级工夫轮来实现，层级工夫轮就相似咱们的时钟，秒针转一圈后，分针才进一格的原理，当内层工夫轮运行完一轮后，外层工夫轮进一格，接下来运行下一格的内层工夫轮。

9.2 红包调配

码客上有一篇晚期微信红包的随机算法源码。算法很简洁，该算法没有事后随机调配好红包金额列表，而是在每个用户点击抢红包时随机生成金额，该算法只需传入以后残余的总金额和残余须要派发的总人数，算法的基本原理是以残余单个红包的均匀金额的 2. 倍为下限，随机本次调配的金额。

这个算法的公平性在于每个领红包的人能支付到的金额是从 0 到残余均匀金额的 2 倍之间的随机值，所以冀望就是残余均匀金额，假如 100 元发给 5 集体，那么第一个人支付到的冀望是 20 元，第 2 集体支付到的冀望是（100-20）/ 4 = 20 元，通过归纳法能够证实每个人支付到的冀望都是 20 元。然而因为每个人支付到的金额随机范畴是不一样的，如第一个人能支付到的范畴是 0 到 40 元，而最初一个人能支付到的范畴是 0 到 100 元，因而方差跟支付的程序是有关系。这也通知咱们抢微信红包想稳的人能够先抢，想博的人能够后抢。

这种调配算法的益处是无状态化，不须要在创立红包时事后调配并存储金额列表，在某些场景可能会对性能带来益处。

10

总结

笔者已经写过一篇《服务器开发设计之词汇宝典》，讲述了一些后台程序架构和零碎方面的设计常识。如果把架构设计比做程序员的内功修炼的话，那么算法就是战斗中的招式，抉择适合的算法能让你的代码化繁为简，或高效或优雅，见招拆招，起到四两拨千斤的成果的同时震撼心灵。如果各位感兴趣，欢送留言。后续咱们为各位分享相干内容。

很多算法的思维都有一些共通性，他们用到的根底思维都有相似之处，如随机，分治递归，多策略相结合，一次不行再来一次等思维。比方随机，这个在后盾开发设计中随处可见的策略。随机带来的是一种个体必然性与总体偶然性的联合，在 jump consistent hash 算法、跳表排序算法、带权重的 A-ExpJ 算法蓄水池抽样等算法中都应用了随机跳跃的思维，实现了在无需统计状态数据的状况下，利用随机的整体均衡性来保障算法正确性的同时极大地简化了算法和进步了效率。

学习和钻研优良的算法目标是心愿能在理论利用场景中做到灵活运用，舍短取长，甚至能联合不同算法思维启发发明出适宜各种问题场景的算法策略。

因为集体程度无限，文中兴许有纰漏，欢送在评论区中探讨斧正。如果感觉本篇文章有用，欢送转发分享~

参考文章：

《The Power of Two Random Choices》

《The Art of Computer Programming（vol. 2_ Seminumerical Algorithms）（3rd ed.）》

《Random Sampling with a Reservoir》JEFFREY SCOTT VITTER

《Weighted Random Sampling》（Efraimidis, Spirakis）

《Weighted random sampling with a reservoir》（Efraimidis, Spirakis）

《多路均衡归并排序算法》

《TDigest 算法原理》

《ElasticSearch 如何应用 TDigest 算法计算亿级数据的百分位数？》

《分位数算法总结》

《Handling Overload》

《zigzag 算法详解》

《markdown》百度百科

《Compress》https://gitee.com/yu120/compress

《罕用缓存淘汰算法 LFU/LRU/ARC/FIFO/MRU》

《缓存淘汰算法 LIRS 原理与实现》

《MySQL 5.7 Reference Manual》

《布隆过滤器过期了，将来属于布谷鸟过滤器？》

《HyperLogLog 算法的原理解说以及 Redis 是如何利用它的》

《对于基数统计》

《算法导论（第 2 版）》

其余网络材料

-End-

原创作者|邹辉林

技术责编|向灿辉

你见过哪些令人赞不绝口的算法？能够在腾讯云开发者公众号评论区中分享。咱们将选取 1 则最有意义的评论，送出腾讯云开发者 - 棒球帽 1 个（见下图）。7 月 3 日中午 12 点开奖。