哈希算法
2010年11月05日 ray_linn 常见算法, 算法与数据结构, 1
文章评分： 哈希（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 “哈希算法”
