之所以寫HashCode，是因為平時我們總聽到它。但你真的了解hashcode嗎？它會在哪里使用？它應該怎樣寫？

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

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

請對以下代碼中 Person 覆寫hashcode()方法，看看會發(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());}

運行結果并不是預期的 true 和 3 ，而是 false 和 4 ！改變 person.age 后HashSet無法找到 person 這個對象了，可見覆寫hahcode對HashSet的存儲和查詢造成了影響。

那么hashcode是如何影響HashSet的存儲和查詢呢？又會造成怎樣的影響呢？

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

存儲結構簡圖如下：

HashMap存儲結構簡圖

數(shù)組的默認長度為16，數(shù)組里每個元素存儲的是一個鏈表的頭結點。組成鏈表的結點結構如下：

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

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

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

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

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

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

分析

第一步是得到key的hashcode值；

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

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

但是，HashMap默認數(shù)組初始化容量大小為16。當數(shù)組長度遠小于鍵的數(shù)量時，不同的鍵可能會產生相同的數(shù)組下標，也就是發(fā)生了哈希沖突！

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

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

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個計算都沒有沖突，直接存入。如表所示

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

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

數(shù)組下標 鍵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ù)組下標 鍵0 121 252 373 4 165 296 487 678 569 10 2211 47

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

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

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

鏈地址法

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

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

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

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

公共溢出法

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

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

HashMap存儲流程簡圖

理解了hashcode和哈希沖突即解決方案后，我們如何設計自己的hashcode()

方法呢？

Effective Java一書中對覆寫hashcode()給出以下指導:

給int變量result賦予某個非零常量值

為對象內每個有意義的域f計算一個int散列碼c

域類型 計算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ù)組 每個元素應用上述規(guī)則boolean c = (f ? 0 : 1)boolean c = (f ? 0 : 1) 合并計算得到散列碼 result = 37 * result + c

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

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

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

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

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

總結

通過上述分析，我們設計hashcode()應該注意的是：

無論何時，對同一個對象調用hashcode()都應該生成同樣的值。 hashcode()盡量使用對象內有意義的識別信息。 好的hashcode()應該產生分布均勻的散列值。

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