自定義對象作為HashMap的Key

這個問題在很多面試者面試時都會被提及，本人也是最近在看effective java第九條:覆蓋equals時總要覆蓋hashcode回想到了當初面試時也被問到了這個問題.于是動手寫了幾行代碼，還真發(fā)現(xiàn)了一些小的問題，所以拿出來分享一下!

首先我們自定義一個學生對象，它有姓名和年齡兩個字段.

class Student{
	public String name;
	public Integer age;
	
	Student(String name,Integer age){
		this.name = name;
		this.age = age;
	}
	
	@Override
	public boolean equals(Object o) {
		//return true;
		if(o==this)
			return true;
			if(!(o instanceof Student))
				return false;
			Student s = (Student)o;
		return s.name.equals(name)&&s.age.equals(age);
	}
	
	@Override
	public int hashCode() {
		int result = 17;
		result = 31 * result + name.hashCode();
		result = 31 * result + age;
		return result;
	}
}

(PS)上面的代碼是一個能作為hashMap的key對象的完整代碼.包括重寫了equals方法和hashCode方法.在重寫equals方法時我還遇到了一個麻煩事，一開始我是下面這樣寫的:

@Override
	public boolean equals(Object o) {
		//***********
		return s.name.equals(name)&&s.age==age;
	}

相信都能找到原因，age是Integer對象而不是int所以比較的是地址值，于是乎無論如何都不能得到我想要的結(jié)果.

然后我們接著把對象裝入HashMap結(jié)構(gòu)中，并取出，看是否能夠成功?

static void demo2(){
		Map<Student, String> map = new HashMap<Student, String>();		
		long l1 = System.currentTimeMillis();
		for(int i = 0;i<10000;i++){
			map.put(new Student("dy"+i, i), ""+i);
		}
		long l2 = System.currentTimeMillis();
		System.out.println(map.get(new Student("dy9999",9999)));
		long l3 = System.currentTimeMillis();
		System.out.println((l2-l1));
		System.out.println((l3-l2));
	}

結(jié)果如下

9999
8
0

已經(jīng)成功了!

那么可能有點新的問題了!那就是Student對象的hashCode方法是怎么實現(xiàn)的呢?equals方法大家都會重寫.那么究竟怎么一個算法能讓不同的對象具有不同的散列值呢?下面這段描述摘抄自effective java給我們的建議:

1.把某個非零的常數(shù)值，比如說17(一個你喜歡的數(shù)字)，保存在一個名為result的int類型的變量中.

2.對于對象中每個關(guān)鍵域(指equals方法中涉及的每個域)，完成以下步驟:

• a.為該域計算int類型的散列碼c:

i.如果該域是boolean類型，則計算(f?1:0)

ii.如果該域是byte，char，short或者int類型，則計算(int)f.

iii.如果該域是long類型，則計算(int)(f^(f>>>32)).

iv.如果該域是float類型，則計算Float.floatToIntBits(f).

v.如果該域是double類型，則計算Double.doubleToLongBits(f)，然后按照步驟2.a.iii，為得到的long類型值計算散列值.

vi.如果該域是一個對象引用，并且該類的equals方法通過遞歸地調(diào)用equals的方式來比較這個域，則同樣為這個域遞歸地調(diào)用hashCode.如果需要更加復雜的比較，則為這個域計算一個"范式"，然后針對這個范式調(diào)用hashCode.如果這個域的值為null，則返回0(或者其他某個常數(shù)，但通常是0).

vii.如果該域是一個數(shù)組，則要把每一個元素當做單獨的域來處理.也就是說，遞歸地應用上述規(guī)則，對每個重要的元素計算一個散列碼，然后根據(jù)步驟2.b中的做法把這些散列值組合起來.如果數(shù)組域中的每個元素都很重要，可以利用發(fā)行版本1.5中增加的其中一個Arrays.hashCode方法.

• b.按照下面的公式，把步驟2.a中計算得到的散列碼c合并到result中:

result = 31 * result +c;

3.返回result

當然如果我們不重寫hashCode方法會出現(xiàn)什么情況呢？請看：

null
8
0

返回結(jié)果為null，因為Student類沒有重寫hashCode方法，從而導致兩個相等的實例具有不相等的散列碼，違反了hashCode的約定.因此put方法把對象放在一個散列桶中，而get方法卻在另一個散列桶中取值.即使這兩個實例恰好被放在同一個散列桶中，get方法也必定會返回null，因為HashMap有一項優(yōu)化，可以將與每個相關(guān)聯(lián)的散列碼緩存起來，如果散列碼不匹配，也不必檢查對象的等同性!這正說明了effective java第九條:覆蓋equals方法時總要覆蓋hashCode.但是現(xiàn)在又有一個問題了，如果我重寫的hashCode代碼如下會如何呢?

