前言

学习各种算法可以使我们在编程时有更多的选择，根据应用场景选择更合适的算法是成为优秀程序员的必要条件之一。
这本书是我正式入门算法的第一本书，对自己理解算法的原理很有帮助。

算法是计算或者解决问题的步骤。
算法运行的时间用时间复杂度表示。

数据结构

什么是数据结构

「数据结构」决定了数据的顺序和位置关系.数据存储于内存时，决定了数据顺序和位置关系的便是「数据结构」。

链表

「链表」中的数据呈线性排列。链表中添加删除数据比较方便，访问数据只能从第一个数据开始，顺着指针指向一一往下访问「顺序访问」。

「双向链表」把数据的指针设定为两个，让它们分别指向前后数据。缺点：指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。

「循环链表」在链表尾部使用指针，并且让它指向链表头部的数据，将链表变成环形。这就是”循环链表”，也称为”环形链表”。使用这种链表，不仅可以从前往后，还可以从后往前遍历数据，十分方便。

「内存分布」数据一般都是分散存储于内存中的，无须存储在连续的空间内。

「添加&删除元素」改变添加位置前后的指针指向就可以。删除元素改变删除元素前一个元素的指针指向即可。删除的元素本身还存在于内存中，但是无法访问到这个数据，所以没有删除它的必要。下次需要用到删除元素所在的存储空间时，只需要用新数据覆盖掉就可以了。

「运行时间」把链表中的数据量记成 n。访问数据时，我们需要从链表头部开始查找(线性查找)，如果目标数据在链表最后位置的话，需要的时间是O(n)。
添加数据只需要改变两个指针的指向，所以耗费的时间与 n 无关。如果已经达到了添加数据的位置，那么添加操作只需花费*O(1)*的时间，删除数据亦是如此。

数组

「数组」中的数据呈线性排列，访问数据十分简单，添加删除数据比较麻烦。

「内存分布」数据是存储在连续空间内的，所以每个数据的内存地址可以通过数组下标算出，我们也就可以借此直接访问目标数据，称为「随机访问」。

「添加&删除元素」首先需要在数组的末尾确保需要增加的存储空间，为了给新数据腾出位置，需要把已有的数据一个一个移开。最后在空出来的位置上写入 Green，添加数据的操作就完成了。反过来，如果要删除数据，需要把删除的元素后面的数据一个个往空位移，最后再删除多余的空间。

「运行时间」假设数组中有 n 个数据，由于访问数据时使用的是随机访问(通过下标可以计算出内存地址),所以需要的运行时间仅为恒定的O（1）

栈

「栈」中的数据呈线性排列，在这种数据结构中，我们只能访问最新添加的数据。

「内存分布」数据是存储在连续空间内的，具有后进先出的特点。

「添加&删除元素」往栈中添加数据的操作叫作”入栈”(push),从栈中取出数据的操作叫作”出栈”(pop)。操作只能在一端进行，访问数据只能访问到顶端的数据，访问中间的数据的话，需要通过出栈操作将目标数据移到栈顶。

队列

「队列」中的数据呈线性排列。在队列中，添加和删除数据的操作分别是在两端进行的。队列具有”先进先出的特点”。

「添加&删除元素」往队列中添加数据的操作叫作”入队”。从队列中删除数据的操作叫做”出队”。从队列中取出(删除)数据时，是从最下面也就是最早入队的数据开始的。队列不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

哈希表

「哈希表」可以使数据的查询效率得到显著提升。哈希表存储的是由键(Key)和值(value)组成的数据。一般来说，可以把键当成数据的标识符，把值当成数据的内容。

存储数据，尝试把 Joe 存进长度为 5 的数组,使用哈希函数(Hash)计算 Joe 的键，也就是字符串”Joe”的哈希值，得到结果为 4928。将得到的哈希值除以数组的长度 5，求得其余数。这样的运算叫做mod 运算,此处的 mod 运算结果为 3。因此，将 Joe 的数据存进数组的 3 号箱子中。如果 mod 运算后，仍有数据需要存放在 3 号箱子中(哈希冲突)，可使用链表在已有数据的后面继续存储新的数据。这种方法称为"链地址法"。

