Electronic Joint Business

Solution for E-Business

哈希算法

文章评分: 哈希(Hash)算法就是单向散列算法,它把某个较大的集合P映射到另一个较小的集合Q中,假如这个算法叫 H,那么就有 Q = H(P)。对于 P 中任何一个值 p 都有唯一确定的 q 与之对应,但是一个 q 可以对应多个 p。作为一个有用的 Hash 算法,H 还应该满足:H(p) 速度比较快;给出一个 q,很难算出一个 p 满足 q = H(p);给出一个 p1,很难算出一个不等于 p1 的 p2 使得 H(p1)=H(p2)。 数学原理听起来很抽象,这里我们举个有趣的例子。农场里有很多的小猪,每个的体重都不一样,假设体重分布比较平均,都在100到120公斤之间(我们考虑到公斤级别),我们按照体重区间来分,建了10个小猪圈。 1号圈圈养90-92公斤的小猪,2号圈圈养92-94公斤的小猪,以此类推…。然后把每个小猪,按照体重赶进各自的猪圈里,记录档案。 好了,如果我们要精确找到某个小猪怎么办呢?我们需要每个猪圈,每个小猪的比对吗? 当然不需要了。 我们先看看要找的这个小猪的体重,然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。 对应回 hash 算法:就是按照 hashcode 分配不同的猪圈,将 hashcode 相同的猪放到一个猪圈里。 查找的时候,先找到 hashcode 对应的猪圈,然后在逐个比较里面的小猪。 关键就是建造多少个猪圈比较合适。如果每个小猪的体重全部不同(考虑到毫克级别),为每个小猪都建一个猪圈,那么我们可以最快速度的找到这头猪。缺点就是,建造那么多猪圈的费用有点太高了。 如果我们按照10公斤级别进行划分,那么建造的猪圈只有几个吧,那么每个圈里的小猪就很多了。我们虽然可以很快的找到猪圈,但从这个猪圈里逐个确定那头小猪也是很累的。 所以,好的hashcode,可以根据实际情况,根据具体的需求,在时间成本(更多的猪圈,更快的速度)和空间成本(更少的猪圈,更低的空间需求)之间平衡。 所以一个简单的定义:哈希算法其本质上就是将一个数据映射成另一个数据,通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希函数或者散列函数。散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。 常见的构造散列函数的方法有: 直接寻址法1 数字分析法 […]

One thought on “哈希算法

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.