之所以寫HashCode，是因?yàn)槠綍r(shí)我們總聽到它。但你真的了解hashcode嗎？它會(huì)在哪里使用？它應(yīng)該怎樣寫？

相信閱讀完本文，能讓你看到不一樣的hashcode。

使用hashcode的目的在于：使用一個(gè)對(duì)象查找另一個(gè)對(duì)象。對(duì)于使用散列的數(shù)據(jù)結(jié)構(gòu)，如 HashSet、HashMap、LinkedHashSet、LinkedHashMap ，如果沒有很好的覆寫鍵的hashcode()和equals()方法，那么將無法正確的處理鍵。

請(qǐng)對(duì)以下代碼中 Person 覆寫hashcode()方法，看看會(huì)發(fā)生什么？

// 覆寫hashcode@Overridepublic int hashCode() { return age;}@Testpublic void testHashCode() { Set<Person> people = new HashSet<Person>(); Person person = null; for (int i = 0; i < 3 ; i++) {person = new Person('name-' + i, i);people.add(person); } person.age = 100; System.out.println(people.contains(person)); people.add(person); System.out.println(people.size());}

運(yùn)行結(jié)果并不是預(yù)期的 true 和 3 ，而是 false 和 4 ！改變 person.age 后HashSet無法找到 person 這個(gè)對(duì)象了，可見覆寫hahcode對(duì)HashSet的存儲(chǔ)和查詢?cè)斐闪擞绊憽?

那么hashcode是如何影響HashSet的存儲(chǔ)和查詢呢？又會(huì)造成怎樣的影響呢？

HashSet的內(nèi)部使用HashMap實(shí)現(xiàn)，所有放入HashSet中的集合元素都會(huì)轉(zhuǎn)為HashMap的key來保存。HashMap使用散列表來存儲(chǔ)，也就是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）。

存儲(chǔ)結(jié)構(gòu)簡圖如下：

HashMap存儲(chǔ)結(jié)構(gòu)簡圖

數(shù)組的默認(rèn)長度為16，數(shù)組里每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)。組成鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ...}

每一個(gè)Node都保存了一個(gè)hash----鍵對(duì)象的hashcode，如果鍵沒有按照任何特定順序保存，查找時(shí)通過equals()逐一與每一個(gè)數(shù)組元素進(jìn)行比較，那么時(shí)間復(fù)雜度為O(n)，數(shù)組長度越大，效率越低。

所以瓶頸在于鍵的查詢速度，如何通過鍵來快速的定位到存儲(chǔ)位置呢？

HashMap將鍵的hash值與數(shù)組下標(biāo)建立映射，通過鍵對(duì)象的hash函數(shù)生成一個(gè)值，以此作為數(shù)組的下標(biāo)，這樣我們就可以通過鍵來快速的定位到存儲(chǔ)位置了。如果hash函數(shù)設(shè)計(jì)的完美的話，數(shù)組的每個(gè)位置只有較少的值，那么在O(1)的時(shí)間我們就可以找到需要的元素，從而不需要去遍歷鏈表。這樣就大大提高了查詢速度。

那么HashMap根據(jù)hashcode是如何得到數(shù)組下標(biāo)呢？可以拆分為以下幾步：

第一步： h = key.hashCode() 第二步： h ^ (h >>> 16) 第三步： (length - 1) & hash

分析

第一步是得到key的hashcode值；

第二步是將鍵的hashcode的高16位異或低16位(高位運(yùn)算)，這樣即使數(shù)組table的length比較小的時(shí)候，也能保證高低Bit都參與到Hash的計(jì)算中，同時(shí)不會(huì)有太大的開銷；

第三步是hash值和數(shù)組長度進(jìn)行取模運(yùn)算，這樣元素的分布相對(duì)來說比較均勻。當(dāng)length總是2的n次方時(shí)， h & (length-1) 運(yùn)算等價(jià)于對(duì)length取模，這樣模運(yùn)算轉(zhuǎn)化為位移運(yùn)算速度更快。

但是，HashMap默認(rèn)數(shù)組初始化容量大小為16。當(dāng)數(shù)組長度遠(yuǎn)小于鍵的數(shù)量時(shí)，不同的鍵可能會(huì)產(chǎn)生相同的數(shù)組下標(biāo)，也就是發(fā)生了哈希沖突！

對(duì)于哈希沖突有開放定址法、鏈地址法、公共溢出區(qū)法等解決方案。

開放定址法就是一旦發(fā)生沖突，就尋找下一個(gè)空的散列地址。過程可用下式描述：

f i (key) = (f(key) + d i ) mod m (d i =1,2,3,...,m-1)

例如鍵集合為 {12,67,56,16,25,37,22,29,15,47,48,34} ，表長 n = 12 ，取 f(key) = key mod 12 。

前5個(gè)計(jì)算都沒有沖突，直接存入。如表所示