「解决哈希冲突的方法」
如果数组空间太小，使用哈希表的时候就很容易发生冲突，线性查找的使用频率也会更高。如果数组空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间很重要。
开放地址法:当有冲突发生时，立即算出一个候补地址(数组上的位置)并将数据存进去。如果仍有冲突。继续计算下一个候补地址知道有空地址为止。

堆

「堆」是一种图的树形结构，被用于实现”优先队列”。优先队列是一种数据结构，可以自由添加数据，但取出数据时候要从最小值开始按顺序取出。在堆的树型结构中，各个顶点被称为”结点”(node),数据就存储在这些结点中。

「存储数据」子结点必须大于父结点。最小值被存储在顶端的根结点中。往堆中添加数据时，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余的空间时，就再往下另起一行，把数据加在这一行的最左端。例如添加数字5。如果子结点的数小于父结点，则交换位置。、

「取出数据」取出堆中最上面的数据，因此堆的结构需要调整。将最后的数据6移动到最顶端。如果子结点的数字小于父结点的，就将父结点与其左右两个子节点中较小的一个进行交换。此时父节点6大于右边的5且大于子节点中的3，所以将左边的子节点中的3与父结点进行交换。重复这个操作直到数据都符合规则。这样，从堆中取出数据的操作便完成了。

「时间复杂度」取出最顶端的数据始终最小,时间复杂度为O(1)。取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log₂ⁿ,那么重构树的时间复杂度便为O(logn)

二叉查找树

「二叉查找树」又叫二叉搜索树或二叉排序树，是一种数据结构，采用图的树型结构。

「特点」每个结点的值均大于其左子树上任意一个结点的值，每个结点的值均小于其右子树上任意一个结点的值。

「存储数据」比如添加数字1。首先，从二叉查找树的顶端结点开始寻找添加数字的位置，将想要添加的1与该结点中的值进行比较，小于它则往左移，大于它则往右移。又由于1<9,所以将1往左移。由于1<3,继续往左移，但前面已经没有结点了，所以把1作为新结点添加到左下方。这样1的添加操作便完成了。

再例如添加数字4后的结果如下图。

「删除数据」删除结点28，如果需要删除的结点没有子结点，直接删除该结点即可。

删除结点8，如果需要删除的结点只有一个子结点，那么先删除目标结点，然后再把子结点移动到被删除结点的位置上即可。
删除结点9，如果需要删除的结点有两个子结点，先删除目标结点，然后在被删除结点的左子树中寻找最大结点(4),然后将最大结点移动到被删除节点的位置上，这样一来，就能在满足二叉查找树性质的前提下删除节点了。

「查找结点」查找12,从二叉查找树的顶端结点开始往下查找，把12和结点中的值进行比较，小于该结点的值则往左移，大于则往右移。

「时间复杂度」比较的次数取决于树的高度，结点数为n，比较大小和移动次数最多为log₂ⁿ,时间复杂度为O(logn)。但是，如果树的形状朝单侧纵向延伸，此时时间复杂度为O(n)。

排序

将数字从小到大的顺序排列

冒泡排序

「冒泡排序」重复”从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”。数字像泡泡一样，慢慢从右往左”浮”到序列的顶端。

在序列的最右边放置一个天平，比较天平两边的数字。如果右边的数字较小，则交换位置。完成后，往左移一个位置比较两个数字大小，重复操作直到天平到达序列的最左边为止。一轮操作后，序列中最小的数字就会移动到最左边。第二轮时候移动到左边第二个位置为止，重复此操作，直到最终排序完成。

「总结」假设序列中有n个数，第1轮需要比较n-1次，第2轮需要比较n-2次。因此,总的次数为总的比较次数为（n-1）+（n-2）+…+1≈n²/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
    不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为O（n²/2）。

选择排序

