第9講 對比hashtable、hashmap、treemap有什么不同_h

1、2018/5/26極客時間 | Java核心技術36講第9講 | 對比Hashtable、HashMap、TreeMap有什么不同？2018-05-24 楊曉峰Map 是廣義 Java 集合框架中的另外一部分，HashMap 作為框架中使用頻率最高的類型之一， 它本身以及相關類型自然也是面試考察的熱點。今天我要問你的問題是，對比 Hashtable、HashMap、TreeMap 有什么不同？談談你對HashMap 的掌握。典型回答Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實現(xiàn)，是以鍵值對的形式存儲和操作數據的容器類型。Hashtable 是早期 Java

2、類庫提供的一個哈希表實現(xiàn)，本身是同步的，不支持 null 鍵和值，由于同步導致的性能開銷，所以已經很少被推薦使用。HashMap 是應用更加廣泛的哈希表實現(xiàn)，行為上大致上與 HashTable 一致，主要區(qū)別在于HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操/column/article/80531/15第9講 | 對比Hashtable、HashMap、TreeMap有什么不同？朗讀人：黃洲君1216 | 5.62M2018/5/26極客時間 | Java核心技術36講作，可以達

3、到常數時間的性能，所以它是絕大部分利用鍵值對存取場景的首選，比如，實現(xiàn)一個用戶 ID 和用戶信息對應的運行時存儲結構。TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間復雜度，具體順序可以由指定的 Comparator 來決定，或者根據鍵的自然順序來判斷。考點分析上面的回答，只是對一些基本特征的簡單總結，針對 Map 相關可以擴展的問題很多，從各種數據結構、典型應用場景，到程序設計實現(xiàn)的技術考量，尤其是在 Java 8 里，HashMap 本身發(fā)生了非常大的變化，這些都是經?？疾斓姆矫?/p>

4、。很多朋友向我反饋，面試官似乎鐘愛考察 HashMap 的設計和實現(xiàn)細節(jié)，所以今天我會增加相應的源碼解讀，主要專注于下面幾個方面：理解 Map 相關類似整體結構，尤其是有序數據結構的一些要點。從源碼去分析 HashMap 的設計和實現(xiàn)要點，理解容量、負載因子等，為什么需要這些參數，如何影響 Map 的性能，實踐中如何取舍等。理解樹化改造的相關原理和改進原因。除了典型的代碼分析，還有一些有意思的并發(fā)相關問題也經常會被提到，如 HashMap 在并發(fā)環(huán)境可能出現(xiàn)無限循環(huán)占用 CPU、size 不準確等詭異的問題。我認為這是一種典型的使用錯誤，因為 HashMap 明確聲明不是線程安全的數據結構，如

5、果忽略這一點，簡單用在多線程場景里，難免會出現(xiàn)問題。理解導致這種錯誤的原因，也是深入理解并發(fā)程序運行的好辦法。對于具體發(fā)生了什么，你可以參考這篇很久以前的分析，里面甚至提供了示意圖，我就不再重復別人寫好的內容了。知識擴展1.Map 整體結構首先，我們先對 Map 相關類型有個整體了解，Map 雖然通常被包括在 Java 集合框架里，但是其本身并不是狹義上的集合類型（Collection），具體你可以參考下面這個簡單類圖。/column/article/80532/152018/5/26極客時間 | Java核心技術36講Hashtable 比較特

6、別，作為類似 Vector、Stack 的早期集合相關類型，它是擴展了 Dictionary類的，類結構上與 HashMap 之類明顯不同。HashMap 等其他 Map 實現(xiàn)則是都擴展了 AbstractMap，里面包含了通用方法抽象。不同Map 的用途，從類圖結構就能體現(xiàn)出來，設計目的已經體現(xiàn)在不同接口上。大部分使用 Map 的場景，通常就是放入、訪問或者刪除，而對順序沒有特別要求，HashMap在這種情況下基本是最好的選擇。HashMap 的性能表現(xiàn)非常依賴于哈希碼的有效性，請務必掌握 hashCode 和 equals 的一些基本約定，比如：equals 相等，hashCode 一定要

7、相等。重寫了 hashCode 也要重寫 equals。hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致。equals 的對稱、反射、傳遞等特性。這方面內容網上有很多資料，我就不在這里詳細展開了。針對有序 Map 的分析內容比較有限，我再補充一些，雖然 LinkedHashMap 和 TreeMap 都可以保證某種順序，但二者還是非常不同的。LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實現(xiàn)是通過為條目（鍵值對）維護一個雙向鏈表。注意，通過特定構造函數，我們可以創(chuàng)建反映訪問順序的實例，所謂的/column/ar