?? ?@Override
?? ?public int hashCode() {
?? ??? ?/*int result = 17;
?? ??? ?result = 31 * result + name.hashCode();
?? ??? ?result = 31 * result + age;*/
?? ??? ?return 32;
?? ?}

運行的結(jié)果如下:

9999
2305
1

可以看到的是，由于每個對象都具有相同的散列值，因此，每個對象都被映射到同一個散列桶中，使散列表退化為鏈表，它使得本該線性時間運行的程序變成了以平方級時間在運行.

關(guān)于對象實現(xiàn)Compareable接口可以參考這篇文章(Java 8 HashMap鍵與Comparable接口).

HashMap使用自定義對象作為Key的注意點

1. 自定義對象不重寫hashCode方法和equals會發(fā)生什么？

public class AboutHashMap {
? ? public static void main(String[] args) {
? ? ? ? Student s1 = new Student("張三",18);
? ? ? ? Student s2 = new Student("張三",18);
? ? ? ? System.out.println(s1.hashCode()); //21685669
? ? ? ? System.out.println(s2.hashCode()); //2133927002
? ? ? ? System.out.println(s1.hashCode() == s2.hashCode()); //false
? ? ? ? System.out.println(s1.equals(s2)); //false
? ? }
}
class Student {
? ? private String name;
? ? private int age;
? ? // 省略getter，setter，有參構(gòu)造
}

結(jié)論：

當我們不重寫Student對象的hashCode方法和equals方法時，Student對象沿用的就是Object對象的hashCode方法和equals方法；從上面代碼的測試來說，即使兩個屬性相同的對象他們的hash值都是不一樣的，調(diào)用equals方法進行比較，他們也是不相同的。

總結(jié)：

• Object對象的equals方法比較的是兩個對象的內(nèi)存地址。
• Object類的hashCode返回對象的內(nèi)存地址經(jīng)過處理后得到的值，由于每個對象的內(nèi)存地址都不一樣，所以哈希碼也不一樣。

public native int hashCode();
public boolean equals(Object obj) {
? ? return (this == obj);
}

2. 在HashMap中使用自定義對象作為key會發(fā)生什么？

public class AboutHashMap {
? ? public static void main(String[] args) {
? ? ? ? Student s1 = new Student("張三",18); // 兩個相同屬性的對象
? ? ? ? Student s2 = new Student("張三",18);
? ? ? ? Map<Student, Integer> hashMap = new HashMap<>();
? ? ? ? hashMap.put(s1, 99); ? ? ? ?
? ? ? ? // 使用屬性相同的對象s2去調(diào)用get方法
? ? ? ? System.out.println( hashMap.get(s2) ); ?// null
? ? }
}
class Student {
? ? private String name;
? ? private int age;
? ? // 省略getter，setter，有參構(gòu)造方法，toString方法
}

分析：

我們可以發(fā)現(xiàn)，通過一個屬性一模一樣的s2去get哈希表中的元素竟然找不到前面put過的 s1-99?。。?？？？

解釋：

put入的元素在HashMap中數(shù)組結(jié)構(gòu)的位置由key的hashCode方法返回值來決定，而此時自定義對象hashCode方法（未重寫），返回值是由對象的內(nèi)存地址值計算而來的，因此即使兩個對象的屬性完全相同，他們的哈希值也不同，所以即使兩個屬性完全相同的對象在HashMap中也完全找不到。

總結(jié)：

使用自定義對象作為HashMap的key不重寫hashCode和equals方法會產(chǎn)生的問題

• get方法：使用屬性完全相同的對象作為key去get元素會找不到元素。
• put方法：即使是有屬性完全相同的對象put到HashMap中，也不會覆蓋已有的value值，只會當作新元素加入到HashMap中
• 即使發(fā)生hash沖突，調(diào)用equal方法比較兩個屬性完全相同的對象也會返回false

所以要想順利使用自定義對象作為hashMap的key就必須正確重寫hashCode和equals方法。

3. 重寫hashCode方法和equals方法的原則

equals:

• 相等的兩個key實例調(diào)用equals()必須返回true(相等指的是屬性完全相等)。

hashCode：

• 如果兩個對象相等，則兩個對象的hashCode()必須相等；
• 如果兩個對象不相等，則兩個對象的hashCode()盡量不要相等, (為了減少發(fā)生hash沖突的情況)。

ps：在IDEA中使用 ALT + INSERT可以快速幫我們實現(xiàn)equals和hashcode方法

class Student {
? ? private String name;
? ? private int age;
? ? @Override
? ? public boolean equals(Object o) {
? ? ? ? if (this == o) return true;
? ? ? ? if (o == null || getClass() != o.getClass()) return false;
? ? ? ? Student student = (Student) o;
? ? ? ? return age == student.age && name.equals(student.name);
? ? }
? ? @Override
? ? public int hashCode() {
? ? ? ? return Objects.hash(name, age);
? ? }
}

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論