第1 部分 hashCode的作用

　　Java集合中有兩類，一類是List，一類是Set他們之間的區(qū)別就在于List集合中的元素師有序的，且可以重復(fù)，而Set集合中元素是無(wú)序不可重復(fù)的。對(duì)于List好處理，但是對(duì)于Set而言我們要如何來(lái)保證元素不重復(fù)呢？通過(guò)迭代來(lái)equals()是否相等。數(shù)據(jù)量小還可以接受，當(dāng)我們的數(shù)據(jù)量大的時(shí)候效率可想而知（當(dāng)然我們可以利用算法進(jìn)行優(yōu)化）。比如我們向HashSet插入1000數(shù)據(jù)，難道我們真的要迭代1000次，調(diào)用1000次equals()方法嗎？hashCode提供了解決方案。怎么實(shí)現(xiàn)？我們先看hashCode的源碼(Object)。

public native int hashCode();

　　它是一個(gè)本地方法，它的實(shí)現(xiàn)與本地機(jī)器有關(guān)，這里我們暫且認(rèn)為他返回的是對(duì)象存儲(chǔ)的物理位置（實(shí)際上不是，這里寫(xiě)是便于理解）。當(dāng)我們向一個(gè)集合中添加某個(gè)元素，集合會(huì)首先調(diào)用hashCode方法，這樣就可以直接定位它所存儲(chǔ)的位置，若該處沒(méi)有其他元素，則直接保存。若該處已經(jīng)有元素存在，就調(diào)用equals方法來(lái)匹配這兩個(gè)元素是否相同，相同則不存，不同則散列到其他位置。這樣處理，當(dāng)我們存入大量元素時(shí)就可以大大減少調(diào)用equals()方法的次數(shù)，極大地提高了效率。

　　所以hashCode在上面扮演的角色為尋域（尋找某個(gè)對(duì)象在集合中區(qū)域位置）。hashCode可以將集合分成若干個(gè)區(qū)域，每個(gè)對(duì)象都可以計(jì)算出他們的hash碼，可以將hash碼分組，每個(gè)分組對(duì)應(yīng)著某個(gè)存儲(chǔ)區(qū)域，根據(jù)一個(gè)對(duì)象的hash碼就可以確定該對(duì)象所存儲(chǔ)區(qū)域，這樣就大大減少查詢匹配元素的數(shù)量，提高了查詢效率。 

　　如何理解hashCode的作用:

　　以java.lang.Object來(lái)理解,JVM每new一個(gè)Object,它都會(huì)將這個(gè)Object丟到一個(gè)Hash哈希表中去,這樣的話,下次做Object的比較或者取這個(gè)對(duì)象的時(shí)候,它會(huì)根據(jù)對(duì)象的hashcode再?gòu)腍ash表中取這個(gè)對(duì)象。這樣做的目的是提高取對(duì)象的效率。具體過(guò)程是這樣:

1.new Object(),JVM根據(jù)這個(gè)對(duì)象的Hashcode值,放入到對(duì)應(yīng)的Hash表對(duì)應(yīng)的Key上,如果不同的對(duì)象確產(chǎn)生了相同的hash值,也就是發(fā)生了Hash key相同導(dǎo)致沖突的情況,那么就在這個(gè)Hash key的地方產(chǎn)生一個(gè)鏈表,將所有產(chǎn)生相同hashcode的對(duì)象放到這個(gè)單鏈表上去,串在一起。

2.比較兩個(gè)對(duì)象的時(shí)候,首先根據(jù)他們的hashcode去hash表中找他的對(duì)象,當(dāng)兩個(gè)對(duì)象的hashcode相同,那么就是說(shuō)他們這兩個(gè)對(duì)象放在Hash表中的同一個(gè)key上,那么他們一定在這個(gè)key上的鏈表上。那么此時(shí)就只能根據(jù)Object的equal方法來(lái)比較這個(gè)對(duì)象是否equal。當(dāng)兩個(gè)對(duì)象的hashcode不同的話，肯定他們不能equal.

