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

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

散列函数的性质

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

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

散列函数的应用

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

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

冲突解决

  • 开放地址法:

    以发生冲突的哈希地址为输入,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法

    。有以下几种方式:

    • 线性探查法:从发生冲突的地址开始,依次探查下一个地址,直到找到一个空闲单元。
    • 平方探查法:设冲突地址为d0,则探查序列为:d0+1^2,d0-1^2,d0+2^2…
  • 拉链法:

    把所有的同义词用单链表链接起来。在这种方法下,哈希表每个单元中存放的不再是元素本身,而是相应同义词单链表的头指针。HashMap就是使用这种方法解决冲突的。