基于数据结构和算法的深入应用

• 回顾数据结构与算法的基础知识
• 学习日常所接触场景中的一些算法和策略
• 这些算法的原理和他背后的思想
• 动手写代码，用java里的数据结构来实现这些算法，如何去做？

1）概述

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

2）划分

从关注的维度看，数据结构可以划分为数据的逻辑结构和物理结构，同一逻辑结构可以对应不同的存储结构。

逻辑结构反映的是数据元素之间的逻辑关系，逻辑关系是指数据元素之间的前后间以什么形式相互关联，这与他们在计算机中的存储位置无关。逻辑结构包括：

• 集合：只是扎堆凑在一起，没有互相之间的关联
• 线性结构：一对一关联，队形
• 树形结构：一对多关联，树形
• 图形结构：多对多关联，网状

• 数据物理结构指的是逻辑结构在计算机存储空间中的存放形式(也称为存储结构)。一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

• 顺序存储：用一组地址连续的存储单元依次存储集合的各个数据元素，可随机存取，但增删需要大批移动
• 链式存储：不要求连续，每个节点都由数据域和指针域组成，占据额外空间，增删快，查找慢需要遍历
• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。检索快，空间占用大
• 哈希存储：将数据元素的存储位置与关键码之间建立确定对应关系，检索快，存在映射函数碰撞问题

3）程序中常见的数据结构

• 数组(Array)：连续存储，线性结构，可根据偏移量随机读取，扩容困难
• 栈( Stack)：线性存储，只允许一端操作，先进后出，类似水桶
• 队列(Queue)：类似栈，可以双端操作。先进先出，类似水管
• 链表( LinkedList)：链式存储，配备前后节点的指针，可以是双向的
• 树( Tree)：典型的非线性结构，从唯一的根节点开始，子节点单向执行前驱（父节点）
• 图(Graph)：另一种非线性结构，由节点和关系组成，没有根的概念，互相之间存在关联
• 堆(Heap)：特殊的树，特点是根结点的值是所有结点中最小的或者最大的，且子树也是堆
• 散列表(Hash)：源自于散列函数，将值做一个函数式映射，映射的输出作为存储的地址

算法指的是基于存储结构下，对数据如何有效的操作，采用什么方式可以更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般涉及的操作有以下几种：

• 检索：在数据结构里查找满足一定条件的节点。
• 插入：往数据结构中增加新的节点，一般有一点位置上的要求。
• 删除：把指定的结点从数据结构中去掉，本身可能隐含有检索的需求。
• 更新：改变指定节点的一个或多个字段的值，同样隐含检索。
• 排序：把节点里的数据，按某种指定的顺序重新排列，例如递增或递减。

简单理解，为了某种运算而花费的时间，使用大写O表示。一般来讲，时间是一个不太容易计量的维度，而为了计算时间复杂度，通常会估计算法的操作单元数量，而假定每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量一般来讲成正比，最多相差一个常量系数。一般来讲，常见时间复杂度有以下几种：

1）常数阶O(1)：时间与数据规模无关，如交换两个变量值

2）线性阶O(n)：时间和数据规模呈线性，可以理解为n的1次方，如单循环里的操作

3）k次方阶O(n k )：执行次数是数量的k次方，如多重循环，以下为2次方阶实例

4）指数阶O(2 n )：随着n的上升，运算次数呈指数增长

5）对数阶O(log 2 n)：执行次数呈对数缩减，如下

6）线性对数阶O(nlog 2 n)：在对数阶的基础上，进行线性n倍乘积

7）总结：

与时间复杂度类似，空间复杂度是对一个算法在运行过程中占用内存空间大小的度量。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助空间。而空间复杂度主要指的是这部分空间的量级。

• 固定空间：主要包括指令空间、常量、简单变量等所占的空间，这部分空间的大小与运算的数据多少无关，属于静态空间。
• 可变空间：主要包括运行期间动态分配的临时空间，以及递归栈所需的空间等，这部分的空间大小与算法有很大关系。

同样，空间复杂度也用大写O表示，相比时间复杂度场景相对简单，常见级别为O(1)和O(n)，以数组逆序为例，两种不同算法对复杂度影响如下：

