希望各位小伙伴能帶著如下幾個(gè)問(wèn)題來(lái)進(jìn)行閱讀，這樣收獲會(huì)更大排苍。
- HashTable沦寂、HashMap、ConcurrentHashMap的區(qū)別淘衙？
- HashMap線程不安全的出現(xiàn)場(chǎng)景传藏？
- **HashMap put方法存放數(shù)據(jù)時(shí)是怎么判斷是否重復(fù)的？ **
- JDK7和JDK8**** 中HashMap的實(shí)現(xiàn)有什么區(qū)別彤守？
- HashMap的長(zhǎng)度為什么是2的冪次方毯侦？
下面先說(shuō)這三個(gè)Map的區(qū)別：
HashTable
- 底層數(shù)組+鏈表實(shí)現(xiàn)，無(wú)論key還是value都不能為null具垫，線程安全侈离，實(shí)現(xiàn)線程安全的方式是在修改數(shù)據(jù)時(shí)鎖住整個(gè)HashTable，效率低筝蚕，ConcurrentHashMap做了相關(guān)優(yōu)化
- 初始size為11卦碾，擴(kuò)容：newsize = olesize*2+1
- 計(jì)算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashMap
- 底層數(shù)組+鏈表實(shí)現(xiàn)，可以存儲(chǔ)null鍵和null值起宽，線程不安全
- 初始size為16洲胖，擴(kuò)容：newsize = oldsize*2，size一定為2的n次冪
- 擴(kuò)容針對(duì)整個(gè)Map坯沪，每次擴(kuò)容時(shí)宾濒，原來(lái)數(shù)組中的元素依次重新計(jì)算存放位置，并重新插入
- 插入元素后才判斷該不該擴(kuò)容屏箍，有可能無(wú)效擴(kuò)容（插入后如果擴(kuò)容，如果沒(méi)有再次插入橘忱，就會(huì)產(chǎn)生無(wú)效擴(kuò)容）
- 當(dāng)Map中元素總數(shù)超過(guò)Entry數(shù)組的75%赴魁，觸發(fā)擴(kuò)容操作，為了減少鏈表長(zhǎng)度钝诚，元素分配更均勻
- 計(jì)算index方法：index = hash & (tab.length – 1)
HashMap的初始值還要考慮加載因子:
哈希沖突：若干Key的哈希值按數(shù)組大小取模后颖御，如果落在同一個(gè)數(shù)組下標(biāo)上，將組成一條Entry鏈，對(duì)Key的查找需要遍歷Entry鏈上的每個(gè)元素執(zhí)行equals()比較潘拱。
加載因子：為了降低哈希沖突的概率疹鳄，默認(rèn)當(dāng)HashMap中的鍵值對(duì)達(dá)到數(shù)組大小的75%時(shí)，即會(huì)觸發(fā)擴(kuò)容芦岂。因此瘪弓，如果預(yù)估容量是100，即需要設(shè)定100/0.75＝134的數(shù)組大小禽最。
空間換時(shí)間：如果希望加快Key查找的時(shí)間腺怯，還可以進(jìn)一步降低加載因子，加大初始大小川无，以降低哈希沖突的概率呛占。
HashMap的內(nèi)部結(jié)構(gòu)可以看作是數(shù)組(Node<K,V>[] table)和鏈表的復(fù)合結(jié)構(gòu)，數(shù)組被分為一個(gè)個(gè)桶（bucket）懦趋，通過(guò)哈希值決定了鍵值對(duì)在這個(gè)數(shù)組中的尋址（哈希值相同的鍵值對(duì)晾虑，則以鏈表形式存儲(chǔ)），如下圖所示仅叫。有一點(diǎn)需要注意帜篇，如果鏈表大小超過(guò)閾值（TREEIFY_THRESHOLD,8），圖中的鏈表就會(huì)被改造為樹(shù)形結(jié)構(gòu)惑芭。
HashMap和Hashtable都是用hash算法來(lái)決定其元素的存儲(chǔ)坠狡，因此HashMap和Hashtable的hash表包含如下屬性：
- 容量（capacity）：hash表中桶的數(shù)量
- 初始化容量（initial capacity）：創(chuàng)建hash表時(shí)桶的數(shù)量，HashMap允許在構(gòu)造器中指定初始化容量
- 尺寸（size）：當(dāng)前hash表中記錄的數(shù)量
- 負(fù)載因子（load factor）：負(fù)載因子等于“size/capacity”遂跟。負(fù)載因子為0逃沿，表示空的hash表，0.5表示半滿的散列表幻锁，依此類(lèi)推凯亮。輕負(fù)載的散列表具有沖突少、適宜插入與查詢的特點(diǎn)（但是使用Iterator迭代元素時(shí)比較慢）
除此之外哄尔，hash表里還有一個(gè)“負(fù)載極限”假消，“負(fù)載極限”是一個(gè)0～1的數(shù)值，“負(fù)載極限”決定了hash表的最大填滿程度岭接。當(dāng)hash表中的負(fù)載因子達(dá)到指定的“負(fù)載極限”時(shí)富拗，hash表會(huì)自動(dòng)成倍地增加容量（桶的數(shù)量），并將原有的對(duì)象重新分配鸣戴，放入新的桶內(nèi)啃沪，這稱(chēng)為rehashing。
HashMap和Hashtable的構(gòu)造器允許指定一個(gè)負(fù)載極限窄锅，HashMap和Hashtable默認(rèn)的“負(fù)載極限”為0.75创千，這表明當(dāng)該hash表的3/4已經(jīng)被填滿時(shí)，hash表會(huì)發(fā)生rehashing。
“負(fù)載極限”的默認(rèn)值（0.75）是時(shí)間和空間成本上的一種折中：
- 較高的“負(fù)載極限”可以降低hash表所占用的內(nèi)存空間追驴，但會(huì)增加查詢數(shù)據(jù)的時(shí)間開(kāi)銷(xiāo)械哟，而查詢是最頻繁的操作（HashMap的get()與put()方法都要用到查詢）
- 較低的“負(fù)載極限”會(huì)提高查詢數(shù)據(jù)的性能，但會(huì)增加hash表所占用的內(nèi)存開(kāi)銷(xiāo)
程序猿可以根據(jù)實(shí)際情況來(lái)調(diào)整“負(fù)載極限”值殿雪，但一般不建議輕易修改暇咆，因?yàn)镴DK自身的默認(rèn)負(fù)載因子是非常符合通用場(chǎng)景需求的。如果確實(shí)需要修改冠摄，建議不要設(shè)置超過(guò)0.75糯崎，因?yàn)闀?huì)顯著增加沖突，降低HashMap的性能河泳。
根據(jù)容量和負(fù)載因子的關(guān)系沃呢，我們可以預(yù)先設(shè)置合適的容量大小，具體數(shù)值我們可以根據(jù)擴(kuò)容發(fā)生的條件來(lái)做簡(jiǎn)單預(yù)估拆挥，計(jì)算公式如下：
負(fù)載因子 * 容量 > 元素?cái)?shù)量
所以預(yù)先設(shè)置的容量需要大于“預(yù)估元素?cái)?shù)量/負(fù)載因子”薄霜，同時(shí)它是2的冪數(shù)。
上面提到HashMap會(huì)樹(shù)化纸兔，為什么會(huì)這樣呢惰瓜？
本質(zhì)上這是個(gè)安全問(wèn)題。因?yàn)樵谠胤胖眠^(guò)程中汉矿，如果一個(gè)對(duì)象哈希沖突崎坊，都被放置到同一個(gè)桶里，則會(huì)形成一個(gè)鏈表洲拇，我們知道鏈表查詢是線性的奈揍，會(huì)嚴(yán)重影響存取的性能。而在現(xiàn)實(shí)世界赋续，構(gòu)造哈希沖突的數(shù)據(jù)并不是非常復(fù)雜的事情男翰，惡意代碼就可以利用這些數(shù)據(jù)大量與服務(wù)器端交互，導(dǎo)致服務(wù)器端CPU大量占用纽乱，這就構(gòu)成了哈希碰撞拒絕服務(wù)攻擊蛾绎，國(guó)內(nèi)一線互聯(lián)網(wǎng)公司就發(fā)生過(guò)類(lèi)似攻擊事件。
ConcurrentHashMap
底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)鸦列，線程安全
通過(guò)把整個(gè)Map分為N個(gè)Segment租冠，可以提供相同的線程安全，但是效率提升N倍薯嗤，默認(rèn)提升16倍肺稀。(讀操作不加鎖，由于HashEntry的value變量是 volatile的应民，也能保證讀取到最新的值。)
Hashtable的synchronized是針對(duì)整張Hash表的，即每次鎖住整張表讓線程獨(dú)占诲锹，ConcurrentHashMap允許多個(gè)修改操作并發(fā)進(jìn)行繁仁，其關(guān)鍵在于使用了鎖分離技術(shù)
有些方法需要跨段，比如size()和containsValue()归园，它們可能需要鎖定整個(gè)表而而不僅僅是某個(gè)段黄虱，這需要按順序鎖定所有段，操作完畢后庸诱，又按順序釋放所有段的鎖
-
擴(kuò)容：段內(nèi)擴(kuò)容（段內(nèi)元素超過(guò)該段對(duì)應(yīng)Entry數(shù)組長(zhǎng)度的75%觸發(fā)擴(kuò)容捻浦，不會(huì)對(duì)整個(gè)Map進(jìn)行擴(kuò)容），插入前檢測(cè)需不需要擴(kuò)容桥爽，有效避免無(wú)效擴(kuò)容
Hashtable和HashMap都實(shí)現(xiàn)了Map接口朱灿，但是Hashtable的實(shí)現(xiàn)是基于Dictionary抽象類(lèi)的。Java5提供了ConcurrentHashMap钠四，它是HashTable的替代盗扒，比HashTable的擴(kuò)展性更好。
HashMap基于哈希思想缀去，實(shí)現(xiàn)對(duì)數(shù)據(jù)的讀寫(xiě)侣灶。當(dāng)我們將鍵值對(duì)傳遞給put()方法時(shí)，它調(diào)用鍵對(duì)象的hashCode()方法來(lái)計(jì)算hashcode缕碎，然后找到bucket位置來(lái)存儲(chǔ)值對(duì)象褥影。當(dāng)獲取對(duì)象時(shí)，通過(guò)鍵對(duì)象的equals()方法找到正確的鍵值對(duì)咏雌，然后返回值對(duì)象凡怎。HashMap使用鏈表來(lái)解決碰撞問(wèn)題，當(dāng)發(fā)生碰撞時(shí)处嫌，對(duì)象將會(huì)儲(chǔ)存在鏈表的下一個(gè)節(jié)點(diǎn)中栅贴。HashMap在每個(gè)鏈表節(jié)點(diǎn)中儲(chǔ)存鍵值對(duì)對(duì)象。當(dāng)兩個(gè)不同的鍵對(duì)象的hashcode相同時(shí)熏迹，它們會(huì)儲(chǔ)存在同一個(gè)bucket位置的鏈表中檐薯，可通過(guò)鍵對(duì)象的equals()方法來(lái)找到鍵值對(duì)。如果鏈表大小超過(guò)閾值（TREEIFY_THRESHOLD,8）注暗，鏈表就會(huì)被改造為樹(shù)形結(jié)構(gòu)坛缕。
在HashMap中，null可以作為鍵捆昏，這樣的鍵只有一個(gè)赚楚，但可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。當(dāng)get()方法返回null值時(shí)骗卜，即可以表示HashMap中沒(méi)有該key宠页，也可以表示該key所對(duì)應(yīng)的value為null左胞。因此，在HashMap中不能由get()方法來(lái)判斷HashMap中是否存在某個(gè)key举户，應(yīng)該用**containsKey()**方法來(lái)判斷烤宙。而在Hashtable中，無(wú)論是key還是value都不能為null俭嘁。
Hashtable是線程安全的躺枕，它的方法是同步的，可以直接用在多線程環(huán)境中供填。而HashMap則不是線程安全的拐云，在多線程環(huán)境中，需要手動(dòng)實(shí)現(xiàn)同步機(jī)制近她。
Hashtable與HashMap另一個(gè)區(qū)別是HashMap的迭代器（Iterator）是fail-fast迭代器叉瘩，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）泄私，將會(huì)拋出ConcurrentModificationException房揭，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為晌端，要看JVM捅暴。
先看一下簡(jiǎn)單的類(lèi)圖：
從類(lèi)圖中可以看出來(lái)在存儲(chǔ)結(jié)構(gòu)中ConcurrentHashMap比HashMap多出了一個(gè)類(lèi)Segment。**ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成咧纠。Segment是一個(gè)可重入鎖（ReentrantLock）蓬痒，在ConcurrentHashMap里扮演鎖的角色；HashEntry則用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)漆羔。一個(gè)ConcurrentHashMap里包含一個(gè)Segment數(shù)組梧奢。Segment的結(jié)構(gòu)和HashMap類(lèi)似，是一種數(shù)組和鏈表結(jié)構(gòu)演痒。一個(gè)Segment里包含一個(gè)HashEntry數(shù)組亲轨，每個(gè)HashEntry是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè)Segment守護(hù)著一個(gè)HashEntry數(shù)組里的元素鸟顺。當(dāng)對(duì)HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)惦蚊，必須首先獲得與它對(duì)應(yīng)的segment鎖。**
ConcurrentHashMap是使用了鎖分段技術(shù)來(lái)保證線程安全的讯嫂。
鎖分段技術(shù)：首先將數(shù)據(jù)分成一段一段的存儲(chǔ)蹦锋，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候欧芽，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)莉掂。
ConcurrentHashMap提供了與Hashtable和SynchronizedMap不同的鎖機(jī)制。Hashtable中采用的鎖機(jī)制是一次鎖住整個(gè)hash表千扔，從而在同一時(shí)刻只能由一個(gè)線程對(duì)其進(jìn)行操作憎妙；而ConcurrentHashMap中則是一次鎖住一個(gè)桶库正。
Hashtable容器在競(jìng)爭(zhēng)激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因是因?yàn)樗性L問(wèn)Hashtable的線程都必須競(jìng)爭(zhēng)同一把鎖，假如容器里有多把鎖尚氛，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)诀诊，那么當(dāng)多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)時(shí)，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)阅嘶，從而可以有效提高并發(fā)訪問(wèn)效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)载迄。首先將數(shù)據(jù)分成一段一段存儲(chǔ)讯柔，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候护昧，其它段的數(shù)據(jù)也能被其它線程訪問(wèn)魂迄。
ConcurrentHashMap默認(rèn)將hash表分為16個(gè)桶，諸如get惋耙、put捣炬、remove等常用操作只鎖住當(dāng)前需要用到的桶。這樣绽榛，原來(lái)只能一個(gè)線程進(jìn)入湿酸，現(xiàn)在卻能同時(shí)有16個(gè)寫(xiě)線程執(zhí)行，并發(fā)性能的提升是顯而易見(jiàn)的灭美。