「选择排序」重复”从待排序的序列中寻找最小值,将其与待排序序列中最左边的数字进行交换”,在序列中寻找最小值时使用的是线性查找。

「将数字1~9排序」线性查找在数据中找到最小值1将其与6位置进行交换,最小值1归位。(如果最小值已经在最左端，就不需要任何操作)。在余下的数据中继续寻找最小值，于是找到了2,将其与6交换位置，最小值2归位。重复操作直到最终排序完成。

「总结」选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈O(n²/2)次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n²）。

插入排序

「插入排序」是一种从序列左端开始依次对数据进行排序的算法，排序过程中左侧的数据陆续归位，右侧留下的就是还未被排序的数据。思路是从右侧未排序区域内取出一个数据，将它插入到已排序区域内合适的位置上。
「将数字1~9排序」接下来从待排数字中取出最左边的数字3，将它与左边已归位的数字进行比较。若左边数字更大，就交换这两个数字。因为5>3,所以交换位置，至此第2轮操作结束。第3轮取出待排序区域中最左边的数字4，将它与左边的数字5比较，由于5>4,所以交换位置。交换后再把4和左边的3进行比较，发现3<4至此操作结束。重复此操作直至排序完成。

「时间复杂度」如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达序列的最左边为止。在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度为O（n²）。

堆排序

「堆排序」首先在堆中存储所有的数据，并按降序来构建堆。为了排序，需要再从堆中把数据一个个取出来。

首先取出根结点数字7后，放到数组重新构造堆。重复此操作即可。

归并排序

「归并排序」会把序列分成长度相同的的两个子序列，当无法继续分时(也就是每个子序列中只有一个数据时),就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

把6和4合并，合并后的顺序为[4,6],接下来把3和7合并,合并后的顺序为[3,7]。接下来我们看看如何合并[4,6]和[3,7]。合并这种含有多个数字的子序列时，要先比较首位数字，在移动较小数字。因为4>3,所以移动3。同样地，再比较序列中剩下的首位数字,因为4<7,所以移动4。

由于6<7,所以移动6,最后移动剩下的7。递归执行上面操作,直到所有的数字都合为一个整体。

「时间复杂度」无论哪一行都是n个数据,所以每行的运行时间都为O（n）。而将长度为n的序列对半分割直到只有一个数据为止时,可以分成log₂n行,因此,总共有log₂n行。也就是说,总的运行时间为O（nlogn）。

快速排序

「快速排序」在序列中随机选择一个基准值,然后将除了基准值以外的数分为”比基准值小的数”和”比基准值大的数”这两个类别。如下?

[比基准值小的数] 基准值 [比基准值大的数]

接着,对两个”[]”中的数据进行排序之后，整体的排序便完成了，对”[]”里面的数据进行排序同样也会使用快速排序。

随机选择基准值,为4。首先,比较3和基准值4,因为3<4,所以将3往左移动。接下来比较5和基准值4,因为5>4,所以将5往右移。以此类推得到下面的排序?。

分别对左边和右边的数据进行排序后,就能得到整体的排序。
「时间复杂度为O(logn)」

数组的查找

线性查找

「线性查找」是一种在数组中查找数据的算法。

「查找数字6」首先,检查数组中最左边的数字,将其与6进行比较。如果结果一致,查找便结束,不一致则向右检查下一个数字直到找到数字6为止。

「时间复杂度」线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为O（n）。

二分查找

「二分查找」它只能查找已经排好序的数据.二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据范围是在数组的左边还是右边。因此,比较一次就可以把查找范围缩小一半。重复执行该操作就可以得到目标数据或得出目标数据不存在的结论。

「查找数字6」首先找到数组中间数字5，将5和要查找的6进行比较，可以得知6在5的右边，将不需要的数字移出查找范围。在剩下的数组中找到中间的数字，此处为7。比较7和6，把不需要的数字移出查找范围，可以得知6在7的左边。然后再在剩下的数组中找到中间的数字，此处为6。6=6成功找到目标数字。
「时间复杂度」数据量为n的数组，将其长度减半log2n次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作log2n次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为O（logn）。
二分查找的时间复杂度为O（logn），与线性查找的O（n）相比速度上得到了指数倍提高（x=log₂n，则n=2^x)。

