歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

淺談Java中的hashcode方法

  哈希表這個數據結構想必大多數人都不陌生,而且在很多地方都會利用到hash表來提高查找效率。在Java的Object類中有一個方法:

  public native int hashCode();

  根據這個方法的聲明可知,該方法返回一個int類型的數值,並且是本地方法,因此在Object類中並沒有給出具體的實現。

  為何Object類需要這樣一個方法?它有什麼作用呢?今天我們就來具體探討一下hashCode方法。

一.hashCode方法的作用

  對於包含容器類型的程序設計語言來說,基本上都會涉及到hashCode。在Java中也一樣,hashCode方法的主要作用是為了配合基於散列的集合一起正常運行,這樣的散列集合包括HashSet、HashMap以及HashTable。

  為什麼這麼說呢?考慮一種情況,當向集合中插入對象時,如何判別在集合中是否已經存在該對象了?(注意:集合中不允許重復的元素存在)

  也許大多數人都會想到調用equals方法來逐個進行比較,這個方法確實可行。但是如果集合中已經存在一萬條數據或者更多的數據,如果采用equals方法去逐一比較,效率必然是一個問題。此時hashCode方法的作用就體現出來了,當集合要添加新的對象時,先調用這個對象的hashCode方法,得到對應的hashcode值,實際上在HashMap的具體實現中會用一個table保存已經存進去的對象的hashcode值,如果table中沒有該hashcode值,它就可以直接存進去,不用再進行任何比較了;如果存在該hashcode值, 就調用它的equals方法與新元素進行比較,相同的話就不存了,不相同就散列其它的地址,所以這裡存在一個沖突解決的問題,這樣一來實際調用equals方法的次數就大大降低了,說通俗一點:Java中的hashCode方法就是根據一定的規則將與對象相關的信息(比如對象的存儲地址,對象的字段等)映射成一個數值,這個數值稱作為散列值。下面這段代碼是java.util.HashMap的中put方法的具體實現:

public V put(K key, V value) {

        if (key == null)

            return putForNullKey(value);

        int hash = hash(key.hashCode());

        int i = indexFor(hash, table.length);

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i);

        return null;

    }

  put方法是用來向HashMap中添加新的元素,從put方法的具體實現可知,會先調用hashCode方法得到該元素的hashCode值,然後查看table中是否存在該hashCode值,如果存在則調用equals方法重新確定是否存在該元素,如果存在,則更新value值,否則將新的元素添加到HashMap中。從這裡可以看出,hashCode方法的存在是為了減少equals方法的調用次數,從而提高程序效率。

有些朋友誤以為默認情況下,hashCode返回的就是對象的存儲地址,事實上這種看法是不全面的,確實有些JVM在實現時是直接返回對象的存儲地址,但是大多時候並不是這樣,只能說可能存儲地址有一定關聯。下面是HotSpot JVM中生成hash散列值的實現:

static inline intptr_t get_next_hash(Thread * Self, oop obj) {

  intptr_t value = 0 ;

  if (hashCode == 0) {

    // This form uses an unguarded global Park-Miller RNG,

    // so it's possible for two threads to race and generate the same RNG.

    // On MP system we'll have lots of RW access to a global, so the

    // mechanism induces lots of coherency traffic.

    value = os::random() ;

  } else

  if (hashCode == 1) {

    // This variation has the property of being stable (idempotent)

    // between STW operations.  This can be useful in some of the 1-0

    // synchronization schemes.

    intptr_t addrBits = intptr_t(obj) >> 3 ;

    value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;

  } else

  if (hashCode == 2) {

    value = 1 ;            // for sensitivity testing

  } else

  if (hashCode == 3) {

    value = ++GVars.hcSequence ;

  } else

  if (hashCode == 4) {

    value = intptr_t(obj) ;

  } else {

    // Marsaglia's xor-shift scheme with thread-specific state

    // This is probably the best overall implementation -- we'll

    // likely make this the default in future releases.

    unsigned t = Self->_hashStateX ;

    t ^= (t << 11) ;

    Self->_hashStateX = Self->_hashStateY ;

    Self->_hashStateY = Self->_hashStateZ ;

    Self->_hashStateZ = Self->_hashStateW ;

    unsigned v = Self->_hashStateW ;

    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;

    Self->_hashStateW = v ;

    value = v ;

  }

  value &= markOopDesc::hash_mask;

  if (value == 0) value = 0xBAD ;

  assert (value != markOopDesc::no_hash, "invariant") ;

  TEVENT (hashCode: GENERATE) ;

  return value;

}

  該實現位於hotspot/src/share/vm/runtime/synchronizer.cpp文件下。

  因此有人會說,可以直接根據hashcode值判斷兩個對象是否相等嗎?肯定是不可以的,因為不同的對象可能會生成相同的hashcode值。雖然不能根據hashcode值判斷兩個對象是否相等,但是可以直接根據hashcode值判斷兩個對象不等,如果兩個對象的hashcode值不等,則必定是兩個不同的對象。如果要判斷兩個對象是否真正相等,必須通過equals方法。

  也就是說對於兩個對象,如果調用equals方法得到的結果為true,則兩個對象的hashcode值必定相等;

  如果equals方法得到的結果為false,則兩個對象的hashcode值不一定不同;

  如果兩個對象的hashcode值不等,則equals方法得到的結果必定為false;

  如果兩個對象的hashcode值相等,則equals方法得到的結果未知。

