哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)想必大多數(shù)人都不陌生，而且在很多地方都會(huì)利用到hash表來(lái)提高查找效率。在Java的Object類中有一個(gè)方法：

public native int hashCode();

根據(jù)這個(gè)方法的聲明可知，該方法返回一個(gè)int類型的數(shù)值，并且是本地方法，因此在Object類中并沒(méi)有給出具體的實(shí)現(xiàn)。

hashCode作用

hashCode方法的主要作用是為了配合基于散列的集合一起正常運(yùn)行，這樣的散列集合包括HashSet、HashMap以及HashTable。

在Java集合中有兩類，一類是List，一類是Set他們之間的區(qū)別就在于List集合中的元素師有序的，且可以重復(fù)，而Set集合中元素是無(wú)序不可重復(fù)的。對(duì)于Set而言我們要如何來(lái)保證元素不重復(fù)呢？

也許大多數(shù)人都會(huì)想到調(diào)用equals方法來(lái)逐個(gè)進(jìn)行比較，這個(gè)方法確實(shí)可行。但是如果集合中已經(jīng)存在一萬(wàn)條數(shù)據(jù)或者更多的數(shù)據(jù)，如果采用equals方法去逐一比較，效率必然是一個(gè)問(wèn)題。

此時(shí)hashCode()派上了用場(chǎng)，它是一個(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è)元素是否相同，相同則不存，不同則散列到其他位置（散列沖突問(wèn)題）。這樣處理，當(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 契約

為了使你的類與其他基于哈希的集合或其他依賴哈希碼的算法一起正常工作，所有 hashCode 的實(shí)現(xiàn)必須遵守一個(gè)簡(jiǎn)單的契約。

這個(gè)契約在 hashCode 方法的 JavaDoc 中進(jìn)行了闡述。它可以大致的歸納為下面幾點(diǎn)：

1. 在一個(gè)運(yùn)行的進(jìn)程中，相等的對(duì)象必須要有相同的哈希碼
2. 請(qǐng)注意這并不意味著以下常見(jiàn)的誤解：
3. 不相等的對(duì)象一定有著不同的哈希碼——錯(cuò)！
4. 有同一個(gè)哈希值的對(duì)象一定相等——錯(cuò)！

這個(gè)契約允許不同的對(duì)象共享相同的哈希碼，例如根據(jù)上圖中的的描述，“A”和“μ”對(duì)象的哈希值就一樣。在數(shù)學(xué)術(shù)語(yǔ)中，從對(duì)象到哈希碼的映射不一定為內(nèi)射或者雙射。這是顯而易見(jiàn)的，因?yàn)榭赡艿牟煌瑢?duì)象的數(shù)量經(jīng)常比可能的哈希嗎的數(shù)量 (2^32)更大。

規(guī)則一：無(wú)論你何時(shí)實(shí)現(xiàn) equals 方法，你必須同時(shí)實(shí)現(xiàn) hashCode 方法

一個(gè)對(duì)象的 hashCode 方法需要與 equals 方法考慮同樣的域。通過(guò)重寫(xiě) equals 方法，你將申明一些對(duì)象與其他對(duì)象相等，但是原始的 hashCode 方法將所有的對(duì)象看做是不同的。所以你將會(huì)有不同哈希碼的相同對(duì)象。這違背了契約1中“相等的對(duì)象必須要有相同的哈希碼”。

規(guī)則二：永遠(yuǎn)不要把哈希碼誤用作一個(gè)key

因?yàn)楦鶕?jù)契約3，具有相同hash的對(duì)象不一定相同

規(guī)則三：在分布式應(yīng)用中不要使用哈希碼

我們可以看到hashCode方法是一個(gè)本地方法，它的實(shí)現(xiàn)取決于所處的操作系統(tǒng)，所以在分布式系統(tǒng)中一個(gè)對(duì)象的hash值在不同的系統(tǒng)中可能會(huì)不一樣。

最好的建議可能是：完全不使用哈希碼，除非你自己創(chuàng)造了基于哈希的算法。

如何重寫(xiě)hashCode()

《Effective Java》中提出了一種簡(jiǎn)單通用的hashCode算法：

A、初始化一個(gè)整形變量，為此變量賦予一個(gè)非零的常數(shù)值，比如int result = 17;

B、選取equals方法中用于比較的所有域（之所以只選擇equals()中使用的域，是為了保證上述原則的第1條），然后針對(duì)每個(gè)域的屬性進(jìn)行計(jì)算：

1. 如果是boolean值，則計(jì)算f ? 1:0
2. 如果是byte\char\short\int,則計(jì)算(int)f
3. 如果是long值，則計(jì)算(int)(f ^ (f >>> 32))
4. 如果是float值，則計(jì)算Float.floatToIntBits(f)
5. 如果是double值，則計(jì)算Double.doubleToLongBits(f)，然后返回的結(jié)果是long,再用規(guī)則(3)去處理long,得到int
6. 如果是對(duì)象應(yīng)用，如果equals方法中采取遞歸調(diào)用的比較方式，那么hashCode中同樣采取遞歸調(diào)用hashCode的方式。否則需要為這個(gè)域計(jì)算一個(gè)范式，比如當(dāng)這個(gè)域的值為null的時(shí)候，那么hashCode 值為0
7. 如果是數(shù)組，那么需要為每個(gè)元素當(dāng)做單獨(dú)的域來(lái)處理。java.util.Arrays.hashCode方法包含了8種基本類型數(shù)組和引用數(shù)組的hashCode計(jì)算，算法同上。

C、最后，把每個(gè)域的散列碼合并到對(duì)象的哈希碼中。

hash替代方案

信息摘要SHA1有時(shí)被用來(lái)標(biāo)識(shí)對(duì)象（例如，git這樣做）。這也是不安全嗎？不。SHA1使用 160 位密鑰，這使得沖突幾乎是不可能的。即使有很多對(duì)象，在這個(gè)空間發(fā)生沖突的幾率遠(yuǎn)遠(yuǎn)低于一顆流星撞到你正在執(zhí)行程序的電腦的幾率。