图的搜索

「图」由顶点和连接每对顶点的边所构成的图形就是图，图表现各种关系。

「加权图」给边加上一个值，这个值叫作边的”权重”或者”权”。加了权的图叫作“加权图”。没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的”连接程度”。
「有向图」当我们想在路线图中表示该路线只能单向行驶时，就可以给边加上箭头，而这样的图就叫作”有向图”。比如网页的链接是有方向性的，用有向图来表示会很方便。边上没有箭头的图是“无向图”。

广度优先搜索

「广度优先搜索」是一种对图进行搜索的算法。假设我们一开始位于某个顶点(即起点)，此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点(终点).在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的的顶点开始搜索。

「G为终点」将A可以直达的三个顶点B,C,D设为下一步的候补顶点。从候补顶点中选出一个顶点。优先选择最早成为候补的那个顶点(候补顶点是用”先入先出”的方式来管理的，因此可以使用”队列”这个数据结构。)，如果多个顶点同时成为候补，随机选择其中一个。

接下来将B直达的两个顶点E和F设为候补顶点。此时，最早成为候补顶点的是C和D，我们选择了左边的顶点C。移动到选中的顶点C上，将C直达的顶点H设为候补顶点。重复上述操作直到到达终点，或者所有的顶点都被遍历为止。这个示例中的搜索顺序为A、B、C、D、E、F、H、I、J、K。完成了从A到I的搜索，现在在顶点J处。到达终点G，搜索结束。
「补充」为了方便说明，上面用的是没有闭环的图(树)。

深度优先搜索

「深度优先搜索」会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

A为起点，G为终点。一开始我们在起点A上。将可以从A直达的三个顶点B、C、D设为下一步的候补点。从候补点中选出一个顶点。优先选择最新成为候补的点(此处候补顶点是用”后入先出”的方式来管理的，因此我们可以用栈这个数据结构)，如果几个顶点同时成为候补，那我们可以从中随意选择一个B。移动到选中的顶点B，此时我们在B上，将可以从B直达的两个顶点E和F设为候补顶点。我们选择左边的顶点E，移动到选中的顶点E上，将E直达的顶点K设为候补顶点。重复上述操作直到到达终点，或者所有顶点都被遍历为止。这个示例的搜索顺序为A、B、E、K、F、C、H。

「差异」广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

贝尔曼-福特算法

贝尔曼-福特算法的名称取自其创始人理查德·贝尔曼和莱斯特·福特的名字。贝尔曼也因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。

「贝尔曼-福特算法」是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

「A–>G」首先设置各个顶点的初始权重：起点为0，其他顶点为无穷大(∞)。这个权重表示的是从A到该顶点的最短路径的的暂定距离。随着计算往下进行，这个值会变得越来越小，最终收敛到正确的数值。
从所有的边中选出一条边，此处选择了连接A-B的边。然后，分别计算这条边从一端到另一端的权重，计算方法是“顶点原本的权重+边的权重”。只要按顺序分别计算两个方向的权重即可，从哪一端开始都没有问题。此处我们选择按顶点权重从小到大的方向开始计算。
A的权重小于B，因此先计算从A到B的权重。A的权重是0，边A-B的权重是9，因此A到B的权重是0+9=9。
如果计算结果小于顶点的值，就更新这个值。顶点B的权重是无穷大，比9大，所以把它更新为9。更新时需要记录计算的是从哪个顶点到该顶点的路径。
接下来计算从B到A的权重。B的权重为9，从B到A的权重便为9+9=18。与顶点A现在的值0进行比较，因为现在的值更小，所以不更新。

对所有的边都执行同样的操作。在执行顺序上没有特定要求，此处我们选择从靠近左侧的边开始计算。先选出一条边数值更新了，顶点C的权重变成了2。同样地，再选出一条边权重又更新了。此时就能看出，从顶点A前往顶点B时，比起从A直达B，在C中转一次的权重更小。接着对所有的边进行更新操作。

