|
hashcode的作用2009年06月24日 星期三 07:13
1.hashcode是用來查找的，如果你學(xué)過數(shù)據(jù)結(jié)構(gòu)就應(yīng)該知道，在查找和排序這一章有
例如內(nèi)存中有這樣的位置 0 1 2 3 4 5 6 7 而我有個(gè)類，這個(gè)類有個(gè)字段叫ID,我要把這個(gè)類存放在以上8個(gè)位置之一，如果不用hashcode而任意存放，那么當(dāng)查找時(shí)就需要到這八個(gè)位置里挨個(gè)去找，或者用二分法一類的算法。 但如果用hashcode那就會(huì)使效率提高很多。 我 們這個(gè)類中有個(gè)字段叫ID,那么我們就定義我們的hashcode為ID％8，然后把我們的類存放在取得得余數(shù)那個(gè)位置。比如我們的ID為9，9除8的余 數(shù)為1，那么我們就把該類存在1這個(gè)位置，如果ID是13，求得的余數(shù)是5，那么我們就把該類放在5這個(gè)位置。這樣，以后在查找該類時(shí)就可以通過ID除8 求余數(shù)直接找到存放的位置了。 2.但是如果兩個(gè)類有相同的hashcode怎么辦那（我們假設(shè)上面的類的ID不是唯一的），例如9除以8和17除以8的余數(shù)都是1，那么這是不是合法的，回答是：可以這樣。那么如何判斷呢？在這個(gè)時(shí)候就需要定義 equals了。
也就是說，我們先通過 hashcode來判斷兩個(gè)類是否存放某個(gè)桶里，但這個(gè)桶里可能有很多類，那么我們就需要再通過 equals 來在這個(gè)桶里找到我們要的類。 那么。重寫了equals()，為什么還要重寫hashCode()呢？ 想想，你要在一個(gè)桶里找東西，你必須先要找到這個(gè)桶啊，你不通過重寫hashcode()來找到桶，光重寫equals()有什么用啊 3。你要對(duì)A類排序，有兩種方法，一種就是讓A類實(shí)現(xiàn)comparabole結(jié)構(gòu)并實(shí)現(xiàn)compareTo()方法，那么可以通過Collections.sort(List <A> list)對(duì)其進(jìn)行排序 另一種方法：自己定義一個(gè)類B實(shí)現(xiàn)Comparator類并實(shí)現(xiàn)compare方法， 然后通過Collections.sort(List <A> list,B b)進(jìn)行排序 hashCode() 是用來產(chǎn)生哈希瑪?shù)?，而哈?，斒怯脕碓谏⒘写鎯?chǔ)結(jié)構(gòu)中確定對(duì)象的存儲(chǔ)地址的，（這一段在 Java編程思想 中講的很清楚的）象util包中的 帶 hash 的集合類都是用這種存儲(chǔ)結(jié)構(gòu) ：HashMap,HashSet, 他們?cè)趯?duì)象存儲(chǔ)時(shí)（嚴(yán)格說是對(duì)象引用），需要確定他們的地址吧， 而HashCode()就是這個(gè)用途的，一般都需要重新定義它的，因?yàn)槟J(rèn)情況下，由 Object 類定義的 hashCode 方法會(huì)針對(duì)不同的對(duì)象返回不同的整數(shù)，這一般是通過將該對(duì)象的內(nèi)部地址轉(zhuǎn)換成一個(gè)整數(shù)來實(shí)現(xiàn)的，現(xiàn)在舉個(gè)例子來說， 就拿HashSet來說 ，在將對(duì)象存入其中時(shí)，通過被存入對(duì)象的 hashCode() 來確定對(duì)象在 HashSet 中的存儲(chǔ)地址，通過equals()來確定存入的對(duì)象是否重復(fù)，hashCode() ，equals()都需要自己重新定義，因?yàn)閔ashCode()默認(rèn)前面已經(jīng)說啦，而equals() 默認(rèn)是比較的對(duì)象引用，你現(xiàn)在想一下，如果你不定義equals()的話，那么同一個(gè)類產(chǎn)生的兩個(gè)內(nèi)容完全相同的對(duì)象都可以存入Set，因?yàn)樗麄兪峭ㄟ^ equals()來確定的，這樣就使得HashSet 失去了他的意義，看一下下面這個(gè)：
public class Test { public static void main(String[] args) { HashSet set = new HashSet(); for (int i = 0; i <= 3; i++){ set.add(new Demo1(i,i)); } System.out.println(set); set.add(new Demo1(1,1)); System.out.println(set); System.out.println(set.contains(new Demo1(0,0))); System.out.println(set.add(new Demo1(1,1))); System.out.println(set.add(new Demo1(4,4))); System.out.println(set); } private static class Demo1 { private int value; private int id; public Demo1(int value,int id) { this.value = value; this.id=id; } public String toString() { return " value = " + value; } public boolean equals(Object o) { Demo1 a = (Demo1) o; return (a.value == value) ? true : false; } public int hashCode() { return id; } } } 你分別注釋掉hashCode()和 equals()來比較一下他們作用就可以拉，關(guān)鍵要自己動(dòng)手看看比較的結(jié)果你就可以記得很清楚啦
如果還不是很明確可以再看另一個(gè)例子:
public final class Test { public static void main(String[] args) { Map m = new HashMap(); m.put(new PhoneNumber(020, 12345678), "shellfeng"); System.out.println(m.get(new PhoneNumber(020, 12345678))); } private static class PhoneNumber { /** * 區(qū)號(hào) */ private short areaCode; /** * 擴(kuò)展號(hào) */ private short extension; public PhoneNumber(int areaCode, int extension) { this.areaCode = (short) areaCode; this.extension = (short) extension; } public boolean equals(Object o) { if (o == this) { return true; } if (!(o instanceof PhoneNumber)) { return false; } PhoneNumber pn = (PhoneNumber) o; return pn.extension == extension && pn.areaCode == areaCode; } /** * @see java.lang.Object#hashCode() * @return result就是我們得到的散列值,其實(shí)我們的計(jì)算過程可以多種,這里只不過是一個(gè)例子,需要你的靈活運(yùn)用,使其接近你需要的理想結(jié)果 */ public int hashCode() { int result = 17; result = 37 * result + areaCode; result = 37 * result + extension; return result; } } } 還是那句話:你注釋掉hashCode()比較一下他們作用就可以拉，關(guān)鍵要自己動(dòng)手看看比較的結(jié)果你就可以記得很清楚啦
總結(jié)
hashCode() 方法使用來提高M(jìn)ap里面的搜索效率的,Map會(huì)根據(jù)不同的hashCode()來放在不同的桶里面,Map在搜索一個(gè)對(duì)象的時(shí)候先通過 hashCode()找到相應(yīng)的桶,然后再根據(jù)equals()方法找到相應(yīng)的對(duì)象.要正確的實(shí)現(xiàn)Map里面查找元素必須滿足一下兩個(gè)條件: (1)當(dāng)obj1.equals(obj2)為true時(shí)obj1.hashCode() == obj2.hashCode()必須為true (2)當(dāng)obj1.hashCode() == obj2.hashCode()為false時(shí)obj.equals(obj2)必須為false Java中的集合（Collection）有兩類，一類是List，再有一類是Set。你知道它們的區(qū)別嗎？前者集合內(nèi)的元素是有序的，元素可以重復(fù)；后者元素?zé)o序，但元素不可重復(fù)。
那么這里就有一個(gè)比較嚴(yán)重的問題了：要想保證元素不重復(fù)，可兩個(gè)元素是否重復(fù)應(yīng)該依據(jù)什么來判斷呢？這就是Object.equals方法了。 但是，如果每增加一個(gè)元素就檢查一次，那么當(dāng)元素很多時(shí)，后添加到集合中的元素比較的次數(shù)就非常多了。 也就是說，如果集合中現(xiàn)在已經(jīng)有1000個(gè)元素，那么第1001個(gè)元素加入集合時(shí)，它就要調(diào)用1000次equals方法。這顯然會(huì)大大降低效率。 哈 希算法也稱為散列算法，是將數(shù)據(jù)依特定算法直接指定到一個(gè)地址上。我們可以認(rèn)為hashCode方法返回的就是對(duì)象存儲(chǔ)的物理地址（實(shí)際可能并不是,例 如:通過獲取對(duì)象的物理地址然后除以8再求余,余數(shù)幾是計(jì)算得到的散列值,我們就認(rèn)為返回一個(gè)不是物理地址的數(shù)值,而是一個(gè)可以映射到物理地址的值）。 這 樣一來，當(dāng)集合要添加新的元素時(shí)，先調(diào)用這個(gè)元素的hashCode方法，就一下子能定位到它應(yīng)該放置的物理位置上。如果這個(gè)位置上沒有元素，它就可以直 接存儲(chǔ)在這個(gè)位置上，不用再進(jìn)行任何比較了；如果這個(gè)位置上已經(jīng)有元素了，就調(diào)用它的equals方法與新元素進(jìn)行比較，相同的話就不存了，不相同就散列 其它的地址。所以這里存在一個(gè)沖突解決的問題。這樣一來實(shí)際調(diào)用equals方法的次數(shù)就大大降低了，幾乎只需要一兩次。 改寫equals時(shí)總是要改寫hashCode ============================================================ java.lnag.Object中對(duì)hashCode的約定： 1. 在一個(gè)應(yīng)用程序執(zhí)行期間，如果一個(gè)對(duì)象的equals方法做比較所用到的信息沒有被修改的話，則對(duì)該對(duì)象調(diào)用hashCode方法多次，它必須始終如一地返回同一個(gè)整數(shù)。
2. 如果兩個(gè)對(duì)象根據(jù)equals(Object o)方法是相等的，則調(diào)用這兩個(gè)對(duì)象中任一對(duì)象的hashCode方法必須產(chǎn)生相同的整數(shù)結(jié)果。 3. 如果兩個(gè)對(duì)象根據(jù)equals(Object o)方法是不相等的，則調(diào)用這兩個(gè)對(duì)象中任一個(gè)對(duì)象的hashCode方法，不要求產(chǎn)生不同的整數(shù)結(jié)果。但如果能不同，則可能提高散列表的性能。 有一個(gè)概念要牢記，兩個(gè)相等對(duì)象的equals方法一定為true, 但兩個(gè)hashcode相等的對(duì)象不一定是相等的對(duì)象。 所以hashcode相等只能保證兩個(gè)對(duì)象在一個(gè)HASH表里的同一條HASH鏈上，繼而通過equals方法才能確定是不是同一對(duì)象，如果結(jié)果為true, 則認(rèn)為是同一對(duì)象不在插入，否則認(rèn)為是不同對(duì)象繼續(xù)插入。
Object的代碼：
public String toString () { return this.getClass().getName() + "@" + Integer.toHexString(this.hashCode()); } public boolean equals (Object o) {
return this == o; } /**
* Answers an integer hash code for the receiver. Any two * objects which answer <code>true</code> when passed to * <code>.equals</code> must answer the same value for this * method. * * @author OTI * @version initial * * @return int * the receiver's hash. * * @see #equals */ public native int hashCode(); 從上面我們可以看到是否很可能Object.hashCode就是代表內(nèi)存地址。下面我們來證明hashcode是不是真的就是Object的內(nèi)存地址呢？實(shí)際上，hashcode根本不能代表object的內(nèi)存地址。 ----------------------------------------- Object.hashCode不可以代表內(nèi)存地址 ---------------------------------------- package com.tools;
import java.util.ArrayList;
/**
* 此方法的作用是證明 java.lang.Object的hashcode 不是代表 對(duì)象所在內(nèi)存地址。 * 我產(chǎn)生了10000個(gè)對(duì)象，這10000個(gè)對(duì)象在內(nèi)存中是不同的地址，但是實(shí)際上這10000個(gè)對(duì)象 * 的hashcode的是完全可能相同的 */ public class HashCodeMeaning { public static void main(String[] args) { ArrayList list = new ArrayList(); int numberExist=0; //證明hashcode的值不是內(nèi)存地址 for (int i = 0; i < 10000; i++) { Object obj=new Object(); if (list.contains(obj.toString())) { System.out.println(obj.toString() +" exists in the list. "+ i); numberExist++; } else { list.add(obj.toString()); } } System.out.println("repetition number:"+numberExist); System.out.println("list size:"+list.size()); //證明內(nèi)存地址是不同的。 numberExist=0; list.clear(); for (int i = 0; i < 10000; i++) { Object obj=new Object(); if (list.contains(obj)) { System.out.println(obj +" exists in the list. "+ i); numberExist++; } else { list.add(obj); } } System.out.println("repetition number:"+numberExist); System.out.println("list size:"+list.size()); } } ============================== 看HashTable的源代碼非常有用： ============================== ============================================================ 有效和正確定義hashCode()和equals()： ============================================================ 級(jí)別：入門級(jí)
每個(gè)Java對(duì)象都有hashCode()和 equals()方法。許多類忽略（Override)這些方法的缺省實(shí)施,以在對(duì)象實(shí)例之間提供更深層次的語義可比性。在Java理念和實(shí)踐這一部分， Java開發(fā)人員Brian Goetz向您介紹在創(chuàng)建Java類以有效和準(zhǔn)確定義hashCode()和equals()時(shí)應(yīng)遵循的規(guī)則和指南。您可以在討論論壇與作者和其它讀者一 同探討您對(duì)本文的看法。(您還可以點(diǎn)擊本文頂部或底部的討論進(jìn)入論壇。) 雖然Java語言不直接支持關(guān)聯(lián)數(shù)組 -- 可以使用任何對(duì)象作為一個(gè)索引的數(shù)組 -- 但在根Object類中使用hashCode()方法明確表示期望廣泛使用HashMap(及其前輩Hashtable)。理想情況下基于散列的容器提供 有效插入和有效檢索；直接在對(duì)象模式中支持散列可以促進(jìn)基于散列的容器的開發(fā)和使用。
定義對(duì)象的相等性
Object類有兩種方法來推斷對(duì)象的標(biāo)識(shí)：equals()和hashCode()。一般來說，如果您忽略了其中一種，您必須同時(shí)忽略這兩種，因?yàn)閮烧?之間有必須維持的至關(guān)重要的關(guān)系。特殊情況是根據(jù)equals() 方法，如果兩個(gè)對(duì)象是相等的，它們必須有相同的hashCode()值(盡管這通常不是真的)。
特定類的equals()的語義在Implementer的左側(cè)定義；定義對(duì)特定類來說equals()意味著什么是其設(shè)計(jì)工作的一部分。Object提供的缺省實(shí)施簡(jiǎn)單引用下面等式：
public boolean equals(Object obj) { return (this == obj); }
在這種缺省實(shí)施情況下，只有它們引用真正同一個(gè)對(duì)象時(shí)這兩個(gè)引用才是相等的。同樣，Object提供的 hashCode()的缺省實(shí)施通過將對(duì)象的內(nèi)存地址對(duì)映于一個(gè)整數(shù)值來生成。由于在某些架構(gòu)上，地址空間大于int值的范圍，兩個(gè)不同的對(duì)象有相同的 hashCode()是可能的。如果您忽略了hashCode()，您仍舊可以使用System.identityHashCode()方法來接入這類缺 省值。
忽略 equals() -- 簡(jiǎn)單實(shí)例
缺省情況下，equals()和hashCode()基于標(biāo)識(shí)的實(shí)施是合理的，但對(duì)于某些類來說，它們希望放寬等式的定義。例如，Integer類定義equals() 與下面類似：
public boolean equals(Object obj) {
return (obj instanceof Integer && intValue() == ((Integer) obj).intValue()); } 在這個(gè)定義中，只有在包含相同的整數(shù)值的情況下這兩個(gè)Integer對(duì)象是相等的。結(jié)合將不可修改的 Integer，這使得使用Integer作為HashMap中的關(guān)鍵字是切實(shí)可行的。這種基于值的Equal方法可以由Java類庫(kù)中的所有原始封裝類 使用，如Integer、Float、Character和Boolean以及String(如果兩個(gè)String對(duì)象包含相同順序的字符，那它們是相等 的)。由于這些類都是不可修改的并且可以實(shí)施hashCode()和equals()，它們都可以做為很好的散列關(guān)鍵字。
為什么忽略 equals()和hashCode()?
如果Integer不忽略equals() 和 hashCode()情況又將如何?如果我們從未在HashMap或其它基于散列的集合中使用Integer作為關(guān)鍵字的話，什么也不會(huì)發(fā)生。但是，如果 我們?cè)贖ashMap中使用這類Integer對(duì)象作為關(guān)鍵字，我們將不能夠可靠地檢索相關(guān)的值，除非我們?cè)趃et()調(diào)用中使用與put()調(diào)用中極其 類似的Integer實(shí)例。這要求確保在我們的整個(gè)程序中，只能使用對(duì)應(yīng)于特定整數(shù)值的Integer對(duì)象的一個(gè)實(shí)例。不用說，這種方法極不方便而且錯(cuò)誤 頻頻。
Object的interface contract要求如果根據(jù) equals()兩個(gè)對(duì)象是相等的，那么它們必須有相同的hashCode()值。當(dāng)其識(shí)別能力整個(gè)包含在equals()中時(shí)，為什么我們的根對(duì)象類需 要hashCode()？hashCode()方法純粹用于提高效率。Java平臺(tái)設(shè)計(jì)人員預(yù)計(jì)到了典型Java應(yīng)用程序中基于散列的集合類 （Collection Class)的重要性--如Hashtable、HashMap和HashSet，并且使用equals()與許多對(duì)象進(jìn)行比較在計(jì)算方面非常昂貴。使所 有Java對(duì)象都能夠支持 hashCode()并結(jié)合使用基于散列的集合，可以實(shí)現(xiàn)有效的存儲(chǔ)和檢索。
==============================
Go deep into HashCode： ============================== 為什么HashCode對(duì)于對(duì)象是如此的重要?
一個(gè)對(duì)象的HashCode就是一個(gè)簡(jiǎn)單的Hash算法的實(shí)現(xiàn),雖然它和那些真正的復(fù)雜的 Hash算法相比還不能叫真正的算法,但如何實(shí)現(xiàn)它,不僅僅是程序員的編程水平問題, 而是關(guān)系到你的對(duì)象在存取時(shí)性能的非常重要的問題.有可能,不同的HashCode可能 會(huì)使你的對(duì)象存取產(chǎn)生,成百上千倍的性能差別. 我們先來看一下,在JAVA中兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu):HashMap和Hashtable,雖然它們有很
大的區(qū)別,如繼承關(guān)系不同,對(duì)value的約束條件(是否允許null)不同,以及線程安全性 等有著特定的區(qū)別,但從實(shí)現(xiàn)原理上來說,它們是一致的.所以,我們只以Hashtable來 說明: 在java中,存取數(shù)據(jù)的性能,一般來說當(dāng)然是首推數(shù)組,但是在數(shù)據(jù)量稍大的容器選擇中,
Hashtable將有比數(shù)據(jù)性能更高的查詢速度.具體原因看下面的內(nèi)容. Hashtable在存儲(chǔ)數(shù)據(jù)時(shí),一般先將該對(duì)象的HashCode和0x7FFFFFFF做與操作,因?yàn)橐粋€(gè)
對(duì)象的HashCode可以為負(fù)數(shù),這樣操作后可以保證它為一個(gè)正整數(shù).然后以Hashtable的 長(zhǎng)度取模,得到該對(duì)象在Hashtable中的索引. index = (o.hashCode() & 0x7FFFFFFF)%hs.length;
這個(gè)對(duì)象就會(huì)直接放在Hashtable的第index位置,對(duì)于寫入,這和數(shù)組一樣,把一個(gè)對(duì)象 放在其中的第index位置,但如果是查詢,經(jīng)過同樣的算法,Hashtable可以直接從第index 取得這個(gè)對(duì)象,而數(shù)組卻要做循環(huán)比較.所以對(duì)于數(shù)據(jù)量稍大時(shí),Hashtable的查詢比數(shù)據(jù) 具有更高的性能. 既然可以根據(jù)HashCode直接定位對(duì)象在Hashtable中的位置,那么為什么Hashtable
要用key來做映射呢(為了一些思維有障礙的人能看到懂我加了一句話:而不是直接放value呢)?這就是關(guān)系Hashtable性能問題的最重要的問題:Hash沖突. 常見的Hash沖突是不同對(duì)象最終產(chǎn)生了相同的索引,而一種非常甚至絕對(duì)少見的Hash沖突
是,如果一組對(duì)象的個(gè)數(shù)大過了int范圍,而HashCode的長(zhǎng)度只能在int范圍中,所以肯定要 有同一組的元素有相同的HashCode,這樣無論如何他們都會(huì)有相同的索引.當(dāng)然這種極端 的情況是極少見的,可以暫不考慮,但對(duì)于相同的HashCode經(jīng)過取模,則會(huì)產(chǎn)中相同的索引, 或者不同的對(duì)象卻具有相同的HashCode,當(dāng)然具有相同的索引. 所以對(duì)于索引相同的對(duì)象,在該index位置存放了多個(gè)對(duì)象,這些值要想能正確區(qū)分,就要依
靠key本身和hashCode來識(shí)別. 事實(shí)上一個(gè)設(shè)計(jì)各好的HashTable,一般來說會(huì)比較平均地分布每個(gè)元素,因?yàn)镠ashtable
的長(zhǎng)度總是比實(shí)際元素的個(gè)數(shù)按一定比例進(jìn)行自增(裝填因子一般為0.75)左右,這樣大多 數(shù)的索引位置只有一個(gè)對(duì)象,而很少的位置會(huì)有幾個(gè)對(duì)象.所以Hashtable中的每個(gè)位置存 放的是一個(gè)鏈表,對(duì)于只有一個(gè)對(duì)象的位置,鏈表只有一個(gè)首節(jié)點(diǎn)(Entry),Entry的next為 null.然后有hashCode,key,value屬性保存了該位置的對(duì)象的HashCode,key和value(對(duì)象 本身),如果有相同索引的對(duì)象進(jìn)來則會(huì)進(jìn)入鏈表的下一個(gè)節(jié)點(diǎn).如果同一個(gè)位置中有多個(gè) 對(duì)象,根據(jù)HashCode和key可以在該鏈表中找到一個(gè)和查詢的key相匹配的對(duì)象. 從上面我看可以看到,對(duì)于HashMap和Hashtable的存取性能有重大影響的首先是應(yīng)該使該
數(shù)據(jù)結(jié)構(gòu)中的元素盡量大可能具有不同的HashCode,雖然這并不能保證不同的HashCode 產(chǎn)生不同的index,但相同的HashCode一定產(chǎn)生相同的index,從而影響產(chǎn)生Hash沖突. 對(duì)于一個(gè)象,如果具有很多屬性,把所有屬性都參與散列,顯然是一種笨拙的設(shè)計(jì).因?yàn)閷?duì)象
的HashCode()方法幾乎無所不在地被自動(dòng)調(diào)用,如equals比較,如果太多的對(duì)象參與了散列. 那么需要的操作常數(shù)時(shí)間將會(huì)增加很大.所以,挑選哪些屬性參與散列絕對(duì)是一個(gè)編程水平 的問題. 從實(shí)現(xiàn)來說,一般的HashCode方法會(huì)這樣:
return Attribute1.HashCode() + Attribute2.HashCode()...[+super.HashCode()],
我們知道,每次調(diào)用這個(gè)方法,都要重新對(duì)方法內(nèi)的參與散列的對(duì)象重新計(jì)算一次它們的
HashCode的運(yùn)算,如果一個(gè)對(duì)象的屬性沒有改變,仍然要每次都進(jìn)行計(jì)算,所以如果設(shè)置一 個(gè)標(biāo)記來緩存當(dāng)前的散列碼,只要當(dāng)參與散列的對(duì)象改變時(shí)才重新計(jì)算,否則調(diào)用緩存的 hashCode,這可以從很大程度上提高性能. 默認(rèn)的實(shí)現(xiàn)是將對(duì)象內(nèi)部地址轉(zhuǎn)化為整數(shù)作為HashCode,這當(dāng)然能保證每個(gè)對(duì)象具有不同 的HasCode,因?yàn)椴煌膶?duì)象內(nèi)部地址肯定不同(廢話),但java語言并不能讓程序員獲取對(duì) 象內(nèi)部地址,所以,讓每個(gè)對(duì)象產(chǎn)生不同的HashCode有著很多可研究的技術(shù). 如何從多個(gè)屬性中采樣出能具有多樣性的hashCode的屬性
|
|
|
