擴展閱讀：HashMap在jdk1.7和1.8中的實現(xiàn)
希望各位小伙伴能帶著如下幾個問題來進行閱讀猛铅，這樣收獲會更大。
HashTable凤藏、HashMap奸忽、ConcurrentHashMap的區(qū)別？
HashMap線程不安全的出現(xiàn)場景揖庄？
HashMap put方法存放數(shù)據(jù)時是怎么判斷是否重復(fù)的栗菜？??
JDK7和JDK8?中HashMap的實現(xiàn)有什么區(qū)別？
下面先說這三個Map的區(qū)別：
HashTable
底層數(shù)組+鏈表實現(xiàn)蹄梢，無論key還是value都不能為null疙筹，線程安全，實現(xiàn)線程安全的方式是在修改數(shù)據(jù)時鎖住整個HashTable禁炒，效率低而咆，ConcurrentHashMap做了相關(guān)優(yōu)化
初始size為11，擴容：newsize = olesize*2+1
計算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashMap
底層數(shù)組+鏈表實現(xiàn)幕袱，可以存儲null鍵和null值暴备，線程不安全
初始size為16，擴容：newsize = oldsize*2们豌，size一定為2的n次冪
擴容針對整個Map涯捻，每次擴容時，原來數(shù)組中的元素依次重新計算存放位置望迎，并重新插入
插入元素后才判斷該不該擴容障癌，有可能無效擴容（插入后如果擴容，如果沒有再次插入辩尊，就會產(chǎn)生無效擴容）
當(dāng)Map中元素總數(shù)超過Entry數(shù)組的75%涛浙，觸發(fā)擴容操作，為了減少鏈表長度，元素分配更均勻
計算index方法：index = hash & (tab.length – 1)
HashMap的初始值還要考慮加載因子:哈希沖突：若干Key的哈希值按數(shù)組大小取模后蝗拿，如果落在同一個數(shù)組下標(biāo)上晾捏，將組成一條Entry鏈，對Key的查找需要遍歷Entry鏈上的每個元素執(zhí)行equals()比較哀托。加載因子：為了降低哈希沖突的概率，默認(rèn)當(dāng)HashMap中的鍵值對達到數(shù)組大小的75%時劳秋，即會觸發(fā)擴容仓手。因此，如果預(yù)估容量是100玻淑，即需要設(shè)定100/0.75＝134的數(shù)組大小嗽冒》褪剑空間換時間：如果希望加快Key查找的時間蛉威，還可以進一步降低加載因子，加大初始大小雇锡，以降低哈希沖突的概率箫锤。
HashMap的內(nèi)部結(jié)構(gòu)可以看作是數(shù)組(Node[] table)和鏈表的復(fù)合結(jié)構(gòu)贬蛙，數(shù)組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數(shù)組中的尋址（哈希值相同的鍵值對谚攒，則以鏈表形式存儲）阳准，如下圖所示。有一點需要注意馏臭，如果鏈表大小超過閾值（TREEIFY_THRESHOLD,8）野蝇，圖中的鏈表就會被改造為樹形結(jié)構(gòu)。
HashMap和Hashtable都是用hash算法來決定其元素的存儲括儒，因此HashMap和Hashtable的hash表包含如下屬性：
容量（capacity）：hash表中桶的數(shù)量
初始化容量（initial capacity）：創(chuàng)建hash表時桶的數(shù)量绕沈，HashMap允許在構(gòu)造器中指定初始化容量
尺寸（size）：當(dāng)前hash表中記錄的數(shù)量
負(fù)載因子（load factor）：負(fù)載因子等于“size/capacity”。負(fù)載因子為0帮寻，表示空的hash表乍狐，0.5表示半滿的散列表，依此類推规婆。輕負(fù)載的散列表具有沖突少澜躺、適宜插入與查詢的特點（但是使用Iterator迭代元素時比較慢）
除此之外，hash表里還有一個“負(fù)載極限”抒蚜，“負(fù)載極限”是一個0～1的數(shù)值掘鄙，“負(fù)載極限”決定了hash表的最大填滿程度。當(dāng)hash表中的負(fù)載因子達到指定的“負(fù)載極限”時嗡髓，hash表會自動成倍地增加容量（桶的數(shù)量）操漠，并將原有的對象重新分配，放入新的桶內(nèi)，這稱為rehashing浊伙。
HashMap和Hashtable的構(gòu)造器允許指定一個負(fù)載極限撞秋，HashMap和Hashtable默認(rèn)的“負(fù)載極限”為0.75，這表明當(dāng)該hash表的3/4已經(jīng)被填滿時嚣鄙，hash表會發(fā)生rehashing吻贿。
“負(fù)載極限”的默認(rèn)值（0.75）是時間和空間成本上的一種折中：
較高的“負(fù)載極限”可以降低hash表所占用的內(nèi)存空間，但會增加查詢數(shù)據(jù)的時間開銷哑子，而查詢是最頻繁的操作（HashMap的get()與put()方法都要用到查詢）
較低的“負(fù)載極限”會提高查詢數(shù)據(jù)的性能舅列，但會增加hash表所占用的內(nèi)存開銷
程序猿可以根據(jù)實際情況來調(diào)整“負(fù)載極限”值，但一般不建議輕易修改卧蜓，因為JDK自身的默認(rèn)負(fù)載因子是非常符合通用場景需求的帐要。如果確實需要修改，建議不要設(shè)置超過0.75弥奸，因為會顯著增加沖突榨惠，降低HashMap的性能。
根據(jù)容量和負(fù)載因子的關(guān)系盛霎，我們可以預(yù)先設(shè)置合適的容量大小赠橙，具體數(shù)值我們可以根據(jù)擴容發(fā)生的條件來做簡單預(yù)估，計算公式如下：
負(fù)載因子 * 容量 > 元素數(shù)量
所以預(yù)先設(shè)置的容量需要大于“預(yù)估元素數(shù)量/負(fù)載因子”摩渺，同時它是2的冪數(shù)简烤。
上面提到HashMap會樹化，為什么會這樣呢摇幻？
本質(zhì)上這是個安全問題横侦。因為在元素放置過程中，如果一個對象哈希沖突绰姻，都被放置到同一個桶里枉侧，則會形成一個鏈表，我們知道鏈表查詢是線性的狂芋，會嚴(yán)重影響存取的性能榨馁。而在現(xiàn)實世界，構(gòu)造哈希沖突的數(shù)據(jù)并不是非常復(fù)雜的事情帜矾，惡意代碼就可以利用這些數(shù)據(jù)大量與服務(wù)器端交互翼虫，導(dǎo)致服務(wù)器端CPU大量占用，這就構(gòu)成了哈希碰撞拒絕服務(wù)攻擊屡萤，國內(nèi)一線互聯(lián)網(wǎng)公司就發(fā)生過類似攻擊事件珍剑。
ConcurrentHashMap
底層采用分段的數(shù)組+鏈表實現(xiàn)，線程安全
通過把整個Map分為N個Segment死陆，可以提供相同的線程安全招拙，但是效率提升N倍，默認(rèn)提升16倍。(讀操作不加鎖别凤，由于HashEntry的value變量是 volatile的饰序，也能保證讀取到最新的值。)
Hashtable的synchronized是針對整張Hash表的规哪，即每次鎖住整張表讓線程獨占求豫，ConcurrentHashMap允許多個修改操作并發(fā)進行，其關(guān)鍵在于使用了鎖分離技術(shù)
有些方法需要跨段由缆，比如size()和containsValue()注祖，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段均唉，操作完畢后，又按順序釋放所有段的鎖
擴容：段內(nèi)擴容（段內(nèi)元素超過該段對應(yīng)Entry數(shù)組長度的75%觸發(fā)擴容肚菠，不會對整個Map進行擴容）舔箭，插入前檢測需不需要擴容，有效避免無效擴容
????????Hashtable和HashMap都實現(xiàn)了Map接口蚊逢，但是Hashtable的實現(xiàn)是基于Dictionary抽象類的层扶。Java5提供了ConcurrentHashMap，它是HashTable的替代烙荷，比HashTable的擴展性更好镜会。
HashMap基于哈希思想，實現(xiàn)對數(shù)據(jù)的讀寫终抽。當(dāng)我們將鍵值對傳遞給put()方法時戳表，它調(diào)用鍵對象的hashCode()方法來計算hashcode，然后找到bucket位置來存儲值對象昼伴。當(dāng)獲取對象時匾旭，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象圃郊。HashMap使用鏈表來解決碰撞問題价涝，當(dāng)發(fā)生碰撞時，對象將會儲存在鏈表的下一個節(jié)點中持舆。HashMap在每個鏈表節(jié)點中儲存鍵值對對象色瘩。當(dāng)兩個不同的鍵對象的hashcode相同時，它們會儲存在同一個bucket位置的鏈表中逸寓，可通過鍵對象的equals()方法來找到鍵值對居兆。如果鏈表大小超過閾值（TREEIFY_THRESHOLD,8），鏈表就會被改造為樹形結(jié)構(gòu)席覆。
在HashMap中史辙，null可以作為鍵，這樣的鍵只有一個，但可以有一個或多個鍵所對應(yīng)的值為null聊倔。當(dāng)get()方法返回null值時晦毙，即可以表示HashMap中沒有該key，也可以表示該key所對應(yīng)的value為null耙蔑。因此见妒，在HashMap中不能由get()方法來判斷HashMap中是否存在某個key，應(yīng)該用containsKey()方法來判斷甸陌。而在Hashtable中须揣，無論是key還是value都不能為null。
??????? Hashtable是線程安全的钱豁，它的方法是同步的耻卡，可以直接用在多線程環(huán)境中。而HashMap則不是線程安全的牲尺，在多線程環(huán)境中卵酪，需要手動實現(xiàn)同步機制。
Hashtable與HashMap另一個區(qū)別是HashMap的迭代器（Iterator）是fail-fast迭代器谤碳，而Hashtable的enumerator迭代器不是fail-fast的溃卡。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會拋出ConcurrentModificationException蜒简，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常瘸羡。但這并不是一個一定發(fā)生的行為，要看JVM搓茬。
先看一下簡單的類圖：
????????從類圖中可以看出來在存儲結(jié)構(gòu)中ConcurrentHashMap比HashMap多出了一個類Segment犹赖，而Segment是一個可重入鎖。
????????ConcurrentHashMap是使用了鎖分段技術(shù)來保證線程安全的垮兑。
鎖分段技術(shù)：首先將數(shù)據(jù)分成一段一段的存儲冷尉，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候系枪，其他段的數(shù)據(jù)也能被其他線程訪問雀哨。?
ConcurrentHashMap提供了與Hashtable和SynchronizedMap不同的鎖機制。Hashtable中采用的鎖機制是一次鎖住整個hash表私爷，從而在同一時刻只能由一個線程對其進行操作雾棺；而ConcurrentHashMap中則是一次鎖住一個桶。
ConcurrentHashMap默認(rèn)將hash表分為16個桶衬浑，諸如get捌浩、put、remove等常用操作只鎖住當(dāng)前需要用到的桶工秩。這樣尸饺，原來只能一個線程進入进统，現(xiàn)在卻能同時有16個寫線程執(zhí)行，并發(fā)性能的提升是顯而易見的浪听。
