自定義對象作為HashMap的Key問題
自定義對象作為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)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
Java調(diào)用Pytorch模型實現(xiàn)圖像識別
這篇文章主要為大家詳細介紹了Java如何調(diào)用Pytorch實現(xiàn)圖像識別功能,文中的示例代碼講解詳細,具有一定的學習價值,感興趣的小伙伴可以了解一下2023-06-06mybatis參數(shù)類型不匹配錯誤argument type mismatch的處理方案
這篇文章主要介紹了mybatis參數(shù)類型不匹配錯誤argument type mismatch的處理方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-01-01mybatis if test 不為空字符串且不為null的問題
這篇文章主要介紹了mybatis if test 不為空字符串且不為null的問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-03-03Spring JdbcTemplate整合使用方法及原理詳解
這篇文章主要介紹了Spring JdbcTemplate整合使用方法及原理詳解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08