8、ticle/80533/152018/5/26極客時間 | Java核心技術36講put、get、compute 等，都算作“訪問”。這種行為適用于一些特定應用場景，例如，我們構建一個空間占用敏感的資源池，希望可以自動將最不常被訪問的對象釋放掉，這就可以利用 LinkedHashMap 提供的機制來實現(xiàn)，參考下面的示例：/column/article/80534/15import java.util.LinkedHashMap; import java.util.Map;public class LinkedHashMapSample publi

9、c static void matring args) LinkedHashMap accessOrderedMap = new LinkedHashMap(16, 0.75F, true) Overrideprotected boolean removeEldestEntry(Map.Entry eldest) / 實現(xiàn)自 return size() 3;accessOrderedMap.put(Project1, Valhalla); accessOrderedMap.put(Project2, Panama); accessOrderedMap.put(Project3, Loom);

10、accessOrderedMap.forEach( (k,v) - System.out.println(k +: + v););/ 模擬訪問accessOrderedMap.get(Project2); accessOrderedMap.get(Project2); accessOrderedMap.get(Project3);System.out.println(Iterate over should be not affected:); accessOrderedMap.forEach( (k,v) - System.out.println(k +: + v););/ 觸發(fā)刪除 acce

11、ssOrderedMap.put(Project4, Mission Control); System.out.println(Oldest entry should be removed:); accessOrderedMap.forEach( (k,v) - / 遍歷順序不變 System.out.println(k +: + v););2018/5/26極客時間 | Java核心技術36講對于 TreeMap，它的整體順序是由鍵的順序關系決定的，通過 Comparator 或Comparable（自然順序）來決定。我在上一講留給你的思考題提到了，構建一個具有優(yōu)先級的調度系統(tǒng)的問題，其本質

12、就是個典型的優(yōu)先隊列場景，Java 標準庫提供了基于二叉堆實現(xiàn)的 PriorityQueue，它們都是依賴于同一種排序機制，當然也包括 TreeMap 的馬甲 TreeSet。類似 hashCode 和 equals 的約定，為了避免模棱兩可的情況，自然順序同樣需要符合一個約定，就是 compareTo 的返回值需要和 equals 一致，否則就會出現(xiàn)模棱兩可情況。我們可以分析 TreeMap 的 put 方法實現(xiàn)：從代碼里，你可以看出什么呢？ 當我不遵守約定時，兩個不符合唯一性（equals）要求的對象被當作是同一個（因為，compareTo 返回 0），這會導致歧義的行為表現(xiàn)。2.Hash

13、Map 源碼分析前面提到，HashMap 設計與實現(xiàn)是個非常高頻的面試題，所以我會在這進行相對詳細的源碼解讀，主要圍繞：HashMap 內部實現(xiàn)基本點分析。容量（capcity）和負載系數（load factor）。/column/article/80535/15public V put(K key, V value) Entry t = cmp = pareTo(t.key); if (cmp 0)t = t.right;elsereturn t.setValue(value);/ .2018/5/26樹化 。極客時間 | Java核

14、心技術36講首先，我們來一起看看 HashMap 內部的結構，它可以看作是數組（Node table）和鏈表結合組成的復合結構，數組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數組的尋址；哈希值相同的鍵值對，則以鏈表形式存儲，你可以參考下面的示意圖。這里需要注意的是，如果鏈表大小超過閾值（TREEIFY_THRESHOLD, 8），圖中的鏈表就會被改造為樹形結構。從非拷貝構造函數的實現(xiàn)來看，這個表格（數組）似乎并沒有在最初就初始化好，僅僅設置了一些初始值而已。所以，我們深刻懷疑，HashMap 也許是按照 lazy-load 原則，在首次使用時被初始化（拷貝構造函數除外，我這里

15、僅介紹最通用的場景）。既然如此，我們去看看 put 方法實現(xiàn)，似乎只有一個 putVal 的調用：/column/article/80536/15public V put(K key, V value) return putVal(hash(key), key, value, false, true);public HashMap(int initialCapacity, float loadFactor)/ .this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCa

16、pacity);2018/5/26極客時間 | Java核心技術36講看來主要的似乎藏在 putVal 里面，到底有什么呢？為了節(jié)省空間，我這里只截取了putVal 比較關鍵的幾部分。從 putVal 方法最初的幾行，我們就可以發(fā)現(xiàn)幾個有意思的地方：如果表格是 null，resize 方負責初始化它，這從 tab = resize() 可以看出。resize 方法兼顧兩個職責，創(chuàng)建初始存儲表格，或者在容量不滿足需求的時候，進行擴容（resize）。在放置新的鍵值對的過程中，如果發(fā)生下面條件，就會發(fā)生擴容。具體鍵值對在哈希表中的位置（數組 index）取決于下面的位運算：仔細觀察哈希值的源頭，我