更新边B-D和边B-E。

更新完所有的边后，第1轮更新就结束了。接着，重复对所有边的更新操作，直到权重不能被更新为止。
第2轮更新也结束了。顶点B的权重从8变成了7，顶点E的权重从9变成了8。接着，再执行一次更新操作。

第3轮更新结束，所有顶点的权重都不再更新，操作到此为止。算法的搜索流程也就此结束，我们找到了从起点到其余各个顶点的最短路径。

根据搜索结果可知，从起点A到终点G的最短路径是A-C-D-F-G，权重为14。

「时间复杂度」将图的顶点数设为n、边数设为m，我们来思考一下贝尔曼-福特算法的时间复杂度是多少。该算法经过n轮更新操作后就会停止，而在每轮更新操作中都需要对各个边进行1次确认，因此1轮更新所花费的时间就是O（m），整体的时间复杂度就是O（nm）。

狄克斯特拉算法

「狄克斯特拉算法(Dijkstra)」 与上面文章中的贝尔曼-福特算法类似。

「A–>G」首先设置各个顶点的初始权重:起点为0，其他顶点勿穷大(∞)。从A出发寻找可以从目前所在的顶点直达且尚未被搜索过的顶点，此处为顶点B和顶点C，将它们设为下一步的候补顶点。

计算各个候补顶点的权重。计算方法是“目前所在顶点的权重+目前所在顶点到候补顶点的权重”。比如起点A的权重是0，那么顶点B的权重就是0+2=2。用同样的方法计算顶点C，结果就是0+5=5。

如果计算结果小于候补顶点的值，就更新这个值。顶点B和顶点C现在的权重都是无穷大，大于计算结果，所以更新这两个顶点的值。
从候补顶点中选出权重最小的顶点。此处B的权重最小，那么路径A-B就是从起点A到顶点B的最短路径。因为如果要走别的路径，那么必定会经过顶点C，其权重也就必定会高于A-B这条路径。确定了最短路径，移动到顶点B。

将可以从顶点B直达的顶点设为新的候补顶点，于是顶点D和顶点E也成为了候补。目前有三个候补顶点C、D、E。

用相同的方法计算各个候补顶点的权重。从B到C的权重为2+6=8，比C当前的权重5大，因此不更新这个值。更新了剩下的顶点D和E。

从候补顶点中选出权重最小的顶点。此处D的权重最小，那么路径A-B-D就是从起点A到顶点D的最短路径。A-B-D这条路径是通过逐步从候补顶点中选择权重最小的顶点来得到的，所以如果经过其他顶点到达D，其权重必定会大于这条路径。

要重复执行同样的操作直到到达终点G为止。移动到顶点D后算出了E的权重，然而并不需要更新它（因为3+4=7）。现在，两个候补顶点C和E的权重都为5，所以选择哪一个都可以。此处我们选择了C，于是起点A到顶点C的最短路径便确定了。

移动到C后，顶点F成为了新的候补顶点，且F的权重被更新为13。此时的候补顶点中，E为5、F为13，所以我们选择了权重更小的E，起点A到顶点E的最短路径也就确定了下来。

移动到F。顶点G的权重计算结果为13+7=20，比现在的值14要大，因此不更新它。由于候补顶点只剩G了，所以选择G，并确定了起点A到顶点G的最短路径。到达终点G，搜索结束。

「解说」比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步选择顶点的操作，这使得它在求最短路径上更为高效。将图的顶点数设为n、边数设为m，那么如果事先不进行任何处理，该算法的时间复杂度就是O（n²）。不过，如果对数据结构进行优化，那么时间复杂度就会变为O（m+nlogn）。

A*算法

「A-Star」算法由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A* 就会预先估算一个值，并利用这个值来省去一些无用的计算。
「A-Star」暂时还未理解步骤，待更新这部分内容。游戏中会用到，但消耗很大计算资源，需要和其他算法配合使用。

安全算法

