自定義對(duì)象作為HashMap的Key問(wèn)題
自定義對(duì)象作為HashMap的Key
這個(gè)問(wèn)題在很多面試者面試時(shí)都會(huì)被提及,本人也是最近在看effective java第九條:覆蓋equals時(shí)總要覆蓋hashcode回想到了當(dāng)初面試時(shí)也被問(wèn)到了這個(gè)問(wèn)題.于是動(dòng)手寫(xiě)了幾行代碼,還真發(fā)現(xiàn)了一些小的問(wè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ì)象的完整代碼.包括重寫(xiě)了equals方法和hashCode方法.在重寫(xiě)equals方法時(shí)我還遇到了一個(gè)麻煩事,一開(kāi)始我是下面這樣寫(xiě)的:
@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)新的問(wèn)題了!那就是Student對(duì)象的hashCode方法是怎么實(shí)現(xiàn)的呢?equals方法大家都會(huì)重寫(xiě).那么究竟怎么一個(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)然如果我們不重寫(xiě)hashCode方法會(huì)出現(xiàn)什么情況呢?請(qǐng)看:
null
8
0
返回結(jié)果為null,因?yàn)镾tudent類沒(méi)有重寫(xiě)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è)問(wèn)題了,如果我重寫(xiě)的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ì)象不重寫(xiě)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)我們不重寫(xiě)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方法(未重寫(xiě)),返回值是由對(duì)象的內(nèi)存地址值計(jì)算而來(lái)的,因此即使兩個(gè)對(duì)象的屬性完全相同,他們的哈希值也不同,所以即使兩個(gè)屬性完全相同的對(duì)象在HashMap中也完全找不到。
總結(jié):
使用自定義對(duì)象作為HashMap的key不重寫(xiě)hashCode和equals方法會(huì)產(chǎn)生的問(wè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就必須正確重寫(xiě)hashCode和equals方法。
3. 重寫(xiě)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è)參考,也希望大家多多支持腳本之家。
相關(guān)文章
Java調(diào)用Pytorch模型實(shí)現(xiàn)圖像識(shí)別
這篇文章主要為大家詳細(xì)介紹了Java如何調(diào)用Pytorch實(shí)現(xiàn)圖像識(shí)別功能,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的小伙伴可以了解一下2023-06-06mybatis參數(shù)類型不匹配錯(cuò)誤argument type mismatch的處理方案
這篇文章主要介紹了mybatis參數(shù)類型不匹配錯(cuò)誤argument type mismatch的處理方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-01-01mybatis if test 不為空字符串且不為null的問(wèn)題
這篇文章主要介紹了mybatis if test 不為空字符串且不為null的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03@TableName注解和@Table的區(qū)別及說(shuō)明
這篇文章主要介紹了@TableName注解和@Table的區(qū)別及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-01-01Spring JdbcTemplate整合使用方法及原理詳解
這篇文章主要介紹了Spring JdbcTemplate整合使用方法及原理詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08