哈希是一种使用频率很高的数据结构,通常来说,哈希是一个定义域到值域的函数,对于任意输入的定义域内的某个值,返回一个值域内的值。因为它是一个函数,所以具备数学中函数定义赋予的性质。简单来说,一个定义域内的值只能对应到一个值域上的值,但是一个值域上的值可能有多个定义域的值。
作为数据结构的哈希,需要尽可能的把定义域内相邻的输入给分散到值域空间里面去,越散越好。学过计算机的都知道,哈希提供了近似算法为O(1)复杂度的访问。常见的基于哈希的数据结构主要是哈希集合和哈希字典。
任何哈希都存在着碰撞的问题。所谓的碰撞是指不同定义域内的值,映射到同一个值域的值上。所以我们常用的数据结构都有解决哈希碰撞的办法。因为篇幅有限,这里我们就不展开讨论了。
哈希在数据库内和分布式系统内也广泛使用,不但用在分布式系统的数据分区上,也用在数据库系统内的”join”的实现上。事实上排序和哈希这两种算法构成了绝大多数分布式数据处理系统算法的基础。
密码学上的哈希和普通的哈希比起来,主要是强度上的不同,它有以下几个特性:
1、给定定义域的输入,很容易算出值域的输出来。但是给定值域的输出要找到定义域对应的输入则是一件几乎不可能的事情。我们定义几乎不可能的事情可以理解为一个人几辈子的时间都无法破解
2、对定义域的输入做微小的变动,都会导致值域的输出有巨大的变动。这也是普通哈希需要具备的性质。只是密码学上的哈希对此强调的更多
3、密码学上的哈希还要有抗碰撞性。简单来说,如果对于定义域内给定的两个不同的输入,它们对应的输出也不同,那么哈希函数具有强碰撞性。
如果给定一个输入,在合理的时间内,无法找到另外一个输入产生同样的输出,那么这个哈希函数就具备了密码学上的抗碰撞性。前者是绝对不存在,后者是无法轻易计算出来
4、密码学上哈希函数还应该具备所谓的难题友好性特点。具体来说,给定值域的值去寻找特定的输入,没有什么办法比暴力穷举更有效的哈希算法成为具备难题友好性。这个特性对比特币很重要
密码学上的哈希最为重要的特点是对一段比特流生成摘要。简单来说如果我们把比特流作为输入,把哈希的结果作为输出的话,那么输出就是一个合法的摘要。如果我们把比特流和摘要同时发布出去。假定哈希无法更改的前提下,我们可以验证比特流是否被篡改。为什么可以这样做呢?
给定不同的输入,哈希函数会产生不同的结果。密码学的哈希不可能在合理的时间内从输出反推出输入,也不可能找到另外一个输入可以产生相同的输出。所以只要我们有办法保证摘要无法被篡改,我们就可以使用下面的步骤来判断比特流是否被篡改:
1、用哈希算法对给定的比特流算哈希
2、比较算出来的哈希和拿到的哈希是否一致,一致表示没有篡改,否则有篡改
密码学的哈希这个特性被广泛用来校验接收到的东西是否在传输途中被篡改。这也是比特币账本保证记录被篡改以后可以立刻检测到的基础。