HashMap、Hash Table、ConcurrentHashMap

這個這個。。。本王最近由于開始找實(shí)習(xí)工作了，所以就在牛客網(wǎng)上刷一些公司的面試題，大多都是一些java，前端HTML，js，jquery，以及一些好久沒有碰的算法題，說實(shí)話，有點(diǎn)難受，其實(shí)在我不知道的很多是地方還有很多很多的知識漏洞，就像這一次寫的這個，也是我在刷題的時候感覺到真的是我空缺的地方，為什么呢？因?yàn)?，做多了，錯多了。然而很尷尬的又是因?yàn)檫@個只是也是很多公司的面試題，所以索性直接寫下來整理一遍。

在這里我也建議各位，?？途W(wǎng)不僅僅是一個找工作的station也是一個可以鍛煉我們的地方，沒事刷刷題啊，逛逛論壇啊，說不定就能找到很多你意想不到的東西。

在面試的過程中，有幾個問題是比較常見的。

* HashTable、HashMap、ConcurrentHashMap的區(qū)別？
* HashMap線程不安全的出現(xiàn)場景？
* HashMap put方法存放數(shù)據(jù)時是怎么判斷是否重復(fù)的？???
* JDK7和JDK8?中HashMap的實(shí)現(xiàn)有什么區(qū)別？
* HashMap的長度為什么是2的冪次方？
只要把這幾個問題過一遍之后，大致了解了他們各自的作用與互相之間的區(qū)別再?。∪デ靡槐槠鋵?shí)就可以掌握了。

HashTable

* 底層數(shù)組+鏈表實(shí)現(xiàn)，無論key還是value都不能為null，線程安全
，實(shí)現(xiàn)線程安全的方式是在修改數(shù)據(jù)時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關(guān)優(yōu)化
* 初始size為11，擴(kuò)容：newsize = oldsize*2+1
* 計(jì)算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashMap

* 在底層數(shù)組+鏈表中實(shí)現(xiàn)，線程不安全，可存儲null鍵和null值
* 初始size為16，可擴(kuò)容：newsize = oldsize*2，size一定為2的n次冪
* 擴(kuò)容針對整個Map，每次擴(kuò)容的時候，原來數(shù)組中的元素依次重新計(jì)算存放的位置，并重新插入
* 插入元素后才判斷該不該擴(kuò)容，有可能無效擴(kuò)容（插入后如果擴(kuò)容，如果沒有再次插入，就會產(chǎn)生無效擴(kuò)容）
* 當(dāng)Map中元素總數(shù)超過Entry數(shù)組的75%，觸發(fā)擴(kuò)容操作，為了減少鏈表長度，元素分配更均勻
* 計(jì)算index方法：index = hash & (tab.length – 1)
*HashMap的初始值還要考慮加載因子:

哈希沖突：若干Key的哈希值按數(shù)組大小取模后，如果落在同一個數(shù)組下標(biāo)上，將組成一條Entry鏈，對Key的查找需要遍歷Entry鏈上的每個元素執(zhí)行equals()比較。

加載因子：為了降低哈希沖突的概率，默認(rèn)當(dāng)HashMap中的鍵值對達(dá)到數(shù)組大小的75%時，即會觸發(fā)擴(kuò)容。因此，如果預(yù)估容量是100，即需要設(shè)定100/0.75＝134的數(shù)組大小。
空間換時間：如果希望加快Key查找的時間，還可以進(jìn)一步降低加載因子，加大初始大小，以降低哈希沖突的概率。

HashMap與HashTable的區(qū)別（面試題?？紐）

1.兩者所繼承的父類不同



HashMap是繼承自AbstractMap類，而HashTable是繼承自Dictionary類。不過它們都實(shí)現(xiàn)了同時實(shí)現(xiàn)了map、Cloneable（可復(fù)制）、Serializable（可序列化）這三個接口。

在這里原本是截取了JDK API1.6 中文版里面的，但實(shí)在是太丑了，就在別人的博客，呵呵，悄咪咪的拿了過來借鑒了一下





?2.兩者對外接口是不同的

HashTable比HashMap多提供了elements()和contains()兩個方法。

elements()方法繼承自HashTable的父類Doctionnary。elements()方法用于返回此時HashTable中的值的枚舉。



contains()方法判斷該Hashtable是否包含傳入的value。它的作用與containsValue()一致。事實(shí)上，contansValue()
就只是調(diào)用了一下contains() 方法，是判斷哈希表中是否包含指定的值。如圖是contains的源碼：
public virtual bool Contains(object key) { return this.ContainsKey(key); }
3.對Null key 和Null value的支持不同
Hashtable既不支持Null key也不支持Null value。


HashMap中，key-value都是存在Entry中的。null可以作為鍵，這樣的鍵只有一個；可以有一個或多個鍵所對應(yīng)的值為null，不保證元素的順序恒久不變，它的底層使用的是數(shù)組和鏈表，用過HashCode()方法和equal()方法來保證鍵的唯一性。當(dāng)get()方法返回null值時，可能是
HashMap中沒有該鍵，也可能使該鍵所對應(yīng)的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵，
而應(yīng)該用containsKey()方法來判斷。
4.線程安全的不同性


