快捷導(dǎo)航

Java hashCode() 方法詳細(xì)解讀

更新時(shí)間：2016年07月06日 15:19:02 投稿：lqh

Java.lang.Object 有一個(gè)hashCode()和一個(gè)equals()方法，這兩個(gè)方法在軟件設(shè)計(jì)中扮演著舉足輕重的角色，本文對(duì)hashCode()方法深入理解，希望能幫助大家

1.WHY hashCode()?

集合Set中的元素是無(wú)序不可重復(fù)的，那判斷兩個(gè)元素是否重復(fù)的依據(jù)是什么呢？ “比較對(duì)象是否相等當(dāng)然用Object.equal()了”，某猿如是說(shuō)。但是，Set中存在大量對(duì)象，后添加到集合Set中的對(duì)象元素比較次數(shù)會(huì)逐漸增多，大大降低了程序運(yùn)行效率。 Java中采用哈希算法(也叫散列算法)來(lái)解決這個(gè)問題，將對(duì)象(或數(shù)據(jù))依特定算法直接映射到一個(gè)地址上，對(duì)象的存取效率大大提高。這樣一來(lái)，當(dāng)含有海量元素的集合Set需要添加某元素(對(duì)象)時(shí)，先調(diào)用這個(gè)元素的hashCode()，就能一下子定位到此元素實(shí)際存儲(chǔ)位置，如果這個(gè)位置沒有元素，說(shuō)明此對(duì)象時(shí)第一次存儲(chǔ)到集合Set, 直接將此對(duì)象存儲(chǔ)在此位置上；若此位置有對(duì)象存在，調(diào)用equal()看看這兩個(gè)對(duì)象是否相等，相等就舍棄此元素不存，不等則散列到其他地址。

2.HOW use hashCode()?

Java語(yǔ)言對(duì)猿設(shè)計(jì)equal()有五個(gè)必須遵循的要求。

對(duì)稱性。若 a.equal(b) 返回”true”, 則 b.equal(a) 也必須返回 “true”.
反射性。a.equal(a) 必須返回”true”.
傳遞性。若a.equal(b) 返回 “true”, 且 b.equal(c)返回 “true”, 則c.equal(a)必返回”true”.
一致性。若a.equal(b) 返回”true”, 只要a, b內(nèi)容不變，不管重復(fù)多少次a.equal(b)必須返回”true”.
任何情況下，a.equals(null)，永遠(yuǎn)返回是“false”；a.equals(和a不同類型的對(duì)象)永遠(yuǎn)返回是“false”.
hashCode()的返回值和equals()的關(guān)系.

如果a.equals(b)返回“true”，那么a和b的hashCode()必須相等。
如果a.equals(b)返回“false”，那么a和b的hashCode()有可能相等，也有可能不等。

下面是一個(gè)例子。在實(shí)際的軟件開發(fā)中，最好重寫這兩個(gè)方法。

public class Employee {
  int    employeeId;
  String   name;

  // other methods would be in here 

  @Override
  public boolean equals(Object obj)
  {
    if(obj==this)
      return true;
    Employee emp=(Employee)obj;
    if(employeeId.equals(emp.getEmployeeId()) && name==emp.getName())
      return true;
    return false;
  }

  @Override
  public int hashCode() {
    int hash = 1;
    hash = hash * 17 + employeeId;
    hash = hash * 31 + name.hashCode();
    return hash;
  }
}

3.下面著重介紹一下常用類的hashCode()實(shí)現(xiàn)方法。

String類的hasCode()

public int hashCode() {
  int h = hash;
  if (h == 0) {
    int off = offset;
    char val[] = value;
    int len = count;

      for (int i = 0; i < len; i++) {
        h = 31*h + val[off++];
      }
      hash = h;
    }
    return h;
  }

這段代碼最有意思的還是hash的實(shí)現(xiàn)方法了。最終計(jì)算的hash值為：

s[0]31n-1 + s[1]31n-2 + … + s[n-1]

s[i]是string的第i個(gè)字符，n是String的長(zhǎng)度。那為什么這里用31，而不是其它數(shù)呢?

31是個(gè)奇素?cái)?shù)，如果乘數(shù)是偶數(shù)，并且乘法溢出的話，信息就會(huì)丟失，因?yàn)榕c2相乘等價(jià)于移位運(yùn)算。使用素?cái)?shù)的好處并不是很明顯，但是習(xí)慣上都使用素?cái)?shù)來(lái)計(jì)算散列結(jié)果。31有個(gè)很好的特性，就是用移位和減法來(lái)代替乘法，可以得到更好的性能：31*i==(i<<5)-i。現(xiàn)在的VM可以自動(dòng)完成這種優(yōu)化。(From Effective Java)

Object類的hasCode()

Object類中hashCode()是一個(gè)Native方法。Native方法如何調(diào)用?

public native int hashCode();

Object類的Native方法類可在這里找到。深入分析請(qǐng)看另外一篇博客

static JNINativeMethod methods[] = {
  {"hashCode",  "()I",          (void *)&JVM_IHashCode},
  {"wait",    "(J)V",          (void *)&JVM_MonitorWait},
  {"notify",   "()V",          (void *)&JVM_MonitorNotify},
  {"notifyAll",  "()V",          (void *)&JVM_MonitorNotifyAll},
  {"clone",    "()Ljava/lang/Object;",  (void *)&JVM_Clone},
};

源代碼包括getClass()(See line58)等, hashCode()(See line43)被定義為一個(gè)指向JVM_IHashCode指針。

jvm.cpp中定義了JVM_IHashCode(line 504)函數(shù), 此函數(shù)里調(diào)用ObjectSynchronizer::FastHashCode，其定在 synchronizer.cpp, 可參考576行的FastHashCode 和 530行的 get_next_hash 的實(shí)現(xiàn)。

您可能感興趣的文章: