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

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

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

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

// 覆寫hashcode
@Override
public int hashCode() {
    return age;
}

@Test
public 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è)對象了，可見覆寫hahcode對HashSet的存儲(chǔ)和查詢造成了影響。 

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

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

HashMap將鍵的hash值與數(shù)組下標(biāo)建立映射，通過鍵對象的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)算，這樣元素的分布相對來說比較均勻。當(dāng)length總是2的n次方時(shí)， h & (length-1) 運(yùn)算等價(jià)于對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ā)生了哈希沖突！

對于哈希沖突有開放定址法、鏈地址法、公共溢出區(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	12
1	25
2
3
4	16
5
6
7	67
8	56
9
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	12
1	25
2	37
3
4	16
5
6
7	67
8	56
9
10
11

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

數(shù)組下標(biāo)	鍵
0	12
1	25
2	37
3
4	16
5	29
6	48
7	67
8	56
9
10	22
11	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)在：

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

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

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

公共溢出法

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

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

HashMap存儲(chǔ)流程簡圖

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

方法呢？

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

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

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

域類型	計(jì)算
boolean	c = (f ? 0 : 1)
byte、char、short、int	c = (int)f
long	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如下：

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

但是在企業(yè)級(jí)代碼中，最好使用第三方庫如 Apache commons 來生成hashocde方法。使用第三方庫的優(yōu)勢是可以反復(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é)

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

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

 

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

 

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。