HashMap詳講

HashMap詳講hashing散列法或哈希法的概念什么是HashMap以及HashMap的構(gòu)成HashMap的基本存儲(chǔ)原理以及存儲(chǔ)內(nèi)容的組成HashMap的工作原理以及存取方法過(guò)程HashMap中的碰撞探測(cè)collision detection以及碰撞的解決方法如何重新調(diào)整HashMap的大小不可變對(duì)象的好處HashMap多線程的條件競(jìng)爭(zhēng)

下面就根據(jù)這些問(wèn)題講解一下HashMap

hashing(散列法或哈希法)的概念

可以自行百度

什么是HashMap以及HashMap的構(gòu)成

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。HashMap儲(chǔ)存的是鍵值對(duì)，HashMap很快。此類(lèi)不保證映射的順序，特別是它不保證該順序恒久不變。

HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

數(shù)組：存儲(chǔ)區(qū)間連續(xù)，占用內(nèi)存嚴(yán)重，尋址容易，插入刪除困難； 鏈表：存儲(chǔ)區(qū)間離散，占用內(nèi)存比較寬松，尋址困難，插入刪除容易； Hashmap綜合應(yīng)用了這兩種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了尋址容易，插入刪除也容易。

hashMap的結(jié)構(gòu)示意圖如下：

HashMap的基本存儲(chǔ)原理以及存儲(chǔ)內(nèi)容的組成

基本原理：先聲明一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素。另外設(shè)計(jì)一個(gè)哈希函數(shù)（也叫做散列函數(shù)）來(lái)獲得每一個(gè)元素的Key（關(guān)鍵字）的函數(shù)值（即數(shù)組下標(biāo)，hash值）相對(duì)應(yīng)，數(shù)組存儲(chǔ)的元素是一個(gè)Entry類(lèi)，這個(gè)類(lèi)有三個(gè)數(shù)據(jù)域，key、value（鍵值對(duì)），next(指向下一個(gè)Entry)。 例如， 第一個(gè)鍵值對(duì)A進(jìn)來(lái)。通過(guò)計(jì)算其key的hash得到的index=0。記做:Entry[0] = A。 第二個(gè)鍵值對(duì)B，通過(guò)計(jì)算其index也等于0， HashMap會(huì)將B.next =A,Entry[0] =B, 第三個(gè)鍵值對(duì) C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方事實(shí)上存取了A,B,C三個(gè)鍵值對(duì),它們通過(guò)next這個(gè)屬性鏈接在一起。我們可以將這個(gè)地方稱(chēng)為桶。 對(duì)于不同的元素，可能計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了“沖突”，這就需要解決沖突，“直接定址”與“解決沖突”是哈希表的兩大特點(diǎn)。

HashMap的工作原理以及存取方法過(guò)程

HashMap的工作原理 ：HashMap是基于散列法（又稱(chēng)哈希法hashing）的原理，使用put(key, value)存儲(chǔ)對(duì)象到HashMap中，使用get(key)從HashMap中獲取對(duì)象。當(dāng)我們給put()方法傳遞鍵和值時(shí)，我們先對(duì)鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket（桶）位置來(lái)儲(chǔ)存Entry對(duì)象。”HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象，作為Map.Entry。并不是僅僅只在bucket中存儲(chǔ)值。

HashMap具體的存取過(guò)程如下： put鍵值對(duì)的方法的過(guò)程是： 1、獲取key ； 2、通過(guò)hash函數(shù)得到hash值； int hash=key.hashCode(); //獲取key的hashCode，這個(gè)值是一個(gè)固定的int值

3、得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模) ，也即數(shù)組下標(biāo)int index=hash%Entry[].length。//獲取數(shù)組下標(biāo)：key的hash值對(duì)Entry數(shù)組長(zhǎng)度進(jìn)行取余

4、 存放key和value在桶內(nèi)。 table[index]=Entry對(duì)象；

get值方法的過(guò)程是: 1、獲取key 2、通過(guò)hash函數(shù)得到hash值 int hash=key.hashCode();

3、得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模) int index =hash%Entry[].length;

4、比較桶的內(nèi)部元素是否與key相等，若都不相等，則沒(méi)有找到。

5、取出相等的記錄的value。

HashMap中直接地址用hash函數(shù)生成；解決沖突，用比較函數(shù)解決。如果每個(gè)桶內(nèi)部只有一個(gè)元素，那么查找的時(shí)候只有一次比較。當(dāng)許多桶內(nèi)沒(méi)有值時(shí)，許多查詢(xún)就會(huì)更快了(指查不到的時(shí)候)。