二.equals方法和hashCode方法

  在有些情況下,程序設計者在設計一個類的時候為需要重寫equals方法,比如String類,但是千萬要注意,在重寫equals方法的同時,必須重寫hashCode方法。為什麼這麼說呢?

  下面看一個例子:

package com.cxh.test1;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Set;

class People{

    private String name;

    private int age;

   

    public People(String name,int age) {

        this.name = name;

        this.age = age;

    } 

   

    public void setAge(int age){

        this.age = age;

    }

       

    @Override

    public boolean equals(Object obj) {

        // TODO Auto-generated method stub

        return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;

    }

}

public class Main {

    public static void main(String[] args) {

       

        People p1 = new People("Jack", 12);

        System.out.println(p1.hashCode());

           

        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();

        hashMap.put(p1, 1);

       

        System.out.println(hashMap.get(new People("Jack", 12)));

    }

}

  在這裡我只重寫了equals方法,也就說如果兩個People對象,如果它的姓名和年齡相等,則認為是同一個人。

  這段代碼本來的意願是想這段代碼輸出結果為“1”,但是事實上它輸出的是“null”。為什麼呢?原因就在於重寫equals方法的同時忘記重寫hashCode方法。

  雖然通過重寫equals方法使得邏輯上姓名和年齡相同的兩個對象被判定為相等的對象(跟String類類似),但是要知道默認情況下,hashCode方法是將對象的存儲地址進行映射。那麼上述代碼的輸出結果為“null”就不足為奇了。原因很簡單,p1指向的對象和

  System.out.println(hashMap.get(new People("Jack", 12)));這句中的new People("Jack", 12)生成的是兩個對象,它們的存儲地址肯定不同。下面是HashMap的get方法的具體實現:

public V get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

                return e.value;

        }

        return null;

    }

  所以在hashmap進行get操作時,因為得到的hashcdoe值不同(注意,上述代碼也許在某些情況下會得到相同的hashcode值,不過這種概率比較小,因為雖然兩個對象的存儲地址不同也有可能得到相同的hashcode值),所以導致在get方法中for循環不會執行,直接返回null���

  因此如果想上述代碼輸出結果為“1”,很簡單,只需要重寫hashCode方法,讓equals方法和hashCode方法始終在邏輯上保持一致性。

package com.cxh.test1;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Set;

class People{

    private String name;

    private int age;

   

    public People(String name,int age) {

        this.name = name;

        this.age = age;

    } 

   

    public void setAge(int age){

        this.age = age;

    }

   

    @Override

    public int hashCode() {

        // TODO Auto-generated method stub

        return name.hashCode()*37+age;

    }

   

    @Override

    public boolean equals(Object obj) {

        // TODO Auto-generated method stub

        return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;

    }

}

public class Main {

    public static void main(String[] args) {

       

        People p1 = new People("Jack", 12);

        System.out.println(p1.hashCode());

           

        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();

        hashMap.put(p1, 1);

       

        System.out.println(hashMap.get(new People("Jack", 12)));

    }

}

  這樣一來的話,輸出結果就為“1”了。

  下面這段話摘自Effective Java一書:
•在程序執行期間,只要equals方法的比較操作用到的信息沒有被修改,那麼對這同一個對象調用多次,hashCode方法必須始終如一地返回同一個整數。
•如果兩個對象根據equals方法比較是相等的,那麼調用兩個對象的hashCode方法必須返回相同的整數結果。
•如果兩個對象根據equals方法比較是不等的,則hashCode方法不一定得返回不同的整數。

  對於第二條和第三條很好理解,但是第一條,很多時候就會忽略。在《Java編程思想》一書中的P495頁也有同第一條類似的一段話:

  “設計hashCode()時最重要的因素就是:無論何時,對同一個對象調用hashCode()都應該產生同樣的值。如果在講一個對象用put()添加進HashMap時產生一個hashCdoe值,而用get()取出時卻產生了另一個hashCode值,那麼就無法獲取該對象了。所以如果你的hashCode方法依賴於對象中易變的數據,用戶就要當心了,因為此數據發生變化時,hashCode()方法就會生成一個不同的散列碼”。

  下面舉個例子:

package com.cxh.test1;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Set;

class People{

    private String name;

    private int age;

    public People(String name,int age) {

        this.name = name;

        this.age = age;

    } 

   

    public void setAge(int age){

        this.age = age;

    }

   

    @Override

    public int hashCode() {

        // TODO Auto-generated method stub

        return name.hashCode()*37+age;

    }

   

    @Override

    public boolean equals(Object obj) {

        // TODO Auto-generated method stub

        return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;

    }

}

public class Main {

    public static void main(String[] args) {

       

        People p1 = new People("Jack", 12);

        System.out.println(p1.hashCode());

       

        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();

        hashMap.put(p1, 1);

       

        p1.setAge(13);

       

        System.out.println(hashMap.get(p1));

    }

}

  這段代碼輸出的結果為“null”,想必其中的原因大家應該都清楚了。

  因此,在設計hashCode方法和equals方法的時候,如果對象中的數據易變,則最好在equals方法和hashCode方法中不要依賴於該字段。

  以上屬個人理解,如有不正之處,歡迎批評指正。

Copyright © Linux教程網 All Rights Reserved