????????最常見的應(yīng)該是在問HashMap與HashTable的區(qū)別，偶爾會談及后兩者的區(qū)別。今天我們先簡單區(qū)別一下這幾個泛型類。

????????1.定義

????????2.HashMap 與HashTable 的區(qū)別

? ? ? ? 3.HashSet?

????????4.TreeSet和TreeMap

? ??????5.常見問題

1.定義

HashMap 是一個散列表，它存儲的內(nèi)容是鍵值對(key-value)映射;

Hashtable 也是一個散列表，它存儲的內(nèi)容是鍵值對(key-value)映射;

HashSet類實現(xiàn)了Set接口，由一個實際上是HashMap實例的散列表??支持，它可視為集合存儲，且不允許集合中有重復的值;

TreeSet 是一個有序的集合，它的作用是提供有序的Set集合;

2.HashMap 與HashTable 的區(qū)別

（a）類別：Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類。但二者都實現(xiàn)了Map接口；

（b）線程安全性不同：最重要的一點是，HashMap并非線程安全的，而HashTable是具有線程安全的（具有同步鎖Synchronize，也就是說每次只能有一個線程進行訪問，訪問前線程必須先取得其同步鎖）。也因此，在多線程使用時候，我們并不需要對HashTable進行同步處理，而HashMap則需要；

（c）key和value是否允許null值 ：其中key和value都是對象，并且不能包含重復key，但可以包含重復的value；

? ? ? ? ? ? HashTable的key和value都不可空，但是HashMap均可以，但是HashMap的key只能有一個為null（補充一下：當get()方法返回null值時，可能是 HashMap中沒有該鍵，也可能使該鍵所對應(yīng)的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵， 而應(yīng)該用containsKey()方法來判斷）;

（d）迭代器：HashMap使用的迭代器Iterator是fail-fast迭代器，但是HashTable使用的迭代器enumerator不是fail-fast的。也因此，當HashMap結(jié)構(gòu)發(fā)生改變（增加或者刪除），會拋出ConcurrentModificationException，但是本身的remove()方法等不會拋出該異常。但是這并不是一個一定發(fā)生的行為，要看JVM。同理，這也是Enumeration和Iterator的區(qū)別；

? ? ???Fail-safe和iterator迭代器相關(guān)。如果某個集合對象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因為這并沒有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進行了更改，再調(diào)用set()方法，將會拋出IllegalArgumentException異常。

?（e）處理速度：主要由于線程同步影響，造成HashTable的速度要比HashMap要來的慢，也因此在單一線程內(nèi)推薦使用HashMap，因為性能要好過Hashtable；

?（f）是否提供contains方法：HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因為contains方法容易讓人引起誤解。

Hashtable則保留了contains，containsValue和containsKey三個方法，其中contains和containsValue功能相同；

?（g）哈希值的使用不同：HashTable直接使用對象的hashCode，代碼是這樣的：

? ? ? ????????int hash = key.hashCode();

? ? ? ????????int index = (hash & 0x7FFFFFFF) % tab.length;

????????而HashMap重新計算hash值，而且用與代替求模：

????????????int hash = hash(k);

????????????int i = indexFor(hash, table.length);

? ?（h）內(nèi)部實現(xiàn)使用的數(shù)組初始化和擴容方式不同：Hashtable和HashMap它們兩個內(nèi)部實現(xiàn)方式的數(shù)組的初始大小和擴容的方式。HashTable中hash數(shù)組默認大小是11，增加的方式是 old*2+1；

HashMap中hash數(shù)組的默認大小是16，而且一定是2的指數(shù)。

? ? 補充一下，為了實現(xiàn)HashMap的同步問題，可以通過Collections獲?。篗ap Collections.synchronizedMap(Map m)? ? 這個方法返回一個同步的Map，這個Map封裝了底層的HashMap的所有方法，使得底層的HashMap即使是在多線程的環(huán)境中也是安全的。而且Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

? ? 然而，我們能用ConcurrentHashMap替代HashTable嗎？這要取決于你的需求，一般情況下是可以的。因為 ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。但是HashTable提供更強的線程安全性。

? ? 要詳細了解ConcurrentHashMap見《構(gòu)建一個更好的 HashMap---ConcurrentHashMap》

3.HashSet

? ? 上面說到它不允許集合中有重復的值，就是在將對象存儲在HashSet之前，要先確保對象重寫equals()和hashCode()方法，這樣才能比較對象的值是否相等，以確保set中沒有儲存相等的對象。如果我們沒有重寫這兩個方法，將會使用這個方法的默認實現(xiàn)。而且對于 HashSet 而言，它是基于 HashMap 實現(xiàn)的，HashSet 底層采用 HashMap 來保存所有元素。

? ? 當然，我們平常并不需要那么繁瑣，可以直接添加進去，public boolean add(Object o)方法用來在Set中添加元素，當元素值重復時則會立即返回false，如果成功添加的話會返回true。

