什么是hashcode,hashcode的作用是什么

hashcode并不是java中獨(dú)有的。設(shè)想一下，如果讓你設(shè)計(jì)一個(gè)算法，根據(jù)關(guān)鍵碼去得到一個(gè)集合中的某個(gè)值或者這個(gè)關(guān)鍵碼所在的位置。普通的做法就是挨個(gè)比較，高級一點(diǎn)的使用二分檢索或者樹形檢索等算法。但是以上的檢索算法都跟集合的長度N有關(guān)，當(dāng)問題規(guī)模N很大時(shí)，這些檢索的效率可能十分低下。

理想的情況是，根據(jù)關(guān)鍵碼，我們就可以定位記錄所在的位置，而不用去挨個(gè)進(jìn)行比較。也就是說，在關(guān)鍵碼與記錄存放的位置之間做一種映射。這個(gè)映射的方法就是hash(哈希)函數(shù)，或者叫散列函數(shù)，也就是java中的hashCode()方法，他所返回的值就是hashcode，根據(jù)hashcode可以找到記錄的位置。

按照散列的存儲方式構(gòu)造的存儲結(jié)構(gòu)叫做散列表。散列表中的一個(gè)位置稱之為一個(gè)槽。

hashCode()方法存在于java.lang.Object類當(dāng)中，任何類都可以繼承修改這個(gè)方法。hashCode()方法返回調(diào)用它的實(shí)例的hashCode值，是個(gè)int值。

注：以下代碼均來自jdk1.7

String中hashCode()方法的實(shí)現(xiàn)：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

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

什么是equals(Object obj)方法

equals(Object obj)方法同樣來自O(shè)bject類。在Object類中，他是這樣實(shí)現(xiàn)的：

public boolean equals(Object obj) {
        return (this == obj);
}

也就是說，默認(rèn)的equals(Object obj)方法直接將要比較的兩個(gè)對象的內(nèi)存地址進(jìn)行了比較，一致則返回true。

這個(gè)方法主要用來實(shí)現(xiàn)兩個(gè)對象間的比較，確認(rèn)他們在邏輯上是否相等。我們同樣可以實(shí)現(xiàn)自己的equals(Object obj)方法。

String中equals(Object obj)方法的實(shí)現(xiàn)：

public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String) anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                            return false;
                    i++;
                }
                return true;
            }
        }
        return false;
}

在java中hashcode方法與equals方法的作用

首先看一下HashMap中的put方法：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//得到hash值
        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;
    }

我們從 int hash = hash(key); 這一行看起，這行起才是put方法的核心。

首先 int hash = hash(key); key就是我們之前提到的關(guān)鍵碼，我們看看HashMap中的這個(gè)hash方法做了些什么：

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}

可以看到，這個(gè)方法里調(diào)用了key本身的hashCode方法，得到了key的hashcode，然后對該hashcode進(jìn)行了一些移位操作，最終返回操作后的int值。返回的這個(gè)值就是HashMap要用到的hashcode值，通過他可以找到記錄所在的位置。那么現(xiàn)在有一個(gè)問題：為什么要專門調(diào)用這個(gè)hash(Onject key)方法來對key的hashcode進(jìn)行包裝然后再使用呢？可以直接使用key的hashcode的呀，這樣做看起來不是多此一舉嗎？

其實(shí)這樣做的目的是為下面的函數(shù)做準(zhǔn)備的，我們看接下來要執(zhí)行的代碼：

int i = indexFor(hash, table.length);找到所謂的槽，也就是記錄存在的位置。

/**
  * Returns index for hash code h.
  */
static int indexFor(int h, int length) {
     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

可以看到，indexFor(int h, int length)如何通過hashcode得到記錄的位置。indexFor方法內(nèi)部是一個(gè)取模運(yùn)算，h是我們通過上面的hash方法得到的，length是散列表的長度。HashMap中的散列表是一個(gè)數(shù)組，通過取模運(yùn)算能保證indexFor方法的返回值(記錄的位置)一定在這個(gè)數(shù)組內(nèi)，沒有超過其長度。因?yàn)閔往往是一個(gè)很大的數(shù)字(int可以表示40億這么大的數(shù)字)，而散列表的初始長度是可以由我們指定的(默認(rèn)是16),另一方面，就算給他這么大的數(shù)組，內(nèi)存也是放不下的。所以取模運(yùn)算是必須的。經(jīng)過取模運(yùn)算得到的才是真正的槽值。

回到上一個(gè)問題，為什么要專門調(diào)用這個(gè)hash(Onject key)方法來對key的hashcode進(jìn)行包裝然后再使用呢？而不是直接使用key的hashcode的？

想明白這個(gè)問題，參考JDK 源碼中 HashMap 的 hash 方法原理是什么？。我們上面也說了這樣做的目的是為indexFor方法做準(zhǔn)備的，總的來說就是為了讓取模運(yùn)算不會出現(xiàn)一種極端情況：大量的不同的h經(jīng)過取模后返回同樣的槽值。這樣會帶來嚴(yán)重的性能問題，也就是嚴(yán)重的沖突情況導(dǎo)致性能下降。關(guān)于沖突，看下文。