數(shù)組下標(biāo) 鍵0 121 252 3 4 165 6 7 678 569 10 11

當(dāng) key = 37 時(shí)， f(37) = 1 ，與25的位置沖突。應(yīng)用公式 f(37) = (f(37) + 1) mod 12 = 2 ，所以37存入數(shù)組下標(biāo)為2的位置。如表所示

數(shù)組下標(biāo) 鍵0 121 252 373 4 165 6 7 678 569 10 11

到了 key = 48 ，與12所在的0沖突了。繼續(xù)往下找，發(fā)現(xiàn)一直到 f(48) = (f(48) + 6) mod 12 = 6 時(shí)才有空位。如表所示

數(shù)組下標(biāo) 鍵0 121 252 373 4 165 296 487 678 569 10 2211 47

所以在解決沖突的時(shí)候還會(huì)出現(xiàn)48和37沖突的情況，也就是出現(xiàn)了 堆積 ，無論是查找還是存入效率大大降低。

鏈地址法解決沖突的做法是：如果哈希表空間為 [0～m-1] ，設(shè)置一個(gè)由m個(gè)指針分量組成的一維數(shù)組 Array[m] , 凡哈希地址為i的數(shù)據(jù)元素都插入到頭指針為 Array[i] 的鏈表中。

它的基本思想是：為每個(gè)Hash值建立一個(gè)單鏈表，當(dāng)發(fā)生沖突時(shí)，將記錄插入到鏈表中。如圖所示：

鏈地址法

鏈表的好處表現(xiàn)在：

remove操作時(shí)效率高，只維護(hù)指針的變化即可，無需進(jìn)行移位操作 重新散列時(shí)，原來散落在同一個(gè)槽中的元素可能會(huì)被散落在不同的地方，對(duì)于數(shù)組需要進(jìn)行移位操作，而鏈表只需維護(hù)指針。 但是，這也帶來了需要遍歷單鏈表的性能損耗。

公共溢出法就是我們?yōu)樗袥_突的鍵單獨(dú)放一個(gè)公共的溢出區(qū)存放。

例如前面例子中 {37,48,34} 有沖突，將他們存入溢出表。如圖所示。

公共溢出法

在查找時(shí)，先與基本表進(jìn)行比對(duì)，如果相等則查找成功，如果不等則在溢出表中進(jìn)行順序查找。公共溢出法適用于沖突數(shù)據(jù)很少的情況。

HashMap解決沖突采取的是鏈地址法。整體流程圖（暫不考慮擴(kuò)容）如下：

HashMap存儲(chǔ)流程簡圖

理解了hashcode和哈希沖突即解決方案后，我們?nèi)绾卧O(shè)計(jì)自己的hashcode()

方法呢？

Effective Java一書中對(duì)覆寫hashcode()給出以下指導(dǎo):

給int變量result賦予某個(gè)非零常量值

為對(duì)象內(nèi)每個(gè)有意義的域f計(jì)算一個(gè)int散列碼c

域類型 計(jì)算boolean c = (f ? 0 : 1)byte、char、short、int c = (int)flong c = (int)(f ^ (f >>> 32))float c = Float.floatToIntBits(f)double long l = Double.doubleToIntLongBits(f) c = (int)(l ^ (l >>> 32))Object c = f.hashcode()數(shù)組 每個(gè)元素應(yīng)用上述規(guī)則boolean c = (f ? 0 : 1)boolean c = (f ? 0 : 1) 合并計(jì)算得到散列碼 result = 37 * result + c

現(xiàn)代IDE通過點(diǎn)擊右鍵上下文菜單可以自動(dòng)生成hashcode方法，比如通過IDEA生成的hashcode如下：

@Overridepublic int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result;}

但是在企業(yè)級(jí)代碼中，最好使用第三方庫如 Apache commons 來生成hashocde方法。使用第三方庫的優(yōu)勢(shì)是可以反復(fù)驗(yàn)證嘗試代碼。下面代碼顯示了如何使用 Apache Commons hash code 為一個(gè)自定義類構(gòu)建生成hashcode。

public int hashCode(){ HashCodeBuilder builder = new HashCodeBuilder(); builder.append(mostSignificantMemberVariable); ........................ builder.append(leastSignificantMemberVariable); return builder.toHashCode();}

如代碼所示，最重要的簽名成員變量應(yīng)該首先傳遞然后跟隨的是沒那么重要的成員變量。

總結(jié)

通過上述分析，我們?cè)O(shè)計(jì)hashcode()應(yīng)該注意的是：

無論何時(shí)，對(duì)同一個(gè)對(duì)象調(diào)用hashcode()都應(yīng)該生成同樣的值。 hashcode()盡量使用對(duì)象內(nèi)有意義的識(shí)別信息。 好的hashcode()應(yīng)該產(chǎn)生分布均勻的散列值。

來自： http://www.jianshu.com/p/e183f75d0289