深入理解Java hashCode()的方法

Java.lang.Object 有一個hashCode()和一個equals()方法，這兩個方法在軟體設計中扮演著舉足輕重的角色。在某些類別中覆寫這兩個方法以完成某些重要功能。本文描述了為什麼要用hashCode(), 如何使用，以及其他的一些擴展。閱讀本文需要有基本的hash演算法知識以及基本的Java集合知識，本文屬於菜鳥入門級講解，大神讀至此請點擊右上角的X，以免浪費您的時間^_^。

WHY hashCode()?

集合Set中的元素是無序不可重複的，那判斷兩個元素是否重複的依據是什麼呢？ “比較物件是否相等當然用Object.equal()了”，某猿如是說。但是，Set中存在大量對象，後面加入集合Set中的物件元素比較次數會逐漸增多，大大降低了程式運作效率。 Java中採用哈希演算法(也叫雜湊演算法)來解決這個問題，將物件(或資料)依特定演算法直接映射到一個位址上，物件的存取效率大大提高。這樣一來，當含有海量元素的集合Set需要加入某元素(物件)時，先呼叫這個元素的hashCode()，就能一下子定位到此元素實際儲存位置，如果這個位置沒有元素，說明此對象時第一次儲存到集合Set, 直接將此物件儲存在此位置上；若此位置有物件存在，呼叫equal()看看這兩個物件是否相等，相等就捨棄此元素不存，不等則散列到其他地址。

HOW use hashCode()?

Java語言對猿設計equal()有五個必須遵循的要求。

1. 對稱性。若 a.equal(b) 回傳”true”, 則 b.equal(a) 也必須傳回 “true”.

2. 反射性。 a.equal(a) 必須回傳”true”.

3. 傳遞性。若a.equal(b) 回傳「true」, 且b.equal(c)回傳「true」, 則c.equal(a)必回傳」true」.

4. 一致性。若a.equal(b) 回傳”true”, 只要a, b內容不變，不管重複多少次a.equal(b)必須回傳”true”.

5. 任何情況下，a.equals(null)，永遠回傳是「false」；a.equals(和a不同類型的物件)永遠回傳是「false」.

hashCode()的傳回值和equals()的關係.

1. 如果a.equals(b)回傳“true”，那麼a和b的hashCode()必須相等。

2. 如果a.equals(b)回傳“false”，那麼a和b的hashCode()有可能相等，也有可能不等。

下面是一個例子。在實際的軟體開發中，最好重寫這兩種方法。

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;
    }
}

下面著重介紹一下常用類別的hashCode()實作方法。

String類別的hasCode()

Java程式碼

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的實作方法了。最後計算的hash值為：

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

s[i]是string的第i個字符，n是String的長度。那為什麼這裡用31，而不是其它數呢?

31是個奇素數，如果乘數是偶數，並且乘法溢出的話，信息就會丟失，因為與2相乘等價於移位元運算。使用質數的好處並不是很明顯，但是習慣上都使用質數來計算雜湊結果。 31有個很好的特性，就是用移位和減法來代替乘法，可以得到更好的性能：31*i==(i<<5)-i。現在的VM可以自動完成這種最佳化。 (From Effective Java)

Object類別的hasCode()

Object類別中hashCode()是一個Native方法。 Native方法如何呼叫?

public native int hashCode();

Object類別的Native方法類別可在這裡找到。 深入分析請看另外一篇部落格

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)被定義為一個指向JVM_IHashCode指標。

jvm.cpp中定義了JVM_IHashCode(line 504)函數, 此函數裡呼叫ObjectSynchronizer::FastHashCode，其定在 synchronizer.cpp, 可參考576行的FastHashCode 和530行的get_next_hash 的實作。

以上是深入理解Java hashCode()的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！