要理解接下來的代碼，我們就需要知道哈希算法的另一個(gè)概念：沖突。

散列函數(shù)可能對于不相等的關(guān)鍵碼計(jì)算出相同的hashcode，該現(xiàn)象稱為沖突。怎么理解呢？

比如我們有這樣一個(gè)串a(chǎn)bcd，我們給出這樣一個(gè)散列函數(shù)：將每一個(gè)字符的ascii值加起來除以字符的個(gè)數(shù)，得到他們的平均值就是這個(gè)串的hashcode。那么，可以保證沒有其他的串經(jīng)過這樣的算法得到相同的hashcode嗎？也就是說，無限多的元素通過散列函數(shù)映射到有窮集合上，一定會產(chǎn)生沖突。這也是我們理解hashcode的一個(gè)重要的點(diǎn)：不同的對象(equals返回false)可以有相同的hashcode。

那么，產(chǎn)生沖突怎么辦呢？產(chǎn)生沖突之后，不同的對象在散列表中找到了相同的位置，為了解決這個(gè)問題，我們將這個(gè)槽中的內(nèi)容設(shè)計(jì)成一個(gè)鏈表，當(dāng)產(chǎn)生沖突的時(shí)候，就將新的元素放到鏈表中，他看起來是這樣的：

image.png

其中：A，B，C分別為三條記錄，他們就是產(chǎn)生沖突的三條記錄。1,2,3....為散列表的索引位置。

接下來的代碼 for (Entry<K,V> e = table[i]; e != null; e = e.next)就容易理解了。找到記錄所對應(yīng)的槽之后，遍歷這個(gè)鏈表直到找到與關(guān)鍵碼相同的位置(可能之前已經(jīng)有以這個(gè)關(guān)鍵碼為key的value插入)。如果遍歷完鏈表還沒有找到這樣的值，說明還不存在此關(guān)鍵碼對應(yīng)的記錄，直接插入即可：addEntry(hash, key, value, i);.

那么，怎么判斷兩個(gè)關(guān)鍵碼在邏輯上是否相同呢？

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

可以看到，首先判斷關(guān)鍵碼的hashcode與鏈表記錄的關(guān)鍵碼hashcode是否相同：·e.hash == hash。為什么要加這樣的判斷？回頭看看indexFor方法，經(jīng)過取模運(yùn)算后，不同的hashcode可以被散列在同一個(gè)槽中。通過這句代碼可以將那些因?yàn)槿∧＿\(yùn)算散列到同一個(gè)槽里的不同對象排除。

我們知道不同的對象(equals返回false)可以有相同的hashcode。相同的對象hashcode也必須相等嗎？試想一下，如果兩個(gè)對象相同，但是他們的hashcode不同，那么這兩個(gè)對象很有可能被散列在不同的槽里，造成了同一個(gè)對象重復(fù)存儲的問題。所以，我們又得出一個(gè)重要結(jié)論：相同的對象(equals返回true)hashcode一定相等。

e.hash == hash && ((k = e.key) == key：這段代碼首先判斷hashcode是否相等，然后判斷關(guān)鍵碼是否相等。注意，是判斷關(guān)鍵碼是否相等，直接比較內(nèi)存地址，如果滿足以上條件，那么可以斷定兩個(gè)關(guān)鍵碼相同，是我們要找的記錄。

key.equals(k)：如果上述兩個(gè)條件沒有滿足，并不能夠斷定這兩個(gè)關(guān)鍵碼相等，此刻要使用equals方法判斷這兩個(gè)關(guān)鍵碼是否相同。如果相同，說明是我們要找的記錄。

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))這句代碼中其實(shí)包含了一種短路思想，|| 之前的判斷如果生效，那么之后的key.equals(k)就不會再執(zhí)行。很明顯內(nèi)存地址的比較要比equals方法高效的多。這也是Hashmap提高查找效率的一個(gè)重要手段。

至此，我們應(yīng)該對equals和hashcode有了一個(gè)相對清晰的認(rèn)識：hashcode提高了查找指定對象的效率。euqals定義了兩個(gè)對象之間是否在邏輯上相同。hashcode只在HashMap，HashSet等這樣使用了散列思想的地方用到，而equals在判斷兩個(gè)對象之間是否相同時(shí)需要用到，比如排序等。

總結(jié)

通過上面的分析，我們知道了hashcode與equals的幾個(gè)關(guān)鍵：

1.不同的對象(equals返回false)可以有相同的hashcode

2.相同的對象(equals返回true)hashcode一定相等

3.若重新定義了上面兩種方法中的一種，那么另一種方法也需要重新定義（對1、2的遵守）

關(guān)于如何重寫equals方法與hashCode方法

equals與==

"==" 比較的是兩個(gè)對象的內(nèi)存地址，是物理意義上的相等

equals比較的是兩個(gè)對象邏輯意義上的相等，是邏輯意義上的相等

兩個(gè)對象進(jìn)行比較：

== 返回true，則equals一定返回true；

equals返回true，== 不一定返回true。