1）O(1)：常数阶，所占空间和数据量大小无关。

2）O(n)：线性阶，与数据量大小呈线性关系

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。时间复杂度低可能借助占用大的存储空间来弥补，反之，某个算法所占据空间小，那么可能就需要占用更多的运算时间。两者往往需要达到一种权衡。

在特定环境下的业务，还需要综合考虑算法的各项性能，如使用频率，数据量的大小，所用的开发语言，运行的机器系统等。两者兼顾权衡利弊才能设计出最适合当前场景的算法。

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题小到可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)，大数据中的MR，现实中如汉诺塔游戏。

分治法对问题有一定的要求：

• 该问题缩小到一定程度后，就可以轻松解决
• 问题具有可拆解性，不是一团无法拆分的乱麻
• 拆解后的答案具有可合并性。能组装成最终结果
• 拆解的子问题要相互独立，互相之间不存在或者很少有依赖关系

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他。依次解决各子问题，最后一个子问题就是初始问题的解。

与分治法最大的不同在于，分治法的思想是并发，动态规划的思想是分步。该方法经分解后得到的子问题往往不是互相独立的，其下一个子阶段的求解往往是建立在上一个子阶段的解的基础上。动态规划算法同样有一定的适用性

场景要求：

• 最优化解：拆解后的子阶段具备最优化解，且该最优化解与追踪答案方向一致
• 流程向前，无后效性：上一阶段的解决方案一旦确定，状态就确定，只会影响下一步，而不会反向影响
• 阶段关联：上下阶段不是独立的，上一阶段会对下一阶段的行动提供决策性指导。这不是必须的，但是如果具备该特征，动态规划算法的意义才能更大的得到体现

同样对问题要求作出拆解，但是每一步，以当前局部为目标，求得该局部的最优解。那么最终问题解决时，得到完整的最优解。也就是说，在对问题求解时，总是做出在当前看来是最好的选择，而不去从整体最优上加以考虑。从这一角度来讲，该算法具有一定的场景局限性。

• 要求问题可拆解，并且拆解后每一步的状态无后效性（与动态规划算法类似）
• 要求问题每一步的局部最优，与整体最优解方向一致。至少会导向正确的主方向。

回溯算法实际上是一个类似枚举的搜索尝试过程，在每一步的问题下，列举可能的解决方式。选择某个方案往深度探究，寻找问题的解，当发现已不满足求解条件，或深度达到一定数量时，就返回，尝试别的路径。回溯法一般适用于比较复杂的，规模较大的问题。有“通用解题法”之称。

• 问题的解决方案具备可列举性，数量有限
• 界定回溯点的深度。达到一定程度后，折返

与回溯法类似，也是一种在空间上枚举寻找最优解的方式。但是回溯法策略为深度优先。分支法为广度优先。分支法一般找到所有相邻结点，先采取淘汰策略，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从存活表中选择一个结点作为下一个操作对象。

• 针对算法做了相应的回顾
• 算法的考量：时间与空间复杂度
• 算法的基本思想

失效算法常见于缓存系统中。因为缓存往往占据大量内存，而内存空间是相对昂贵，且空间有限的，那么针对一部分值，就要依据相应的算法进行失效或移除操作。

1）概述

First In First Out，先来先淘汰。这种算法在每一次新数据插入时，如果队列已满，则将最早插入的数据移除。

2）实现

可以方便的借助LinkedList来实现

3）结果分析

4）优缺点

实现非常简单

不管元素的使用情况，哪怕有些数据会被频繁用到，时间最久也会被踢掉

1）概述

LRU全称是Least Recently Used，即淘汰最后一次使用时间最久远的数值。FIFO非常的粗暴，不管有没有用到，直接踢掉时间久的元素。而LRU认为，最近频繁使用过的数据，将来也很大程度上会被频繁用到，故而淘汰那些懒惰的数据。LinkedHashMap，数组，链表均可实现LRU，下面仍然以链表为例：新加入的数据放在头部，最近访问的，也移到头部，空间满时，将尾部元素删除。

2）实现

3）结果分析

1）概述

