一、什么是 Hash 算法

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

Hash 算法能将将任意长度的二进制明文映射为较短的二进制串的算法，并且不同的明文很难映射为相同的 Hash 值。

也可以理解为空间映射函数，是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，Hash 函数转换后不可逆，意思是不可能通过逆操作和 Hash 值还原出原始的值。

散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值K为自变量，通过一定的函数关系h(K)(称为散列函数)，计算出对应的函数值来，把这个值解释为结点的存储地址，将结点存入到此存储单元中。检索时，用同样的方法计算地址，然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列（hash，也称“哈希”）是一种重要的存储方式，也是一种常见的检索方法。

二、Hash 算法有什么特点

Hash 值又称为指纹或者摘要，具有以下特点：

    正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值。
    逆向困难：给定 Hash 值，在有限时间内很难逆推出明文。
    输入敏感：原始输入信息发生任何变化，新的 Hash 值都应该出现很大变化。
    冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致。

三、Hash 算法有哪些

常见 Hash 算法有 MD5 和 SHA 系列，目前 MD5 和 SHA1 已经被破解，一般推荐至少使用 SHA2-256 算法。

下面我们来看具体写一个 Hash 函数需要注意些什么，首先要明白 Hash 函数是把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存，另外 Hash 函数也会应用于查找上。

四、Hash 算法碰撞

稍微想一下就可以发现，既然输入数据长度不固定，而输出的哈希值却是固定长度的，这意味着哈希值是一个有限集合，而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的，所以一个成熟的哈希算法会有较好的抗冲突性，同时在实现哈希表的结构时也要考虑到哈希冲突的问题。

比如“666”经过 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”，相同 Hash 算法得到的值是一样的。比如 WiFi 密码如果是 8 位纯数字的话，顶多就是 99999999 种可能性，破解这个密码需要做的就是提前生成好 0 到 1 亿数字的 Hash 值，然后做 1 亿次布尔运算（就是 Bool 值判断，0 或者 1），而现在普通 I5 四核 CPU 每秒能到达 200 亿次浮点数计算，做 1 亿次布尔运算也就是秒级别的时间就破解了。

所以密码尽量不要用纯数字，因为根本没有任何安全性。

五、加盐防碰撞

对数字内容进行 Hash 运算，获取唯一的摘要值来指代原始完整的数字内容，利用 Hash 函数的抗碰撞性来确保内容未被篡改。

常用于用户名和密码来确保用户信息安全，为了防止攻击会采用加盐的方法，就是原来的明文加上一个随机数之后的 Hash 值，Hash 值和盐会保存在两个地方，只要不是同时泄漏就很难被破解。

六、Hash算法在信息安全方面的应用 

1.文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的“数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。

2.数字签名

Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称“数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

3.鉴权协议

鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

本节是《Java数据结构及算法实战》系列的第2节，主要介绍描述算法的常用的4种方式。

要定义一个算法，我们可以用自然语言、流程图、伪代码的方式描述解决某个问题的过程或是编写一段程序来实现这个过程。比如，在前面所举的“学生信息管理系统”例子中，我们希望实现添加用户、删除用户、查询用户三个算法。

1. 自然语言描述算法

可以采用自然语言的方式来描述添加用户、删除用户、查询用户三个算法：

• 添加用户：将用户信息添加到系统中。如果已经添加了过该用户的信息，则提示用户。否则将用户信息添加到系统中，并给出提示。
• 删除用户：将用户信息从系统中删除。如果用户信息不存在于系统中，则提示用户。否则将用户信息从系统中删除，并给出提示。
• 查询用户：将系统中所有的用户信息查询出来。如果系统中不存在用户，则提示用户。否则将用户信息查询出来返回，并将用户信息打印出来。

使用自然语言描述的好处是任何人都能看懂。当然相比于伪代码或者程序语言而言，使用自然语言描述有时会显得繁琐。

2. 流程图描述算法

流程图（Flow Diagram）是一种通用的图形符号表示法是一种非正式的，可以清楚描述步骤和判断。图1-2展示的是用流程图的方式来描述添加用户、删除用户、查询用户三个算法。