java.lang.Object中對(duì)hashCode的約定：

   1. 在一個(gè)應(yīng)用程序執(zhí)行期間，如果一個(gè)對(duì)象的equals方法做比較所用到的信息沒(méi)有被修改的話，則對(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鏈上，繼而通過(guò)equals方法才能確定是不是同一對(duì)象，如果結(jié)果為true, 則認(rèn)為是同一對(duì)象在插入，否則認(rèn)為是不同對(duì)象繼續(xù)插入。 

第2部分 hashCode對(duì)于一個(gè)對(duì)象的重要性

　　一個(gè)對(duì)象的HashCode就是一個(gè)簡(jiǎn)單的Hash算法的實(shí)現(xiàn)，雖然它和那些真正的復(fù)雜的Hash算法相比還不能叫真正的算法，它如何實(shí)現(xiàn)它，不僅僅是程序員的編程水平問(wèn)題， 而是關(guān)系到你的對(duì)象在存取是性能的非常重要的關(guān)系.有可能，不同的HashCode可能會(huì)使你的對(duì)象存取產(chǎn)生，成百上千倍的性能差別。先來(lái)看一下，在JAVA中兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu):HashMap和Hashtable，雖然它們有很大的區(qū)別，如繼承關(guān)系不同，對(duì)value的約束條件(是否允許null)不同，以及線程安全性等有著特定的區(qū)別，但從實(shí)現(xiàn)原理上來(lái)說(shuō)，它們是一致的。所以，只以Hashtable來(lái)說(shuō)明：

