之所以寫HashCode，是因為平時我們總聽到它剧蚣。但你真的了解hashcode嗎支竹？它會在哪里使用？它應(yīng)該怎樣寫鸠按？
相信閱讀完本文礼搁，能讓你看到不一樣的hashcode。
使用hashcode的目的在于：使用一個對象查找另一個對象目尖。對于使用散列的數(shù)據(jù)結(jié)構(gòu)馒吴，如 HashSet、HashMap、LinkedHashSet饮戳、LinkedHashMap 豪治，如果沒有很好的覆寫鍵的hashcode()和equals()方法，那么將無法正確的處理鍵扯罐。
請對以下代碼中 Person 覆寫hashcode()方法负拟，看看會發(fā)生什么？
// 覆寫hashcode
@Override
public int hashCode() {
return age;
}
@Test
public void testHashCode() {
Set people = new HashSet();
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());
}
運行結(jié)果并不是預(yù)期的 true 和 3 歹河，而是 false 和 4 掩浙！改變 person.age 后HashSet無法找到 person 這個對象了，可見覆寫hahcode對HashSet的存儲和查詢造成了影響秸歧。
那么hashcode是如何影響HashSet的存儲和查詢呢厨姚？又會造成怎樣的影響呢？
HashSet的內(nèi)部使用HashMap實現(xiàn)键菱，所有放入HashSet中的集合元素都會轉(zhuǎn)為HashMap的key來保存谬墙。HashMap使用散列表來存儲，也就是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）经备。
存儲結(jié)構(gòu)簡圖如下：
HashMap存儲結(jié)構(gòu)簡圖
數(shù)組的默認長度為16拭抬，數(shù)組里每個元素存儲的是一個鏈表的頭結(jié)點。組成鏈表的結(jié)點結(jié)構(gòu)如下：
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
...
}
每一個Node都保存了一個hash----鍵對象的hashcode弄喘，如果鍵沒有按照任何特定順序保存玖喘，查找時通過equals()逐一與每一個數(shù)組元素進行比較甩牺，那么時間復(fù)雜度為O(n)蘑志，數(shù)組長度越大，效率越低贬派。
所以瓶頸在于鍵的查詢速度急但，如何通過鍵來快速的定位到存儲位置呢？
HashMap將鍵的hash值與數(shù)組下標(biāo)建立映射搞乏，通過鍵對象的hash函數(shù)生成一個值波桩，以此作為數(shù)組的下標(biāo)，這樣我們就可以通過鍵來快速的定位到存儲位置了请敦。如果hash函數(shù)設(shè)計的完美的話镐躲，數(shù)組的每個位置只有較少的值，那么在O(1)的時間我們就可以找到需要的元素侍筛，從而不需要去遍歷鏈表萤皂。這樣就大大提高了查詢速度。
那么HashMap根據(jù)hashcode是如何得到數(shù)組下標(biāo)呢匣椰？可以拆分為以下幾步：
第一步： h = key.hashCode()
第二步： h ^ (h >>> 16)
第三步： (length - 1) & hash
分析
第一步是得到key的hashcode值裆熙；
第二步是將鍵的hashcode的高16位異或低16位(高位運算)，這樣即使數(shù)組table的length比較小的時候，也能保證高低Bit都參與到Hash的計算中入录，同時不會有太大的開銷蛤奥；
第三步是hash值和數(shù)組長度進行取模運算，這樣元素的分布相對來說比較均勻僚稿。當(dāng)length總是2的n次方時凡桥， h & (length-1) 運算等價于對length取模，這樣模運算轉(zhuǎn)化為位移運算速度更快贫奠。
但是唬血，HashMap默認數(shù)組初始化容量大小為16。當(dāng)數(shù)組長度遠小于鍵的數(shù)量時唤崭，不同的鍵可能會產(chǎn)生相同的數(shù)組下標(biāo)拷恨，也就是發(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個計算都沒有沖突，直接存入薪捍。如表所示
當(dāng) key = 37 時笼痹， f(37) = 1 ，與25的位置沖突酪穿。應(yīng)用公式 f(37) = (f(37) + 1) mod 12 = 2 凳干，所以37存入數(shù)組下標(biāo)為2的位置。如表所示
到了 key = 48 被济，與12所在的0沖突了救赐。繼續(xù)往下找，發(fā)現(xiàn)一直到 f(48) = (f(48) + 6) mod 12 = 6 時才有空位只磷。如表所示
所以在解決沖突的時候還會出現(xiàn)48和37沖突的情況经磅，也就是出現(xiàn)了 堆積 ，無論是查找還是存入效率大大降低钮追。
鏈地址法解決沖突的做法是：如果哈希表空間為 [0～m-1] 预厌，設(shè)置一個由m個指針分量組成的一維數(shù)組 Array[m] , 凡哈希地址為i的數(shù)據(jù)元素都插入到頭指針為 Array[i] 的鏈表中。
它的基本思想是：為每個Hash值建立一個單鏈表畏陕，當(dāng)發(fā)生沖突時配乓，將記錄插入到鏈表中。如圖所示：
鏈地址法
鏈表的好處表現(xiàn)在：
remove操作時效率高，只維護指針的變化即可犹芹，無需進行移位操作
重新散列時崎页，原來散落在同一個槽中的元素可能會被散落在不同的地方，對于數(shù)組需要進行移位操作腰埂，而鏈表只需維護指針飒焦。
但是，這也帶來了需要遍歷單鏈表的性能損耗屿笼。
公共溢出法就是我們?yōu)樗袥_突的鍵單獨放一個公共的溢出區(qū)存放牺荠。
例如前面例子中 {37,48,34} 有沖突，將他們存入溢出表驴一。如圖所示休雌。
公共溢出法
在查找時，先與基本表進行比對肝断，如果相等則查找成功杈曲，如果不等則在溢出表中進行順序查找。公共溢出法適用于沖突數(shù)據(jù)很少的情況胸懈。
HashMap解決沖突采取的是鏈地址法担扑。整體流程圖（暫不考慮擴容）如下：
HashMap存儲流程簡圖
理解了hashcode和哈希沖突即解決方案后，我們?nèi)绾卧O(shè)計自己的hashcode()
方法呢趣钱？
Effective Java一書中對覆寫hashcode()給出以下指導(dǎo):
給int變量result賦予某個非零常量值
為對象內(nèi)每個有意義的域f計算一個int散列碼c
域類型計算
booleanc = (f ? 0 : 1)
byte涌献、char、short首有、intc = (int)f
longc = (int)(f ^ (f >>> 32))
floatc = Float.floatToIntBits(f)
doublelong l = Double.doubleToIntLongBits(f)
c = (int)(l ^ (l >>> 32))
Objectc = f.hashcode()
數(shù)組每個元素應(yīng)用上述規(guī)則
booleanc = (f ? 0 : 1)
booleanc = (f ? 0 : 1)
合并計算得到散列碼 result = 37 * result + c
現(xiàn)代IDE通過點擊右鍵上下文菜單可以自動生成hashcode方法燕垃，比如通過IDEA生成的hashcode如下：
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
但是在企業(yè)級代碼中，最好使用第三方庫如 Apache commons 來生成hashocde方法绞灼。使用第三方庫的優(yōu)勢是可以反復(fù)驗證嘗試代碼利术。下面代碼顯示了如何使用 Apache Commons hash code 為一個自定義類構(gòu)建生成hashcode呈野。
public int hashCode(){
HashCodeBuilder builder = new HashCodeBuilder();
builder.append(mostSignificantMemberVariable);
........................
builder.append(leastSignificantMemberVariable);
return builder.toHashCode();
}
如代碼所示低矮，最重要的簽名成員變量應(yīng)該首先傳遞然后跟隨的是沒那么重要的成員變量。
總結(jié)
通過上述分析被冒，我們設(shè)計hashcode()應(yīng)該注意的是：
無論何時军掂，對同一個對象調(diào)用hashcode()都應(yīng)該生成同樣的值。
hashcode()盡量使用對象內(nèi)有意義的識別信息昨悼。
好的hashcode()應(yīng)該產(chǎn)生分布均勻的散列值蝗锥。
如果你是一名程序員，如果你剛好又是Java程序員率触，恰巧剛好你的技術(shù)又遇到了瓶頸但是你又拒絕平庸终议，期待蛻變，想進入一線互聯(lián)網(wǎng)公司或者給自己漲薪
我這里剛好有一套自己保存的Java進階學(xué)習(xí)資料。包含了Spring框架穴张、Mybatis框架SpringBoot框架细燎、SpringMVC框架、SpringCloud微服務(wù)皂甘、Dubbo框架玻驻、Redis緩存、RabbitMq消息偿枕、JVM調(diào)優(yōu)璧瞬、Tomcat容器、MySQL數(shù)據(jù)庫
之前的兩千人群滿了 這個是新群Java高級進階群：963,944.895渐夸，免費發(fā)送的喲