17、們會發(fā)現(xiàn)，它并不是 key 本身的 hashCode，而是來自于HashMap 內部的另外一個 hash 方法。注意，為什么這里需要將高位數據移位到低位進行異或/column/article/80537/15i = (n - 1) & hashif (+size threshold) resize();final V putVal(int hash, K key, V value, boolean onlyIfAbent, boolean evit) Node tab; Node p; int , i;if (tab = table) = nul

18、l | (n = tab.length) = 0) n = (tab = resize().legth;if (p = tabi = (n - 1) & hash) = ull) tabi = newNode(hash, key, value, nll);else / .if (binCount = TREEIFY_THRESHOLD - 1) / -1 for first treeifyBin(tab, hash);/.2018/5/26極客時間 | Java核心技術36講運算呢？這是因為有些數據計算出的哈希值差異主要在高位，而 HashMap 里的哈希尋址是忽略容量以上的高位的，那么這種處

19、理就可以有效避免類似情況下的哈希碰撞。我前面提到的鏈表結構（這里叫 bin），會在達到一定門限值時，發(fā)生樹化，我稍后會分析為什么 HashMap 需要對 bin 進行處理?？梢钥吹剑琾utVal 方法本身邏輯非常集中，從初始化、擴容到樹化，全部都和它有關，推薦你閱讀源碼的時候，可以參考上面的主要邏輯。我進一步分析一下身兼多職的 resize 方法，很多朋友都反饋經常被面試官追問它的源碼設計。/column/article/80538/15final Node resize() / .else if (newCap = oldCap 1) = DE

20、FAULT_INITIAL_CAPAITY)newThr = oldThr 0) / initial capacity was placed in threshold newCap = oldThr;else / zero initial threshold signifies using defaultsfults newCap = DEFAULT_INITIAL_CAPAITY;newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY； if (newThr =0) float ft = (float)newCap * loadF

21、ator;newThr = (newCap MAXIMUM_CAPACITY & ft (float)MAXIMUM_CAPACITY ?(int)ft : Integethreshold = neThr;Node newTab = (Node)new Nodenewap; table = n； static final int hash(Object kye) int h;return (key = null) ? 0 : (h = key.hashCode() (h 16;2018/5/26極客時間 | Java核心技術36講依據 resize 源碼，不考慮情況（容量理論最大極限由 MAX

22、IMUM_CAPACITY 指定，數值為 130，也就是 2 的 30 次方），我們可以歸納為：門限值等于（負載因子）x（容量），如果構建 HashMap 的時候沒有指定它們，那么就是依據相應的默認常量值。門限通常是以倍數進行調整 （newThr = oldThr 元素數量 / 移動到新的數組結構 e 數組結構 2018/5/26極客時間 | Java核心技術36講如果確實需要調整，建議不要設置超過 0.75 的數值，因為會顯著增加沖突，降低 HashMap的性能。如果使用太小的負載因子，按照上面的公式，預設容量值也進行調整，否則可能會導致更加頻繁的擴容，增加無謂的開銷，本身訪問性能也會受影響

23、。我們前面提到了樹化改造，對應邏輯主要在 putVal 和 treeifyBin 中。上面是精簡過的 treeifyBin 示意，綜合這兩個方法，樹化改造的邏輯就非常清晰了，可以理解為，當 bin 的數量大于 TREEIFY_THRESHOLD 時：如果容量小于 MIN_TREEIFY_CAPACITY，只會進行簡單的擴容。如果容量大于 MIN_TREEIFY_CAPACITY ，則會進行樹化改造。那么，為什么 HashMap 要樹化呢？本質上這是個安全問題。因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能。而在

24、現(xiàn)實世界，構造哈希沖突的數據并不是非常復雜的事情，惡意代碼就可以利用這些數據大量與服務器端交互，導致服務器端 CPU 大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯(lián)網公司就發(fā)生過類似攻擊。今天我從 Map 相關的幾種實現(xiàn)對比，對各種 Map 進行了分析，講解了有序集合類型容易混淆的地方，并從源碼級別分析了 HashMap 的基本結構，希望對你有所幫助。一課一練關于今天我們討論的題目你做到心中有數了嗎？留一道思考題給你，解決哈希沖突有哪些典型方法呢？/column/article/805310/15final void treeifyBin

25、(Node tab, int hash) int n, index; Node e;if (tab = null | (n = tab.length) MIN_TREEIFY_CAPACITY) resize();else if (e = tabindex = (n - 1) & hash) != null) / 樹化改造邏輯 2018/5/26極客時間 | Java核心技術36講請你在留言區(qū)寫寫你對這個問題的思考，我會選出經過認真思考的留言，送給你一份學習鼓勵金，歡迎你與我一起討論。你的朋友是不是也在準備面試呢？你可以“請朋友讀”，把今天的題目分享給好友，或許你能幫到他。版權歸極客邦科技所有

26、，未經許可不得轉載精選留言17公眾號:代碼榮耀Hashtable、HashMap、TreeMap心得三者均實現(xiàn)了Map接口，存儲的內容是基于key-value的鍵值對映射，一個映射不能有重復的 鍵，一個鍵最多只能映射一個值。（1）元 素 特 性HashTable中的key、value都不能為null；HashMap中的key、value可以為null，很顯然只能有一個key為null的鍵值對，但是允許有多個值為null的鍵值對；TreeMap中當未實現(xiàn) Co mparator 接口時，key 不可以為null；當實現(xiàn) Comparator 接口時，若未對null情況進行判斷，則key不可以為n

27、ull，反之亦然。（2） 順 序 特 性HashTable、HashMap具有無序特性。TreeMap是利用紅黑樹來實現(xiàn)的（樹中的每個節(jié)點的值，都會大于或等于它的左子樹種的所有節(jié)點的值，并且小于或等于它的右子樹中的所有節(jié)點的值），實現(xiàn)了SortMap接口，能夠對保存的記錄根據鍵進行排序。所以一般需要排序的情況下是選擇TreeMap來進行，默認為升序排序方式（深度優(yōu)先搜索），可自定義實現(xiàn)Com parator接口實現(xiàn)排序方式。/column/article/805311/152018/5/26極客時間 | Java核心技術36講（3）初始化與增長方

28、式初始化時：HashTable在不指定容量的情況下的默認容量為11，且不要求底層數組的容量一 定要為2的整數次冪；HashMap默認容量為16，且要求容量一定為2的整數次冪。擴容時：Hashtable將容量變?yōu)樵瓉淼?倍加1；HashMap擴容將容量變?yōu)樵瓉淼?倍。（4） 線 程 安 全 性HashTable其方法函數都是同步的（采用synchronized修飾），不會出現(xiàn)兩個線程同時對數據進行操作的情況，因此保證了線程安全性。也正因為如此，在多線程運行環(huán)境下效率表現(xiàn)非常低下。因為當一個線程訪問HashTable的同步方法時，其他線程也訪問同步方法就會進入阻塞狀態(tài)。比如當一個線程在添加數據時候

