HashCode和hashMap、hashTable

2019獨角獸企業重金招聘Python工程師標準>>>

什么是哈希碼(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.Objectjava.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