　　在java中，存取數(shù)據(jù)的性能，一般來(lái)說(shuō)當(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中的索引。

int index = (hash & 0x7FFFFFFF) % tab.length;

這個(gè)對(duì)象就會(huì)直接放在Hashtable的每index位置，對(duì)于寫(xiě)入，這和數(shù)據(jù)一樣，把一個(gè)對(duì)象放在其中的第index位置，但如果是查詢，經(jīng)過(guò)同樣的算法，Hashtable可以直接從第index取得這個(gè)對(duì)象，而數(shù)組卻要做循環(huán)比較.所以對(duì)于數(shù)據(jù)量稍大時(shí)，Hashtable的查詢比數(shù)據(jù)具有更高的性能。

既然一個(gè)對(duì)象可以根據(jù)HashCode直接定位它在Hashtable中的位置，那么為什么Hashtable還要用key來(lái)做映射呢?這就是關(guān)系Hashtable性能問(wèn)題的最重要的問(wèn)題：Hash沖突。

　　常見(jiàn)的Hash沖突是不同對(duì)象最終產(chǎn)生了相同的索引，而一種非常甚至絕對(duì)少見(jiàn)的Hash沖突是，如果一組對(duì)象的個(gè)數(shù)大過(guò)了int 范圍，而HashCode的長(zhǎng)度只能在int范圍中，所以肯定要有同一組的元素有相同的HashCode，這樣無(wú)論如何他們都會(huì)有相同的 索引。當(dāng)然這種極端的情況是極少見(jiàn)的，可以暫不考慮，但是對(duì)于同的HashCode經(jīng)過(guò)取模，則會(huì)產(chǎn)生相同的索引，或者不同 的對(duì)象卻具有相同的HashCode，當(dāng)然具有相同的索引。所以對(duì)于索引相同的對(duì)象，在該index位置存放了多個(gè)值，這些值要想能正確區(qū)分，就要依靠key來(lái)識(shí)別。事實(shí)上一個(gè)設(shè)計(jì)各好的HashTable，一般來(lái)說(shuō)會(huì)比較平均地分布每個(gè)元素，因?yàn)镠ashtable的長(zhǎng)度總是比實(shí)際元素的個(gè)數(shù)按一 定比例進(jìn)行自增(裝填因子一般為0.75)左右，這樣大多數(shù)的索引位置只有一個(gè)對(duì)象，而很少的位置會(huì)有幾個(gè)元素，所以 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)來(lái)則 會(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()方法幾乎無(wú)所不在 地被自動(dòng)調(diào)用，如equals比較，如果太多的對(duì)象參與了散列。那么需要的操作常數(shù)時(shí)間將會(huì)增加很大。所以，挑選哪些屬性參與散列絕對(duì)是一個(gè)編程水平的問(wèn)題。

我們知道，每次調(diào)用HashCode方法方法，都要重新 對(duì)方法內(nèi)的參與散列的對(duì)象重新計(jì)算一次它們的HashCode的運(yùn)算，如果一個(gè)對(duì)象的屬性沒(méi)有改變，仍然要每次都進(jìn)行計(jì)算， 所以如果設(shè)置一個(gè)標(biāo)記來(lái)緩存當(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語(yǔ)言并不能讓程序員獲取對(duì)象內(nèi)部地址，所以，讓每個(gè)對(duì)象產(chǎn)生不同的HashCode有著很多可研究 的技術(shù)。如果從多個(gè)屬性中采樣出能具有平均分布的hashCode的屬性，這是一個(gè)性能和多樣性相矛盾的地方，如果所有屬性都參與散 列，當(dāng)然hashCode的多樣性將大大提高，但犧牲了性能，而如果只能少量的屬性采樣散列，極端情況會(huì)產(chǎn)生大量的散列沖突 ，如對(duì)"人"的屬性中，如果用性別而不是姓名或出生日期，那將只有兩個(gè)或幾個(gè)可選的hashcode值，將產(chǎn)生一半以上的散列 沖突.所以如果可能的條件下，專門(mén)產(chǎn)生一個(gè)序列用來(lái)生成HashCode將是一個(gè)好的選擇(當(dāng)然產(chǎn)生序列的性能要比所有屬性參 與散列的性能高的情況下才行，否則還不如直接用所有屬性散列). 如何對(duì)HashCode的性能和多樣性求得一個(gè)平衡，可以參考相關(guān)算法設(shè)計(jì)的書(shū)，其實(shí)并不一定要求非常的優(yōu)秀，只要能盡最大 可能減少散列值的聚集。重要的是我們應(yīng)該記得HashCode對(duì)于我們的程序性能有著重要的影響，在程序設(shè)計(jì)時(shí)應(yīng)該時(shí)時(shí)加以注 意.

請(qǐng)記?。喝绻阆胗行У氖褂肏ashMap，你就必須重寫(xiě)在其的HashCode()。

還有兩條重寫(xiě)HashCode()的原則：

1.不必對(duì)每個(gè)不同的對(duì)象都產(chǎn)生一個(gè)唯一的hashcode，只要你的HashCode方法使get()能夠得到put()放進(jìn)去的內(nèi)容就可以了。即“不為一原則”。

2.生成hashcode的算法盡量使hashcode的值分散一些， 不要很多hashcode都集中在一個(gè)范圍內(nèi)，這樣有利 于提高HashMap的性能。即“分散原則”。

至于第二條原則的具體原因，有興趣者可以參考Bruce Eckel的《Thinking in Java》，在那里有對(duì)HashMap內(nèi)部實(shí)現(xiàn)原理的介紹，這里就不贅述了。 

第3部分 hashCode與equals

在Java中hashCode的實(shí)現(xiàn)總是伴隨著equals，他們是緊密配合的，你要是自己設(shè)計(jì)了其中一個(gè)，就要設(shè)計(jì)另外一個(gè)。當(dāng)然在多數(shù)情況下，這兩個(gè)方法是不用我們考慮的，直接使用默認(rèn)方法就可以幫助我們解決很多問(wèn)題。但是在有些情況，我們必須要自己動(dòng)手來(lái)實(shí)現(xiàn)它，才能確保程序更好的運(yùn)作。

      對(duì)于equals，我們必須遵循如下規(guī)則：

      對(duì)稱性：如果x.equals(y)返回是“true”，那么y.equals(x)也應(yīng)該返回是“true”。

      反射性：x.equals(x)必須返回是“true”。

      類推性：如果x.equals(y)返回是“true”，而且y.equals(z)返回是“true”，那么z.equals(x)也應(yīng)該返回是“true”。

      一致性：如果x.equals(y)返回是“true”，只要x和y內(nèi)容一直不變，不管你重復(fù)x.equals(y)多少次，返回都是“true”。

      任何情況下，x.equals(null)，永遠(yuǎn)返回是“false”；x.equals(和x不同類型的對(duì)象)永遠(yuǎn)返回是“false”。

      對(duì)于hashCode，我們應(yīng)該遵循如下規(guī)則：

      1. 在一個(gè)應(yīng)用程序執(zhí)行期間，如果一個(gè)對(duì)象的equals方法做比較所用到的信息沒(méi)有被修改的話，則對(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é)果。但如果能不同，則可能提高散列表的性能。

      至于兩者之間的關(guān)聯(lián)關(guān)系，我們只需要記住如下即可：

      如果x.equals(y)返回“true”，那么x和y的hashCode()必須相等。

      如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等。

      理清了上面的關(guān)系我們就知道他們兩者是如何配合起來(lái)工作的。先看下圖： 

      整個(gè)處理流程是：

      1、判斷兩個(gè)對(duì)象的hashcode是否相等，若不等，則認(rèn)為兩個(gè)對(duì)象不等，完畢，若相等，則比較equals。

      2、若兩個(gè)對(duì)象的equals不等，則可以認(rèn)為兩個(gè)對(duì)象不等，否則認(rèn)為他們相等。

實(shí)例： 

 package com.weakHashMap;
 /**
 * 重新實(shí)現(xiàn)了hashCode方法和equals方法
 * @ClassName: Person 
 * 
 * 
 */
 public class Person {
  private int age;
  private int sex; // 0：男，1：女
  private String name;
  private final int PRIME = 37;
  Person(int age ,int sex ,String name){
   this.age = age;
   this.sex = sex;
   this.name = name;
  }
  public int getAge() {
   return age;
  }
  public void setAge(int age) {
   this.age = age;
  }
  public int getSex() {
   return sex;
  }
  public void setSex(int sex) {
   this.sex = sex;
  }
  public String getName() {
   return name;
  }
  public void setName(String name) {
   this.name = name;
  }
  @Override
  public int hashCode() {
   System.out.println("調(diào)用hashCode方法...........");
   int hashResult = 1;
   hashResult = (hashResult + Integer.valueOf(age).hashCode() + Integer.valueOf(sex).hashCode()) * PRIME;
   hashResult = PRIME * hashResult + ((name == null) ? 0 : name.hashCode()); 
   System.out.println("name:"+name +" hashCode:" + hashResult);
   return hashResult;
  }
  /**
  * 重寫(xiě)hashCode()
  */
  public boolean equals(Object obj) {
   System.out.println("調(diào)用equals方法...........");
   if(obj == null){
    return false;
   }
   if(obj.getClass() != this.getClass()){
    return false;
   }
   if(this == obj){
    return true;
   }
   Person person = (Person) obj;
   if(getAge() != person.getAge() || getSex()!= person.getSex()){
    return false;
   }
   if(getName() != null){
    if(!getName().equals(person.getName())){
     return false;
    }
   }
   else if(person != null){
    return false;
   }
   return true;
  }
 
 }
 
 package com.weakHashMap;
 import java.util.HashSet;
 import java.util.Set;
 /**
 * 
 * @ClassName: test1
 * TODO *
 * 
 */
 public class test extends Person{
  /**
  * @param age
  * @param sex
  * @param name
  */
  test(int age, int sex, String name) {
   super(age, sex, name);
   // TODO Auto-generated constructor stub
  }
  public static void main(String[] args){
   Set<Person> set = new HashSet<Person>();
   Person p1 = new Person(11, 1, "張三");
   Person p2 = new Person(12, 1, "李四");
  Person p3 = new Person(11, 1, "張三");
   Person p4 = new Person(11, 1, "李四");
   //只驗(yàn)證p1、p3
   System.out.println("p1 == p3? :" + (p1 == p3));
  System.out.println("p1.equals(p3)?:"+p1.equals(p3));
   System.out.println("-----------------------分割線--------------------------");
  set.add(p1);
  set.add(p2);
  set.add(p3);
   set.add(p4);
  System.out.println("set.size()="+set.size());
 }
 }

結(jié)果：

p1 == p3? :false
調(diào)用equals方法...........
p1.equals(p3)?:true
-----------------------分割線--------------------------
調(diào)用hashCode方法...........
name:張三 hashCode:792686
調(diào)用hashCode方法...........
name:李四 hashCode:861227
調(diào)用hashCode方法...........
name:張三 hashCode:792686
調(diào)用equals方法...........
調(diào)用hashCode方法...........
name:李四 hashCode:859858
set.size()=3 

可以看到張三的兩次hashCode相同，調(diào)用equals進(jìn)行匹配，最后hashCode 和 equals 都返回true，則不添加。

以上所述是小編給大家介紹的Java 中HashCode作用_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

最新評(píng)論