###1.1 什么是算法
算法和程序有些相似，区别在于程序是以计算机能够理解的编程语言编写而成的，可以在计算机上运行，而算法是以人类能够理解的方式描述的，用于编写程序之前。不过，在这个过程中到哪里为止是算法、从哪里开始是程序，并没有明确的界限。就算使用同一个算法，编程语言不同，写出来的程序也不同；即便使用相同的编程语言，写程序的人不同，那么写出来的程序也是不同的。
###1.2 时间复杂度
我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。
####如何求得运行时间呢？
如何测算不同输入所导致的运行时间的变化程度呢？最为现实的方法就是在计算机上运行一下程序，测试其实际花费的时间。但是，就算使用同样的算法，花费的时间也会根据所用计算机的不同而产生偏差，十分不便。
所以在这里，我们使用“步数”来描述运行时间。“1步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。
作为示例，现在我们试着从理论层面求出选择排序的运行时间。选择排序的步骤如下。
- ① 从数列中寻找最小值
- ② 将最小值和数列最左边的数字进行交换，排序结束。回到①
如果数列中有n个数字，那么①中“寻找最小值”的步骤只需确认n个数字即可。这里，将“确认1个数字的大小”作为操作的基本单位，需要的时间设为Tc，那么步骤①的运行时间就是n×Tc。
接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为Ts。那么，①和②总共重复n次，每经过“1轮”，需要查找的数字就减少1个，因此总的运行时间如下。
虽说只剩最后1个数字的时候就不需要确认了，但是方便起见还是把对它的确认和交换时间计算在内比较好。
####运行时间的表示方法
我们已经求得了运行时间，但其实这个结果还可以简化。Tc和Ts都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度n，所以接下来考虑n变大的情况。
n越大，上式中的n2也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是n2。所以，我们删掉其他部分，将结果表示成下式右边的形式。
通过这种表示方法，我们就能大致了解到排序算法的运行时间与输入数据量n的平方成正比。
同样地，假设某个算法的运行时间如下。
那么，这个结果就可以用O（n3）来表示。
如果运行时间为
这个结果就可以用O（nlogn）来表示。
O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”
比如，当我们知道选择排序的时间复杂度为O（n2）、快速排序的时间复杂度为O（nlogn）时，很快就能判断出快速排序的运算更为高速。二者的运行时间根据输入n产生的变化程度也一目了然。
链表中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。
链表的特点：
- 每个数据都有1个“指针”，它指向下一个数据的内存地址。
- 在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。
- 因为数据都是分散存储的，所以如果想要访问数据，只能从第1个数据开始，顺着指针的指向一一往下访问（这便是顺序访问）。
- 如果想要添加数据，只需要改变添加位置前后的指针指向就可以
- 数据的删除也一样，只要改变指针的指向就可以
操作复杂度：
访问数据时，我们需要从链表头部开始查找（线性查找），如果目标数据在链表最后的话，需要的时间就是O（n）。
另外，添加数据只需要更改两个指针的指向，所以耗费的时间与n无关。如果已经到达了添加数据的位置，那么添加操作只需花费O（1）的时间。删除数据同样也只需O（1）的时间。
循环链表：
在链表尾部使用指针，并且让它指向链表头部的数据，将链表变成环形。循环链表没有头和尾的概念。想要保存数量固定的最新数据时通常会使用这种链表。
双向链表：
可以把链表的指针设定为两个，并且让它们分别指向前后数据，这就是“双向链表”。使用这种链表，不仅可以从前往后，还可以从后往前遍历数据，十分方便。双向链表存在两个缺点：一是指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。
数组也是数据呈线性排列的一种数据结构。与链表不同，在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。
数组的特点：
- 数据按顺序存储在内存的连续空间内。
- 由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”）。
- 如果想在任意位置上添加或者删除数据，数组的操作就要比链表复杂多了。需要逐一将数据后移（新增）或者前移（删除）。
操作复杂度：
这里讲解一下对数组操作所花费的运行时间。假设数组中有n个数据，由于访问数据时使用的是随机访问（通过下标可计算出内存地址），所以需要的运行时间仅为恒定的O（1）。
想要向数组中添加新数据时，必须把目标位置后面的数据一个个移开。所以，如果在数组头部添加数据，就需要O（n）的时间。删除操作同理。
在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂。
栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。
像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为Last In First Out，简称LIFO。
与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。
栈只能在一端操作这一点看起来似乎十分不便，但在只需要访问最新数据时，使用它就比较方便了。比如，规定（AB（C（DE）F）（G（（H）I J）K））这一串字符中括号的处理方式如下：首先从左边开始读取字符，读到左括号就将其入栈，读到右括号就将栈顶的左括号出栈。此时，出栈的左括号便与当前读取的右括号相匹配。通过这种处理方式，我们就能得知配对括号的具体位置。
与前面提到的数据结构相同，队列中的数据也呈线性排列。虽然与栈有些相似，但队列中添加和删除数据的操作分别是在两端进行的。就和“队列”这个名字一样，把它想象成排成一队的人更容易理解。在队列中，处理总是从第一名开始往后进行，而新来的人只能排在队尾。
从队列中取出（删除）数据时，是从最下面，也就是最早入队的数据开始的。
像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为First In FirstOut，简称FIFO。
与栈类似，队列中可以操作数据的位置也有一定的限制。在栈中，数据的添加和删除都在同一端进行，而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。
哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。(关键字就是所要存储的数据，存储位置相当于数组的索引)
在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。
如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要。
在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。
时间复杂度：
- 无限空间时，时间为O(1)
- 1的空间时，时间为O(n)
堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。
堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。
在堆中存储数据时必须遵守这样一条规则：**子结点必定大于父结点。**因此，最小值被存储在顶端的根结点中。
往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置。
从堆中取出数据时，取出的是最上面的数据。这样，堆中就能始终保持最上面的数据最小。将最后的数据移动到最顶端，如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换。直到满足堆的要求。
时间复杂度：
堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）。取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）。
添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O（logn）。
如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。
####二叉树的定义
二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构。
二叉查找树有两个性质：
- 第一个是每个结点的值均大于其左子树上任意一个结点的值。
- 第二个是每个结点的值均小于其右子树上任意一个结点的值。
查找数字：二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。
新增数字：从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的数字与该结点中的值进行比较，小于它则往左移，大于它则往右移。
删除数字：如果需要删除的结点没有子结点，直接删掉该结点即可。如果需要删除的结点只有一个子结点，那么先删掉目标结点，然后把子结点移到被删除结点的位置上即可。
时间复杂度：
我们可以把二叉查找树当作是二分查找算法思想的树形结构体现。比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树遍历有以下方式。
-
前序遍历：先访问根节点，然后前序遍历左子树，在前序遍历后子树；
/** * 前序遍历二叉树。具体过程： * 先访问根节点 * 再序遍历左子树 * 最后序遍历右子树 * * @param start */ public void preOrder(TreeNode start) { if (null == start) { return; } // 1、先遍历当前节点 start.displayNode(); // 2、遍历左子树 preOrder(start.left); // 3、遍历右子树 preOrder(start.right); }
-
中序遍历：中序遍历根节点的左子树，然后是访问根节点，最后遍历右子树；
/** * 中序遍历。步骤： * 先中序遍历左子树 * 再访问根节点 * 最后中序遍历右子树 */ public void inOrder(TreeNode start) { if (null == start) { return; } // 1、遍历左子树 preOrder(start.left); // 2、遍历当前节点 start.displayNode(); // 3、遍历右子树 preOrder(start.right); }
-
后序遍历：从左到右先叶子后节点的方式遍历左右子树，最后访问根节点；
/** * 后续遍历 * 先后序遍历左子树 * 再后序遍历右子树 * 最后访问根节点 */ public void posOrder(TreeNode start) { if (null == start) { return; } // 1、遍历左子树 preOrder(start.left); // 2、遍历右子树 preOrder(start.right); // 3、遍历当前节点 start.displayNode(); }
-
层序遍历：从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问。
/** * 层序遍历：逐层遍历树。 * 首先申请一个新的队列，记为queue； * 将头结点head压入queue中； * 每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队； * 重复步骤3，直到queue为空。 * @param start */ public void levelOrder(TreeNode start) { if (null == start) { return; } Queue<TreeNode> queue = new ArrayBlockingQueue<TreeNode>(15); queue.add(start); // 循环遍历整颗树 while(!queue.isEmpty()) { // 得到当前层级的节点，并输出 TreeNode node = queue.poll(); node.displayNode(); // 将当前节点的左右子节点加入队列中进行遍历 if (null != node.left) { queue.add(node.left); } if (null != node.right) { queue.add(node.right); } } }
通常有如下排序算法：
- 插入排序
- 希尔排序（面试几率较高）
- 冒泡排序
- 选择排序
- 快速排序（面试几率较高）
- 堆排序（面试几率较高）
- 归并排序
排序算法复杂度如下：
###3.1 冒泡排序
####算法描述
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。
可以从序列左边开始，也可以从序列右边开始，每遍历一趟获取一个最大值或者最小值，重复n-1次后得到有序序列。
比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位 ...... 因此需要n-1趟；
####场景
简单，适用于n比较小的场景。否则比较和交换的时间复杂度都很高
为了便于自己记住这些算法的逻辑，我给每个算法都找了一些场景，可能不是特别合理，只是为了记住算法的核心逻辑。
那冒泡算法的场景是什么呢？刚上小学时，体育课上，老师会让大家排队，我的体育老师（从他自己的角度）一般就是让大家从左往右，按照从低到高的顺序来排列。第一堂课时，大家站的非常混乱。
体育老师说，大家对比一下你左手边的人（从我们的角度），没你高的你们就换个位置。于是大家开始跟自己左手边的人比较，不一会就变得高矮有序，最高的人到了最左边，最爱的人没得换就留在了最右边。
这里的左右大家要区分好，老师的角度和我们自己的角度是不一样的。
这个场景我个人觉得个冒泡排序很像，只不过冒泡排序是按照一轮一轮有节奏的进行。
时间复杂度: 第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为（n-1）+（n-2）+…+1≈n2/2，所以时间复杂度为
。 空间复杂度: 冒泡排序只需要定义一个temp变量，用于每次两两交换位置的临时存储，所以不管n多大，都只用一个temp变量的位置，空间复杂度为
稳定性：稳定。相同的值位置不会变。
####伪代码
// 从头向后遍历
// i代表需要遍历的趟数
for (i = 0; i < n; i++) {
// j代表每趟遍历中，需要比较的相邻数据下标
for (j = 0; j < n - (i + 1); j++) {
// 如果前一个比后一个大，则交换位置
if (arr[j] > arr[j+1]) {
switch(arr[j], arr[j + 1])
}
}
}// 从后向前遍历
// i代表需要遍历的趟数
for (i = 0; i < n; i++) {
// j代表每趟遍历中，需要比较的相邻数据下标
for (j = n-1; j > i; j--) {
// 如果前一个比后一个大，则交换位置
if (arr[j] < arr[j - 1]) {
switch(arr[j], arr[j - 1])
}
}
}package com.p.seven.algorithm.sort;
/**
* 冒泡排序
*/
public class BubbleSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
sort();
print();
}
private static void sort() {
int n = oriArray.length;
// i代表需要遍历的趟数
for (int i = 0; i < n; i++) {
// 如果前一个比后一个大，则交换位置
for (int j = 0; j < n - 1 - i; j++) {
int temp = 0;
if (oriArray[j] > oriArray[j + 1]) {
temp = oriArray[j];
oriArray[j] = oriArray[j + 1];
oriArray[j + 1] = temp;
}
}
}
}
private static void print() {
for (int i = 0; i < oriArray.length; i++ ) {
System.out.print(oriArray[i]+ ", ");
}
}
}选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。
适用大多数场景
到了二年级，换了个体育老师，这个体育老师比较负责任。
他说让大家站好，然后开始找，对比了一圈发现小A最高，他直接对小A说你站到最右边。
然后又开始找，又发现小C最高，让小C站到小A的右手边。
......
找了n个过后，轮到小E，但是小E这时已经在最右边，而且整个队伍已经有序了。
这就是选择排序，每轮比较找出最大或者最小值，放到右边或者左边，再找出第二大.....以此类推。
时间复杂度：O(n²)。选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。
空间复杂度：O(1)。同冒泡，每轮只需要一个附加程序单元用于交换
稳定性：选择排序是不稳定的排序算法，因为无法保证值相等的元素的相对位置不变，例如 [3, 4, 3, 1, 5]这个数组，第一次交换，第一个3和1交换位置，此时原来两个3的相对位置发生了变化。
// i代表当前遍历找到最小值时要交换的位置
for (i = 0; i < n; i++) {
// j代表每趟遍历中，需要比较的相邻数据下标
int minIdx = i;
for (j = i + 1; j < n; j++) {
// 如果前一个比后一个大，则标记为最小下标
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 最后交换下标位置
swap(i, minIdx);
}package com.p.seven.algorithm.sort;
/**
* 选择排序
*/
public class SelectSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
sort();
print();
}
private static void sort() {
int n = oriArray.length;
for (int i = 0; i < n; i ++ ) {
// 先找出当前最小值的位置
int minIdx = i;
for (int j = i+1; j< n;j++) {
if (oriArray[j] < oriArray[minIdx]) {
minIdx = j;
}
}
// 交换左边元素和最小值的位置
int temp = oriArray[i];
oriArray[i] = oriArray[minIdx];
oriArray[minIdx] = temp;
}
}
private static void print() {
for (int i = 0; i < oriArray.length; i++ ) {
System.out.print(oriArray[i]+ ", ");
}
}
}###3.3 插入排序
插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置
适用于已有部分数据有序的情况，有序部分越大越好
有一天，A班同学按原来的规定排好队等老师上体育课，老师过来的时候带着B班所有同学一起来了。
老实说，B班数学老师跟我换了一节体育课，准备明天两节课连起来做数学考试，所以今天要两个班一起上课了。那么首先还是先站好队吧。
老师接着说，B班的人，你们一个一个按顺序在A班的队伍里找位置，找到右边比你矮，左边比你高的人，你就站他们中间。一个一个来。
......
过来一会，最后一个人也站好了，A、B两班合成了一个有序的队伍。
插入排序适合大部分有序的队列，效率较高。实际操作时，我们也会假定一部分队列已经有序，但不会是一半，通常我们是假定第一个数字的队列有序，然后依次进行比较。
时间复杂度：
空间复杂度：在直接插入排序中只使用了i,j,tmp这三个辅助元素，与问题规模无关，空间复杂度为
稳定性：相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序
// i左边是已排序的有序列表
for (int i = 1; i < n-1;i++) {
// 加上有序列表右边元素j，重新执行排序
for (int j = i; j > 0; j--) {
// 如果j比有序队列最右边小，则交换位置，继续向左比较
if (oriArray[j] < oriArray[j-1]) {
swap(j, j-1);
} else {
// 如果j比有序队列最右边大，则本轮排序结束
break;
}
}
}package com.p.seven.algorithm.sort;
/**
* 选择排序
*/
public class InsertSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
sort();
print();
}
private static void sort() {
int n = oriArray.length;
// i左边是已排序的有序列表
for (int i = 1; i < n-1;i++) {
int temp = 0;
// 加上有序列表右边元素j，重新执行排序
for (int j = i; j > 0; j--) {
// 如果j比有序队列最右边小，则交换位置，继续向左比较
if (oriArray[j] < oriArray[j-1]) {
temp = oriArray[j-1];
oriArray[j-1] = oriArray[j];
oriArray[j] = temp;
} else {
// 如果j比有序队列最右边大，则本轮排序结束
break;
}
}
}
}
private static void print() {
for (int i = 0; i < oriArray.length; i++ ) {
System.out.print(oriArray[i]+ ", ");
}
}
}堆排序的特点是利用了数据结构中的堆。
####算法描述
快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。
原理：
快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。
[比基准值小的数] 基准值 [比基准值大的数]
接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。
快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。
分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序的运行时间和归并排序的一样，都为O（nlogn）。和归并排序类似，将序列对半分割log2n次之后，子序列里便只剩下一个数据，这时子序列的排序也就完成了。因此，如果像下图这样一行行地展现根据基准值分割序列的过程，那么总共会有log2n行。
每行中每个数字都需要和基准值比较大小，因此每行所需的运行时间为O（n）。由此可知，整体的时间复杂度为O（nlogn）
为什么快速排序是性能最好的算法？
- 首先，如果我们已经知道
，那么之后
就无需再比较了，假如再进行比较就是重复在快排中其中有一个一定是基准，因此假如进行一次比较之后就不会再次进行比较了。
- 第二，假如我们已知，
,那么
就不需要进行比较了，再进行比较就算是冗余，而在快排中这种情况是不会发生的，因为
就是递归排序的基准，因此
每次都选择最小值作为基准值，那么每次都需要把其他数据移到基准值的右边，递归执行n行，运行时间也就成了O（n2）。这就相当于每次都选出最小值并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为O（nlogn）
还没有想到一个快速排序比较生动的现实场景，想到了在补充。
####复杂度
时间复杂度：O(nlogn)。采用分治法，每次分成2部分，则一共需要分成log2n次（行），每行中的数据都要和基准值作比较，复杂度为O(n)，所以整体时间复杂度为O(nlogn)。
空间复杂度：
稳定性：不稳定。在与基准值比较时，<和<=会影响比较的结果，导致顺序不一致。
private int[] sort(int[] arr, int left, int right) {
if (left < right) {
int index = partition(arr, left, right);
sort(arr, left, index - 1);
sort(arr, index + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
// 定义左边第一个为基准值，基准值是不会变的
int pivot = arr[left];
// 此时需要定义3个变量：最左边位置left, 最右边位置right, 当前比较的位置index
// 因为最左边实际是pivot，所以初始时index的位置是不等于left的，最终每轮index都会+1，
// 而left和right会根据比较情况移动一位，最终当index(=left+1)=right时，比较结束。
int index = left + 1;
// 循环终止的条件是index(=left+1)=right, 或者是left < right
while (left < right) {
int temp = 0;
if (arr[index] <= pivot) {
// 将index位置的数据移动到left，left向右一位，index向右一位
arr[left++] = arr[index++];
} else if (arr[index] > pivot) {
// 将index位置的数据移动到right，将right数据移动到index，right向左一位，index不变
temp = arr[right];
arr[right--] = arr[index];
arr[index] = temp;
}
}
arr[left] = pivot;
return --index;
}package com.p.seven.algorithm.sort;
/**
* 快速排序
*/
public class QuickSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
int[] result = sort(oriArray, 0, oriArray.length - 1);
print(result);
}
private static int[] sort(int[] arr, int left, int right) {
if (left < right) {
int index = partition(arr, left, right);
print(arr);
System.out.println(left + "-" + (index - 1) + ", " + (index + 1) + "-" + right);
sort(arr, left, index - 1);
sort(arr, index + 1, right);
}
return arr;
}
private static int partition(int[] arr, int left, int right) {
// 定义左边第一个为基准值，基准值是不会变的
int pivot = arr[left];
// 此时需要定义3个变量：最左边位置left, 最右边位置right, 当前比较的位置index
// 因为最左边实际是pivot，所以初始时index的位置是不等于left的，最终每轮index都会+1，
// 而left和right会根据比较情况移动一位，最终当index(=left+1)=right时，比较结束。
//int left = 0;
//int right = oriArray.length - 1;
int index = left + 1;
// 循环终止的条件是index(=left+1)=right, 或者是left < right
while (left < right) {
int temp = 0;
if (arr[index] <= pivot) {
// 将index位置的数据移动到left，left向右一位，index向右一位
arr[left++] = arr[index++];
} else if (arr[index] > pivot) {
// 将index位置的数据移动到right，将right数据移动到index，right向左一位，index不变
temp = arr[right];
arr[right--] = arr[index];
arr[index] = temp;
}
print(arr);
}
arr[left] = pivot;
return --index;
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
}
}算法思想
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
实现逻辑
1、迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 ② 设定两个指针，最初位置分别为两个已经排序序列的起始位置 ③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 ④ 重复步骤③直到某一指针到达序列尾 ⑤ 将另一序列剩下的所有元素直接复制到合并序列尾
2、递归法
① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素 ② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素 ③ 重复步骤②，直到所有元素排序完毕
####场景
无。
平均时间复杂度：O(nlogn)。也是一个树状结构，按照折半的方式来进行分组。 空间复杂度：O(n) 稳定性：稳定
// 迭代实现归并排序
private static void sort() {
int len = oriArray.length;
int[] result = new int[len];
// 从每个分组1个元素开始迭代，每次分组元素合并后变成原来的2倍
for (int block = 1; block < (len / 2) + 1; block *= 2) {
for (int s = 0; s < len; s += 2 * block) {
int low = s;
int mid = s + block;
int hign = s + 2 * block;
// 计算两个块的下标[,)
int b1s = low;
int b1e = mid;
int b2s = mid;
int b2e = hign;
// 对两个block进行归并操作
while (b1s < b1e && b2s < b2e) {
result[low++] = (oriArray[b1s] < oriArray[b2s])?oriArray[b1s++]:oriArray[b2s++];
}
// 如果两个block合并结束后，仍有一个block有数据，则需要单独处理
while (b1s < b1e) {
result[low++] = oriArray[b1s++];
}
while (b2s < b2e) {
result[low++] = oriArray[b2s++];
}
}
}
}// 递归法实现归并排序
private static void sort2(int[] arr, int[] result, int s, int e) {
if (s >= e) {
return;
}
int len = e - s;
int mid = (len / 2) + s;
// 计算两个块的下标[,)
int b1s = s;
int b1e = mid;
int b2s = mid;
int b2e = e;
// 递归拆分
sort2(arr, result, b1s, b1e);
sort2(arr, result, b2s, b2e);
// 对两个block进行归并操作
int k = s;
while (b1s < b1e && b2s < b2e) {
result[s++] = (arr[b1s] < arr[b2s]) ? arr[b1s++] : arr[b2s++];
}
// 如果两个block合并结束后，仍有一个block有数据，则需要单独处理
while (b1s < b1e) {
result[s++] = arr[b1s++];
}
while (b2s < b2e) {
result[s++] = arr[b2s++];
}
// 将合并后的子集更新到源数据中
for (int i = s; i <= e; i++) {
arr[i] = result[i];
}
}package com.p.seven.algorithm.sort;
/**
* 迭代实现归并排序排序
*/
public class MergeSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
sort();
print();
}
private static void sort() {
int len = oriArray.length;
int[] result = new int[len];
// 从每个分组1个元素开始迭代，每次分组元素合并后变成原来的2倍
for (int block = 1; block < (len / 2) + 1; block *= 2) {
for (int s = 0; s < len; s += 2 * block) {
int low = s;
int mid = s + block;
int hign = s + 2 * block;
// 计算两个块的下标[,)
int b1s = low;
int b1e = mid;
int b2s = mid;
int b2e = hign;
// 对两个block进行归并操作
while (b1s < b1e && b2s < b2e) {
result[low++] = (oriArray[b1s] < oriArray[b2s]) ? oriArray[b1s++] : oriArray[b2s++];
}
// 如果两个block合并结束后，仍有一个block有数据，则需要单独处理
while (b1s < b1e) {
result[low++] = oriArray[b1s++];
}
while (b2s < b2e) {
result[low++] = oriArray[b2s++];
}
}
}
oriArray = result;
}
private static void print() {
for (int i = 0; i < oriArray.length; i++) {
System.out.print(oriArray[i] + ", ");
}
}
}package com.p.seven.algorithm.sort;
/**
* 递归法实现归并排序
*/
public class MergeSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
int[] result = new int[oriArray.length];
sort2(oriArray, result, 0, oriArray.length - 1);
oriArray = result;
print();
}
private static void sort2(int[] arr, int[] result, int s, int e) {
if (s >= e) {
return;
}
int len = e - s;
int mid = (len / 2) + s;
// 计算两个块的下标[,)
int b1s = s;
int b1e = mid;
int b2s = mid;
int b2e = e;
// 递归拆分
sort2(arr, result, b1s, b1e);
sort2(arr, result, b2s, b2e);
// 对两个block进行归并操作
int k = s;
while (b1s < b1e && b2s < b2e) {
result[s++] = (arr[b1s] < arr[b2s]) ? arr[b1s++] : arr[b2s++];
}
// 如果两个block合并结束后，仍有一个block有数据，则需要单独处理
while (b1s < b1e) {
result[s++] = arr[b1s++];
}
while (b2s < b2e) {
result[s++] = arr[b2s++];
}
// 将合并后的子集更新到源数据中
for (int i = s; i <= e; i++) {
arr[i] = result[i];
}
}
}本质上来说，希尔排序是插入排序的升级版。
对于插入排序来说，平均时间复杂度O(n^2)并不是一个高效算法，在下面这种场景时，插入排序的性能最好：
- 在大多数元素已经有序的情况下，插入排序的工作量最小；
- 在元素数量较少的情况下，插入排序的工作量较小；
但是，如何能够满足以上两个条件，让插入排序的性能最高呢？我们来看看希尔排序的思想。
采用逐步分组跨度的思想，对序列进行多轮排序，最后在数组基本有序的情况下，执行一轮插入排序。
像这样逐步分组进行粗调，再进行直接插入排序的思想，就是希尔排序，根据该算法的发明者，计算机科学家Donald Shell的名字所命名。
上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。
以上就是希尔排序的思想，他利用分组粗调的方式减少了直接插入排序的工作量，使得算法的平均时间复杂度低于O(n^2)。
不过，在某些极端情况下，希尔排序的最坏时间复杂度依然是O(n^2)，甚至比插入排序还要慢。
2，1，5，3，7，6，9，8
例如上面这个数组，如果按照希尔排序的思想，前几轮增量排序都没有发生任何交换，直到最后一论插入排序，才让数组变得有效。对于这样的数据，不但没有减少直接插入排序的工作量，反而白白增加了分组操作的成本。
希尔排序的复杂度和增量序列是相关的
{1,2,4,8,...}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)
Hibbard提出了另一个增量序列{1,3,7，...,2^k-1}^，这种序列的时间复杂度(最坏情形)为O(n^1.5)
Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,...}
实在想不到希尔排序现实生活中恰当的场景，基本思想就是先粗略的满足条件，然后再逐一比较，来减少逐一比较时的工作量，让工作效率更高。
举个不相关的例子，老婆让我洗圣女果的时候，每次都要强调要一个一个洗干净，但是一个一个实在是麻烦。于是我就全部倒进池子里，放在手里搓，搓的差不多了换水再搓，搓个几次后，基本已经看起来很干净了。然后再拿起每个快速的在水龙头下过一遍，这个时候就很快了，基本拿起来两个手指揉一圈冲一下就好了。
非常的快，非常的流畅， 非常的干净。
时间复杂度：O(n^1.3^)
空间复杂度：O(1)，每次比较只需要一个临时变量。
稳定性：不稳定，在分组调整过程中，相同数字位置会发生交换。
private static void sort() {
int len = oriArray.length;
// 进行分组，最开始的增量为数组长度的一半，每轮减半
for (int round = len / 2; round > 0; round = round / 2) {
// 找到第二个分组，开始向前比较，逐渐递增
for (int i = round; i < len; i++) {
// 分别和之前的每组数字分别比较
for (int j = i - round; j >= 0; j = j - round) {
if (oriArray[j + round] < oriArray[j]) {
swap(oriArray[j], oriArray[j + round])
}
}
}
}
}package com.p.seven.algorithm.sort;
/**
* 希尔排序
*/
public class ShellSort {
private static int[] oriArray = new int[]{9, 6, 5, 3, 8, 12, 43, 6, 7, 3, 16, 11, 13, 19, 24, 26, 28};
public static void main(String[] args) {
sort();
print();
}
private static void sort() {
int len = oriArray.length;
// 进行分组，最开始的增量为数组长度的一半，每轮减半
for (int round = len / 2; round > 0; round = round / 2) {
// 找到第二个分组，开始向前比较，逐渐递增
for (int i = round; i < len; i++) {
// 分别和之前的每组数字分别比较
for (int j = i - round; j >= 0; j = j - round) {
if (oriArray[j + round] < oriArray[j]) {
int temp = oriArray[j];
oriArray[j] = oriArray[j + round];
oriArray[j + round] = temp;
}
}
}
}
}
private static void print() {
for (int i = 0; i < oriArray.length; i++) {
System.out.print(oriArray[i] + ", ");
}
}
}##5、安全算法
###5.1 安全和算法
在互联网交换数据时，存在以下4个问题。
-
窃听
A向B发送的消息可能会在传输途中被X偷看。
-
假冒
A以为向B发送了消息，然而B有可能是X冒充的；反过来，B以为从A那里收到了消息，然而A也有可能是X冒充的。
-
篡改
即便B确实收到了A发送的消息，但也有可能像右图这样，该消息的内容在途中就被X更改了。
除了被第三者篡改外，通信故障导致的数据损坏也可能会使消息内容发生变化。
-
事后否认
B从A那里收到了消息，但作为消息发送者的A可能对B抱有恶意，并在事后声称“这不是我发送的消息”。这种情况会导致互联网上的商业交易或合同签署无法成立。这种行为便是“事后否认”。
如何解决这4个问题呢？
-
窃听：加密技术；
-
假冒：消息认证码或数字签名技术；
-
篡改：消息认证码或数字签名技术；
-
事后否认：数字签名；
###5.2 加密的基础知识
计算机会用由0和1这两个数字表示的二进制来管理所有数据。如下图所示，数据虽然有文本、音频、图像等不同的形式，但是在计算机中都是用二进制来表示的。
对计算机来说，数据就是一串有意义的数字罗列。密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列。也就是说，加密就是数据经过某种运算后，变成计算机无法理解的数的过程。
在加密运算上会用到“密钥”。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程。反过来，解密就是像下图这样，通过密钥进行数值计算，把密文恢复成原本数据的过程。
将数据变成第三者的计算机无法理解的形式，然后再将其恢复成原本数据的一系列操作就是加密技术。
###5.3 哈希函数
####5.3.1 概念
哈希函数可以把给定的数据转换成固定长度的无规律数值。转换后的无规律数值可以作为数据摘要应用于各种各样的场景。
哈希值虽然是数字，但多用十六进制来表示。
哈希函数的特征。
- 第一个特征是输出的哈希值数据长度不变。
- 第二个特征是如果输入的数据相同，那么输出的哈希值也必定相同。
- 第三个特征是即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。
- 第四个特征是即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
- 第五个特征是不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不
- 最后一个特征是求哈希值的计算相对容易。
使用哈希函数可以更安全地实现基于密码的用户认证。哈希函数的算法中具有代表性的是MD5、SHA-1和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用。
####5.3.2 MD5
MD5讯息摘要演算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码杂凑函数，可以产生出一个128位元（16位元组）的散列值（hash value），用于确保信息传输完整一致。
1、输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）；
2、不同的输入得到的不同的结果（唯一性）；
3、MD5算法是否可逆？
MD5不可逆的原因是其是一种散列函数，使用的是hash算法，在计算过程中原文的部分信息是丢失了的。
不过有个地方值得指出的是，一个MD5理论上的确是可能对应无数多个原文的，因为MD5是有限多个的而原文可以是无数多个。比如主流使用的MD5将任意长度的“字节串映射为一个128bit的大整数。也就是一共有2^128种可能，大概是3.4*10^38，这个数字是有限多个的，而但是世界上可以被用来加密的原文则会有无数的可能性。
不过需要注意的一点是，尽量这是一个理论上的有限对无限，不过问题是这个无限在现实生活中并不完全成立，因为一方面现实中原文的长度往往是有限的（以常用的密码为例，一般人都在20位以内），另一方面目前想要发现两段原文对应同一个MD5（专业的说这叫杂凑冲撞）值非常困难。
MD5相当于超损压缩。
4、MD5安全性
普遍认为MD5是很安全，因为暴力破解的时间是一般人无法接受的。实际上如果把用户的密码MD5处理后再存储到数据库，其实是很不安全的。因为用户的密码是比较短的，而且很多用户的密码都使用生日，手机号码，身份证号码，电话号码等等。或者使用常用的一些吉利的数字，或者某个英文单词。如果我把常用的密码先MD5处理，把数据存储起来，然后再跟你的MD5结果匹配，这时我就有可能得到明文。
在实际应用中，通常认为MD5是安全的，但是现在基于彩虹表的手段，已经能够明显加快对MD5的破解。所以在安全性要求比较高的场合，不建议直接使用MD5算法。
可以通过加盐值的手段，加强MD5的安全性。将盐值拼接在原密码中，在MD5的方式，避开彩虹表，增加摘要的安全性。
#####III_MD5用途
1.防止被篡改： 1）比如发送一个电子文档，发送前，我先得到MD5的输出结果a。然后在对方收到电子文档后，对方也得到一个MD5的输出结果b。如果a与b一样就代表中途未被篡改。 2）比如我提供文件下载，为了防止不法分子在安装程序中添加木马，我可以在网站上公布由安装文件得到的MD5输出结果。 3）SVN在检测文件是否在CheckOut后被修改过，也是用到了MD5。
2.防止直接看到明文： 现在很多网站在数据库存储用户的密码的时候都是存储用户密码的MD5值。这样就算不法分子得到数据库的用户密码的MD5值，也无法知道用户的密码。（比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。）
3.防止抵赖（数字签名）： 这需要一个第三方认证机构。例如A写了一个文件，认证机构对此文件用MD5算法产生摘要信息并做好记录。若以后A说这文件不是他写的，权威机构只需对此文件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，相同的话，就证明是A写的了。这就是所谓的“数字签名”。
#####IV_MD5算法过程
对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
第一步、填充：如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)；
第二步、记录信息长度：用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N*512+448+64=(N+1)*512位。
第三步、装入标准的幻数（四个整数）：标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=(76543210)16）。如果在程序中定义应该是: （A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。
第四步、四轮循环运算：循环的次数是分组的个数（N+1）
1）将每一512字节细分成16个小组，每个小组32位（4个字节）
2）先认识四个线性函数(&是与,|是或,~是非,^是异或)
F(X,Y,Z)=(X&Y)|((~X)&Z)
G(X,Y,Z)=(X&Z)|(Y&(~Z))
H(X,Y,Z)=X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))1234
3）设Mj表示消息的第j个子分组（从0到15），<<
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)1234
4）四轮运算
第一轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)
第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。
#####V_MD5使用
在java中实现MD5是很简单的，在包java.security有个类MessageDigest。官方文档如下 : MessageDigest 类为应用程序提供信息摘要算法的功能，如 MD5 或 SHA 算法。信息摘要是安全的单向哈希函数，它接收任意大小的数据，输出固定长度的哈希值。
MessageDigest 对象开始被初始化。该对象通过使用 update 方法处理数据。任何时候都可以调用 reset 方法重置摘要。一旦所有需要更新的数据都已经被更新了，应该调用 digest 方法之一完成哈希计算。
对于给定数量的更新数据，digest 方法只能被调用一次。digest 被调用后，MessageDigest 对象被重新设置成其初始状态。
JAVA代码如下：
import java.security.MessageDigest;
public class MyMD5 {
static char[] hex = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
public static void main(String[] args) {
try{
MessageDigest md5 = MessageDigest.getInstance("MD5");//申明使用MD5算法
md5.update("a".getBytes());//
System.out.println("md5(a)="+byte2str(md5.digest()));
md5.update("a".getBytes());
md5.update("bc".getBytes());
System.out.println("md5(abc)="+byte2str(md5.digest()));
}catch(Exception e){
e.printStackTrace();
}
}
/**
* 将字节数组转换成十六进制字符串
* @param bytes
* @return
*/
private static String byte2str(byte []bytes){
int len = bytes.length;
StringBuffer result = new StringBuffer();
for (int i = 0; i < len; i++) {
byte byte0 = bytes[i];
result.append(hex[byte0 >>> 4 & 0xf]);
result.append(hex[byte0 & 0xf]);
}
return result.toString();
}
} #####VI_算法模拟
####5.3.3 SHA-1
安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准（Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。
#####II_SHA-1特性
- 1 SHA-1是一种数据加密算法，该算法的思想是接收一段明文，然后以一种不可逆的方式将它转换成一段（通常更小）密文，也可以简单的理解为取一串输入码（称为预映射或信息），并把它们转化为长度较短、位数固定的输出序列即散列值（也称为信息摘要或信息认证代码）的过程。
- 2 单向散列函数的安全性在于其产生散列值的操作过程具有较强的单向性。如果在输入序列中嵌入密码，那么任何人在不知道密码的情况下都不能产生正确的散列值，从而保证了其安全性。SHA将输入流按照每块512位（64个字节）进行分块，并产生20个字节的被称为信息认证代码或信息摘要的输出。
- 3 该算法输入报文的长度不限，产生的输出是一个160位的报文摘要。输入是按512 位的分组进行处理的。SHA-1是不可逆的、防冲突，并具有良好的雪崩效应。
- 4 通过散列算法可实现数字签名实现，数字签名的原理是将要传送的明文通过一种函数运算（Hash）转换成报文摘要（不同的明文对应不同的报文摘要），报文摘要加密后与明文一起传送给接受方，接受方将接受的明文产生新的报文摘要与发送方的发来报文摘要解密比较，比较结果一致表示明文未被改动，如果不一致表示明文已被篡改。
- 5 MAC （信息认证代码）就是一个散列结果，其中部分输入信息是密码，只有知道这个密码的参与者才能再次计算和验证MAC码的合法性。
#####III_SHA-1算法过程
SHA-1的实现逻辑基本同MD5，不做赘述。
SHA-1算法和MD5算法都有MD4算法导出，因此他们俩的特点、缺陷、应用场景基本是相同的。
- 1 它俩的区别在于SHA-1算法在长度上是40位十六进制，即160位的二进制，而MD5算法是32位的十六进制，即128位的二进制，所以2的160次是远远超过2的128次这个数量级的，所以SHA-1算法相对来说要比MD5算法更安全一些。
- 2 对密码分析的安全性:由于MD5的设计.易受密码分析的攻击,SHA-1显得不容易受这样的攻击.
- 3 速度:在相同的硬件上,SHA-1的运行速度比MD5慢.
####5.3.4 SHA-2
#####I_SHA-2说明
SHA-2又称安全散列算法2（Secure Hash Algorithm 2），是一种密码散列函数算法标准，其输出长度可取224位、256位、384位、512位，分别对应SHA-224、SHA-256、SHA-384、SHA-512。它含包含另外两个算法：SHA-512/224、SHA-512/256。
基本同SHA-1和MD5。
#####III_SHA-1和SHA-2区别对比
首先，人们一般把哈希值位数长度作为重要的区别，SHA-1是160位的哈希值，而SHA-2是组合值，有不同的位数，其中最受欢迎的是256位。
因为SHA-2有多种不同的位数，导致这个名词有一些混乱。但是无论是“SHA-2”，“SHA-256”或“SHA-256位”，其实都是指同一种加密算法。但是SHA-224”，“SHA-384”或“SHA-512”，表示SHA-2的二进制长度。还要另一种就是会把算法和二进制长度都写上，如“SHA-2 384”。
SSL行业选择SHA作为数字签名的散列算法，从2011到2015，一直以SHA-1位主导算法。但随着互联网技术的提升，SHA-1的缺点越来越突显。从去年起，SHA-2成为了新的标准，所以现在签发的SSL证书，必须使用该算法签名。
也许有人偶尔会看到SHA-2 384位的证书，很少会看到224位，因为224位不允许用于公共信任的证书，512位，不被软件支持。初步预计，SHA-2的使用年限为五年，但也许会被提前淘汰。这需要时间来验证。
下面是SSL证书的SHA-1和SHA-2签名对比
两者在表面上似乎没有什么特别，但是数字签名对于SSL/TLS的安全性具有重要的作用。哈希值越大，组合越多，其安全性就越高。加密哈希算法的一个重要功能是产生独特的散列，当两个不同的值或文件可以产生相同的散列，则会创建所谓的碰撞。只有在不发生碰撞时，才能保证数字签名的安全性。碰撞对于哈希算法来说是极其危险的，因为碰撞允许两个文件产生相同的签名。当计算机检查签名时，即使该文件未真正签署，也会被计算机识别为有效的。
###5.4 共享秘钥加密
####5.4.1 概念
共享密钥加密是加密和解密都使用相同密钥的一种加密方式。由于使用的密钥相同，所以这种算法也被称为“对称加密”。
我们先从整体上来了解一下共享密钥加密的处理流程。
- 假设A准备通过互联网向B发送数据。
- 由于有被窃听的风险，所以需要把想要保密的数据加密后再发送。
- A使用密钥加密数据。
- A将密文发送给B。
- B收到密文后，使用相同的密钥对其进行解密。这样，B就取得了原本的数据。只要是加密好的数据，就算被第三者恶意窃听也无须担心。
接下来想一想共享密钥加密中的问题。
- 让我们回到B收到A发送的密文的时候。
- 密文可能已经被X窃听了。
- 这里假设A和B无法直接沟通，B不知道加密时使用的是什么密钥。
- A需要通过某种手段将密钥交给B。和密文一样，A又在互联网上向B发送了密钥。
- B使用收到的密钥对密文进行解密。
- 但是，该密钥也有可能会被X窃听。这样一来，X也可以使用密钥对密文进行解密了。
秘钥分配问题
既然密钥有被第三者窃听的风险，那是不是也可以先加密密钥再发送呢？使用这种方式，又会产生如何把加密密钥的密钥发送给对方的问题，还是回到了一开始的问题。
因此需要找到可以把密钥安全送出的方法，这就是“密钥分配问题”。
要想解决这个问题，可以使用“密钥交换协议”和“公开密钥加密”两种方法。
####5.4.2 凯撒密码
####5.4.3 AES
####5.4.4 DES
####5.4.5 动态口令
公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。
我们先从整体上来了解一下公开密钥加密的处理流程。
-
假设A准备通过互联网向B发送数据。
-
首先，需要由接收方B来生成公开密钥和私有密钥。
-
然后把公开密钥发送给A。
-
A使用B发来的公开密钥加密数据。
-
A将密文发送给B, B再使用私有密钥对密文进行解密。这样，B就得到了原本的数据。
公开密钥和密文都是通过互联网传输的，因此可能会被X窃听。但是，使用公开密钥无法解密密文，因此X也无法得到原本的数据。此外，在和多人传输数据时，使用公开密钥加密十分方便。
如果使用共享密钥加密，密钥的需求数量会随着发送人数的增多而急剧增多。上一节的例子中只有2个人，因此只需要2个密钥，但5人就需要10个，100人就需要4950个（n=人数，需要的数量便是n(n-1)/2）
要想找到实现公开密钥加密的算法并不容易。考虑到加密所需的计算流程，算法必须满足如下条件。
- ① 可以使用某个数值对数据进行加密（计算）。
- ② 使用另一个数值对加密数据进行计算就可以让数据恢复原样。
- ③ 无法从一种密钥推算出另一种密钥。
公开密钥加密还有一个问题，那就是加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密”。
####5.5.2 中间人攻击
公开密钥加密存在公开密钥可靠性的问题。
- 让我们回到B生成公开密钥和私有密钥的时候。
- 在接下来的说明中，B生成的公开密钥用PB表示、私有密钥用SB来表示。
- X想要窃听A发给B的数据，于是他也准备了公开密钥PX和私有密钥SX。
- 在B把公开密钥PB发给A的时候……
- X把公开密钥PB替换成自己的公开密钥PX……
- 于是公开密钥PX传到了A那里。由于公开密钥无法显示自己是由谁生成的，所以A不会发现自己收到的公开密钥已经被人替换。
- A使用公开密钥PX对数据加密。20[插图]当A把想要给B的密文发送出去后，X接收了这个密文。21[插图]这个密文由X生成的公开密钥PX加密而成，所以X可以用自己的私有密钥SX对密文进行解密。
- 接下来，X用B生成的公开密钥PB加密数据。
- X把密文发送给B，这个密文由B发出的公开密钥PB加密而成，所以B可以用自己的私有密钥SB来解密。
从收到密文到解密密文都没发生任何问题，因此B也意识不到数据已经被窃听。这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middleattack）。
公开密钥的可靠性会出现问题，就是因为A无法判断收到的公开密钥是否来自B。要想解决这个问题，就要用到之后会讲到的“数字证书”。
####5.5.3 RSA
共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。
在混合加密中，要用处理速度较快的共享密钥加密对数据进行加密。不过，加密时使用的密钥，则需要用没有密钥分配问题的公开密钥加密进行处理。
我们来看看混合加密具体的处理流程。
- 假设A准备通过互联网向B发送数据。
- 使用处理速度较快的共享密钥加密对数据进行加密。加密时所用的密钥在解密时也要用到，因此A需要把密钥发送给B。
- 将密钥通过公开密钥加密进行加密后，A就可以将其安全地发送给B了。因此，作为接收方，B需要事先生成公开密钥[插图]和私有密钥。
- B将公开密钥发送给A。
- A使用收到的公开密钥，对共享密钥加密中需要使用的密钥进行加密。
- A将加密后的密钥发送给B。
- B使用私有密钥对密钥进行解密。
- 这样，A就把共享密钥加密中使用的密钥安全地发送给了B。
- 接下来，A只要将使用这个密钥加密好的数据发送给B即可。加密数据时使用的是处理速度较快的共享密钥加密。
像这样，混合加密在安全性和处理速度上都有优势。能够为网络提供通信安全的SSL协议也应用了混合加密方法。SSL是Secure Sockets Layer（安全套接层）的简写，该协议经过版本升级后，现在已正式命名为TLS（Transport Layer Security，传输层安全）。但是，SSL这个名字在人们心中已经根深蒂固，因此该协议现在也常被称为SSL协议或者SSL / TLS协议。
迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。
假设有一种方法可以合成两个密钥。使用这种方法来合成密钥P和密钥S，就会得到由这两个密钥的成分所构成的密钥P-S。
这种合成方法有三个特征。
- 第一，即使持有密钥P和合成的密钥P-S，也无法把密钥S单独取出来。
- 第二，不管是怎样合成而来的密钥，都可以把它作为新的元素，继续与别的密钥进行合成。比如上图中的这个例子，使用密钥P和密钥P-S，还能合成出新的密钥P-P-S。
- 第三，密钥的合成结果与合成顺序无关，只与用了哪些密钥有关。比如合成密钥B和密钥C后，得到的是密钥B-C，再将其与密钥A合成，得到的就是密钥A-B-C。而合成密钥A和密钥C后，得到的是密钥A-C，再将其与密钥B合成，得到的就是密钥B-A-C。此处的密钥A-B-C和密钥B-A-C是一样的。
我们试一试用这种方法，在A和B这两人之间安全地交换密钥吧。
- 首先由A生成密钥P。
- 然后A把密钥P发送给B。
- 接下来，A和B各自准备自己的私有密钥SA和SB。
- A利用密钥P和私有密钥SA合成新的密钥P-SA。
- B也利用密钥P和私有密钥SB合成新的密钥P-SB。
- A将密钥P-SA发送给B, B也将密钥P-SB发送给A。
- A将私有密钥SA和收到的密钥P-SB合成为新的密钥SA-P-SB。
- 同样地，B也将私有密钥SB和收到的密钥P-SA合成为新的密钥P-SA-SB。
- 于是A和B都得到了密钥P-SA-SB。这个密钥将作为“加密密钥”和“解密密钥”来使用。
使用迪菲-赫尔曼密钥交换，通信双方仅通过交换一些公开信息就可以实现密钥交换。但实际上，双方并没有交换密钥，而是生成了密钥。因此，该方法又被叫作“迪菲-赫尔曼密钥协议”。
####5.8.1 概念
消息认证码（message authentication code）是一种确认完整性并进行认证的技术，取三个单词的首字母，简称为MAC。
消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。
使用 MAC 验证消息完整性的具体过程是：假设通信双方 A 和 B 共享密钥 K，A用消息认证码算法将 K 和消息 M 计算出消息验证码 Mac，然后将 Mac 和 M 一起发送给 B。B 接收到 Mac 和 M 后，利用 M 和 K 计算出新的验证码 Mac*，若 Mac*和Mac 相等则验证成功，证明消息未被篡改。由于攻击者没有密钥 K，攻击者修改了消息内容后无法计算出相应的消息验证码，因此 B 就能够发现消息完整性遭到破坏。
首先，我们来看看什么情况下需要使用消息认证码。
- 假设A在B处购买商品，需要将商品编号abc告诉B。
- 此处，假设A使用共享密钥加密对消息进行加密。A通过安全的方法将密钥发送给了B。
- A使用双方共有的密钥对消息进行加密。
- A把密文发送给B, B收到后对密文进行解密，最终得到了原本的商品编号abc。
- 以上是没有出现问题时的流程，然而在这个过程中可能会发生下面的情况。
- 假设A发送给B的密文在通信过程中被X恶意篡改了，而B收到密文后没有意识到这个问题。
- B对被篡改的密文进行解密，得到消息xyz。
- B以为A订购的是编号为xyz的商品，于是将错误的商品发送给了A。
如果使用消息认证码，就能检测出消息已被篡改。
- 为了让大家了解实际的处理流程，我们再一次回到A正要向B发送密文的时候。
- A生成了一个用于制作消息认证码的密钥，然后使用安全的方法将密钥发送给了B。
- 接下来，A使用密文和密钥生成一个值。此处生成的是7f05。这个由密钥和密文生成的值就是消息认证码，以下简称为MAC（Message Authentication Code）。
- A将MAC（7f05）和密文发送给B。
- 和A一样，B也需要使用密文和密钥来生成MAC。经过对比，B可以确认自己计算出来的7f05和A发来的7f05一致。
- 接下来，B只需使用密钥对密文进行解密即可。最终B成功取得了A发送过来的商品编号abc。
- X在通信过程中对密文进行了篡改是怎样一种情况呢？让我们回到A正要向B发送密文的时候。
- 假设在A向B发送密文和MAC时，X对密文进行了篡改。
- B使用该密文计算MAC，得到的值是b85c，发现和收到的MAC不一致。
- 由此，B意识到密文或者MAC，甚至两者都可能遭到了篡改。于是B废弃了收到的密文和MAC，向A提出再次发送的请求。
我们可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC[插图]、OMAC[插图]、CMAC[插图]等。目前，HMAC的应用最为广泛。
加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。
如果原本的消息是很长的句子，那么它被篡改后意思会变得很奇怪，所以接收者有可能会发现它是被篡改过的。
但是，如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息验证码来检测。
接着我们来进一步思考：X会不会为了让密文的篡改变得合理，而对MAC也进行篡改呢？X没有计算MAC的密钥，所以即便他可以篡改MAC，也无法让篡改后的密文变得合理。
所以，只要B计算出MAC，发现密文对应的MAC与自己算出的不同，就能确认通信过程中发生了篡改。
数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。
什么是数字签名？
- 首先，我们来看一看数字签名的特征。假设A要向B发送消息。
- 在发送前A给消息加上数字签名。数字签名只能由A生成。
- 只要发送的消息上有A的数字签名，就能确定消息的发送者就是A。
- B可以验证数字签名的正确性，但无法生成数字签名。
数字签名的生成使用的是公开密钥加密。
公开密钥加密中，加密使用的是公开密钥P，解密使用的是私有密钥。任何人都可以使用公开密钥对数据进行加密，但只有持有私有密钥的人才能解密数据。然而，数字签名却是恰恰相反的。
数字签名怎么产生呢？
- 首先由A准备好需要发送的消息、私有密钥和公开密钥。由消息的发送者来准备这两个密钥，这一点与公开密钥加密有所不同。
- A将公开密钥发送给B。
- A使用私有密钥加密消息。
- 加密后的消息就是数字签名。
- A将消息和签名都发送给了B。
- B使用公开密钥对密文（签名）进行解密。
- B对解密后的消息进行确认，看它是否和收到的消息一致。流程到此结束。
在以上步骤中，生成的是“只能由持有私有密钥的A来加密，但只要有公开密钥，谁都可以进行解密的密文”。这个密文作为密码似乎没有任何意义。但是换一个角度来看就会发现，它可以保证这个密文的制作者只能是持有私有密钥的A。
在数字签名中，是将“只能由A来加密的密文”作为“签名”来使用的。严格来说，也有使用加密运算以外的计算方法来生成签名的情况。但是，用私有密钥生成签名、用公开密钥验证签名这一机制是相同的，所以为了方便我们就以上文的方式进行了说明。
在公开密钥加密中，用公开密钥加密的数据都可以用私有密钥还原。而本节讲解的数字签名利用的是用私有密钥加密的数据，用公开密钥解密后就能还原这一性质。也就是说，即使密钥的使用顺序不同，运行结果也都是一样的。
并不是所有的公开密钥加密都具有这个性质，不过RSA加密算法是可以的。
能够用A的公开密钥解密的密文，必定是由A生成的。因此，我们可以利用这个结论来确认消息的发送者是否为A，消息是否被人篡改。由于B只有公开密钥，无法生成A的签名，所以也预防了“事后否认”这一问题的发生。
虽然数字签名可以实现“认证”“检测篡改”“预防事后否认”三个功能，但它也有一个缺陷。
那就是，虽然使用数字签名后B会相信消息的发送者就是A，但实际上也有可能是X冒充了A。
其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁。收到的公开密钥上也没有任何制作者的信息。因此，公开密钥有可能是由某个冒充A的人生成的。
####5.10.1 概念
“公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。
什么是数字证书呢？
-
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。
####5.10.2 证书交付过程
我们来看看公开密钥的交付过程有没有什么问题。
- 假设X冒充A，准备向B发送公开密钥PX[插图]。
- 但是，B没有必要信任以非证书形式收到的公开密钥。
- 假设X为了假冒A，准备在认证中心登记自己的公开密钥。然而X无法使用A的邮箱地址，因此无法获得A的证书。
认证中心是管理数字证书的组织机构。原则上谁都可以成为认证中心，所以认证中心的数量也比较多，但建议在经过政府审查的大型企业机构进行申请，这些机构更令人放心。
通过数字证书，信息的接收者可以确认公开密钥的制作者。但此处仍有一个疑问。那就是，B得到的公开密钥PC真的来自认证中心吗？由于公开密钥自身不能表示其制作者，所以有可能是冒充认证中心的X所生成的。也就是说，这里同样存在公开密钥问题
实际上，认证中心的公开密钥PC是以数字证书的形式交付的，会有更高级别的认证中心对这个认证中心署名。
就像下页图中的树结构一样，由上面的认证中心为下面的认证中心发行证书。那么，我们来看看这个树结构是怎么形成的吧。
假设存在一个被社会广泛认可的认证中心A。此时出现了一个刚成立的公司B，虽然B想要开展认证中心的业务，但它无法得到社会的认可。于是B向A申请发行数字证书。当然A会对B能否开展认证中心业务进行适当的检测。只要A发行了证书，公司B就可以向社会表示自己获得了公司A的信任。
于是，通过大型组织对小组织的信赖担保，树结构就建立了起来。
最顶端的认证中心被称为“根认证中心”（root CA），其自身的正当性由自己证明。对根认证中心自身进行证明的证书为“根证书”。如果根认证中心不被信任，整个组织就无法运转。因此根认证中心多为大型企业，或者与政府关联且已经取得了社会信赖的组织。
到目前为止，我们了解的都是个人之间交付公开密钥的例子，其实在网站之间的通信中同样也要用到数字证书。只要能收到来自网站的含有公开密钥的证书，就能确认该网站未被第三者冒充。此处的证书叫作“服务器证书”，同样由认证中心发行。
个人的证书会与他的邮箱信息相对应，而服务器证书与域名信息相对应。因此，我们还可以确认网站域名和存储网站本身内容的服务器是由同一个组织来管理的。
数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施”（Public Key Infrastructure, PKI）。