Hashtable是線程安全的，它的每個方法中都加入了Synchronize方法。在多線程并發(fā)的環(huán)境下，可以直接使用Hashtable，不需要自己為它的方法實(shí)現(xiàn)同步。

HashMap不是線程安全的，在多線程并發(fā)的環(huán)境下，可能會產(chǎn)生死鎖等問題。所以使用HashMap時就必須要自己增加同步處理，


雖然HashMap不是線程安全的，但是它的效率會比Hashtable要好很多。這樣設(shè)計(jì)是合理的。在我們的日常使用當(dāng)中，大部分時間是單線程操作的。HashMap把這部分操作解放出來了。當(dāng)需要多線程操作的時候可以使用線程安全的ConcurrentHashMap。ConcurrentHashMap雖然也是線程安全的，但是它的效率比Hashtable要高好多倍。因?yàn)镃oncurrentHashMap使用了分段鎖，并不對整個數(shù)據(jù)進(jìn)行鎖定。
5.Hash值的計(jì)算方法不同

為了求得元素的位置，需要根據(jù)元素的Key計(jì)算出一個哈希值，然后再用這個哈希值來計(jì)算出崔忠的位置。




Hashtable直接使用對象的hashCode。hashCode是JDK根據(jù)對象的地址或者字符串或者數(shù)字算出來的int類型的數(shù)值。然后再使用除留余數(shù)發(fā)來獲得最終的位置。

Hashtable在計(jì)算元素的位置時需要進(jìn)行一次除法運(yùn)算，而除法運(yùn)算是比較耗時的。

HashMap為了提高計(jì)算效率，將哈希表的大小固定為了2的冪，這樣在取模預(yù)算時，不需要做除法，只需要做位運(yùn)算。位運(yùn)算比除法的效率要高很多。

HashMap的效率雖然提高了，但是hash沖突卻也增加了。因?yàn)樗贸龅膆ash值的低位相同的概率比較高，而計(jì)算位運(yùn)算


為了解決這個問題，HashMap重新根據(jù)hashcode計(jì)算hash值后，又對hash值做了一些運(yùn)算來打散數(shù)據(jù)。使得取得的位置更加分散，從而減少了hash沖突。當(dāng)然了，為了高效，HashMap只做了一些簡單的位處理。從而不至于把使用2
的冪次方帶來的效率提升給抵消掉。

ConcurrentHashMap

* 底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，線程安全。
* key和value都不能為null。
* 通過把整個Map分為N個Segment，可以提供相同的線程安全，但是效率提升N倍，默認(rèn)提升16倍。
*
Hashtable的synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨(dú)占，ConcurrentHashMap允許多個修改操作并發(fā)進(jìn)行，其關(guān)鍵在于使用了鎖分離技術(shù)
*
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖
* 擴(kuò)容：段內(nèi)擴(kuò)容（段內(nèi)元素超過該段對應(yīng)Entry數(shù)組長度的75%觸發(fā)擴(kuò)容，不會對整個Map進(jìn)行擴(kuò)容），插入前檢測需不需要擴(kuò)容，有效避免無效擴(kuò)容
這個就很棒了，上面總結(jié)的源于某猿大神，Java5提供的ConcurrentHashMap就像是HashTable的升級版，擴(kuò)容性更強(qiáng)。


在HashMap中，通過get()返回的null值，既可以表示返回該Key所對應(yīng)過的Value是null值，也可以表示為沒有該Key，在這種情況下就應(yīng)該采用ConcurrentHashMap。

來看一張簡單的類圖：




ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一個可重入鎖（ReentrantLock），在ConcurrentHashMap里扮演鎖的角色；HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含一個Segment數(shù)組。Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)。一個Segment里包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結(jié)構(gòu)的元素，每個Segment守護(hù)著一個HashEntry數(shù)組里的元素。當(dāng)對HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時，必須首先獲得與它對應(yīng)的segment鎖。


?Hashtable中采用的鎖機(jī)制是一次鎖住整個hash表，從而在同一時刻只能由一個線程對其進(jìn)行操作；而ConcurrentHashMap中則是一次鎖住一個桶。


簡單理解就是，ConcurrentHashMap是一個Segment數(shù)組，Segment通過繼承ReentrantLock來進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個Segment，只要保證每個Segment是線程安全的，也就實(shí)現(xiàn)了全局的線程安全。
重申一下，Segment數(shù)組不能擴(kuò)容，擴(kuò)容是Segment數(shù)組某個位置內(nèi)部的數(shù)組HashEntry<K,V>[]進(jìn)行擴(kuò)容，擴(kuò)容后，容量為原來的2倍。
可以回顧下出發(fā)擴(kuò)容的地方，put的時候，如果判斷該值的插入會導(dǎo)致該Segment的元素個數(shù)超過閾值，那么先進(jìn)行擴(kuò)容，再插值。

• ? 上一篇：記一道字節(jié)跳動的算法面試題
• ? 下一篇：.NET Core C#中級篇2-5 常見實(shí)用類