安全与算法

「源由」互联网数据传输过程中会被某些恶意用户盗用。数据传输时的问题。

• 窃听: A向B发送的消息可能会在传输途中被X偷看。加密技术
• 假冒: A以为向B发送了消息，然而B有可能是X假冒的；反过来，B以为从A哪里收到了消息，然而A也有可能是X冒充的。消息认证码或数字签名
• 篡改: 即便B确实收到了A发送的消息，但有可能消息的内容在传途中就被X更改了。 消息认证码或数字签名
• 事后否认: B从A那里收到了消息，但作为消息发送者的A可能对B抱有恶意，并在事后声称“这不是我发送的消息”。这种情况会导致互联网上的商业交易或合同签署无法成立。这种行为便是“事后否认”。 数字签名

加密的基础知识

「密文」我们给想要保密的数据加密。加密后的数据被称为“密文”。

「解密」A把密文发送给B，B收到密文后，需要解除加密才能得到原本的数据。把密文恢复为原本数据的操作就叫作“解密”。像这样对数据进行加密，就不用担心会被人窃听了。

「加密的具体操作」

• 首先，计算机会用由0和1这两个数字表示的二进制来管理所有数据。数据虽然有文本、音频、图像等不同的形式，但是在计算机中都是用二进制来表示的。
• 对计算机来说，数据就是一串有意义的数字罗列。密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列。
• 在加密运算上会用到“密钥”。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程。
• 反过来，解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程。

哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。把哈希函数想像成搅拌数据的搅拌机就很容易理解了。输出的无规律数值就是“哈希值”。哈希值虽然是数字，但多用十六进制来表示。

• 输出的哈希值数据长度不变
• 如果输入的数据相同，那么输出的哈希值也必定相同。
• 即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。
• 即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
• 不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同。
• 求哈希值的计算相对容易。

「解说」哈希函数的算法中具有代表性的是MD5、SHA-1和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用。

「应用」将用户输入的密码保存到服务器时需要用到哈希函数。因此需要算出密码的哈希值，并只存储哈希值。当用户输入密码时，先算出该输入密码的哈希值，再把它和服务器中的哈希值进行比对。

共享密钥加密

「加密数据」方法可以分为两种：加密和解密都使用相同密钥的“共享密钥加密(对称加密)”和分别使用不同密钥的“公开密钥加密”。

「流程」A使用密钥加密数据,A将密文发送给B,B收到密文后，使用相同的密钥对其进行解密。这样，B就取得了原本的数据。只要是加密好的数据，就算被第三者恶意窃听也无须担心。

「存在的问题」密钥有被第三者窃听的风险,这样一来，X可使用密钥对密文进行解密。

「解决措施」需要找到可以把密钥安全送出的方法，这就是“密钥分配问题”。可以使用“密钥交换协议”和“公开密钥加密”两种方法。

「算法」实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛。

公开密钥加密

「公开密钥加密」是加密和解密使用不同密钥的一种加密方法(非对称加密)。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。

「流程」假设A准备通过互联网向B发送数据。首先，需要由接收方B来生成公开密钥和私有密钥,然后把公开密钥发送给A,A使用B发来的公开密钥加密数据.A将密文发送给B, B再使用私有密钥对密文进行解密。

「存在的问题」公开密钥的可靠性会出现问题，就是因为A无法判断收到的公开密钥是否来自B。要想解决这个问题，就要用到之后会讲到的“数字证书”。公开密钥加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密”。

「算法」实现公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法。

混合加密

「混合加密」用处理速度较快的共享密钥加密对数据进行加密,不过，加密时使用的密钥，则需要用没有密钥分配问题的公开密钥加密进行处理。

「优势及应用」混合加密在安全性和处理速度上都有优势。能够为网络提供通信安全的SSL协议也应用了混合加密方法。SSL是Secure SocketsLayer（安全套接层）的简写，该协议经过版本升级后，现在已正式命名为TLS（Transport Layer Security，传输层安全）。但是，SSL这个名字在人们心中已经根深蒂固，因此该协议现在也常被称为SSL协议或者SSL /TLS协议。

