自定義對(duì)象作為HashMap的Key

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

首先我們自定義一個(gè)學(xué)生對(duì)象，它有姓名和年齡兩個(gè)字段.

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)上面的代碼是一個(gè)能作為hashMap的key對(duì)象的完整代碼.包括重寫了equals方法和hashCode方法.在重寫equals方法時(shí)我還遇到了一個(gè)麻煩事，一開始我是下面這樣寫的:

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

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

然后我們接著把對(duì)象裝入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)成功了!

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

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

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

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

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

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

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

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

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

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

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

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

result = 31 * result +c;

3.返回result

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

null
8
0

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

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

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

9999
2305
1

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

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

HashMap使用自定義對(duì)象作為Key的注意點(diǎn)

1. 自定義對(duì)象不重寫hashCode方法和equals會(huì)發(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é)論：

當(dāng)我們不重寫Student對(duì)象的hashCode方法和equals方法時(shí)，Student對(duì)象沿用的就是Object對(duì)象的hashCode方法和equals方法；從上面代碼的測(cè)試來(lái)說(shuō)，即使兩個(gè)屬性相同的對(duì)象他們的hash值都是不一樣的，調(diào)用equals方法進(jìn)行比較，他們也是不相同的。

總結(jié)：

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

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

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

public class AboutHashMap {
? ? public static void main(String[] args) {
? ? ? ? Student s1 = new Student("張三",18); // 兩個(gè)相同屬性的對(duì)象
? ? ? ? Student s2 = new Student("張三",18);
? ? ? ? Map<Student, Integer> hashMap = new HashMap<>();
? ? ? ? hashMap.put(s1, 99); ? ? ? ?
? ? ? ? // 使用屬性相同的對(duì)象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)，通過(guò)一個(gè)屬性一模一樣的s2去get哈希表中的元素竟然找不到前面put過(guò)的 s1-99?。。。?？？

解釋：

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

總結(jié)：

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

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

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

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

equals:

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

hashCode：

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

ps：在IDEA中使用 ALT + INSERT可以快速幫我們實(shí)現(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);
? ? }
}

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

最新評(píng)論