Least Frequently Used，即最近最少使用。它要淘汰的是最近一段时间内，使用次数最少的值。可以认为比LRU多了一重判断。LFU需要时间和次数两个维度的参考指标。需要注意的是，两个维度就可能涉及到同一时间段内，访问次数相同的情况，就必须内置一个计数器和一个队列，计数器算数，队列放置相同计数时的访问时间。

2）实现

3）结果分析

redis属于缓存失效的典型应用场景，常见策略如下：

• noeviction: 不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息（ 比较危险）。
• allkeys-lru：对所有key，优先删除最近最少使用的 key (LRU)。
• allkeys-random： 对所有key， 随机删除一部分（听起来毫无道理）。
• volatile-lru：只限于设置了 expire 的key，优先删除最近最少使用的key (LRU)。
• volatile-random：只限于设置了 expire 的key，随机删除一部分。
• volatile-ttl：只限于设置了 expire 的key，优先删除剩余时间(TTL) 短的key。

限流是对系统的一种保护措施。即限制流量请求的频率（每秒处理多少个请求）。一般来说，当请求流量超过系统的瓶颈，则丢弃掉多余的请求流量，保证系统的可用性。即要么不放进来，放进来的就保证提供服务。

1）概述

计数器采用简单的计数操作，到一段时间节点后自动清零

2）实现

3）结果分析

3个ok一组呈现，到下一个计数周期之前被阻断

4）优缺点

• 实现起来非常简单。
• 控制力度太过于简略，假如1s内限制3次，那么如果3次在前100ms内已经用完，后面的900ms将只能处于阻塞状态，白白浪费掉。

5）应用

使用计数器限流的场景较少，因为它的处理逻辑不够灵活。最常见的可能在web的登录密码验证，输入错误次数冻结一段时间的场景。如果网站请求使用计数器，那么恶意攻击者前100ms吃掉流量计数，使得后续正常的请求被全部阻断，整个服务很容易被搞垮。

1）概述

漏桶算法将请求缓存在桶中，服务流程匀速处理。超出桶容量的部分丢弃。漏桶算法主要用于保护内部的处理业务，保障其稳定有节奏的处理请求，但是无法根据流量的波动弹性调整响应能力。现实中，类似容纳人数有限的服务大厅开启了固定的服务窗口。

2）实现

3）结果分析

4）优缺点

• 有效的挡住了外部的请求，保护了内部的服务不会过载
• 内部服务匀速执行，无法应对流量洪峰，无法做到弹性处理突发任务
• 任务超时溢出时被丢弃。现实中可能需要缓存队列辅助保持一段时间

5）应用

nginx中的限流是漏桶算法的典型应用，配置案例如下：

1）概述

令牌桶算法可以认为是漏桶算法的一种升级，它不但可以将流量做一步限制，还可以解决漏桶中无法弹性伸缩处理请求的问题。体现在现实中，类似服务大厅的门口设置门禁卡发放。发放是匀速的，请求较少时，令牌可以缓存起来，供流量爆发时一次性批量获取使用。而内部服务窗口不设限。

2）实现

3）结果分析

4）应用

springcloud中gateway可以配置令牌桶实现限流控制，案例如下：

1）概述

滑动窗口可以理解为细分之后的计数器，计数器粗暴的限定1分钟内的访问次数，而滑动窗口限流将1分钟拆为多个段，不但要求整个1分钟内请求数小于上限，而且要求每个片段请求数也要小于上限。相当于将原来的计数周期做了多个片段拆分。更为精细。

2）实现

3）结果分析

4）应用

滑动窗口算法，在tcp协议发包过程中被使用。在web现实场景中，可以将流量控制做更细化处理，解决计数器模型控制力度太粗暴的问题。

调度算法常见于操作系统中，因为系统资源有限，当有多个进程（或多个进程发出的请求）要使用这些资源时，就必须按照一定的原则选择进程（请求）来占用资源。这就是所谓的调度。在现实生活中也是一样，比如会议室的占用。

1）概念

先来先服务，很好理解，就是按照服务提交申请的顺序，依次执行。讲究先来后到。

2）实现

定义一个Task类作为任务实例，BlockingQueue作为服务队列

3）结果分析

4）优缺点

