哈希（Hash）：修订间差异

来自非小号百科
可视化wikitext
0x YU小鱼（留言 | 贡献）
200次编辑
创建页面，内容为“== 简述 == 通过密码学算法将任意大小的数据转换为固定大小的字符串，用于验证数据完整性和唯一性。 == 什么是哈希（Hash）？ == '''哈希（Hash）''' 是一种广泛应用于计算机科学和密码学的技术，用于将任意长度的输入（如数据、文件或消息）通过特定算法转换为固定长度的输出（通常称为哈希值或摘要）。 这种转换过程不可逆，且哈希值具有唯一…”
 
Doge（留言 | 贡献）
453次编辑
无编辑摘要
 
（未显示同一用户的1个中间版本）
第1行： 第1行：
== 简述 ==
'''哈希函数'''（英语：Hash function）又称'''哈希算法'''、散列'''函数'''，是一种从任何一种数据中创建小的数字“指纹”的方法。哈希函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做'''哈希值'''（又叫散列值）（hash values，hash codes，hash sums，或hashes）的指纹。哈希值通常用一个短的随机字母和数字组成的字符串来代表<ref>[https://www.heg-fr.ch/media/lbdfnyd1/schueffelgroenewegbaldegger2019_crypto-encyclopedia_eng.pdf THE CRYPTO ENCYCLOPEDIA Coins, Tokens and Digital Assets from A to Z] Growth Publisher.</ref>。好的哈希函数在输入域中很少出现哈希冲突。如果在哈希表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
通过密码学算法将任意大小的数据转换为固定大小的字符串，用于验证数据完整性和唯一性。


== 什么是哈希（Hash）？ ==
如今，哈希函数也被用来加密存在数据库中的密码（password）字符串，由于哈希算法所计算出来的'''哈希值（Hash Value）'''具有'''不可逆'''（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。
'''哈希（Hash）''' 是一种广泛应用于计算机科学和密码学的技术，用于将任意长度的输入（如数据、文件或消息）通过特定算法转换为固定长度的输出（通常称为哈希值或摘要）。


这种转换过程不可逆，且哈希值具有唯一性、固定性和高效性。
哈希函数与校验和、校验位、指纹、失真压缩、随机化函数、纠错码和密码学有所关联并常被混淆。尽管这些概念在某些方面有所重叠，但每个概念都有其特定的用途和要求，并且在设计和优化上有所不同。哈希函数与这些概念的主要区别在于数据完整性。哈希表可能使用非加密哈希函数，而加密哈希函数则用于网络安全领域，以保护敏感数据，例如密码。


在区块链技术中，哈希函数是保障数据完整性、安全性和链上透明性的基础工具。
== 哈希函数的性质 ==
所有哈希函数都有如下一个基本特性：如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的。这个特性是哈希函数具有确定性的结果，具有这种性质的哈希函数称为单向哈希函数。但另一方面，哈希函数的输入和输出不是唯一对应关系的，如果两个哈希值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“哈希碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出哈希值，然后部分改变输入值，一个具有强混淆特性的哈希函数会产生一个完全不同的哈希值<ref>[http://www.azillionmonkeys.com/qed/hash.html Hash functions.] by Paul Hsieh</ref>。


== 哈希的核心概念 ==
典型的哈希函数都有非常大的定义域，比如SHA-2最高接受(2<sup>64</sup>-1)/8长度的字节字符串。同时哈希函数一定有着有限的值域，比如固定长度的比特串。在某些情况下，哈希函数可以设计成具有相同大小的定义域和值域间的单射。在密码学中，哈希函数必须具有不可逆性。


# '''输入（Input）'''
在哈希表中，哈希函数将一个键作为输入。键与数据或记录相关联，用于在数据存储和检索应用中标识它们。键可以是固定长度的（如整数）或可变长度的（如名字）。在某些情况下，键本身就是数据。哈希函数的输出是一个哈希码，用于索引存放数据或记录（或指向它们的指针）的哈希表。
#* 哈希函数可以接受任意长度的数据（字符串、文件、交易信息等）作为输入。
# '''输出（Output）'''
#* 哈希函数输出的是固定长度的哈希值（通常为 256 位、512 位等），与输入数据大小无关。
#* 示例：使用 SHA-256 算法对字符串 <code>blockchain</code> 进行哈希：
#* 输入："blockchain" 输出："7c1a95e65a2dc66d203d2d8f5f7f8f43c2d845b2efb5d13964e099fa034d3e4d"


'''3.不可逆性（Irreversibility）'''
哈希函数可以视为执行以下三个功能：


通过输出无法还原原始输入，确保数据的安全性。
# '''将可变长度的键转换为固定长度的值'''（通常是机器字长或更小），通过使用诸如加法（ADD）或异或（XOR）等保持奇偶性的操作符进行分组处理；
# '''对键的位进行扰乱'''，使生成的值在键空间中均匀分布；
# '''将键值映射到小于或等于哈希表大小的值'''。


'''4.确定性（Deterministic）'''
一个好的哈希函数需要满足两个基本属性：计算速度非常快，并且尽量减少输出值的重复（碰撞）。哈希函数通过生成理想的概率分布来提高其效率，使访问时间接近于恒定。然而，高的表负载因子、不利的键集和设计不良的哈希函数可能会导致访问时间接近于与表中项目数量成线性关系。


相同的输入始终产生相同的输出。
哈希函数可以设计成在最坏情况下也能提供最佳性能，在高表负载因子下保持良好性能，并在特殊情况下实现键到哈希码的完美（无碰撞）映射。其实现基于奇偶保持位操作（如XOR和ADD）、乘法或除法。


'''5.敏感性（Avalanche Effect）'''
与哈希函数配套的必要机制是'''碰撞解决方法'''，通常使用辅助数据结构（如链表）或系统地探测哈希表中的空槽来解决碰撞问题。


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


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


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


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


# '''SHA 系列（Secure Hash Algorithm）'''
=== 哈希表 ===
#* '''SHA-256'''：区块链领域中最常用的哈希算法，输出 256 位哈希值。
哈希表是哈希函数的一个主要应用，使用哈希表能够快速的按照''关键字''查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，哈希函数必须把按照字母顺序排列的字符串映射到为哈希表的内部数组所建立的索引上。
#* '''SHA-3'''：更现代化的哈希算法，抗攻击能力更强。
# '''MD5（Message Digest Algorithm 5）'''
#* 输出 128 位哈希值，速度快，但安全性不足，容易被破解。
# '''Keccak-256'''
#* 用于以太坊网络，是 SHA-3 的变体，生成钱包地址和验证交易。
# '''RIPEMD-160'''
#* 输出 160 位哈希值，用于比特币的地址生成。


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


# '''固定长度输出'''
一个好的哈希函数（包括大多数加密哈希函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机哈希函数不太会出现非常高的冲突率。但是，少量的可以估计的冲突在实际状况下是不可避免的（参考生日悖论或鸽洞原理）。
#* 不论输入数据长度是多少，输出的哈希值长度始终一致。
# '''唯一性'''
#* 不同的输入生成不同的哈希值，碰撞概率极低。
# '''抗篡改性'''
#* 任何对输入的修改都会导致哈希值完全改变。
# '''无碰撞性'''
#* 两个不同的输入几乎不可能产生相同的哈希值（即哈希碰撞）。
# '''抗逆性'''
#* 哈希函数的计算是单向的，无法通过哈希值反推出原始输入。


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


# '''区块的哈希值'''
在很多情况下，heuristic哈希函数所产生的冲突比随机哈希函数少的多。Heuristic函数利用了相似关键字的相似性。例如，可以设计一个heuristic函数使得像<code>FILE0000.CHK</code>, <code>FILE0001.CHK</code>, <code>FILE0002.CHK</code>，等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机哈希函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的哈希函数表意味着查找操作会退化为费时的线性搜索。
#* 区块链中，每个区块都有一个哈希值，标识该区块的数据摘要。
#* 例如，比特币区块头包含上一个区块的哈希值，确保区块链的链式结构。
# '''交易数据的完整性验证'''
#* 区块中存储的每笔交易都会经过哈希处理，确保交易数据无法被篡改。
# '''Merkle 树（默克尔树）'''
#* 通过哈希算法构建树状结构，将大量交易数据压缩成一个根哈希值，用于快速验证大批数据的完整性。
# '''数字签名和公钥生成'''
#* 哈希算法在生成钱包地址和数字签名中起到关键作用。
# '''共识机制'''
#* 比特币等区块链采用工作量证明（Proof of Work, PoW）共识机制，通过哈希运算进行挖矿。


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


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


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


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


2.改变输入数据中的一个字符（如 <code>Hello, Web3!</code> 改为 <code>Hello, Web3.</code>），生成的哈希值为：
=== 专门用途 ===


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


可以看到，仅一个字符的改变导致输出哈希值发生巨大变化，验证了哈希函数的敏感性和抗篡改性。
== 目前常见的哈希算法 ==
{| class="wikitable"
!算法名称
!输出大小(bits)
!内部大小
!区块大小
!长度大小
!字符尺寸
!碰撞情形
|-
|'''HAVAL'''
|256/224/192/160/128
|256
|1024
|64
|32
|是
|-
|'''MD2'''
|128
|384
|128
|No
|8
|大多数
|-
|'''MD4'''
|128
|128
|512
|64
|32
|是
|-
|'''MD5'''
|128
|128
|512
|64
|32
|是
|-
|'''PANAMA'''
|256
|8736
|256
|否
|32
|是
|-
|'''RadioGatún'''
|任意长度
|58字
|3字
|否
|1-64
|否
|-
|'''RIPEMD'''
|128
|128
|512
|64
|32
|是
|-
|'''RIPEMD-128/256'''
|128/256
|128/256
|512
|64
|32
|否
|-
|'''RIPEMD-160/320'''
|160/320
|160/320
|512
|64
|32
|否
|-
|'''SHA-0'''
|160
|160
|512
|64
|32
|是
|-
|'''SHA-1'''
|160
|160
|512
|64
|32
|有缺陷
|-
|'''SHA-256/224'''
|256/224
|256
|512
|64
|32
|否
|-
|'''SHA-512/384'''
|512/384
|512
|1024
|128
|64
|否
|-
|'''Tiger（2）-192/160/128'''
|192/160/128
|192
|512
|64
|64
|否
|-
|'''WHIRLPOOL'''
|512
|512
|512
|256
|8
|否
|}


== 哈希的优势与限制 ==
=== Rabin-Karp字符串搜索算法 ===
Rabin-Karp字符串搜索算法是一个相对快速的字符串搜索算法，它所需要的平均搜索时间是O(n)。这个算法是建立在使用哈希来比较字符串的基础上的。


==== 优势 ====
== 参考链接 ==
 
<references />
# '''高效性'''：适合快速处理大规模数据。
# '''安全性'''：哈希不可逆，保障数据的隐私和完整性。
# '''可靠性'''：哈希碰撞几率极低。
 
==== 限制 ====
 
# '''算法强度依赖'''：较弱的哈希算法（如 MD5）容易被破解。
# '''碰撞可能性'''：虽然几率极低，但理论上仍可能发生。
# '''量子计算威胁'''：未来的量子计算可能破解现有哈希算法。
 
== 哈希在未来的发展 ==
 
# '''抗量子计算的哈希算法'''
#* 研究和应用抗量子安全的新型哈希算法，如基于格理论的哈希函数。
# '''优化区块链性能'''
#* 提升现有哈希算法在区块链中的效率，降低计算成本。
# '''多领域应用扩展'''
#* 哈希技术将在 Web3、物联网、数据隐私等领域发挥更大作用。
 
== 总结 ==
哈希是一种高效、安全、不可逆的数据处理技术，是区块链、密码学和现代信息技术的重要支柱。在区块链系统中，哈希不仅保障了数据的完整性和透明性，还构建了区块链的核心链式结构。理解哈希的工作原理及其在区块链中的应用，对于深入了解去中心化技术至关重要。

2024年12月10日 (二) 02:12的最新版本

哈希函数（英语：Hash function）又称哈希算法、散列函数，是一种从任何一种数据中创建小的数字“指纹”的方法。哈希函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做哈希值（又叫散列值）（hash values，hash codes，hash sums，或hashes）的指纹。哈希值通常用一个短的随机字母和数字组成的字符串来代表[1]。好的哈希函数在输入域中很少出现哈希冲突。如果在哈希表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

如今，哈希函数也被用来加密存在数据库中的密码（password）字符串，由于哈希算法所计算出来的哈希值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。

哈希函数与校验和、校验位、指纹、失真压缩、随机化函数、纠错码和密码学有所关联并常被混淆。尽管这些概念在某些方面有所重叠，但每个概念都有其特定的用途和要求，并且在设计和优化上有所不同。哈希函数与这些概念的主要区别在于数据完整性。哈希表可能使用非加密哈希函数，而加密哈希函数则用于网络安全领域，以保护敏感数据，例如密码。

哈希函数的性质[编辑 | 编辑源代码]

所有哈希函数都有如下一个基本特性：如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的。这个特性是哈希函数具有确定性的结果，具有这种性质的哈希函数称为单向哈希函数。但另一方面，哈希函数的输入和输出不是唯一对应关系的，如果两个哈希值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“哈希碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出哈希值，然后部分改变输入值，一个具有强混淆特性的哈希函数会产生一个完全不同的哈希值[2]。

典型的哈希函数都有非常大的定义域，比如SHA-2最高接受(264-1)/8长度的字节字符串。同时哈希函数一定有着有限的值域，比如固定长度的比特串。在某些情况下，哈希函数可以设计成具有相同大小的定义域和值域间的单射。在密码学中，哈希函数必须具有不可逆性。

在哈希表中，哈希函数将一个键作为输入。键与数据或记录相关联，用于在数据存储和检索应用中标识它们。键可以是固定长度的（如整数）或可变长度的（如名字）。在某些情况下，键本身就是数据。哈希函数的输出是一个哈希码，用于索引存放数据或记录（或指向它们的指针）的哈希表。

哈希函数可以视为执行以下三个功能：

  1. 将可变长度的键转换为固定长度的值（通常是机器字长或更小），通过使用诸如加法（ADD）或异或（XOR）等保持奇偶性的操作符进行分组处理；
  2. 对键的位进行扰乱，使生成的值在键空间中均匀分布；
  3. 将键值映射到小于或等于哈希表大小的值。

一个好的哈希函数需要满足两个基本属性：计算速度非常快，并且尽量减少输出值的重复（碰撞）。哈希函数通过生成理想的概率分布来提高其效率，使访问时间接近于恒定。然而，高的表负载因子、不利的键集和设计不良的哈希函数可能会导致访问时间接近于与表中项目数量成线性关系。

哈希函数可以设计成在最坏情况下也能提供最佳性能，在高表负载因子下保持良好性能，并在特殊情况下实现键到哈希码的完美（无碰撞）映射。其实现基于奇偶保持位操作（如XOR和ADD）、乘法或除法。

与哈希函数配套的必要机制是碰撞解决方法，通常使用辅助数据结构（如链表）或系统地探测哈希表中的空槽来解决碰撞问题。

哈希函数的应用[编辑 | 编辑源代码]

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

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

保护资料[编辑 | 编辑源代码]

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

确保传递真实的信息[编辑 | 编辑源代码]

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

哈希表[编辑 | 编辑源代码]

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

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

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

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

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

错误校正[编辑 | 编辑源代码]

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

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

语音识别[编辑 | 编辑源代码]

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

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

专门用途[编辑 | 编辑源代码]

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

目前常见的哈希算法[编辑 | 编辑源代码]

算法名称 输出大小(bits) 内部大小 区块大小 长度大小 字符尺寸 碰撞情形
HAVAL 256/224/192/160/128 256 1024 64 32 是
MD2 128 384 128 No 8 大多数
MD4 128 128 512 64 32 是
MD5 128 128 512 64 32 是
PANAMA 256 8736 256 否 32 是
RadioGatún 任意长度 58字 3字 否 1-64 否
RIPEMD 128 128 512 64 32 是
RIPEMD-128/256 128/256 128/256 512 64 32 否
RIPEMD-160/320 160/320 160/320 512 64 32 否
SHA-0 160 160 512 64 32 是
SHA-1 160 160 512 64 32 有缺陷
SHA-256/224 256/224 256 512 64 32 否
SHA-512/384 512/384 512 1024 128 64 否
Tiger（2）-192/160/128 192/160/128 192 512 64 64 否
WHIRLPOOL 512 512 512 256 8 否

Rabin-Karp字符串搜索算法[编辑 | 编辑源代码]

Rabin-Karp字符串搜索算法是一个相对快速的字符串搜索算法，它所需要的平均搜索时间是O(n)。这个算法是建立在使用哈希来比较字符串的基础上的。

参考链接[编辑 | 编辑源代码]

  1. ↑ THE CRYPTO ENCYCLOPEDIA Coins, Tokens and Digital Assets from A to Z Growth Publisher.
  2. ↑ Hash functions. by Paul Hsieh
检索自“https://zh.feixiaohao.wiki/index.php?title=哈希（Hash）&oldid=854”