【java基础】重写hashCode和equals方法

标签: hashCode  equals

在使用HashMap和HashSet保存数据时,需要根据键的哈希值来进行散列,先来看如果不重写这两个方法会怎么样?

public class Main {
	
	public static void main(String[] args) {
		//HashSet hs=new HashSet();
		HashMap<People,Integer> map=new HashMap<People,Integer>();
		People p1=new People("蜀","刘备");
		People p2=new People("蜀","张飞");
		People p3=new People("魏","曹操");
		People p4=new People("蜀","刘备");
		map.put(p1, 1);
		map.put(p2, 2);
		map.put(p3, 3);
		System.out.println(map.get(p4));
	}
	
}
class  People{
	String country="";
	String name="";
	public People(String country,String name){
		this.country=country;
		this.name=name;
	}
	
}

输出的结果为     null

因为HashMap是使用hash算法进行散列到数组中的。

HashMap的put()方法

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

 final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

首先调用函数hash(key),获取哈希值,然后在调用方法index(hash,table.length)获取散列表的索引位置。

获取索引位置后,就获取这个索引位置的Entry<K,V>对象,然后遍历此链表,在此过程中通过判断key是否是同一个对象,或者调用key的equals()方法,来判断是否和已存在此链表上的Entry<K,V>是否相等。如果相等就覆盖旧值,返回旧值,否则就讲此对象存放在该数组位置,该对象的后继节点就是原来存放在此数组位置的那个对象。

所以经过上面分析,我们知道HashMap会先使用key的hashCode函数来获取散列表的索引位置,获取索引位置后,就通过key的equals()方法对此索引位置上的对象链进行遍历判断是否相等。相等就覆盖,否则就存在对象链的头位置。

由此可以看出,重写equals()判断对象相等的话,那么hashCode()返回的哈希值也要相等,只要hashCode相等才能在散列表中搜索到这个索引位置进行对象相等判断。

现在我们对开头的示例进行重写:

public class Main {
	
	public static void main(String[] args) {
		//HashSet hs=new HashSet();
		HashMap<People,Integer> map=new HashMap<People,Integer>();
		People p1=new People("蜀","刘备");
		People p2=new People("蜀","张飞");
		People p3=new People("魏","曹操");
		People p4=new People("蜀","刘备");
		map.put(p1, 1);
		map.put(p2, 2);
		map.put(p3, 3);
		System.out.println(map.get(p4));
	}
	
}
class  People{
	String country="";
	String name="";
	public People(String country,String name){
		this.country=country;
		this.name=name;
	}
	public boolean equals(Object obj){
		if(obj instanceof People){
			People p=(People)obj;
			if(country.equals(p.country)&&name.equals(p.name))
				return true;
			else
				return false;	
		}else{
			return false;
		}
	}
	
	public int hashCode(){
		return country.hashCode();
	}
}

输出结果是  1

下面给出重写hashCode的规则:

Google首席Java架构师Joshua Bloch在他的著作《Effective Java》中提出了一种简单通用的hashCode算法

1. 初始化一个整形变量,为此变量赋予一个非零的常数值,比如int result = 17;

2. 选取equals方法中用于比较的所有域,然后针对每个域的属性进行计算:

  (1) 如果是boolean值,则计算f ? 1:0

  (2) 如果是byte\char\short\int,则计算(int)f

  (3) 如果是long值,则计算(int)(f ^ (f >>> 32))

  (4) 如果是float值,则计算Float.floatToIntBits(f)

  (5) 如果是double值,则计算Double.doubleToLongBits(f),然后返回的结果是long,再用规则(3)去处理long,得到int

  (6) 如果是对象应用,如果equals方法中采取递归调用的比较方式,那么hashCode中同样采取递归调用hashCode的方式。  否则需要为这个域计算一个范式,比如当这个域的值为null的时候,那么hashCode 值为0

  (7) 如果是数组,那么需要为每个元素当做单独的域来处理。如果你使用的是1.5及以上版本的JDK,那么没必要自己去    重新遍历一遍数组,java.util.Arrays.hashCode方法包含了8种基本类型数组和引用数组的hashCode计算,算法同上,

public static int hashCode(long a[]) {
        if (a == null)
            return 0;
 
        int result = 1;
        for (long element : a) {
            int elementHash = (int)(element ^ (element >>> 32));
            result = 31 * result + elementHash;
        }
 
        return result;
}

Arrays.hashCode(...)只会计算一维数组元素的hashCOde,如果是多维数组,那么需要递归进行hashCode的计算,那么就需要使用Arrays.deepHashCode(Object[])方法。

 

3. 最后,要如同上面的代码,把每个域的散列码合并到result当中:result = 31 * result + elementHash;

4. 测试,hashCode方法是否符合文章开头说的基本原则,这些基本原则虽然不能保证性能,但是可以保证不出错。

 

2. 为什么每次需要使用乘法去操作result? 主要是为了使散列值依赖于域的顺序,还是上面的那个例子,Test t = new Test(1, 0)跟Test t2 = new Test(0, 1), t和t2的最终hashCode返回值是不一样的。

3. 为什么是31? 31是个神奇的数字,因为任何数n * 31就可以被JVM优化为 (n << 5) -n,移位和减法的操作效率要比乘法的操作效率高的多。

 

 

 

 

 

 

 

版权声明:本文为fxkcsdn原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fxkcsdn/article/details/81839449