• 多应用于CPU密集型任务场景，对io密集型的不利。
• 时间相对均衡的业务可以排队处理，比如现实中排队打卡进站。
• 如果业务需要依赖大量的外部因素，执行时间片长短不一，FCFS算法不利于任务的整体处理进度，可能会因为一个长时间业务的阻塞而造成大量等待。

1）概念

执行时间短的优先得到资源。即执行前申报一个我需要占据cpu的时间，根据时间长短，短的优先被调度。我不占时间所以我先来。

2）实现

使用TreeMap可以实现优先级的任务排序。

3）结果分析

4）优缺点

• 适用于任务时间差别较大的场景，仍然以进站为例，拿出公交卡的优先刷卡，还没办卡的让一让。
• 解决了FCFS整体处理时间长的问题，降低平均等待时间，提高了系统吞吐量。
• 未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理
• 对长作业的不利，可能等待很久而得不到执行
• 时间基于预估和申报，主观性因素在内，无法做到100%的精准

1）概念

时间片逐个扫描轮询，轮到谁谁执行。大家公平裁决来者有份，谁也别插队。像是棋牌游戏中的发牌操作，做到了时间和机会上的平均性。

2）实现

基于数组做为数据插槽方式实现。

3）结果分析

4）优缺点

• 做到了机会的相对平均，不会因为某个任务执行时间超长而永远得不到执行
• 缺乏任务主次的处理。重要的任务无法得到优先执行，必须等到时间片轮到自己，着急也没用

1）概述

进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。

2）实现

在Task类中新增一个属性level作为优先级标识

依然使用TreeMap实现排序，注意的是，key要取优先级

3）结果分析

• CPU资源调度
• 云计算资源调度
• 容器化Docker编排与调度

系统或者项目中难免会遇到各种需要自动去执行的任务，实现这些任务的手段也多种多样，如操作系统的crontab，spring框架的quartz，java的Timer和ScheduledThreadPool都是定时任务中的典型手段。

1）概述

Timer是java中最典型的基于优先级队列 最小堆实现的定时器，内部维护一个存放定时任务的优先级队列，该优先级队列使用了最小堆排序。当我们调用schedule方法的时候，一个新的任务被加入queue，堆重排，始终保持堆顶是执行时间最小（即最近马上要执行）的。同时，内部相当于起了一个线程不断扫描队列，从队列中依次获取堆顶元素执行，任务得到调度。

下面以Timer为例，介绍优先级队列 最小堆算法的实现原理：

2）案例

3）源码分析

新加任务时，t.schedule方法会add到队列

add实现了容量维护，不足时扩容，同时将新任务追加到队列队尾，触发堆排序，始终保持堆顶元素最小

线程调度中的run，主要调用内部mainLoop()方法，使用while循环

4）应用

• 本节使用Timer为了介绍算法原理，但是Timer已过时，实际应用中推荐使用ScheduledThreadPoolExecutor（同样内部使用DelayedWorkQueue和最小堆排序）
• Timer是单线程，一旦一个失败或出现异常，将打断全部任务队列，线程池不会
• Timer在jdk1.3 ，而线程池需要jdk1.5

1）概述

时间轮是一种更为常见的定时调度算法，各种操作系统的定时任务调度，linux crontab，基于java的通信框架Netty等。其灵感来源于我们生活中的时钟。

轮盘实际上是一个头尾相接的环状数组，数组的个数即是插槽数，每个插槽中可以放置任务。以1天为例，将任务的执行时间，根据得到的数值，放置在时间轮上，小时指针沿着轮盘扫描，扫到的点取出

任务执行：

• 问题：比如3点钟，有多个任务执行怎么办？

答案：在每个槽上设置一个队列，队列可以无限追加，解决时间点冲突问题（类似HashMap结构）

• 问题：每个轮盘的时间有限，比如1个月后的第3天的5点怎么办？

方案一：加长时间刻度，扩充到1年

优缺点：简单，占据大量内存，即使插槽没有任务也要空轮询，白白的资源浪费，时间、空间复杂度都高

方案二：每个任务记录一个计数器，表示转多少圈后才会执行。没当指针过来后，计数器减1，减到0的再执行

优缺点：每到一个指针都需要取出链表遍历判断，时间复杂度高，但是空间复杂度低