迪菲-赫尔曼密钥交换

「迪菲-赫尔曼密钥交换」是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。

消息认证码

「消息认证码」可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

「流程」A生成了一个用于制作消息认证码的密钥，然后使用安全的方法将密钥发送给了B。接下来，A使用密文和密钥生成一个值。此处生成的是7f05。这个由密钥和密文生成的值就是消息认证码，以下简称为MAC（Message AuthenticationCode）。A将MAC（7f05）和密文发送给B。和A一样，B也需要使用密文和密钥来生成MAC。经过对比，B可以确认自己计算出来的7f05和A发来的7f05一致。

「算法」计算MAC的算法有HMAC、OMAC、CMAC等。目前，HMAC的应用最为广泛。

「存在的问题」在使用消息认证码的过程中，AB双方都可以对消息进行加密并且算出MAC。也就是说，我们无法证明原本的消息是A生成的还是B生成的。这个问题可以用“数字签名”来解决。

数字签名

「数字签名」不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。

「流程」假设A要向B发送消息,在发送前A给消息加上数字签名。数字签名只能由A生成,只要发送的消息上有A的数字签名，就能确定消息的发送者就是A。B可以验证数字签名的正确性，但无法生成数字签名。接下来看一看数字签名具体是怎样生成的吧。数字签名的生成使用的是公开密钥加密。

• 首先由A准备好需要发送的消息、私有密钥和公开密钥。由消息的发送者来准备这两个密钥，这一点与公开密钥加密有所不同。
• A将公开密钥发送给B,A使用私有密钥加密消息。加密后的消息就是数字签名,然后A将消息和签名都发送给了B
• B使用公开密钥对密文（签名）进行解密，B对解密后的消息进行确认，看它是否和收到的消息一致。流程到此结束

「说明」公开密钥加密的加密和解密都比较耗时。为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用。

「存在的问题」虽然使用数字签名后B会相信消息的发送者就是A，但实际上也有可能是X冒充了A。其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁。收到的公开密钥上也没有任何制作者的信息。因此，公开密钥有可能是由某个冒充A的人生成的。

「解决措施」数字证书

数字证书

「回顾」“公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。

「数字证书流程」

• A持有公开密钥PA和私有密钥SA，现在想要将公开密钥PA发送给B。
• A首先需要向认证中心（Certification Authority, CA）申请发行证书，证明公开密钥PA确实由自己生成。
• 认证中心里保管着他们自己准备的公开密钥PC和私有密钥SC。
• A将公开密钥PA和包含邮箱信息的个人资料发送给认证中心,认证中心对收到的资料进行确认，判断其是否为A本人的资料。确认完毕后，认证中心使用自己的私有密钥SC，根据A的资料生成数字签名。
• 认证中心将生成的数字签名和资料放进同一个文件中,然后，把这个文件发送给A,这个文件就是A的数字证书。
• A将作为公开密钥的数字证书发送给了B,B收到数字证书后，确认证书里的邮件地址确实是A的地址。接着，B获取了认证中心的公开密钥。
• B对证书内的签名进行验证，判断它是否为认证中心给出的签名。证书中的签名只能用认证中心的公开密钥PC进行验证。如果验证结果没有异常，就能说明这份证书的确由认证中心发行。
• 确认了证书是由认证中心发行的，且邮件地址就是A的之后，B从证书中取出A的公开密钥PA。这样，公开密钥便从A传到了B。

「补充」到目前为止，我们了解的都是个人之间交付公开密钥的例子，其实在网站之间的通信中同样也要用到数字证书。只要能收到来自网站的含有公开密钥的证书，就能确认该网站未被第三者冒充。此处的证书叫作“服务器证书”，同样由认证中心发行。个人的证书会与他的邮箱信息相对应，而服务器证书与域名信息相对应。因此，我们还可以确认网站域名和存储网站本身内容的服务器是由同一个组织来管理的。数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施”（Public Key Infrastructure, PKI）。