????HashSet和HashMap的區(qū)別? *HashMap* —— *HashSet*：

????HashMap實現(xiàn)了Map接口 —— HashSet實現(xiàn)了Set接口

????HashMap儲存鍵值對 —— HashSet僅僅存儲對象（且無重復對象）

????使用put()方法將元素放入map中 —— HashSet使用add()方法將元素放入set中

????HashMap中使用鍵對象來計算hashcode值 —— HashSet使用成員對象來計算hashcode值，對于兩個對象來說hashcode可能相同，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話，那么返回false

????HashMap比較快，因為是使用唯一的鍵來獲取對象 —— HashSet較HashMap來說比較慢

4.TreeSet和TreeMap

? ??TreeMap 和 TreeSet 是 Java Collection Framework 的兩個重要成員，其中 TreeMap 是 Map 接口的常用實現(xiàn)類，而 TreeSet 是 Set 接口的常用實現(xiàn)類。雖然 TreeMap?和 TreeSet?實現(xiàn)的接口規(guī)范不同，但 TreeSet 底層是通過 TreeMap 來實現(xiàn)的（如同HashSet底層是是通過HashMap來實現(xiàn)的一樣），因此二者的實現(xiàn)方式完全一樣。而 TreeMap 的實現(xiàn)就是紅黑樹算法。

與HashSet完全類似，TreeSet里面絕大部分方法都市直接調(diào)用TreeMap方法來實現(xiàn)的。

????相同點：

????TreeMap和TreeSet都是有序的集合，也就是說他們存儲的值都是拍好序的。

????TreeMap和TreeSet都是非同步集合，因此他們不能在多線程之間共享，不過可以使用方法Collections.synchroinzedMap()來實現(xiàn)同步

????運行速度都要比Hash集合慢，他們內(nèi)部對元素的操作時間復雜度為O(logN)，而HashMap/HashSet則為O(1)。

????不同點：

????最主要的區(qū)別就是TreeSet和TreeMap非別實現(xiàn)Set和Map接口

????TreeSet只存儲一個對象，而TreeMap存儲兩個對象Key和Value（僅僅key對象有序）

????TreeSet中不能有重復對象，而TreeMap中可以存在

5.常見問題

“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”

????答：“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。”這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當?shù)恼_，也顯示出面試者確實知道hashing以及HashMap的工作原理。

“如果兩個鍵的hashcode相同，你如何獲取值對象？”

?????面試者會回答：當我們調(diào)用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。

????其中一些記得這個重要知識點的面試者會說，找到bucket位置之后，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象。完美的答案！

????許多情況下，面試者會在這個環(huán)節(jié)中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對象的時候才出現(xiàn)。一些優(yōu)秀的開發(fā)者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。

????如果你認為到這里已經(jīng)完結(jié)了，那么聽到下面這個問題的時候，你會大吃一驚。

“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”

????除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing，因為它調(diào)用hash方法找到新的bucket位置。如果你能夠回答這道問題，下面的問題來了：

“你了解重新調(diào)整HashMap大小存在什么問題嗎？”

????你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產(chǎn)生條件競爭(race condition)。

????當重新調(diào)整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了。這個時候，你可以質(zhì)問面試官，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢？：）

”為什么String, Interger這樣的wrapper類適合作為鍵？“

? ??String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

????“我們可以使用自定義的對象作為鍵嗎？?”這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經(jīng)滿足了作為鍵的條件，因為當它創(chuàng)建之后就已經(jīng)不能改變了。

“我們可以使用CocurrentHashMap來代替Hashtable嗎？”

? ? 上面也簡單說過了，這里再說明一下，畢竟這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性?？纯床榭?a target="_blank" rel="nofollow">《HashMap Vs ConcurrentHashMap》Hashtable和ConcurrentHashMap的區(qū)別。

? ? 歸納一下，我們可以發(fā)現(xiàn)，這些問題主要圍繞著探索這些知識點：

????????hashing的概念

????????HashMap中解決碰撞的方法

????????equals()和hashCode()的應(yīng)用，以及它們在HashMap中的重要性

????????不可變對象的好處

????????HashMap多線程的條件競爭

????????重新調(diào)整HashMap的大小

????當然，這些知識還是很粗淺的，而且主要來源于多個參考博客，如有錯誤和缺點，敬請指正！

---------------------

參考博文：

作者：speedme? 來源：CSDN? ?題目：java中的HashTable,HashMap和HashSet

鏈接：https://blog.csdn.net/SpeedMe/article/details/22485681

作者：微wx笑? 來源：CSDN? ?題目：Java中Map與HashMap,Hashtable,HashSet的區(qū)別

鏈接：https://blog.csdn.net/testcs_dn/article/details/41925595

作者：speedme? 來源：CSDN? ?題目：java集合類TreeMap和TreeSet

鏈接：https://blog.csdn.net/SpeedMe/article/details/22661671

---------------------