哈希（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个小猪圈。 然后把每个小猪，按照体重赶进各自的猪圈里，记录档案。
好了，如果我们要精确找到某个小猪怎么办呢？我们需要每个猪圈，每个小猪的比对吗？ 当然不需要了。 我们先看看要找的这个小猪的体重，然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。
对应回hash算法：就是按照hashcode分配不同的猪圈，将hashcode相同的猪放到一个猪圈里。 查找的时候，先找到hashcode对应的猪圈，然后在逐个比较里面的小猪。
关键就是建造多少个猪圈比较合适。如果每个小猪的体重全部不同（考虑到毫克级别)，每个都建一个猪圈，那么我们可以最快速度的找到这头猪。缺点就是，建造那么多猪圈的费用有点太高了。 如果我们按照10公斤级别进行划分，那么建造的猪圈只有几个吧，那么每个圈里的小猪就很多了。我们虽然可以很快的找到猪圈，但从这个猪圈里逐个确定那头小猪也是很累的。 所以，好的hashcode，可以根据实际情况，根据具体的需求，在时间成本(更多的猪圈，更快的速度)和空间本(更少的猪圈，更低的空间需求)之间平衡。
所以一个简单的定义：哈希算法其本质上就是将一个数据映射成另一个数据，通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希函数或者散列函数。散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
构造散列函数
常见的构造散列函数的方法有：
-
直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a×key + b，其中a和b为常数（这种散列函数叫做自身函数）
-
数字分析法
-
平方取中法
-
折叠法
-
随机数法
-
求模取余法
求模取余法
最经典的莫过于求模取余法。我们知道，任给一个整数A,将自然数1,2,3,4,…依次除以A,所得的余数总是循环出现,呈周期性变化, 所以，我们可以取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key % p, p<=m。
假设我们有一个很大集合A中有{496,387,184,21,96,31,.....}等等元素，回忆我们上面提到的小猪问题，我们可以将大的集合A（小猪）映射到一个小的集合B（猪圈）（假设B只有16个元素，请参考下图）。我们对元素A的每一个元素采用求模算法，得到： 496 % 16 = 0, 所以我们把496填入集合B的0号位置，387 % 16 = 3，那么387被填入集合B的3号位置。
当我们查询140是否在集合A中时，我们可以对140进行同样的求模算法，140 % 16=12 ，如果集合B的12号位置为空，就可以推断140不在集合A之中。但是，如果12号位置不为空，是否可以确定140在集合A之中呢？答案是否定的，主要是由于求模算法会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，比方说{108,12,140,28}，这些元素用上面的算法得到的余数都是12,所以就会有“冲突”这一问题。解决冲突的方法有很多种，最直观的莫过于”拉链法“，即12号位置填入的不是元素本身，而是一个链表，所有余数相同的元素，都写入该链表。显然链表中的元素要远比集合A中的元素少了很多，这时就可以对链表做遍历比较了。
从上面的例子，我们知道对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词，即所谓的“冲突”或“碰撞”。发生“冲突”的概率可以用装填因子来表示，装填因子Load factor a=哈希表的实际元素数目(n)/ 哈希表的容量(m) a越大，哈希表冲突的概率越大，但是a越接近0，那么哈希表的空间就越浪费。
一般情况下建议Load factor的值为0-0.7，Java实现的HashMap默认的Load factor的值为0.75，当装载因子大于这个值的时候，HashMap会对数组进行扩张至原来两倍大。
转载自：
http://blog.163.com/clevertanglei900@126/blog/static/111352259201171111938208/
阅读(2708) | 评论(0) | 转发(0) |