29、，另外一個線程即使執(zhí)行獲取其他數據的操作也必須被阻塞，大大降低了程序的運行效率，在新版本中已被廢棄，不推薦使用。HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數據的不一致。如果需要同步（1）可以用Collections的synchronizedMap方法；（2）使用Co ncurrentHashMap類，相較于HashTable鎖住的是對象整體， ConcurrentHashMap基于lo ck實現(xiàn)鎖分段技術。首先將Map存放的數據分成一段一段的存儲方式，然后給每一段數據分配一把鎖，當一個線程占用鎖訪問其中一個段的數據時，其他段的數據也能被其他線程訪問

30、。ConcurrentHashMap不僅保證了多線程運行環(huán)境下的數據訪問安全性，而且性能上有 長足的提升。(5) 一 段 話 HashMapHashMap基于哈希思想，實現(xiàn)對數據的讀寫。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。當兩個不同的鍵對象的hashcode相同時，它們會儲存在同一個

31、bucket位置的鏈表中，可通過鍵對象的equals()方法用來找到鍵值對。如果鏈表大小超過閾值（TREEIFY_THRESHOLD, 8），鏈表就會被改造為樹形結構。2018-05-244天涼好個秋解決哈希沖突的常用方法有：開放定址法基本思想是：當關鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎，產生另一個哈 希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。再哈希法這種方法是同時構造多個不同的哈希函數： Hi=RH1（key） i=1，2，k當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（

32、key），直到沖突不再產生。 這種方法不易產生聚集，但增加了計算時間。/column/article/805312/152018/5/26極客時間 | Java核心技術36講鏈地址法這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經常進行插入和刪除的情況。建立公共溢出區(qū)這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元 素，一律填入溢出表。2018-05-244j.c.這是面試必問題。什么時候也能講講紅黑樹的樹化具體過程，那個旋轉一直沒搞懂。另外tre eifyBin這個單詞的詞面意思是什么？2018-05-24灰飛灰豬不會灰飛.煙滅這是1.7的hashmap吧？2018-05-2410代碼狂徒針對負載因子，您所指的存太滿會影響性能是指什么？畢竟已經開辟了相應內存空間的，沒 什么不用呢？2018-05-24作者回復沖突可能會增加,影響查詢之類性能，當然看具體的需求2018-05-250代碼狂徒為什么不是一開始就樹化，而是要等到一定程度再樹化，鏈表一開始就是消耗查找性能啊