方案三：设置多个时间轮，年轮，月轮，天轮。1天内的放入天轮，1年后的则放入年轮，当年轮指针读到后，将任务取出，放入下一级的月轮对应的插槽，月轮再到天轮，直到最小精度取到，任务被执行。

优缺点：不需要额外的遍历时间，但是占据了多个轮的空间。空间复杂度升高，但是时间复杂度降低

2）java实现

定义Task类

时间轮算法：

3）结果分析

负载均衡，英文名称为Load Balance，其含义就是指将负载（工作任务）进行平衡、分摊到多个操作单元上进行运行，例如FTP服务器、Web服务器、企业核心应用服务器和其它主要任务服务器等，从而协同完成工作任务。既然涉及到多个机器，就涉及到任务如何分发，这就是负载均衡算法问题。

1）概述

轮询即排好队，一个接一个。前面调度算法中用到的时间片轮转，就是一种典型的轮询。但是前面使用数组和下标轮询实现。这里尝试手动写一个双向链表形式实现服务器列表的请求轮询算法。

2）实现

3）结果分析

4）优缺点

• 实现简单，机器列表可以自由加减，且时间复杂度为o(1)
• 无法针对节点做偏向性定制，节点处理能力的强弱无法区分对待

1）概述

从可服务的列表中随机取一个提供响应。随机存取的场景下，适合使用数组更高效的实现下标随机读取。

2）实现

定义一个数组，在数组长度内取随机数，作为其下标即可。非常简单

3）结果分析

1）概述

对当前访问的ip地址做一个hash值，相同的key被路由到同一台机器去。场景常见于分布式集群环境下，用户登录时的请求路由和会话保持。

2）实现

使用HashMap可以实现请求值到对应节点的服务，其查找时的时间复杂度为o(1)。固定一种算法，将请求映射到key上即可。举例，将请求的来源ip末尾，按机器数取余作为key：

3）结果分析

1）概述

WeightRoundRobin，轮询只是机械的旋转，加权轮询弥补了所有机器一视同仁的缺点。在轮询的基础上，初始化时，机器携带一个比重。

2）实现

维护一个链表，每个机器根据权重不同，占据的个数不同。轮询时权重大的，个数多，自然取到的次数变大。举个例子：a，b，c 三台机器，权重分别为4，2，1，排位后会是a,a,a,a,b,b,c，每次请求时，从列表中依次取节点，下次请求再取下一个。到末尾时，再从头开始。

但是这样有一个问题：机器分布不够均匀，扎堆出现了....

解决：为解决机器平滑出现的问题，nginx的源码中使用了一种平滑的加权轮询的算法，规则如下：

• 每个节点两个权重，weight和currentWeight，weight永远不变是配置时的值，current不停变化
• 变化规律如下：选择前所有current =weight，选current最大的响应，响应后让它的current-=total

3）结果分析

1）概述

WeightRandom，机器随机被筛选，但是做一组加权值，根据权值不同，选中的概率不同。在这个概念上，可以认为随机是一种等权值的特殊情况。

2）实现

设计思路依然相同，根据权值大小，生成不同数量的节点，节点排队后，随机获取。这里的数据结构主要涉及到随机的读取，所以优选为数组。

与随机相同的是，同样为数组随机筛选，不同在于，随机只是每台机器1个，加权后变为多个。

3）结果分析

1）概述

LeastConnections，即统计当前机器的连接数，选最少的去响应新的请求。前面的算法是站在请求维度，而最小连接数是站在机器的维度。

2）实现

定义一个链接表记录机器的节点id和机器连接数量的计数器。内部采用最小堆做排序处理，响应时取堆顶节点即是最小连接数。

3）结果分析

1）nginx upstream

• ip_hash：即源地址hash算法
• down：表示当前的server暂时不参与负载
• weight：即加权算法，默认为1，weight越大，负载的权重就越大。
• backup：备份机器，只有其它所有的非backup机器down或者忙的时候，再请求backup机器。
• max_fails：最大失败次数，默认值为1，这里为3，也就是最多进行3次尝试
• fail_timeout：超时时间为30秒，默认值是10s。

注意！weight和backup不能和ip_hash关键字一起使用。

2）springcloud ribbon IRule

