hash算法-JAVA SET

 首先数学原理：哈希（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)。

所以一个简单的定义：哈希算法其本质上就是将一个数据映射成另一个数据，通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希函数或者散列函数。散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

 

散列方法最经典的莫过于求模取余法。我们知道，任给一个整数A,将自然数1,2,3,4,…依次除以A,所得的余数总是循环出现,呈周期性变化, 所以，我们可以取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key % p, p<=m。

 

 

必然会有冲突，解决冲突的最经典方法，莫过于”拉链法“，即某个位置填入的不是元素本身，而是一个链表，所有余数相同的元素，都写入该链表。显然链表中的元素要远比原集合中的元素少了很多，这时就可以对链表做遍历比较了。

 

 

装填因子Load factor a=哈希表的实际元素数目(n)/ 哈希表的容量(m) a越大，哈希表冲突的概率越大，但是a越接近0，那么哈希表的空间就越浪费。Java实现的HashMap默认的Load factor的值为0.75，当装载因子大于这个值的时候，HashMap会对数组进行扩张至原来两倍大。

 

然后看看JAVA SET:通过上面，可以知道hashcode其实就是个地址。SET的大概原理，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。 

如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了， 
就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。 
所以这里存在一个冲突解决的问题（应该也是拉链法吧）。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

 

最后：

Java对于eqauls方法和hashCode方法是这样规定的： 
1、如果两个对象相同，那么它们的hashCode值一定要相同；

2、如果两个对象的hashCode相同，它们并不一定相同     。

也就是说hashcode和equals必须同时存在。