HashMap相關類：Hashtable、LinkHashMap、TreeMap-有解無憂

前言

很高興遇見你~

在深入剖析HashMap 文章中我從散串列的角度決議了HashMap，在深入決議ConcurrentHashMap：感受并發編程智慧決議了ConcurrentHashMap的底層實作原理，本文是HashMap系列文章的第三篇，主要內容是講解與HashMap相關的集合類，

HashMap本身功能已經相對完善，但在某些特殊的情景下，他就顯得無能為力，如高并發、需要記住key插入順序、給key排序等，實作這些功能往往需要付出一定的代價，在沒有必然的需求情景下，增添這些功能是沒必要的，因而，為了提高性能，Java并沒有把這些特性直接集成到HashMap中，拓展了擁有這些特性的其他集合類作為補充：

執行緒安全的ConcurrentHashMap、Hashtable、SynchronizeMap
記住插入順序的LinkedHashMap
記錄key順序的TreeMap

這樣，我們就可以在特定的需求情景下，選擇最適合我們的集合框架，從而來提高性能，那么今天這篇文章，主要就是分析這些其他的集合類的特性、付出的性能代價、與HashMap的區別，

那么，我們開始吧~

Hashtable

Hashtable是屬于JDK1.1的第一批集合框架其中之一，其他的還有Vector、Stack等，這些集合框架由于設計上的缺陷，導致了性能的瓶頸，在jdk1.2之后就被新的一套集合框架取代，也就是HashMap、ArrayList這些，HashMap在jdk1.8之后進行了全面的優化，而Hashtable依舊保持著舊版本的設計，在很多方面都落后于HashMap，下面主要分析Hashtable在：介面繼承、哈希函式、哈希沖突、擴容方案、執行緒安全等方面決議他們的不同，

介面繼承

Hashtable繼承自Dictionary類而不是AbstractMap，類圖如下（jdk1.8）

Hashtable誕生的時間是比Map早，但為了兼容新的集合在jdk1.2之后也繼承了Map介面，Dictionary在目前已經完全被Map取代了，所以更加建議使用繼承自AbstractMap的HashMap，為了兼容新版本介面還有Hashtable的迭代器：Enumerator，他的介面繼承結構如下：

他不僅實作了舊版的Enumeration介面，同時也實作了Iteractor介面，兼容了新的api與使用習慣，這里關于Hashtable還有一個問題：Hashtable是fast-fail的嗎 ？

fast-fail指的是在使用迭代器遍歷集合程序中，如果集合發生了結構性改變，如添加資料、擴容、洗掉資料等，迭代器會拋出例外，Enumerator本身的實作是沒有fast-fail設計的，但他繼承了Iteractor介面之后，就有了fast-fail，看一下原始碼：

public T next() {
    // 這里在Enumerator的基礎上，增加了fast-fail
    if (Hashtable.this.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    //  nextElement()是Enumeration的介面方法
    return nextElement();
}

private void addEntry(int hash, K key, V value, int index) {
    ...
    // 在添加資料之后，會改變modCount的值
    modCount++;
}

所以，Hashtable本身的設計是有fastfail的，但如果使用的Enumerator，則享受不到這個設計了，

哈希演算法

Hashtable的哈希演算法非常簡單粗暴，如下代碼

hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;

獲取key的hashcode，通過直接對陣列長度求余來獲取下標，這里還有一步是hash & 0x7FFFFFFF，目的是把最高位變成0，把hashcode變成一個非負數，為了使得hash可以分布更加均勻，Hashtable默認控制陣列的長度為一個素數：初始值為11，每次擴容為原來的兩倍+1 ，

沖突解決

Hashtable使用的是鏈表法，也稱為拉鏈法，發生沖突之后會轉換為鏈表，HashMap在jdk1.8之后增加了紅黑樹，所以在劇烈沖突的情況下，Hashtable的性能下降會比HashMap明顯非常多，

Hashtable的裝載因子與HashMap一致，默認都是0.75，且建議非特殊情況不要進行修改，

擴容方案

Hashtable的擴容方案也非常簡單粗暴，新建一個長度為原來的兩倍+1長度的陣列，遍歷所有的舊陣列的資料，重新hash插入新的陣列，他的原始碼非常簡單，有興趣可以看一下：

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    // 設定陣列長度為原來的2倍+1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // 如果長度達到最大值，則直接回傳
            return;
        // 超過最大值設定長度為最大
        newCapacity = MAX_ARRAY_SIZE;
    }
    // 新建陣列
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
	// modcount++，表示發生結構性改變
    modCount++;
    // 初始化裝載因子，改變table參考
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
	// 遍歷所有的資料，重新hash后插入新的陣列，這里使用的是頭插法
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

執行緒安全

Hashtable和HashMap最大的不同就是執行緒安全了，jdk1.1的第一批集合框架都被設計為執行緒安全，但手段都非常粗暴：直接給所有方法上鎖 ，但我們知道，鎖是一個非常重量級的操作，會嚴重影響性能，Hashtable直接對整個物件上鎖的缺點有：

同一時間只能有一個執行緒在讀或者寫，并發效率極低
頻繁上鎖進行系統呼叫，嚴重影響性能

所以雖然Hashtable實作了一定程度上的執行緒安全，但是卻付出了非常大的性能代價，這也是為什么在jdk1.2他們馬上就被淘汰了，

不允許空鍵值

允許空鍵值這個設計有利也有弊，在ConcurrentHashMap中也禁止插入空鍵值，但HashMap是允許的，允許value空值會導致get方法回傳null時有兩種情況：

找不到對應的key
找到了但是value為null；

