工作证明
在更不寻常的哈希用法中,有一种思想是比特币的工作证明算法。在这种场景下,有一块数据需要发布,在服务器声称验证该事务之前,它必须找到一个数据项(译注:也称为验证码,该计算生成block过程被称为“挖金矿”,因为计算会得到一定的奖励),这个数据项加到这个数据块的时候,采用的是其哈希值,且其中含有一个给定数目的零。由于逆向计算哈希函数不容易,唯一的办法就是加上估计数据,并计算哈希值,直到结果具有给定数目的零。这个过程需要时间,这也意味着非常有可能只有一个服务器最先找到这个结果——这样就避免了多个服务器验证这个数据块的问题。 锦上添花的是,这个算法面临着更优异的硬件性能。它包括,通过测量解决哈希问题的平均时间来给出反馈,以及根据需要来增加额外的零。你可以证明,找到一些数据加给这个数据块,然后在哈希算法中得出n个零,其中需要的时间随n呈指数级变化。用其他话来说,这个问题的难度是可以变化的,可以以此来保持需要的时间大致相同。
一旦这个问题被解决,数据块声明有效,结果数据将被附加到这个数据块,如果没有证明这个哈希值(防止事务被篡改的哈希值)是无效的,在此之后,这个数据块中包含的数据将不能被改变。 算法中的哈希函数
哈希函数还有很多种用法可以来加速算法。举个例子,如果你需要剔除大小为N的集合中的重复记录,你可能会疲于比较每一对可能的数据,即大约N2/2次比较,否则你最好对表格进行排序。一个替代的方法是,计算所有记录的哈希值,并将指向每个记录的指针存储于一个哈希表。这样重复的记录就是表中的冲突记录。
你还可以用具有附加属性的哈希函数来实现匹配算法。如果你可以发明一种哈希函数,将你认为相似的数据,映射为相近的哈希值,那么你就可以不仅用哈希来查找副本,即相等的数值,也可以用来查找相近的数值。这个方法在字符串匹配,声音匹配,甚至是模式识别中,都非常重要。 有很多非常聪明的算法使你能用快速和简单的方式检查数据间的不等性。一个基本的原则就是,如果两个对象的哈希值不同,那么他们不可能为同一事物,也就是不相等的。
你可以用 Bloom filter 的例子做检验. |