hash算法

有一点你搞错了。Hash算法不是为了快速找出相同的元素，而是为了快速判断两个元素不相等。

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。

例如：设计一个针对字符串的Hash算法，简单地返回字符串的首字母：

def Hash_string(str):

return str[0]

那么：

Hash_string(a)=Hash(gfdgfd)=g

Hash_string(b)=Hash(xzcfs)=x

这样就可以最快速地判断出两个字符串不相等。这个Hash算法常用于将大量文件分散存储。

对于首字母相同的两个字符串，本算法得到的Hash值肯定相同，这就是出现了命中冲突。解决命中冲突有很多策略，比如：再散列法、链地址法、公共溢出法……等等。

一个好的Hash算法，应该保证高命中率和均匀分布。

常见 HASH 算法：

HASH 算法主要应用：

1）文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。

2）数字签名 　 　

Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

3）鉴权协议

如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

数字签名签署和验证数据的步骤如图所示：

PKCS1 和 PKCS7 标准格式的签名：

1. PKCS1签名：即裸签名，签名值中只有签名信息。

2. PKCS7签名：签名中可以带有其他的附加信息，例如签名证书信息、签名原文信息、时间戳信息等。

PKCS7 的 attached 和 detached 方式的数字签名：

1. attached 方式是将签名内容和原文放在一起，按 PKCS7 的格式打包。PKCS7的结构中有一段可以放明文，但明文必需进行ASN.1编码。在进行数字签名验证的同时，提取明文。这里的明文实际上是真正内容的摘要。

2. detached 方式打包的 PKCS7格式包中不包含明文信息。因此在验证的时候，还需要传递明文才能验证成功。同理，这里的明文实际上是真正内容的摘要。

---