散列函數：修订间差异

{{mergefromredirect|散列}}

'''[[散列]]函数'''（{{lang-en|Hash function}}）又称-{zh-cn:'''散列算法'''、'''哈希函数'''; zh-tw:'''雜湊演算法'''}-，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该[[函数]]将数据打乱混合，重新创建一个叫做'''散列值'''（又叫'''哈希值'''）（{{lang|en|hash values}}，{{lang|en|hash codes}}，{{lang|en|hash sums}}，或{{lang|en|hashes}}）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。<ref>{{Cite book|title=The Crypto Encyclopedia: Coins, Tokens and Digital Assets from A to Z|last=Schueffel|first=Patrick|publisher=Growth Publisher|year=2019|isbn=|location=Bern, 瑞士|pages=|url=https://www.heg-fr.ch/media/lbdfnyd1/schueffelgroenewegbaldegger2019_crypto-encyclopedia_eng.pdf|last2=Groeneweg|first2=Nikolaj|last3=Baldegger|first3=Rico|access-date=2020-02-18|archive-date=2019-08-28|archive-url=https://web.archive.org/web/20190828012710/https://www.heg-fr.ch/media/lbdfnyd1/schueffelgroenewegbaldegger2019_crypto-encyclopedia_eng.pdf|dead-url=yes}}</ref>好的散列函数在输入域中很少出现[[碰撞_(计算机科学)|散列冲突]]。如果在[[散列表]]和[[数据处理]]中，不抑制冲突来区别数据，会使得[[数据库记录]]更难找到。

由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，[[加密散列函数]]假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个「单向」操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如[[SHA-2]]，被广泛的用作检验散列函数。這樣軟件下載的時候，就會對照驗證代碼之後才下載正確的文件部分。此代碼有可能不会因為環境因素的變化，如機器配置或者IP地址的改變而有變動。以保證源文件的安全性。

雜湊值可用於唯一地識別機密資訊。這需要雜湊函式是抗碰撞(collision-resistant)的，意味著很難找到產生相同雜湊值的資料。雜湊函式分類為密碼雜湊函式和可證明的安全雜湊函式。第二類中的函式最安全，但對於大多數實際目的而言也太慢。透過生成非常大的雜湊值來部分地實現抗碰撞。例如，SHA-2256是最廣泛使用的密碼雜湊函式之一，它生成256位元值的雜湊值。

那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够健壮的散列函数确实存在。现存的绝大多数散列算法都是不够健壮的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的健壮性。有一个实际的例子是[[Shazam Entertainment|Shazam]][http://www.shazam.com/] {{Wayback|url=http://www.shazam.com/ |date=20080821140538 }} 服务。用户可以用手机打开其app，并将话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名。

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

* [[交叉点表SHA家族]]

=== 参考资料来源 ===

* [http://www.sigma.me/2011/09/13/hash-and-bloom-filter.html Hash和Bloom Filter介绍] {{Wayback|url=http://www.sigma.me/2011/09/13/hash-and-bloom-filter.html |date=20111020130547 }}

* [http://www.partow.net/programming/hashfunctions/index.html General purpose hash function algorithms C/C++/Pascal/Java/Ruby] {{Wayback|url=http://www.partow.net/programming/hashfunctions/index.html |date=20060618031431 }}

* [http://burtleburtle.net/bob/hash/evahash.html Hash Functions for Hash Table Lookup] {{Wayback|url=http://burtleburtle.net/bob/hash/evahash.html |date=20160112012118 }} by Bob Jenkins

* [http://www.azillionmonkeys.com/qed/hash.html 散列函数] {{Wayback|url=http://www.azillionmonkeys.com/qed/hash.html |date=20060615013036 }}by Paul Hsieh

* [http://3amsystems.com/monetics/crypto.php Crypto-Toolbox] {{Wayback|url=http://3amsystems.com/monetics/crypto.php |date=20080828022508 }} - Online cryptography, hashing and PIN block sanity checking for EftPos developers.

* [https://web.archive.org/web/20180620001154/https://passwordsgenerator.pro/sha256 Hash值在线计算]