HashTable

• 底層數(shù)組+鏈表實(shí)現(xiàn)帅掘，無(wú)論key還是value都不能為null，線(xiàn)程安全奋姿，實(shí)現(xiàn)線(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值，線(xiàn)程不安全
• 初始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和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表示半滿(mǎn)的散列表，依此類(lèi)推蚕礼。輕負(fù)載的散列表具有沖突少烟具、適宜插入與查詢(xún)的特點(diǎn)（但是使用Iterator迭代元素時(shí)比較慢）

除此之外，hash表里還有一個(gè)“負(fù)載極限”奠蹬，“負(fù)載極限”是一個(gè)0～1的數(shù)值朝聋，“負(fù)載極限”決定了hash表的最大填滿(mǎn)程度。當(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)被填滿(mǎn)時(shí)腊尚，hash表會(huì)發(fā)生rehashing吨拗。

“負(fù)載極限”的默認(rèn)值（0.75）是時(shí)間和空間成本上的一種折中：

• 較高的“負(fù)載極限”可以降低hash表所占用的內(nèi)存空間，但會(huì)增加查詢(xún)數(shù)據(jù)的時(shí)間開(kāi)銷(xiāo)婿斥，而查詢(xún)是最頻繁的操作（HashMap的get()與put()方法都要用到查詢(xún)）
• 較低的“負(fù)載極限”會(huì)提高查詢(xún)數(shù)據(jù)的性能劝篷，但會(huì)增加hash表所占用的內(nèi)存開(kāi)銷(xiāo)
• 程序猿可以根據(jù)實(shí)際情況來(lái)調(diào)整“負(fù)載極限”值。

ConcurrentHashMap

• 底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)民宿，線(xiàn)程安全
• 通過(guò)把整個(gè)Map分為N個(gè)Segment携龟，可以提供相同的線(xiàn)程安全，但是效率提升N倍勘高，默認(rèn)提升16倍。(讀操作不加鎖坟桅，由于HashEntry的value變量是 volatile的华望，也能保證讀取到最新的值。)
• Hashtable的synchronized是針對(duì)整張Hash表的仅乓，即每次鎖住整張表讓線(xiàn)程獨(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是線(xiàn)程安全的，它的方法是同步的涮坐，可以直接用在多線(xiàn)程環(huán)境中凄贩。而HashMap則不是線(xiàn)程安全的，在多線(xiàn)程環(huán)境中膊升，需要手動(dòng)實(shí)現(xiàn)同步機(jī)制怎炊。

Hashtable與HashMap另一個(gè)區(qū)別是HashMap的迭代器（Iterator）是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的廓译。所以當(dāng)有其它線(xiàn)程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）评肆，將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常非区。但這并不是一個(gè)一定發(fā)生的行為瓜挽，要看JVM。