设为首页收藏本站

LUPA开源社区

 找回密码
 注册
文章 帖子 博客
LUPA开源社区 首页 IT综合资讯 查看内容

Hashing:一种很棒的编程思路

2013-11-16 21:45| 发布者: joejoe0332| 查看: 3310| 评论: 0|原作者: yale8848, super0555, jingxing05, bigtiger02, ley|来自: oschina

摘要: 尽管这个观点仁者见仁智者见智,虽然你不能够对其提供帮助,但你应该钦佩hash函数这一思想。它不仅仅能够解决基本的计算问题——查找存储数据,也可以帮助检测文件篡改,密码安全等诸多问题。 ...


    工作证明


    在更不寻常的哈希用法中,有一种思想是比特币的工作证明算法。在这种场景下,有一块数据需要发布,在服务器声称验证该事务之前,它必须找到一个数据项(译注:也称为验证码,该计算生成block过程被称为“挖金矿”,因为计算会得到一定的奖励),这个数据项加到这个数据块的时候,采用的是其哈希值,且其中含有一个给定数目的零。由于逆向计算哈希函数不容易,唯一的办法就是加上估计数据,并计算哈希值,直到结果具有给定数目的零。这个过程需要时间,这也意味着非常有可能只有一个服务器最先找到这个结果——这样就避免了多个服务器验证这个数据块的问题。


    锦上添花的是,这个算法面临着更优异的硬件性能。它包括,通过测量解决哈希问题的平均时间来给出反馈,以及根据需要来增加额外的零。你可以证明,找到一些数据加给这个数据块,然后在哈希算法中得出n个零,其中需要的时间随n呈指数级变化。用其他话来说,这个问题的难度是可以变化的,可以以此来保持需要的时间大致相同。


    一旦这个问题被解决,数据块声明有效,结果数据将被附加到这个数据块,如果没有证明这个哈希值(防止事务被篡改的哈希值)是无效的,在此之后,这个数据块中包含的数据将不能被改变。


    算法中的哈希函数


    哈希函数还有很多种用法可以来加速算法。举个例子,如果你需要剔除大小为N的集合中的重复记录,你可能会疲于比较每一对可能的数据,即大约N2/2次比较,否则你最好对表格进行排序。一个替代的方法是,计算所有记录的哈希值,并将指向每个记录的指针存储于一个哈希表。这样重复的记录就是表中的冲突记录。


    你还可以用具有附加属性的哈希函数来实现匹配算法。如果你可以发明一种哈希函数,将你认为相似的数据,映射为相近的哈希值,那么你就可以不仅用哈希来查找副本,即相等的数值,也可以用来查找相近的数值。这个方法在字符串匹配,声音匹配,甚至是模式识别中,都非常重要。


   有很多非常聪明的算法使你能用快速和简单的方式检查数据间的不等性。一个基本的原则就是,如果两个对象的哈希值不同,那么他们不可能为同一事物,也就是不相等的。


    你可以用 Bloom filter 的例子做检验.  


hash3


相关文章

Advanced Hashing高级哈希 

The Bloom Filter Bloom过滤 

The Invertible Bloom Filter 可逆Bloom过滤

Universal Hashing全域散列

Storage Mapping Functions 存储映射函数      

Inside Bitcoin - virtual currency深入比特币-虚拟货币
Assemblers and assembly language 编译器和汇编语言      


酷毙

雷人

鲜花

鸡蛋

漂亮
  • 快毕业了,没工作经验,
    找份工作好难啊?
    赶紧去人才芯片公司磨练吧!!

最新评论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187 浙公网安备 33010602006705号   

返回顶部