相比较自然语言而言，通过流程图的描述，可以很清楚的看到操作的流向及经过的步骤。但需要注意的是，流程图应该只描述核心的操作步骤以及关键的节点判断，而不是事无巨细的把所有的操作都描述出来，否则只会让整个图看上去复杂难以理解。

3. 伪代码描述算法

伪代码（Pseudocode）是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。可以采用伪代码的方式来描述添加用户、删除用户、查询用户三个算法。

添加用户的伪代码如下：

input(student)
if student in studentList
    print "Student exsit"
else 
    add student in studentList
    print "Add student success"

删除用户的伪代码如下：

input(student)
if student in studentList
    remove student from studentList
    print "Remove student success"
else 
    print "Student not exsit"

查询用户的伪代码如下：

if student in studentList
    output studentList
else 
    print "No student exsit"

伪代码结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。相比程序语言（例如Java、C++、C等等）它更类似自然语言。它虽然不是标准的语言，却可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。

4. 程序语言描述算法

程序语言描述算法，实际上就是用程序语言实现算法。不同的编程语言其语法不尽相同。以下是采用Java语言的方式来描述添加用户、删除用户、查询用户三个算法。

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

public class StudentInfoManageSystem {

	private List<Student> studentList = new ArrayList<>();

	public void addStudent(Student student) {
		// 如果已经添加了过该用户的信息，则提示用户。
		// 否则将用户信息添加到系统中，并给出提示。
		if (studentList.contains(student)) {
			System.out.println("Student exsit");
		} else {
			studentList.add(student);
			System.out.println("Add student success");
		}
	}

	public void removeStudent(Student student) {
		// 如果用户信息不存在于系统中，则提示用户。
		// 否则将用户信息从系统中删除，并给出提示。
		if (studentList.contains(student)) {
			studentList.remove(student);
			System.out.println("Remove student success");
		} else {
			System.out.println("Student not exsit");
		}
	}

	public List<Student> getStudentList() {
		// 如果系统中不存在用户，则提示用户。
		// 否则将用户信息查询出来返回，并将用户信息打印出来。
		if (studentList.isEmpty()) {
			System.out.println("No student exsit");
		} else {
			for (Student s : studentList) {
				System.out.format("Student info: name %s, age %d, phone %s, address %s%n", 
						s.getName(), s.getAge(), s.getPhoneNumer(), s.getAddress());
			}
		}

		return studentList;
	}
}

为了演示上述算法，还需要一个应用入口。我们用StudentInfoManageSystemDemo类来表示应用主程序，代码如下：

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

public class StudentInfoManageSystemDemo {

	public static void main(String[] args) {
		// 初始化系统
		StudentInfoManageSystem system = new StudentInfoManageSystem();

		// 初始化学生信息
		Student student = new Student(32, "Way Lau", "17088888888", "Shenzhen");

		// 添加学生
		system.addStudent(student); // Add student success

		// 再次添加学生
		system.addStudent(student); // Student exsit

		// 第一次查询所有学生
		List<Student> studentList = system.getStudentList();

		// 删除学生
		system.removeStudent(student); // Remove student success

		// 再次删除学生
		system.removeStudent(student); // Student not exsit

		// 查询所有学生
		studentList = system.getStudentList(); // No student exsit

	}

}

运行上述程序，可以看到控制台输出内容如下：

Add student success
Student exsit
Student info: name Way Lau, age 32, phone 17088888888, address Shenzhen
Remove student success
Student not exsit
No student exsit

程序语言描述算法一步到位，写出的算法可直接交予计算机处理。对于懂得这类程序语言的开发者而言，通过运行程序可以马上验证算法的正确性。当然其缺点也较为明显：

• 不便于体现自顶向下、逐步求解的思想；
• 程序语言包含很多细节内容，会淹没算法的主要思想。

因此，在描述某个算法时，往往通过几种描述方式结合起来使用。

参考引用

• 原本同步至：https://waylau.com/description-of-algorithms/
• 本系列归档：https://github.com/waylau/java-data-structures-and-algorithms-in-action
• 数据结构和算法基础（Java语言实现）：https://item.jd.com/13014179.html