equals和HashCode深入理解以及Hash算法原理

equals和HashCode深入理解以及Hash算法原理1.深入理解equals():提醒：Object類(lèi)中的equals方法和“==”是一樣的，沒(méi)有區(qū)別，即倆個(gè)對(duì)象的比較是比較他們的棧內(nèi)存中存儲(chǔ)的內(nèi)存地址。而String類(lèi)，Integer類(lèi)等等一些類(lèi)，是重寫(xiě)了equals方法，才使得equals和“==不同”，他們比較的是值是不是相等。所以，當(dāng)自己創(chuàng)建類(lèi)時(shí)，自動(dòng)繼承了Object的equals方法，要想實(shí)現(xiàn)不同的等于比較，必須重寫(xiě)equals方法。我們看下面這個(gè)例子：packagecn.galc.test;publicclassTestEquals{publicstaticvoidmain(String[]args){/***這里使用構(gòu)造方法Cat()在堆內(nèi)存里面new出了兩只貓，*這兩只貓的color，weight，height都是一樣的，*但c1和c2卻永遠(yuǎn)不會(huì)相等，這是因?yàn)閏1和c2分別為堆內(nèi)存里面兩只貓的引用對(duì)象，*里面裝著可以找到這兩只貓的地址，但由于兩只貓?jiān)诙褍?nèi)存里面存儲(chǔ)在兩個(gè)不同的空間里面，*所以c1和c2分別裝著不同的地址，因此c1和c2永遠(yuǎn)不會(huì)相等。*/Catc1=newCat(1,1,1);Catc2=newCat(1,1,1);System.out.println("c1==c2的結(jié)果是："+(c1==c2));//falseSystem.out.println("c1.equals(c2)的結(jié)果是："+c1.equals(c2));//false}}classCat{intcolor,weight,height;publicCat(intcolor,intweight,intheight){this.color=color;this.weight=weight;this.height=height;}}畫(huà)出內(nèi)存分析圖分析c1和c2比較的結(jié)果，當(dāng)執(zhí)行Catc1=newCat(1,1,1);Catc2=newCat(1,1,1);之后內(nèi)存之中布局如下圖：由此我們看出，當(dāng)我們new一個(gè)對(duì)象時(shí)，將在內(nèi)存里加載一份它自己的內(nèi)存，而不是共用！對(duì)于static修飾的變量和方法則保存在方法區(qū)中，只加載一次，不會(huì)再多copy一份內(nèi)存。所以我們?cè)谂袛鄠z個(gè)對(duì)象邏輯上是否相等，即對(duì)象的內(nèi)容是否相等不能直接使用繼承于Object類(lèi)的equals()方法，我們必須得重寫(xiě)equals()方法，改變這個(gè)方法默認(rèn)的實(shí)現(xiàn)。下面在Cat類(lèi)里面重寫(xiě)這個(gè)繼承下來(lái)的equals()方法：classCat{intcolor,weight,height;publicCat(intcolor,intweight,intheight){this.color=color;this.weight=weight;this.height=height;}/***這里是重寫(xiě)相等從Object類(lèi)繼承下來(lái)的equals()方法，改變這個(gè)方法默認(rèn)的實(shí)現(xiàn)，*通過(guò)我們自己定義的實(shí)現(xiàn)來(lái)判斷決定兩個(gè)對(duì)象在邏輯上是否相等。*這里我們定義如果兩只貓的color，weight，height都相同，*那么我們就認(rèn)為這兩只貓?jiān)谶壿嬌鲜且荒Ｒ粯拥?，即這兩只貓是“相等”的。*/publicbooleanequals(Objectobj){if(obj==null){returnfalse;}else{/***instanceof是對(duì)象運(yùn)算符。*對(duì)象運(yùn)算符用來(lái)測(cè)定一個(gè)對(duì)象是否屬于某個(gè)指定類(lèi)或指定的子類(lèi)的實(shí)例。*如果左邊的對(duì)象是右邊的類(lèi)創(chuàng)建的對(duì)象，則運(yùn)算結(jié)果為true，否則為false。*/if(objinstanceofCat){Catc=(Cat)obj;if(c.color==this.color&&c.weight==this.weight&&c.height==this.height){returntrue;}}}returnfalse;}}設(shè)計(jì)思路很簡(jiǎn)單：先判斷比較對(duì)象是否為null—>判斷比較對(duì)象是否為要比較類(lèi)的實(shí)例—–>比較倆個(gè)成員變量是否完全相等。//另外一種常用重寫(xiě)方法@Overridepublicbooleanequals(Objectobj){if(this==obj)returntrue;if(obj==null)returnfalse;if(getClass()!=obj.getClass())returnfalse;Peopleother=(People)obj;if(age!=other.age)returnfalse;if(firstName==null){if(other.firstName!=null)returnfalse;}elseif(!firstName.equals(other.firstName))returnfalse;if(lastName==null){if(other.lastName!=null)returnfalse;}elseif(!lastName.equals(other.lastName))returnfalse;returntrue;}這樣通過(guò)在類(lèi)中重寫(xiě)equals()方法，我們可以比較在同一個(gè)類(lèi)下不同對(duì)象是否相等了。2.Hash算法原理以及HashCode深入理解Java中的Collection有兩類(lèi)，一類(lèi)是List，一類(lèi)是Set。List內(nèi)的元素是有序的，元素可以重復(fù)。Set元素?zé)o序，但元素不可重復(fù)。要想保證元素不重復(fù)，兩個(gè)元素是否重復(fù)應(yīng)該依據(jù)什么來(lái)判斷呢？用Object.equals方法。但若每增加一個(gè)元素就檢查一次，那么當(dāng)元素很多時(shí)，后添加到集合中的元素比較的次數(shù)就非常多了。也就是說(shuō)若集合中已有1000個(gè)元素，那么第1001個(gè)元素加入集合時(shí)，它就要調(diào)用1000次equals方法。這顯然會(huì)大大降低效率。于是Java采用了哈希表的原理。當(dāng)Set接收一個(gè)元素時(shí)根據(jù)該對(duì)象的內(nèi)存地址算出hashCode，看它屬于哪一個(gè)區(qū)間，再這個(gè)區(qū)間里調(diào)用equeals方法?！咎貏e注意】這里需要注意的是：當(dāng)倆個(gè)對(duì)象的hashCode值相同的時(shí)候，Hashset會(huì)將對(duì)象保存在同一個(gè)位置，但是他們equals返回false，所以實(shí)際上這個(gè)位置采用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)保存多個(gè)對(duì)象。上面方法確實(shí)提高了效率。但一個(gè)面臨問(wèn)題：若兩個(gè)對(duì)象equals相等，但不在一個(gè)區(qū)間，因?yàn)閔ashCode的值在重寫(xiě)之前是對(duì)內(nèi)存地址計(jì)算得出，所以根本沒(méi)有機(jī)會(huì)進(jìn)行比較，會(huì)被認(rèn)為是不同的對(duì)象。所以Java對(duì)于eqauls方法和hashCode方法是這樣規(guī)定的：1如果兩個(gè)對(duì)象相同，那么它們的hashCode值一定要相同。也告訴我們重寫(xiě)equals方法，一定要重寫(xiě)hashCode方法，也就是說(shuō)hashCode值要和類(lèi)中的成員變量掛上鉤，對(duì)象相同–>成員變量相同—->hashCode值一定相同。2如果兩個(gè)對(duì)象的hashCode相同，它們并不一定相同，這里的對(duì)象相同指的是用eqauls方法比較。下面來(lái)看一下一個(gè)具體的例子：RectObject對(duì)象：packagecom.weijia.demo;publicclassRectObject{publicintx;publicinty;publicRectObject(intx,inty){this.x=x;this.y=y;}@OverridepublicinthashCode(){finalintprime=31;intresult=1;result=prime*result+x;result=prime*result+y;returnresult;}@Overridepublicbooleanequals(Objectobj){if(this==obj)returntrue;if(obj==null)returnfalse;if(getClass()!=obj.getClass())returnfalse;finalRectObjectother=(RectObject)obj;if(x!=other.x){returnfalse;}if(y!=other.y){returnfalse;}returntrue;}}我們重寫(xiě)了父類(lèi)Object中的hashCode和equals方法，看到hashCode和equals方法中，如果兩個(gè)RectObject對(duì)象的x,y值相等的話(huà)他們的hashCode值是相等的，同時(shí)equals返回的是true;下面是測(cè)試代碼：packagecom.weijia.demo;importjava.util.HashSet;publicclassDemo{publicstaticvoidmain(String[]args){HashSet<RectObject>set=newHashSet<RectObject>();RectObjectr1=newRectObject(3,3);RectObjectr2=newRectObject(5,5);RectObjectr3=newRectObject(3,3);set.add(r1);set.add(r2);set.add(r3);set.add(r1);System.out.println("size:"+set.size());}}我們向HashSet中存入到了四個(gè)對(duì)象，打印set集合的大小，結(jié)果是多少呢？運(yùn)行結(jié)果：size:2為什么會(huì)是2呢？這個(gè)很簡(jiǎn)單了吧，因?yàn)槲覀冎貙?xiě)了RectObject類(lèi)的hashCode方法，只要RectObject對(duì)象的x,y屬性值相等那么他的hashCode值也是相等的，所以先比較hashCode的值，r1和r2對(duì)象的x,y屬性值不等，所以他們的hashCode不相同的，所以r2對(duì)象可以放進(jìn)去，但是r3對(duì)象的x,y屬性值和r1對(duì)象的屬性值相同的，所以hashCode是相等的，這時(shí)候在比較r1和r3的equals方法，因?yàn)樗磧傻膞,y值是相等的，所以r1,r3對(duì)象是相等的，所以r3不能放進(jìn)去了，同樣最后再添加一個(gè)r1也是沒(méi)有沒(méi)有添加進(jìn)去的，所以set集合中只有一個(gè)r1和r2這兩個(gè)對(duì)象下面我們把RectObject對(duì)象中的hashCode方法注釋?zhuān)床恢貙?xiě)Object對(duì)象中的hashCode方法，在運(yùn)行一下代碼：運(yùn)行結(jié)果：size:3這個(gè)結(jié)果也是很簡(jiǎn)單的，首先判斷r1對(duì)象和r2對(duì)象的hashCode，因?yàn)镺bject中的hashCode方法返回的是對(duì)象本地內(nèi)存地址的換算結(jié)果，不同的實(shí)例對(duì)象的hashCode是不相同的，同樣因?yàn)閞3和r1的hashCode也是不相等的，但是r1==r1的，所以最后set集合中只有r1,r2,r3這三個(gè)對(duì)象，所以大小是3下面我們把RectObject對(duì)象中的equals方法中的內(nèi)容注釋?zhuān)苯臃祷豧alse，不注釋hashCode方法，運(yùn)行一下代碼：運(yùn)行結(jié)果：size:3這個(gè)結(jié)果就有點(diǎn)意外了，我們來(lái)分析一下：首先r1和r2的對(duì)象比較hashCode，不相等，所以r2放進(jìn)set中，再來(lái)看一下r3,比較r1和r3的hashCode方法，是相等的，然后比較他們兩的equals方法，因?yàn)閑quals方法始終返回false,所以r1和r3也是不相等的，r3和r2就不用說(shuō)了，他們兩的hashCode是不相等的，所以r3放進(jìn)set中，再看r4,比較r1和r4發(fā)現(xiàn)hashCode是相等的，在比較equals方法，因?yàn)閑quals返回false,所以r1和r4不相等，同一r2和r4也是不相等的，r3和r4也是不相等的，所以r4可以放到set集合中，那么結(jié)果應(yīng)該是size:4,那為什么會(huì)是3呢？這時(shí)候我們就需要查看HashSet的源碼了，下面是HashSet中的add方法的源碼：/***Addsthespecifiedelementtothissetifitisnotalreadypresent.*Moreformally,addsthespecifiedelement<tt>e</tt>tothissetif*thissetcontainsnoelement<tt>e2</tt>suchthat*<tt>(e==null?e2==null:uals(e2))</tt>.*Ifthissetalreadycontainstheelement,thecallleavestheset*unchangedandreturns<tt>false</tt>.**@parameelementtobeaddedtothisset*@return<tt>true</tt>ifthissetdidnotalreadycontainthespecified*element*/publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}這里我們可以看到其實(shí)HashSet是基于HashMap實(shí)現(xiàn)的，我們?cè)邳c(diǎn)擊HashMap的put方法，源碼如下：/***Associatesthespecifiedvaluewiththespecifiedkeyinthismap.*Ifthemappreviouslycontainedamappingforthekey,theold*valueisreplaced.**@paramkeykeywithwhichthespecifiedvalueistobeassociated*@paramvaluevaluetobeassociatedwiththespecifiedkey*@returnthepreviousvalueassociatedwith<tt>key</tt>,or*<tt>null</tt>iftherewasnomappingfor<tt>key</tt>.*(A<tt>null</tt>returncanalsoindicatethatthemap*previouslyassociated<tt>null</tt>with<tt>key</tt>.)*/publicVput(Kkey,Vvalue){if(key==null)returnputForNullKey(value);inthash=hash(key);inti=indexFor(hash,table.length);for(Entry<K,V>e=table[i];e!=null;e=e.next){Otk;if(e.hash==hash&&((k=e.key)==key||key.equals(k))){VoldValue=e.value;e.value=value;e.recordAccess(this);returnoldValue;}}modCount++;addEntry(hash,key,value,i);returnnull;}我們主要來(lái)看一下if的判斷條件，首先是判斷hashCode是否相等，不相等的話(huà)，直接跳過(guò)，相等的話(huà)，然后再來(lái)比較這兩個(gè)對(duì)象是否相等或者這兩個(gè)對(duì)象的equals方法，因?yàn)槭沁M(jìn)行的或操作，所以只要有一個(gè)成立即可，那這里我們就可以解釋了，其實(shí)上面的那個(gè)集合的大小是3,因?yàn)樽詈蟮囊粋€(gè)r1沒(méi)有放進(jìn)去，以為r1==r1返回true的，所以沒(méi)有放進(jìn)去了。所以集合的大小是3，如果我們將hashCode方法設(shè)置成始終返回false的話(huà)，這個(gè)集合就是4了。最后我們?cè)趤?lái)看一下hashCode造成的內(nèi)存泄露的問(wèn)題：看一下代碼：packagecom.weijia.demo;importjava.util.HashSet;publicclassDemo{publicstaticvoidmain(String[]args){HashSet<RectObject>set=newHashSet<RectObject>();RectObjectr1=newRectObject(3,3);RectObjectr2=newRectObject(5,5);RectObjectr3=newRectObject(3,3);set.add(r1);set.add(r2);set.add(r3);r3.y=7;System.out.println("刪除前的大小size:"+set.size());set.remove(r3);System.out.println("刪除后的大小size:"+set.size());}}運(yùn)行結(jié)果：刪除前的大小size:3刪除后的大小size:3擦，發(fā)現(xiàn)一個(gè)問(wèn)題了，而且是個(gè)大問(wèn)題呀，我們調(diào)用了remove刪除r3對(duì)象，以為刪除了r3,但事實(shí)上并沒(méi)有刪除，這就叫做內(nèi)存泄露，就是不用的對(duì)象但是他還在內(nèi)存中。所以我們多次這樣操作之后，內(nèi)存就爆了?？匆幌聄emove的源碼：/***Removesthespecifiedelementfromthissetifitispresent.*Moreformally,removesanelement<tt>e</tt>suchthat*<tt>(o==null?e==null:o.equals(e))</tt>,*ifthissetcontainssuchanelement.Returns<tt>true</tt>if*thissetcontainedtheelement(orequivalently,ifthisset*changedasaresultofthecall).(Thissetwillnotcontainthe*elementoncethecallreturns.)**@paramoobjecttoberemovedfromthisset,ifpresent*@return<tt>true</tt>ifthesetcontainedthespecifiedelement*/publicbooleanremove(Objecto){returnmap.remove(o)==PRESENT;}然后再看一下remove方法的源碼：/***Removesthemappingforthespecifiedkeyfromthismapifpresent.**@paramkeykeywhosemappingistoberemovedfromthemap*@returnthepreviousvalueassociatedwith<tt>key</tt>,or*<tt>null</tt>iftherewasnomappingfor<tt>key</tt>.*(A<tt>null</tt>returncanalsoindicatethatthemap*previouslyassociated<tt>null</tt>with<tt>key</tt>.)*/publicVremove(Objectkey){Entry<K,V>e=removeEntryForKey(key);return(e==null?null:e.value);}在看一下removeEntryForKey方法源碼：/***Removesandreturnsthe