zhb8015

什么是hashcode    （轉(zhuǎn)）  
    分析HashMap之前先介紹下什么Hashcode(散列碼)。它是一個(gè)int，每個(gè)對(duì)象都會(huì)有一個(gè)hashcode，它在內(nèi)存的存放位置是放在對(duì)象的 頭部（對(duì)象頭部存放的信息有hashcode，指向Class的引用，和一些有關(guān)垃圾回收信息）。具體如何生成hashcode，這個(gè)相當(dāng)復(fù)雜，由于我們 的主題是“淺析”，所以不深入探討。有個(gè)問(wèn)題需要講的是，如果在你的類中覆蓋了Object的equals(Object)方法，那么你必須覆蓋 hashCode方法，不然，當(dāng)你使用HashMap，HashSet，HashTable時(shí)會(huì)出現(xiàn)問(wèn)題。具體原因下文會(huì)詳細(xì)描述。
String類的hashcode
    String類重寫(xiě)了Object類中的equals和hashCode方法，原因很簡(jiǎn)單，Object中的equals方法是指比較兩個(gè)對(duì)象是不是指向 同一個(gè)引用對(duì)象，而String類指需要比較內(nèi)容相不相等就可以了。所以String覆蓋了equals方法，同時(shí)覆蓋了hashCode方法。這里需要 提一下Object規(guī)范里規(guī)定：如果兩個(gè)對(duì)象根據(jù)equals(Object)方式是相等的，那么這兩個(gè)對(duì)象的hashCode一定要相等。
String中的hashcode算法很簡(jiǎn)單如下：

Val是一個(gè)char[]，存放的是字符串的各個(gè)字符；Len是字符串長(zhǎng)度；off從0開(kāi)始；h從0開(kāi)始。比如一個(gè)字符串“abc”(a的ascii碼是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354
存儲(chǔ)方式
    列表的存儲(chǔ)方式是基于數(shù)組，如下圖：


    鏈表的存儲(chǔ)方式是基于指針，如下圖：（單向鏈表）


    HashMap的存儲(chǔ)方式是上面兩種的結(jié)合，如下圖：


HashMap的存取
    HashMap的功能是通過(guò)“鍵(key)”能夠快速的找到“值”。下面我們分析下HashMap存數(shù)據(jù)的基本流程：
    1、 當(dāng)調(diào)用put(key,value)時(shí)，首先獲取key的hashcode，int hash = key.hashCode();
    2、 再把hash通過(guò)一下運(yùn)算得到一個(gè)int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
為什么要經(jīng)過(guò)這樣的運(yùn)算呢？這就是HashMap的高明之處。先看個(gè)例子，一個(gè)十進(jìn)制數(shù)32768(二進(jìn)制1000 0000 0000 0000)，經(jīng)過(guò)上述公式運(yùn)算之后的結(jié)果是35080(二進(jìn)制1000 1001 0000 1000)。看出來(lái)了嗎？或許這樣還看不出什么，再舉個(gè)數(shù)字61440(二進(jìn)制1111 0000 0000 0000)，運(yùn)算結(jié)果是65263(二進(jìn)制1111 1110 1110 1111)，現(xiàn)在應(yīng)該很明顯了，它的目的是讓“1”變的均勻一點(diǎn)，散列的本意就是要盡量均勻分布。那這樣有什么意義呢？看第3步。
    3、 得到h之后，把h與HashMap的承載量（HashMap的默認(rèn)承載量length是16，可以自動(dòng)變長(zhǎng)。在構(gòu)造HashMap的時(shí)候也可以指定一個(gè)長(zhǎng) 度。這個(gè)承載量就是上圖所描述的數(shù)組的長(zhǎng)度。）進(jìn)行邏輯與運(yùn)算，即 h & (length-1)，這樣得到的結(jié)果就是一個(gè)比length小的正數(shù)，我們把這個(gè)值叫做index。其實(shí)這個(gè)index就是索引將要插入的值在數(shù)組中的 位置。第2步那個(gè)算法的意義就是希望能夠得出均勻的index，這是HashTable的改進(jìn)，HashTable中的算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會(huì)造成index分布不均勻。還有一點(diǎn)需要說(shuō)明，HashMap的鍵可以為null，它的值是放在數(shù)組的第一個(gè)位置。
    4、 我們用table[index]表示已經(jīng)找到的元素需要存儲(chǔ)的位置。先判斷該位置上有沒(méi)有元素（這個(gè)元素是HashMap內(nèi)部定義的一個(gè)類Entity， 基本結(jié)構(gòu)它包含三個(gè)類，key，value和指向下一個(gè)Entity的next）,沒(méi)有的話就創(chuàng)建一個(gè)Entity<K,V>對(duì)象，在 table[index]位置上插入，這樣插入結(jié)束；如果有的話，通過(guò)鏈表的遍歷方式去逐個(gè)遍歷，看看有沒(méi)有已經(jīng)存在的key，有的話用新的value替 換老的value；如果沒(méi)有，則在table[index]插入該Entity，把原來(lái)在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結(jié)束。
再回頭看看前面提到的為什么覆蓋了equals方法之后一定要覆蓋hashCode方法，很簡(jiǎn)單，比如，String a = new String(“abc”);String b = new String(“abc”);如果不覆蓋hashCode的話，那么a和b的hashCode就會(huì)不同，把這兩個(gè)類當(dāng)做key存到HashMap中的話就 會(huì)出現(xiàn)問(wèn)題，就會(huì)和key的唯一性相矛盾。

    HashMap取的過(guò)程也類似。太累了，不寫(xiě)了。趕緊結(jié)束。
    文中可能會(huì)有錯(cuò)誤的地方請(qǐng)指出，謝謝！