• RoundRobinRule：轮询
• RandomRule：随机
• AvailabilityFilteringRule：先过滤掉由于多次访问故障而处于断路器跳闸状态的服务，还有并发的连接数量超过阈值的服务，然后对剩余的服务轮询
• WeightedResponseTimeRule：根据平均响应时间计算所有服务的权重，响应时间越快服务权重越大。刚启动时如果统计信息不足，则使用RoundRobinRule策略，等统计信息足够，会切换到该策略
• RetryRule：先按照RoundRobinRule的策略，如果获取服务失败则在指定时间内重试，获取可用的服务
• BestAvailableRule：会先过滤掉由于多次访问故障而处于断路器跳闸状态的服务，然后选择一个并发量最小的服务
• ZoneAvoidanceRule：默认规则，综合判断server所在区域的性能和server的可用性

3）dubbo负载均衡

使用Service注解

• RandomLoadBalance: 随机，这种方式是dubbo默认的负载均衡策略
• RoundRobinLoadBalance：轮询
• LeastActiveLoadBalance：最少活跃次数，dubbo框架自定义了一个Filter，用于计算服务被调用的次数
• ConsistentHashLoadBalance：一致性hash

1）概述

严格来讲这不算是一种加密，而应该叫做信息摘要算法。该算法使用散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。通过数据打乱混合，重新创建一个叫做 散列值

2）常见算法

MD5、SHA（128、256）系列

3）应用

常用于密码存储，或文件指纹校验。

网站用户注册后，密码经过MD5加密后的值，存储进DB。再次登录时，将用户输入的密码按同样的方式加密，与数据库中的密文比对。这样即使数据库被破解，或者开发人员可见，基于MD5的不可逆性，仍然不知道密码是什么。

其次是文件校验场景。例如从某站下载的文件（尤其是大文件，比如系统镜像iso），官方网站都会放置一个签名（可能是MD5，或者SHA），当用户拿到文件后，可以本地执行散列算法与官网签名比对是否一致，来判断文件是否被篡改。如ubuntu20.04的镜像：

4）实现

先添加commons坐标

5）结果分析

1）概述

加密与解密用的都是同一个秘钥，性能比非对称加密高很多。

2）常见算法

常见的对称加密算法有 DES、3DES、AES

DES算法在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密，如信用卡持卡人的PIN的加密传输，IC卡与POS间的双向认证、金融交易数据包的MAC校验等

3DES是DES加密算法的一种模式，是DES的一个更安全的变形。从DES向AES的过渡算法

AES，是下一代的加密算法标准，速度快，安全级别更高。

3）应用

常用于对效率要求较高的实时数据加密通信。

4）实现

以AES为例：

5）结果分析

1）概述

非对称即加密与解密不是同一把钥匙，而是分成公钥和私钥。私钥在个人手里，公钥公开。这一对钥匙一个用于加密，另一个用于解密。使用其中一个加密后，则原始明文只能用对应的另一个密钥解密，即使最初用于加密的密钥也不能用作解密。正是因为这种特性，所以称为非对称加密。

2）常见算法

RSA、ElGamal、背包算法、Rabin（RSA的特例）、迪菲－赫尔曼密钥交换协议中的公钥加密算法、椭圆曲线加密算法（英语：Elliptic Curve Cryptography, ECC）。使用最广泛的是RSA算法（发明者Rivest、Shmir和Adleman姓氏首字母缩写）

3）应用

最常见的，两点：https和数字签名。

严格意义上讲，https并非所有请求都使用非对称。基于性能考虑，https先使用非对称约定一个key，后期使用该key进行对称加密和数据传输。

数字签名则是用于验证报文是否为服务器发出的，用于防伪和认证。过程如下：

签发：

• 服务器外发布公钥，私钥保密
• 服务器对消息M计算摘要（如MD5等公开算法），得到摘要D
• 服务器使用私钥对D进行签名，得到签名S
• 将M和S一起发给客户

验证：

• 客户端对M使用同一摘要算法计算摘要，得到摘要D
• 使用服务器公钥对S进行解密，得到摘要D’
• 如果D和D’相同，那么证明M确实是服务器发出的

4）实现

5）结果分析