聚类

「聚类」在输入为多个数据时，将“相似”的数据分为一组的操作,1个组就叫作1个“簇”。

「如何定义相似」定义数据间的差距,使用用最具代表性的聚类算法“k-means算法”。该算法可以把数据按要求分为k个簇。

「k-means算法」它可以根据事先给定的簇的数量进行聚类。

「流程」

• 首先准备好需要聚类的数据，然后决定簇的数量。本例中我们将簇的数量定为3。此处用点表示数据，用两点间的直线距离表示数据间的差距。
• 随机选择3个点作为簇的中心点。计算各个数据分别和3个中心点中的哪一个点距离最近。
• 将数据分到相应的簇中。这样，3个簇的聚类就完成了。
• 计算各个簇中数据的重心，然后将簇的中心点移动到这个位置。
• 重新计算距离最近的簇的中心点，并将数据分到相应的簇中。
• 重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置”这两个操作，直到中心点不再发生变化为止。操作到此结束，聚类也就完成了

「特点」k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明。

「层次聚类算法」不需要事先设定簇的数量,一开始每个数据都自成一类。也就是说，有n个数据就会形成n个簇。然后重复执行“将距离最近的两个簇合并为一个”的操作n-1次。每执行1次，簇就会减少1个。执行n-1次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的1个结果就好。合并簇的时候，为了找出“距离最近的两个簇”，需要先对簇之间的距离进行定义。根据定义方法不同，会有“最短距离法”“最长距离法”“中间距离法”等多种算法。

其他算法

「欧几里得算法」（又称辗转相除法）用于计算两个数的最大公约数。

「流程」首先用较大的数字去除以较小的数字，求出余数。也就是对两个数字进行mod运算。

• A mod B就是算出A除以B后的余数C。例:1112 mod 695 =417，设A = 1112，B = 695。接下来再用被除数695和余数417进行mod运算。结果为278。
• 接下来再用除数695和余数417进行mod运算。结果为278。继续重复同样的操作，对417和278进行mod运算，结果为139。对278和139进行mod运算，结果为0。也就是说，278可以被139整除。
• 余数为0时，最后一次运算中的被除数139就是1112和695的最大公约数。

素性测试

「素性测试」判断一个自然数是否为素数的测试。素数（prime number）就是只能被1和其自身整除，且大于1的自然数。

「费马测试」被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。

「素数的性质(案例用素数5)」

• 对于比5小的数，分别计算它们的5次方

• 再对结果分别进行mod运算，求得它们除以5后的余数

• 观察原本的数和余数，发现两者一致。由此，可以推导出关于素数5，以上公式成立。

• 费马测试数字113是素数

「补充知识」如果p是素数，那么所有比p小的数n都满足n^p mod p=n这个条件。但反过来，即使所有n都满足条件，p也有可能不是素数。因为在极低概率下会出现所有n都满足条件的合数（非素数的自然数）。
比如数字561可以表示为3×11×17，所以561是合数，不是素数。然而比561小的所有数字都满足上述条件。这样的合数就叫作“卡迈克尔数”（Carmichael numbers），也叫“绝对伪素数”。

网页排名

「网页排名」（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。网页排名就是利用网页之间的链接结构计算出网页价值的算法。

汉诺塔

「汉诺塔」是一种移动圆盘的游戏，同时也是一个简单易懂的递归算法应用示例。

「原理」在算法描述中调用算法自身的方法就叫作“递归”。递归被运用到各种各样的算法中，这些算法统称为“递归算法”。
「补充说明」假设解决有n个圆盘的汉诺塔问题时需要的时间为T（n）。只有1个圆盘时只需1步就能完成，所以T（1）=1。圆盘数为n时，把上面的n-1个圆盘从A移到B上需要T（n-1），再把最大的圆盘移到C上需要1步，最后把B上的n-1个圆盘移到C上需要T（n-1），因此T（n）=2T（n-1）+1。
上面的公式即为T（n）=2ⁿ-1，这便是解决这个问题所需要的最短时间。