當get方法回傳null時無法判斷是哪種情況，在并發環境下containsKey方法已不再可靠，需要回傳null來表示查詢不到資料，允許key空值需要額外的邏輯處理，占用了陣列空間，且并沒有多大的實用價值，HashMap支持鍵和值為null，但基于以上原因，ConcurrentHashMap是不支持空鍵值，

小結

總體來說，Hashtable屬于舊版本的集合框架，他的設計已經落后了，官方更加推薦使用HashMap；而Hashtable執行緒安全的特性的同時，也帶來了極大的性能代價，更加推薦使用ConcurrentHashMap來代替Hashtable，

SynchronizeMap

SynchronizeMap這個集合類可能并不太熟悉，他是Collections.synchronizeMap()方法回傳的物件，如下：

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<>(m);
}

SynchronizeMap的作用是保證了執行緒安全，但是他的方法和Hashtable一致，也是簡單粗暴，直接加鎖，如下圖：

這里的mutex是什么呢？直接看到構造器：

final Object      mutex;        // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
    this.m = Objects.requireNonNull(m);
    // 默認為本物件
    mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
    this.m = m;
    this.mutex = mutex;
}

可以看到默認鎖的就是物件本身，效果和Hashtable其實是一樣的，所以，一般情況下也是不推薦使用這個方法來保證執行緒安全，

ConcurrentHashMap

前面講到的兩個執行緒安全的Map集合框架，由于性能低下而不被推薦使用，ConcurrentHashMap就是來解決這個問題的，關于ConcurrentHashMap的詳細內容，在深入決議ConcurrentHashMap：感受并發編程智慧一文中已經有了具體的介紹，這里簡單介紹一下ConcurrentHashMap的思路，

ConcurrentHashMap并不是和Hashtable一樣采用直接對整個陣列進行上鎖，而是對陣列上的一個節點上鎖，這樣如果并發訪問的不是同個節點，那么就無需等待釋放鎖，如下圖：

不同執行緒之間的訪問不同的節點不互相干擾，提高了并發訪問的性能，ConcurrentHashMap讀取內容是不需要加鎖的，所以實作了可以邊寫邊讀，多執行緒共讀，提高了性能，

這是jdk1.8優化之后的設計結構，jdk1.7之前是分為多個小陣列，鎖的粒度比Hashtable稍小了一些，如下：

鎖的是Segment，每個Segment對應一個陣列，而jdk1.8之后鎖的粒度進一步降低，性能也進一步提高了，

LinkedHashMap

HashMap是無法記住插入順序的，在一些需要記住插入順序的場景下，HashMap就顯得無能為力，所以LinkHashMap就應運而生，LinkedHashMap內部新建一個內部節點類LinkedHashMapEntry繼承自HashMap的Node，增加了前后指標，每個插入的節點，都會使用前后指標聯系起來，形成一個鏈表，這樣就可以記住插入的順序，如下圖：

圖中的紅色線表示雙向鏈表的參考，遍歷時從head出發可以按照插入順序遍歷所有節點，

LinkedHashMap繼承于HashMap，完全是基于HashMap進行改造的，在HashMap中就能看到LinkedMap的身影，如下：

HashMap.java

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

HashMap本身已經預留了介面給LinkedHashMap重寫，LinkedHashMap本身的put、remove、get等等方法都是直接使用HashMap的方法，

LinkedHashMap的好處就是記住Node的插入順序，當使用Iteractor遍歷LinkedHashMap時，會按照Node的插入順序遍歷，HashMap則是按照陣列的前后順序進行遍歷，

TreeMap

有沒有發現前面兩個集合框架的命名都是 xxHashMap，而TreeMap并不是，原因就在于TreeMap并不是散串列，只是實作了散串列的功能，

HashMap的key排列是無序的，hash函式把每個key都隨機散列到陣列中，而如果想要保持key有序，則可以使用TreeMap，TreeMap的繼承結構如下：

他繼承自Map體系，實作了Map的介面，同時還實作了NavigationMap介面，該介面拓展了非常多的方便查找key的介面，如最大的key、最小的key等，

TreeMap雖然擁有映射表的功能，但是他底層并不是一個映射表，而是一個紅黑樹，他可以將key進行排序，但同時也失去了HashMap在常數時間復雜度下找到資料的優點，平均時間復雜度是O(logN），所以若不是有排序的需求，常規情況下還是使用HashMap，

需要注意的是，TreeMap中的元素必須實作Comparable介面或者在TreeMap的建構式中傳入一個Comparator物件，他們之間才可以進行比較大小，

TreeMap本身的使用和特性是比較簡單的，核心的重點在于他的底層資料結構：紅黑樹，這是一個比較復雜的資料結構，限于篇幅，筆者會在另外的文章中詳解紅黑樹，

最后

文章詳解了Hashtable這個舊版的集合框架，同時簡單介紹了SynchronizeMap、ConcurrentHashMap、LinkedHashMap、TreeMap，這個類都在HashMap的基礎功能上，拓展了一些新的特性，同時也帶來一些性能上的代價，HashMap并沒有稱為功能的集大成者，而是把具體的特性分發到其他的Map實作類中，這樣做得好處是，我們不需要在單執行緒的環境下卻要付出執行緒安全的代價，所以了解這些相關Map實作類的特性以及付出的性能代價，則是我們學習的重點，

希望文章對你有幫助~

全文到此，原創不易，覺得有幫助可以點贊收藏評論關注轉發，
筆者才疏學淺，有任何想法歡迎評論區交流指正，
如需轉載請評論區或私信交流，

另外歡迎光臨筆者的個人博客：傳送門

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/232859.html

標籤：Java

上一篇：帶妹入坑，她該怎樣提高自己的編程能力？

下一篇：常用的DOS命令