编辑“哈希（Hash）”（章节）

== 哈希函数的应用 ==
由于哈希函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密哈希函数假设存在一个要找到具有相同哈希值的原始输入的敌人。一个设计优秀的加密哈希函数是一个“单向”操作：对于给定的哈希值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密哈希为目的设计的函数，如SHA-2，被广泛的用作检验哈希函数。这样软件下载的时候，就会对照验证代码之后才下载正确的文件部分。此代码不会因为环境因素的变化，如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。

错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当哈希函数被用于校验和的时候，可以用相对较短(但不能短于某个安全参数, 通常不能短于160位)的哈希值来验证任意长度的数据是否被更改过。

=== 保护资料 ===
哈希值可用于唯一地识别机密信息。这需要哈希函数是抗碰撞(collision-resistant)的，意味着很难找到产生相同哈希值的资料。哈希函数分类为密码哈希函数和可证明的安全哈希函数。第二类中的函数最安全，但对于大多数实际目的而言也太慢。透过生成非常大的哈希值来部分地实现抗碰撞。例如，SHA-256是最广泛使用的密码哈希函数之一，它生成256比特值的哈希值。

=== 确保传递真实的信息 ===
消息或数据的接受者确认消息是否被篡改的性质叫数据的真实性，也称为完整性。发信人通过将原消息和哈希值一起发送，可以保证真实性。

=== 哈希表 ===
哈希表是哈希函数的一个主要应用，使用哈希表能够快速的按照''关键字''查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，哈希函数必须把按照字母顺序排列的字符串映射到为哈希表的内部数组所建立的索引上。

哈希表哈希函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上（参考完美哈希），因为这样能够保证直接访问表中的每一个数据。

一个好的哈希函数（包括大多数加密哈希函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机哈希函数不太会出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论或鸽洞原理）。

* '''链式哈希'''：每个槽是一个链表或链的头部，碰撞的项会被添加到链中。链表可以保持随机顺序并线性搜索，或按顺序排列，或者按访问频率自排序以加速访问。
* '''开放地址哈希'''：从已占用的槽开始以指定方式探测表，通常采用线性探测、二次探测或双重哈希，直到找到一个空槽或探测完整个表（溢出）。搜索数据项时遵循相同的程序，直到找到目标项、找到空槽或探测完整个表（数据项不在表中）。

在很多情况下，heuristic哈希函数所产生的冲突比随机哈希函数少的多。Heuristic函数利用了相似关键字的相似性。例如，可以设计一个heuristic函数使得像<code>FILE0000.CHK</code>, <code>FILE0001.CHK</code>, <code>FILE0002.CHK</code>，等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机哈希函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的哈希函数表意味着查找操作会退化为费时的线性搜索。

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

校正错误时，至少会对可能出现的扰动大致假定一个分布模式。对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定H（x）和x+s，那么只要s足够小，我们就能有效的计算出x。那样的哈希函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德-所罗门码。

=== 语音识别 ===
对于像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的哈希函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。

那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够健壮的哈希函数确实存在。现存的绝大多数哈希算法都是不够健壮的，但是有少数哈希算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的健壮性。有一个实际的例子是Shazam[1] （页面存档备份，存于互联网档案馆） 服务。用户可以用手机打开其app，并将话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的哈希值进行比较。用户就能够收到被识别的音乐的曲名。

=== 专门用途 ===

* '''缓存'''：哈希函数还用于为存储在慢速介质上的大型数据集构建缓存。缓存通常比哈希搜索表更简单，因为任何碰撞都可以通过丢弃或回写较旧的冲突项来解决。
* '''布隆过滤器'''：哈希函数是布隆过滤器的核心组成部分，布隆过滤器是一种空间高效的概率数据结构，用于测试某个元素是否是集合的成员。
* '''几何哈希（或网格方法）'''：这是哈希的一种特殊情况。在这些应用中，所有输入组成一个度量空间，而哈希函数可被解释为将该空间划分为一个网格单元。哈希表通常是一个具有两个或多个索引的数组（称为网格文件、网格索引、桶网格等），哈希函数返回一个索引元组。这一原理广泛用于计算机图形学、计算几何学以及许多其他学科，用于解决平面或三维空间中的邻近问题，例如在点集间查找最近点对、在形状列表中寻找相似形状、在图像数据库中查找相似图像等。
* '''关联数组与动态集合'''：哈希表还用于实现关联数组和动态集合。