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