Hash（计算机算法概念）

Hash（计算机算法概念）

Hash （计算机算法概念） 次浏览 | 2022.11.27 16:56:56 更新 来源 ：互联网 精选百科 本文由作者推荐 Hash计算机算法概念

Hash，一般翻译做“散列”，也有直接音译为”哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

中文名

哈希

英文名

Hash

表示

任意长度的输入

应用领域

计算机算法领域

别名

散列

简介

若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个事先建立的表为散列表。

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

性质

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。

函数

·直接取余法：f(x):=x mod maxM; maxM一般是不太接近2^t的一个质数。

·乘法取整法：f(x):=trunc((x/maxX)*maxlongit)mod maxM，主要用于实数。

·平方取中法：f(x):=(x*x div 1000)mod1000000);平方后取中间的，每位包含信息比较多。

构造方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

1．直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=a·key+b，其中a和b为常数（这种散列函数叫做自身函数）

2．数字分析法

3．平方取中法

4．折叠法

5．随机数法

6．除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

算法

（1)MD4

MD4(RFC 1320)是MIT的Ronald L. Rivest在1990年设计的，MD是Message Digest（消息摘要）的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于32位操作数的位操作来实现的。

（2)MD5

MD5(RFC1321)是Rivest于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与MD4相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

（3)SHA-1及其他

SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1设计时基于和MD4相同原理,并且模仿了该算法。

参考资料