散列函數
维基百科，自由的百科全书
散列函数（或散列算法）是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
目录 |
[编辑] 散列函数的性质
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
典型的散列函数都有无限定义域,比如任意长度的字节字符串,和有限的值域,比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一映射。一一映射的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
[编辑] 散列函数的应用
由于散列函数的应用的多样性，它们经常是专为某一应用而设计的。例如，加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个“单向”操作：对于给定的散列值，没有实用的方法可以计算出一个原始输入，也就是说很难伪造。为加密散列为目的设计的函数，如MD5，被广泛的用作检验散列函数。這樣軟件下載的時候，就會對照驗證代碼之後才下載正確的文件部分。此代碼有可能因為環境因素的變化，如機器配置或者IP地址的改變而有變動。以保證源文件的安全性。
错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候，可以用相对较短的散列值来验证任意长度的数据是否被更改过。
[编辑] 加密
- Main article: 加密散列函数
一个典型的加密单向函数是“非对称”的，并且由一个高效的散列函数构成；一个典型的加密暗门函数是“对称”的，并且由一个高效的随机函数构成。
[编辑] 散列表
- Main article: 哈希表
散列表是散列函数的一个主要应用，使用散列表能够快速的按照关键字查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所建立的索引上。
散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上（参考完美散列），因为这样能够保证直接访问表中的每一个数据。
一个好的散列函数（包括大多数加密散列函数）具有均匀的真正随机输出，因而平均只需要一两次探测（依赖于装填因子）就能找到目标。同样重要的是，随机散列函数几乎不可能出现非常高的冲突率。但是，少量的可以估计的冲突在实际狀況下是不可避免的（参考生日悖论）。
在很多情况下，heuristic散列函数所产生的冲突比随机散列函数少的多。Heuristic函数利用了相似关键字的相似性。例如，可以设计一个heuristic函数使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK, 等等这样的文件名映射到表的连续指针上，也就是说这样的序列不会发生冲突。相比之下，对于一组好的关键字性能出色的随机散列函数，对于一组坏的关键字经常性能很差，这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。
Aside from minimizing collisions, the hash function for a hash table should also be fast relative to the cost of retrieving a record in the table, as the goal of minimizing collisions is minimizing the time needed to retrieve a desired record. Consequently, the optimal balance of performance characteristics depends on the application.
One of the most respected hash functions for use in typical hash tables is Bob Jenkins' LOOKUP2 hash function, published in an article in Dr. Dobb's Journal. The hash function performs well as long as there is no adversary, for it is trivially reversible and useless as a cryptographic hash function.
[编辑] 错误校正
- Main article: 错误校正与检测
使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。
对于错误校正，假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。 对于一个信息串的微扰可以被分为两类，大的（不可能的）错误和小的（可能的）错误。我们对于第二类错误重新定义如下，假如给定 H(x) 和 x+s，那么只要s足够小，我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类：循环冗余校验和里德所罗门码。
[编辑] 语音识别
对与像从一个已知列表中匹配一个MP3文件这样的应用，一种可能的方案是使用传统的散列函数——例如MD5，但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同（从音频文件的二进制数据来看）的音频文件，但是要找到全部相同（从音频文件的内容来看）的音频文件就需要使用其他更高级的算法了。
那些并不紧随IT工业潮流的人往往能反其道而行之，对于那些微小差异足够鲁棒的散列函数确实存在。现存的绝大多数散列算法都是不够鲁棒的，但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码，并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐，并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名（需要收取一定的费用）。
[编辑] Rabin-Karp 字符串搜索算法
Rabin-Karp 字符串搜索算法 是一个相对快速的字符串搜索算法，它所需要的平均搜索时间是O(n).这个算法是建立在使用散列来比较字符串的基础上的。
[编辑] 术语来源
The term "hash" apparently comes by way of analogy with its standard meaning in the physical world, to
"chop and mix." Knuth notes that Hans Peter Luhn of IBM appears to have been the first to use the concept,
in a memo dated January 1953; the term hash came into use some ten years later.
In the SHA-1 algorithm, for example, the domain is "flattened" and "chopped" into "words" which are
then "mixed" with one another using carefully chosen mathematical functions. The range ("hash value")
is made to be a definite size, 160 bits (which may be either smaller or larger than the domain),
through the use of modular division.
[编辑] 参阅
- Cryptography
- Cryptographic hash function
- HMAC
- Geometric hashing
- Message digest
- Perfect hash function
- Rabin-Karp string search algorithm
- Zobrist hashing
- Bloom filter
- Hash table
- Hash list
- Hash tree
- Coalesced hashing
- 交叉点表
[编辑] References
[编辑] 外部链接
- General purpose hash function algorithms C/C++/Pascal/Java/Ruby
- Hash Functions for Hash Table Lookup by Bob Jenkins
- 散列函数 by Paul Hsieh
- 什么是散列函数? from RSA Laboratories
- Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, etc. hashing algorithms
- Crypto-Toolbox - Online cryptography, hashing and PIN block sanity checking for EftPos developers.
