散列(Hash)

Hash-nomal

通过一些计算，即散列函数（Hash function），把关键码值映射到数组中的特定位置来访问记录，这个过程称为散列。通过散列函数得到的固定长度的输出值就是散列值，一般关键码范围中的值比散列值多，有些不同关键码会被映射到相同的散列值的槽里，这种现象称为冲突（碰撞）。

1. 散列的用途

1.1 散列表

哈希函数用于散列表，可以快速定位给定其搜索关键字（词条）的数据记录（例如字典定义）。具体地，哈希函数用于将搜索关键字映射到列表; 索引给出哈希表中应存储相应记录的位置。哈希表也用于实现关联数组和动态集。

通常，哈希函数的域（可能的键的集合）大于其范围（不同表索引的数量），因此它将映射几个不同的键到同一个索引。那么，哈希表的每个插槽与（隐含或明确地）一个相关的一系列的记录，而不是单一的记录。因此，哈希表的每个时隙通常称为存储桶，散列值也称为桶列表[ 需要引用 ]或桶索引。

因此，哈希函数只会在记录的位置提示。然而，在半满表中，好的散列函数通常将搜索缩小到只有一个或两个条目。

编写完整的哈希表实现的人员会选择一个特定的哈希函数，例如Jenkins哈希或Zobrist哈希，并且独立地选择哈希表冲突解决方案，例如合并散列，杜鹃哈希或跳房子散列散列。

1.2 缓存

散列函数也用于为缓存介质中存储的大型数据集构建高速缓存。缓存通常比散列搜索表更简单，因为任何冲突都可以通过丢弃或写回两个较小的碰撞项来解决。这也用于文件比较。

1.3 保护数据

散列值可用于唯一标识秘密信息。这要求散列函数是防冲突的，这意味着很难找到将生成相同哈希值的数据。这些功能分为加密哈希函数和可证明的安全哈希函数。第二类中的功能是最安全的，但对于大多数实际目的也是太慢。碰撞抵抗是通过产生非常大的哈希值来实现的。例如，最广泛使用的密码散列函数之一的SHA-1生成160位值。

1.4 查找重复记录

在大型未分类文件中存储记录时，可以使用散列函数将每个记录映射到表T中的索引，并在每个存储桶T [ i ]中收集具有相同散列值的所有记录的编号列表我。一旦表完成，任何两个重复的记录将结束在同一个桶中。然后可以通过扫描包含两个或多个成员的每个桶T [ i ]，获取这些记录并进行比较来找到重复项。使用适当大小的表，该方法可能比任何替代方法（例如排序文件并比较所有连续对）快得多。

1.5 查找类似记录

散列函数也可用于定位与给定键相似但不完全相同的表记录; 或具有类似键的大文件中的记录对。为此，需要一个散列函数，将类似的键映射到不同于m的散列值，其中m是一个小整数（例如1或2）。如果使用这样的哈希函数建立所有记录号的表T，则类似的记录将在同一个桶或附近的桶中结束。然后，只需要检查每个桶T [ i ]中的记录与桶T [ i + k ]中的记录，其中k的范围在-m和 m。

该类包括所谓的声音指纹算法，用于在大量音频文件集合中定位类似声音的条目。对于此应用程序，散列函数必须尽可能不敏感，数据捕获或传输错误，以及时间和体积更改，压缩等简单的更改。

1.6 错误校正

使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。

对于错误校正，假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定 H(x) 和 x+s，那么只要s足够小，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德所罗门码。

1.7 在信息安全上的应用

1.7.1 验证文件或消息的完整性

使用HMAC（哈希消息认证码），以一个密钥和一个消息作为输入，生成一个消息摘要作为输出。通过比较传输之前和传输之后的消息摘要来完成校验。

HMAC的作用：
（1）验证TPM接受的授权数据和认证数据；
（2）确认TPM接受到的命令请求是已授权的请求，并且，命令在传送的过程中没有被改动过。

过程简述：首先根据消息内容提取一个随机长度的信息（可以直接利用关键字，也可以对其进行折叠、平方取中等运算），然后对信息进行补位，使信息的字节长度是32的倍数，经过一系列补位和附加值处理，产生一个128位的消息摘要。

1.7.2 数字签名

Hash签名也称为数字摘要法（digital digest）、数字指纹法（digital finger print）。
最常见的实现方法是建立在公钥密码体制和单向安全散列函数的组合基础上的。

过程简述：将要发送的消息作为输入，用哈希算法得到此消息的消息摘要，并用自己的私钥加密此消息摘要，然后将消息本身和加密后的消息摘要一同发送出去。接收方收到后利用公钥解密加密消息得到消息摘要，然后通过接收到的消息本身利用哈希算法得到用于验证的消息摘要，比较这两个消息摘要是否相同，从而对消息发送者进行身份验证。

1.7.3 密码验证

使用MD5、SHA1等单向Hash算法可以让原密码无法通过计算还原。
过程简述：储存原密码的哈希摘要，当需要进行身份验证时，用户输入的密码被散列并鱼储存的散列进行比较。

1.7.4 伪随机生成和密钥推导

散列函数也可用于生成伪随机位，或者从单个安全密钥或密码导出新密钥或密码。

2. Hash构造函数的方法 详细内容

2.1 直接定址法

2.2 数字分析法

2.3 折叠法

2.4 平方取中法

2.5 减去法

2.6 基数转换法

2.7 除留余数法

2.8 随机数法

2.9 随机乘数法

2.10 字符串数值哈希法

2.11 旋转法

3. 散列函数 详细内容

3.1 除法散列法

3.2 乘法散列法

3.3 全域散列法

3.4 平方散列法

3.5 斐波那契（Fibonacci）散列法

3.6 加法Hash

3.7 位运算Hash

3.8 乘法Hash

3.9 除法Hash

3.10 混合Hash

3.11 数组hash

4. 冲突解决方法 详细内容

4.1 链接法（开散列方法）

4.2 开放寻址法（闭散列方法）

4.2.1 线性探查法(Linear Probing)

4.2.2 线性补偿探测法

4.2.3 随机探测

4.3 再散列法

4.4 建立公共溢出区

5. 散列算法

5.1 MD5算法

MD5即 Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一（又译摘要算法、哈希算法），主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。

MD5算法具有以下特点：
1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。
2、容易计算：从原数据计算出MD5值很容易。
3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。
4、强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

MD5介绍

5.2 SHA-1算法

SHA (Secure Hash Algorithm，译作安全散列算法) 是美国国家安全局 (NSA) 设计，美国国家标准与技术研究院(NIST) 发布的一系列密码散列函数。正式名称为 SHA 的家族第一个成员发布于 1993年。然而人们给它取了一个非正式的名称 SHA-0 以避免与它的后继者混淆。两年之后， SHA-1，第一个 SHA 的后继者发布了。 另外还有四种变体，曾经发布以提升输出的范围和变更一些细微设计： SHA-224, SHA-256, SHA-384 和 SHA-512 (这些有时候也被称做 SHA-2)。

参考资料

1. 维基百科。哈希函数，加密散列函数。
2. 百度百科。MD5、SHA-1
3. 算法导论。第十一章散列表，机械工业出版社。
4. 数据结构与算法分析第三版（C++版）。第九章，散列方法。
5. 浅析几种典型的哈希算法
6. hash算法原理详解
7. 浅谈散列
8. 几种经典的hash算法
9. 解决哈希（HASH）冲突的主要方法