负载均衡策略中，我们提到过源地址hash算法，让某些请求固定的落在对应的服务器上。这样可以解决会话信息保留的问题。

同时，标准的hash，如果机器节点数发生变更。那么请求会被重新hash，打破了原始的设计初衷，怎么解决呢？一致性hash上场。

以4台机器为例，一致性hash的算法如下：

• 首先求出各个服务器的哈希值，并将其配置到0～2 32 的圆上
• 然后采用同样的方法求出存储数据的键的哈希值，也映射圆上
• 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上
• 如果到最大值仍然找不到，就取第一个。这就是为啥形象的称之为环

添加节点：

删除节点原理雷同

单调性(Monotonicity)：单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理，又有新的服务器加入到系统中时候，应保证原有的请求可以被映射到原有的或者新的服务器中去，而不会被映射到原来的其它服务器上去。

分散性(Spread)：分布式环境中，客户端请求时可能只知道其中一部分服务器，那么两个客户端看到不同的部分，并且认为自己看到的都是完整的hash环，那么问题来了，相同的key可能被路由到不同服务器上去。以上图为例，加入client1看到的是1,4；client2看到的是2,3；那么2-4之间的key会被俩客户端重复映射到3,4上去。分散性反应的是这种问题的严重程度。

平衡性(Balance)：平衡性是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到尽量分散，但是不能保证每个服务器处理的请求的数量完全相同。这种偏差称为hash倾斜。如果节点的分算法设计不合理，那么平衡性就会收到很大的影响。

优化

增加虚拟节点可以优化hash算法，使得切段和分布更细化。即实际有m台机器，但是扩充n倍，在环上放置m*n个，那么均分后，key的段会分布更细化。

1）场景

敏感词、文字过滤是一个网站必不可少的功能，高效的过滤算法是非常有必要的。针对过滤首先想到的可能是这样：

方案一、使用java里的String contains，逐个遍历敏感词：

方案二、正则表达式：

其实无论采取哪个方法，基本是换汤不换药。都是整体字符匹配，效率值得商榷。

那怎么办呢？DFA算法出场。

2）概述

DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event state=nextstate。

对照到以上案例，查找和停止查找是动作，找没找到是状态，每一步的查找和结果决定下一步要不要继续。DFA算法在敏感词上应用的关键是构建敏感词库，如果我们把以上案例翻译成json表达如下：

查找过程如下：首先把text按字拆分，逐个字查找词库的key，先从“讨”开始，没有就下一个字“厌”，直到“广”，找到就判断isEnd，如果为1，说明匹配成功包含敏感词，如果为0，那就继续匹配“告”，直到isEnd=1为止。匹配策略上，有两种。最小和最大匹配。最小则匹配【广告】，最大则需要匹配到底【广告词】

3）java实现

先加入fastjson坐标，查看敏感词库结构要用到

4）结果分析

topk是一个典型的业务场景，除了最优商品，包括推荐排名、积分排名所有涉及到排名前k的地方都是该算法的应用场合。

topk即得到一个集合后，筛选里面排名前k个数值。问题看似简单，但是里面的数据结构和算法体现着对解决方案性能的思索和深度挖掘。到底有几种方法，这些方案里蕴含的优化思路究竟是怎么样的？这节来讨论

方案一：

全局排序，将集合整体排序后，取出最大的k个值就是需要的结果。

这种方案最糟糕，我只需要排名前k的元素，其他n-k个的顺序我并不关心，但是运算过程中，都得跟着做了没用的排序操作。

方案二：

局部排序，既然全局没必要，那我只取前k个，后面的就没必要理会了。

冒泡排序在排序算法中可以胜任该操作。我们按最大值往上冒泡为例，只要执行k次冒泡，那前k名就可以确定。但是这种方案依然不是最优办法。因为我们需要的是前k名，那至于这k个，谁大谁小并不需要关心，排序依然是个浪费。

方案三：

最小堆，既然没必要排序，那我们就不排序。

先将前k个元素形成一个最小堆，后面的n-k个元素依次与堆顶比较，小则丢弃大则替换堆顶并调整堆。直到n个全部完成为止。最小堆是topk的经典解决方案。

下面就用最小堆实现topk