HashCode和hashMap、hashTable
來自： http://my.oschina.net/yongqingfan/blog/628174
什么是哈希碼(HashCode)
在Java中，哈希碼代表對象的特征。
例如對象 String str1 = “aa”, str1.hashCode= 3104
String str2 = “bb”, str2.hashCode= 3106
String str3 = “aa”, str3.hashCode= 3104
根據HashCode由此可得出str1!=str2,str1==str3
下面給出幾個常用的哈希碼的算法。
1：Object類的hashCode.返回對象的內存地址經過處理后的結構，由于每個對象的內存地址都不一樣，所以哈希碼也不一樣。
2：String類的hashCode.根據String類包含的字符串的內容，根據一種特殊算法返回哈希碼，只要字符串所在的堆空間相同，返回的哈希碼也相同。
3：Integer類，返回的哈希碼就是Integer對象里所包含的那個整數的數值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可見，2個一樣大小的Integer對象，返回的哈希碼也一樣。
HashSet和HashMap一直都是JDK中最常用的兩個類，HashSet要求不能存儲相同的對象，HashMap要求不能存儲相同的鍵。
那么Java運行時環境是如何判斷HashSet中相同對象、HashMap中相同鍵的呢？當存儲了“相同的東西”之后Java運行時環境又將如何來維護呢？
在研究這個問題之前，首先說明一下JDK對equals(Object obj)和hashcode()這兩個方法的定義和規范：
在Java中任何一個對象都具備equals(Object obj)和hashcode()這兩個方法，因為他們是在Object類中定義的。
equals(Object obj)方法用來判斷兩個對象是否“相同”，如果“相同”則返回true，否則返回false。
hashcode()方法返回一個int數，在Object類中的默認實現是“將該對象的內部地址轉換成一個整數返回”。
接下來有兩個個關于這兩個方法的重要規范(我只是抽取了最重要的兩個,其實不止兩個)：
規范1：若重寫equals(Object obj)方法，有必要重寫hashcode()方法，確保通過equals(Object obj)方法判斷結果為true的兩個對象具備相等的hashcode()返回值。說得簡單點就是：“如果兩個對象相同，那么他們的hashcode應該 相等”。不過請注意：這個只是規范，如果你非要寫一個類讓equals(Object obj)返回true而hashcode()返回兩個不相等的值，編譯和運行都是不會報錯的。不過這樣違反了Java規范，程序也就埋下了BUG。
規范2：如果equals(Object obj)返回false，即兩個對象“不相同”，并不要求對這兩個對象調用hashcode()方法得到兩個不相同的數。說的簡單點就是：“如果兩個對象不相同，他們的hashcode可能相同”。
根據這兩個規范，可以得到如下推論：
1、如果兩個對象equals，Java運行時環境會認為他們的hashcode一定相等。
2、如果兩個對象不equals，他們的hashcode有可能相等。
3、如果兩個對象hashcode相等，他們不一定equals。
4、如果兩個對象hashcode不相等，他們一定不equals。
這樣我們就可以推斷Java運行時環境是怎樣判斷HashSet和HastMap中的兩個對象相同或不同了。我的推斷是：先判斷hashcode是否相等，再判斷是否equals。
測試程序如下：首先我們定義一個類，重寫hashCode()和equals(Object obj)方法
class A {
@Override
public boolean equals(Object obj) {
System.out.println("判斷equals");
return false;
}
@Override
public int hashCode() {
System.out.println("判斷hashcode");
return 1;
}
} 然后寫一個測試類，代碼如下：
public class Test {
public static void main(String[] args) {
Map<A,Object> map = new HashMap<A, Object>();
map.put(new A(), new Object());
map.put(new A(), new Object());
System.out.println(map.size());
}
} 運行之后打印結果是：
判斷hashcode
判斷hashcode
判斷equals
HashCode的作用
首先，想要明白hashCode的作用，你必須要先知道Java中的集合。
總的來說，Java中的集合（Collection）有兩類，一類是List，再有一類是Set。你知道它們的區別嗎？前者集合內的元素是有序的，元素可以重復；后者元素無序，但元素不可重復。那么這里就有一個比較嚴重的問題了：要想保證元素不重復，可兩個元素是否重復應該依據什么來判斷呢？這就是Object.equals方法了。但是，如果每增加一個元素就檢查一次，那么當元素很多時，后添加到集合中的元素比較的次數就非常多了。也就是說，如果集合中現在已經有1000個元素，那么第1001個元素加入集合時，它就要調用1000次equals方法。這顯然會大大降低效率。
于是，Java采用了哈希表的原理。哈希（Hash）實際上是個人名，由于他提出一哈希算法的概念，所以就以他的名字命名了。哈希算法也稱為散列算法，是將數據依特定算法直接指定到一個地址上。如果詳細講解哈希算法，那需要更多的文章篇幅，我在這里就不介紹了。初學者可以這樣理解，hashCode方法實際上返回的就是對象存儲的物理地址（PS：這是一種算法，數據結構里面有提到。在某一個地址上（對應一個哈希值，該值并不特指內存地址），存儲的是一個鏈表。在put一個新值時，根據該新值計算出哈希值，找到相應的位置，發現該位置已經蹲了一個，則新值就鏈接到舊值的下面，由舊值指向（next）它（也可能是倒過來指。。。）。可以參考HashMap）。
這樣一來，當集合要添加新的元素時，先調用這個元素的hashCode方法，就一下子能定位到它應該放置的物理位置上。如果這個位置上沒有元素，它就可以直接存儲在這個位置上，不用再進行任何比較了；如果這個位置上已經有元素了，就調用它的equals方法與新元素進行比較，相同的話就不存了，不相同就散列其它的地址。所以這里存在一個沖突解決的問題。這樣一來實際調用equals方法的次數就大大降低了，幾乎只需要一兩次。
所以，Java對于eqauls方法和hashCode方法是這樣規定的：
1、如果兩個對象相同，那么它們的hashCode值一定要相同；
2、如果兩個對象的hashCode相同，它們并不一定相同
上面說的對象相同指的是用eqauls方法比較。
你當然可以不按要求去做了，但你會發現，相同的對象可以出現在Set集合中。同時，增加新元素的效率會大大下降。
怎么重寫HashCode?
下面介紹如何來重寫hashCode()方法。通常重寫hashCode()方法按以下設計原則實現。
（1）把某個非零素數，例如17，保存在int型變量result中。
（2）對于對象中每一個關鍵域f（指equals方法中考慮的每一個域）參照以下原則處理。
boolean型，計算（f?0:1)。
byte、char和short型，計算(int)f。
long型，計算(int)(f^(f>>32))。
float型，計算Float.floatToIntBits(f)。
double型，計算Double.doubleToLongBits(f)得到一個long，再執行long型的處理。
對象引用，遞歸調用它的hashCode()方法。
數組域，對其中的每個元素調用它的hashCode()方法。
（3）將上面計算得到的散列碼保存到int型變量c，然后執行result = 37 * result + c。
（4）返回result。
類 HashMap<K,V>
java.lang.Object java.util.AbstractMap<K,V> java.util.HashMap<K,V>
類型參數：
K- 此映射所維護的鍵的類型V- 所映射值的類型基于哈希表的 Map 接口的實現。此實現提供所有可選的映射操作，并允許使用 null 值和null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恒久不變。
HashCode和HashMap之間的關系
先如下代碼:
import java.util.HashMap;
public class Test {
//重寫Equals不重寫HashCode
static class Key {
private Integer id;
private String value;
public Key(Integer id, String value) {
super();
this.id = id;
this.value = value;
}
@Override
public boolean equals(Object o) {
if(o == null || !(o instanceof Key)) {
return false;
}else {
return this.id.equals(((Key)o).id);
}
}
}
//重寫Equals也重寫HashCode
static class Key_ {
private Integer id;
private String value;
public Key_(Integer id, String value) {
super();
this.id = id;
this.value = value;
}
@Override
public boolean equals(Object o) {
if(o == null || !(o instanceof Key_)) {
return false;
}else {
return this.id.equals(((Key_)o).id);
}
}
@Override
public int hashCode() {
return id.hashCode();
}
}
public static void main(String[] args) {
//test hashcode
HashMap<Object, String> values = new HashMap<Object, String>(5);
Test.Key key1 = new Test.Key(1, "one");
Test.Key key2 = new Test.Key(1, "one");
System.out.println(key1.equals(key2));
values.put(key1, "value 1");
System.out.println(values.get(key2));
Test.Key_ key_1 = new Test.Key_(1, "one");
Test.Key_ key_2 = new Test.Key_(1, "one");
System.out.println(key_1.equals(key_2));
System.out.println(key_1 == key_2);
values.put(key_1, "value 1");
System.out.println(values.get(key_2));
}
} 輸出如下:
由上述例子可見:只重寫了equasl方法的Key類 在用做Hash中的鍵值的時候 兩個equasl為true的對象不能獲取相應 的Value的而重寫了hashCode方法和equals方法的key_類 兩個相等的對象 可以獲取同一個Value的,這樣更符合生活中 的邏輯HashMap對象是根據Key的hashCode來獲取對應的Vlaue 因而兩個HashCode相同的對象可以獲取同一個Value
<span style="color:#cc66cc;"> </span>