哈希（hash）算法

前言

       在java中，每个对象（Object）都有对应的hashcode，hashcode，顾名思义，就是散列的意思，把对象分散存储，哈希（hash）算法将数据依特定算法直接指定到一个地址桶(bucket：一个链表)上，当集合中增加新的元素时，调用这个元素的hashcode()方法，把这个元素定位到它应该放置的桶的位置上。如果这个桶的位置上没有元素，它就可以直接存储在这个桶的位置上；如果这个桶的位置上已经有别的元素，就调用它的equals()方法与新元素进行比较，相同的话就不存了，不相同就散列到其它的地址。

        所以，java对eqauls方法和hashCode方法定义如下：

        1、如果两个对象相同，那么它们的hashCode值一定要相同；
        2、如果两个对象的hashCode相同，两个对象并不一定相同。

 

关于hashcode()

1. hashcode是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有
例如内存中有这样的位置
0     1     2     3     4     5     6     7    
而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。
2. 但是如果两个类有相同的hashcode怎么办，例如9除以8和17除以8的余数都是1。这时如何判断呢？在这个时候就需要定义 equals()了。
也就是说，我们先通过hashcode来判断两个对象是否存放某个桶(bucket)里，但这个桶里可能有很多对象，那么我们就需要再通过 equals() 来在这个桶里找我们要的对象。

 

进阶
哈希算法hashCode()是用来产生哈希玛，哈希玛是用来在散列存储结构中确定对象的存储地址，（这一段在 Java编程思想中讲的很清楚的）象util包中的 带 hash 的集合类都是用这种存储结构 ：HashMap,HashSet, 他们在将对象存储时（严格说是对象引用），需要确定他们的地址，而HashCode()就是这个用途的，一般都需要重新定义它的，因为默认情况下，由 Object 类定义的 hashCode 方法会针对不同的对象返回不同的整数，这一般是通过将该对象的内部地址转换成一个整数来实现的，现在举个例子来说， 就拿HashSet来说，在将对象存入其中时，通过被存入对象的 hashCode() 来确定对象在 HashSet 中的存储地址，通过equals()来确定存入的对象是否重复，hashCode() ，equals()都需要自己重新定义，因为hashCode()默认前面已经说啦，而equals() 默认是比较的对象引用，你现在想一下，如果你不定义equals()的话，那么同一个类产生的两个内容完全相同的对象都可以存入Set，因为他们是通过 equals()来确定的，这样就使得HashSet 失去了他的意义，看一下下面这个： 

import java.util.*;

/**
 * Description HashSet测试
 * 重写equals（）和hashcode()
 * @author usr1999  2014-5-11
 */
public class HashSetTest {

	public static void main(String[] args) {
		HashSet set = new HashSet();
		for (int i = 0; i <= 3; i++) {
			set.add(new Demo1(i, i));
		}
		System.out.println(set);
		set.add(new Demo1(1, 1));
		System.out.println(set);
		System.out.println(set.contains(new Demo1(0, 0)));
		System.out.println(set.add(new Demo1(1, 1)));
		System.out.println(set.add(new Demo1(4, 4)));
		System.out.println(set);
	}

	private static class Demo1 {
		private int value;

		private int id;

		public Demo1(int value, int id) {
			this.value = value;
			this.id = id;
		}

		public String toString() {
			return " value = " + value;
		}

		public boolean equals(Object o) {
			Demo1 a = (Demo1) o;
			return (a.value == value) ? true : false;
		}

		public int hashCode() {
			return id;
		}
	}
}

         分别注释掉hashCode()和 equals()来比较一下
结果：
[ value = 2,  value = 1,  value = 3,  value = 0]
[ value = 2,  value = 1,  value = 3,  value = 0]
true
false
true
[ value = 2,  value = 4,  value = 1,  value = 3,  value = 0]

注释掉hashCode()
[ value = 1,  value = 0,  value = 2,  value = 3]
[ value = 1,  value = 0,  value = 1,  value = 2,  value = 3]
false
true
true
[ value = 1,  value = 0,  value = 1,  value = 2,  value = 3,  value = 4,  value = 1]

注释掉equals()
[ value = 2,  value = 1,  value = 3,  value = 0]
[ value = 2,  value = 1,  value = 1,  value = 3,  value = 0]
false
true
true
[ value = 2,  value = 4,  value = 1,  value = 1,  value = 1,  value = 3,  value = 0]

 

总结

        hashCode()方法因为是用来提高Map里面的搜索效率的,Map会根据不同的hashCode()来放在不同的桶里面,Map在搜索一个对象的时候先通过hashCode()找到相应的桶,然后再根据equals()方法找到相应的对象。要正确的实现Map里面查找元素必须满足一下两个条件:
(1)当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()==true；
(2)当obj1.hashCode() == obj2.hashCode()为false时，obj.equals(obj2)==false。