HashMap淺談
HashMap作為集合框架的重點(diǎn)，面試常常被提到。但是，如果僅僅是記住定論的你，往往會(huì)最后很痛苦，典型的問(wèn)題HashMap和HashTable有什么相同或不同?那么當(dāng)然會(huì)知道HashMap是線程不安全的，然后HashTable是安全的。然后其實(shí)只回答到這里往往是不夠的。為什么不安全呢?怎么導(dǎo)致不安全了?解決方案呢?所以今天就記錄下個(gè)人認(rèn)為比較重要的幾個(gè)知識(shí)點(diǎn)吧。
1.HashMap的hash如何獲取
hashCode是jdk根據(jù)對(duì)象的地址或者字符串或者數(shù)字算出來(lái)的int類型的數(shù)值 ,然后應(yīng)該都知道hashmap的下標(biāo)沖突（就是同一個(gè)數(shù)組下標(biāo)通過(guò)鏈表存放的對(duì)象，但是不一定是該數(shù)組下標(biāo)的對(duì)象hashcode都相同）,那么怎么樣的對(duì)象會(huì)存放在同一個(gè)數(shù)組下標(biāo)呢?
一般認(rèn)為通過(guò)hashcode%數(shù)組長(zhǎng)度，得到的數(shù)為存放的數(shù)組下標(biāo)，但是這樣子的問(wèn)題是，我么你的計(jì)算機(jī)都是二進(jìn)制的，取模算法的效率并不高，所以這時(shí)候我們可以利用位運(yùn)算了。不了解位運(yùn)算的話自己去科普科普吧。如何確定對(duì)象存放的數(shù)組下標(biāo)呢?
1.獲取對(duì)象hashcode，然后將其進(jìn)行右移16位
2.將右移16位的結(jié)果和其本身進(jìn)行或運(yùn)算
3.將獲取的hash與數(shù)組長(zhǎng)度-1進(jìn)行&運(yùn)算。
tab[i]中的i就是數(shù)組下標(biāo)，i=(n-1&hash)，就是數(shù)組長(zhǎng)度和上一部獲取到的hash進(jìn)行與運(yùn)算的值。以上代碼截圖均是JDK1.8版本。
那么就說(shuō)說(shuō)這個(gè)簡(jiǎn)單的獲取數(shù)組下標(biāo)的方法涉及的幾個(gè)關(guān)鍵的問(wèn)題吧。其實(shí)總體步驟就是下面這張圖。
1.為什么要將hashcode右移16位的結(jié)果和其本身進(jìn)行或運(yùn)算
?看看如果我們不講hashcode進(jìn)行右移，然后直接與數(shù)組長(zhǎng)度-1進(jìn)行&運(yùn)算的結(jié)果。
調(diào)用hashCode:? ?1111? ? 1111? ? 1111? ? 1111? ? 1111? ? 0000? ? 1110? ? 1010
?數(shù)組長(zhǎng)度16-1? : 0000????0000????0000????0000????0000????0000????0000? ? 1111
我們會(huì)發(fā)現(xiàn)就是數(shù)組長(zhǎng)度的大小都不會(huì)特別大，一開(kāi)始都是默認(rèn)16.那么hashcode與數(shù)組長(zhǎng)度-1進(jìn)行&運(yùn)算的話。由于數(shù)組長(zhǎng)度-1的值其高位幾乎都為0，那么hashcode的高位與其進(jìn)行&運(yùn)算無(wú)論hashcode的高位取值是什么都會(huì)為0，也就是說(shuō)由于數(shù)組長(zhǎng)度的高位幾乎都為0就導(dǎo)致與運(yùn)算后的hash值高位也為0，那么就是hashcode的高位并沒(méi)有參與運(yùn)算。所以這時(shí)就會(huì)導(dǎo)致進(jìn)行運(yùn)算只有低位起作用，那么很大程度上我們就只是運(yùn)用了低位進(jìn)行了運(yùn)算。
從上面兩張圖我們就發(fā)現(xiàn)，其實(shí)高位做的運(yùn)算是無(wú)效的，因?yàn)椴还躧ashcode的高位如何運(yùn)算，最后由于進(jìn)行了&運(yùn)算，導(dǎo)致其實(shí)我們得出的結(jié)果和hashcode高位無(wú)效。
2.為什么數(shù)組的長(zhǎng)度要是2的冪方呢？
首先我們知道計(jì)算機(jī)是二進(jìn)制運(yùn)算哈，然后%的運(yùn)算效率是很低的，當(dāng)然你感受不出來(lái)。
那么我們又要如何的變相去實(shí)現(xiàn)hash%數(shù)組長(zhǎng)度呢?這時(shí)候就有個(gè)巧妙地?cái)?shù)學(xué)運(yùn)算。
當(dāng)然只是我個(gè)人的試驗(yàn)。
所以數(shù)組的長(zhǎng)度取2的冪次可以利用hash&length-1來(lái)代替hash%length，其結(jié)果一模一樣。
二進(jìn)制運(yùn)算中決定奇數(shù)還是偶數(shù)是由其低位最后一個(gè)數(shù)字決定的，如果其為0則證明這個(gè)數(shù)是偶數(shù)，如果是1就代表是奇數(shù)。0&任何數(shù)都是0，則得出來(lái)的下標(biāo)數(shù)組都是偶數(shù)，那么其空間浪費(fèi)極大，下標(biāo)碰撞概率極大。所以2的冪-1得出來(lái)的是奇數(shù)，那么他與任何hash進(jìn)行&運(yùn)算其結(jié)果分布較為均勻。
HashMap 的 key 和 value 都能為 null 么？如果 key 能為 null，那么它是怎么樣查找值的？
這一個(gè)問(wèn)題很有可能會(huì)問(wèn)你，hashmap和hashtable中有什么區(qū)別，但是我們往往記得一個(gè)線程不安全，一個(gè)線程安全而已。
如果 key 為 null，則直接從哈希表的第一個(gè)位置 table[0] 對(duì)應(yīng)的鏈表上查找,由 putForNullKey（）實(shí)現(xiàn)。記住，key 為 null 的鍵值對(duì)永遠(yuǎn)都放在以 table[0] 為頭結(jié)點(diǎn)的鏈表中
HashMap為什么是線程不安全的呢?
1.put數(shù)據(jù)的時(shí)候由于沒(méi)有加鎖，所以允許兩個(gè)線程同時(shí)進(jìn)行寫操作，那么必定線程不安全。
2.擴(kuò)容機(jī)制沒(méi)有加鎖，有可能導(dǎo)致死循環(huán)。
擴(kuò)容機(jī)制中，擴(kuò)容中原來(lái)數(shù)組中的鏈表順序?qū)?huì)逆過(guò)來(lái)（自己好好理解代碼）。
我們假設(shè)有兩個(gè)線程同時(shí)需要執(zhí)行resize操作，我們?cè)瓉?lái)的桶數(shù)量為2，記錄數(shù)為3，需要resize桶到4，原來(lái)的記錄分別為：[3,A],[7,B],[5,C]，在原來(lái)的map里面，我們發(fā)現(xiàn)這三個(gè)entry都落到了第二個(gè)桶里面。
假設(shè)線程thread1執(zhí)行到了transfer方法的Entry next = e.next這一句，然后時(shí)間片用完了，此時(shí)的e = [3,A], next = [7,B]。線程thread2被調(diào)度執(zhí)行并且順利完成了resize操作，需要注意的是，此時(shí)的[7,B]的next為[3,A]。此時(shí)線程thread1重新被調(diào)度運(yùn)行，此時(shí)的thread1持有的引用是已經(jīng)被thread2 resize之后的結(jié)果。線程thread1首先將[3,A]遷移到新的數(shù)組上，然后再處理[7,B]，而[7,B]被鏈接到了[3,A]的后面，處理完[7,B]之后，就需要處理[7,B]的next了啊，而通過(guò)thread2的resize之后，[7,B]的next變?yōu)榱薣3,A]，此時(shí)，[3,A]和[7,B]形成了環(huán)形鏈表，在get的時(shí)候，如果get的key的桶索引和[3,A]和[7,B]一樣，那么就會(huì)陷入死循環(huán)。
