2.2.1 哈希算法

在介绍哈希算法之前，我们先通过一个数百年来争论不休的千古疑案，引出哈希算法的用武之地。

这个疑案就是：雍正是不是篡位登基的。

公元1722年，在一个寒冷的冬夜，京城老百姓还沉浸在睡梦之中，但他们不知道此时此刻紫禁城里一件惊天动地的大事即将发生。就在当天夜里，康熙大帝驾崩了，7日之后，康熙遗诏公布，立皇四子胤禛继任为新皇帝，即雍正皇帝。雍正继位后，清朝宫廷内外动荡不已。不久，有关雍正篡位的流言蜚语就开始四处传播，传闻胤禛将康熙皇帝藏于金匾下的传位遗诏中，传位十四子篡改为传位于四子，这才得以登上皇帝宝座，如图2-10所示。

“历史总是由胜利者来书写，而受害者只能将历史保留在自己的记忆中”，对于受害者，这是多么无奈的一句话。如果当年有哈希算法，那么雍正还能轻易地篡改遗诏吗？还能顺利地继承大统吗？答案是否定的。因为哈希算法有一个特性，即能用来验证信息是否被篡改，这样一来，恐怕那段中国历史要重新改写了，如图2-11所示。

哈希算法是密码哈希函数的基础，而密码哈希函数是区块链中使用最多的一类加密算法，它被广泛应用于构建区块以及确认交易信息的完整性上。那么什么是哈希算法呢？一般来讲，哈希算法是一类以哈希函数为基础的算法统称，哈希的英文为Hash，它也被翻译为“散列”，所以又被称为散列算法。

什么是哈希函数？哈希函数的本质就是一个数学函数，它有一个输入和一个输出，其输入称为消息；输出值是根据消息内容计算出的值，称为哈希值或散列值，如图2-12所示。

哈希函数的特性：

（1）输入消息长度任意。

（2）输出哈希值长度固定。

（3）可以在合理的时间范围内计算出哈希值。长度为n的输入消息，它的哈希计算时间复杂度为O（n）。

由前两个特性可知，首先哈希函数的输入可以是任意长度的消息；其次不管输入多长的消息，其输出哈希值总是固定长度的。一般哈希算法计算后的输出值长度比输入消息长度小，因此在实际使用中能更好地进行存储和处理，同时也隐藏了输入消息。第三个特性主要说明哈希值的计算时间不能无限长，否则就没有任何实际使用的意义。

在现实中以哈希函数为基础可以创建各种数据结构，如哈希表。

以求余函数（图2-13）为例，它就是一个简单的哈希函数：

H（x）=xmod 3　（x是大于0的整数）

其中，mod是数学运算符号，表示取模（取余）运算，m=xmody，也可写为m=mod（x，y），表示x整除y得到余数m；H（·）表示哈希函数。

任意大于0的整数x除以3以后，函数值H（x）只有0，1，2三个数值，于是任意的输入产生了固定长度的输出。可以把哈希函数理解为一个压缩机，任意长度的输入经过压缩机处理后吐出一个固定长度的输出。这种转换是一种压缩映射，即将任意长度的消息压缩到某一固定长度。