HashMap中的碰撞探測(cè)(collision detection)以及碰撞的解決方法

當(dāng)兩個(gè)對(duì)象的hashcode相同時(shí)，它們的bucket位置相同，‘碰撞’會(huì)發(fā)生。因?yàn)镠ashMap使用LinkedList存儲(chǔ)對(duì)象，這個(gè)Entry(包含有鍵值對(duì)的Map.Entry對(duì)象)會(huì)存儲(chǔ)在LinkedList中。這兩個(gè)對(duì)象就算hashcode相同，但是它們可能并不相等。 那如何獲取這兩個(gè)對(duì)象的值呢？當(dāng)我們調(diào)用get()方法，HashMap會(huì)使用鍵對(duì)象的hashcode找到bucket位置，遍歷LinkedList直到找到值對(duì)象。找到bucket位置之后，會(huì)調(diào)用keys.equals()方法去找到LinkedList中正確的節(jié)點(diǎn)，最終找到要找的值對(duì)象使用不可變的、聲明作final的對(duì)象，并且采用合適的equals()和hashCode()方法的話，將會(huì)減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個(gè)獲取對(duì)象的速度，使用String，Interger這樣的wrapper類(lèi)作為鍵是非常好的選擇。

如何重新調(diào)整HashMap的大小

“如果HashMap的大小超過(guò)了負(fù)載因子(load factor)定義的容量，怎么辦？” 默認(rèn)的負(fù)載因子大小為0.75，也就是說(shuō)，當(dāng)一個(gè)map填滿(mǎn)了75%的bucket時(shí)候，和其它集合類(lèi)(如ArrayList等)一樣，將會(huì)創(chuàng)建原來(lái)HashMap大小的兩倍的bucket數(shù)組，來(lái)重新調(diào)整map的大小，并將原來(lái)的對(duì)象放入新的bucket數(shù)組中。這個(gè)過(guò)程叫作rehashing，因?yàn)樗{(diào)用hash方法找到新的bucket位置。

不可變對(duì)象的好處

上面說(shuō)到使用包裝類(lèi)時(shí)刻作為鍵的原因是 String, Interger這樣的wrapper類(lèi)作為HashMap的鍵是很合適的，而且String最為常用。因?yàn)镾tring是不可變的，也是final的，而且已經(jīng)重寫(xiě)了equals()和hashCode()方法了。其他的wrapper類(lèi)也有這個(gè)特點(diǎn)。不可變性是必要的，因?yàn)闉榱艘?jì)算hashCode()，就要防止鍵值改變，如果鍵值在放入時(shí)和獲取時(shí)返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對(duì)象。不可變性還有其他的優(yōu)點(diǎn)如線程安全。如果你可以?xún)H僅通過(guò)將某個(gè)field聲明成final就能保證hashCode是不變的，那么請(qǐng)這么做吧。因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫(xiě)這兩個(gè)方法是非常重要的。如果兩個(gè)不相等的對(duì)象返回不同的hashcode的話，那么碰撞的幾率就會(huì)小些，這樣就能提高HashMap的性能。

HashMap多線程的條件競(jìng)爭(zhēng)

重新調(diào)整HashMap大小存在什么問(wèn)題嗎？”在多線程的情況下，可能產(chǎn)生條件競(jìng)爭(zhēng)(race condition)。因?yàn)槿绻麅蓚€(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會(huì)同時(shí)試著調(diào)整大小。在調(diào)整大小的過(guò)程中，存儲(chǔ)在LinkedList中的元素的次序會(huì)反過(guò)來(lái)，因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候，HashMap并不會(huì)將元素放在LinkedList的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競(jìng)爭(zhēng)發(fā)生了，那么就死循環(huán)了。(在多線程的情況下，為什么還要使用HashMap呢？不懂)

我們也可以使用自定義的對(duì)象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當(dāng)對(duì)象插入到Map中之后將不會(huì)再改變了。如果這個(gè)自定義對(duì)象時(shí)不可變的，那么它已經(jīng)滿(mǎn)足了作為鍵的條件，因?yàn)楫?dāng)它創(chuàng)建之后就已經(jīng)不能改變了。

我們可以使用CocurrentHashMap來(lái)代替HashTable嗎？這是另外一個(gè)很熱門(mén)的面試題，因?yàn)镃oncurrentHashMap越來(lái)越多人用了。我們知道HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，因?yàn)樗鼉H僅根據(jù)同步級(jí)別對(duì)map的一部分進(jìn)行上鎖。ConcurrentHashMap當(dāng)然可以代替HashTable，但是HashTable提供更強(qiáng)的線程安全性。