如何理解Java容器中Map的源碼分析

本篇文章為大家展示了如何理解Java容器中Map的源碼分析，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

如果沒有特別說明，以下源碼分析基于 JDK 1.8。

一、HashMap

為了便于理解，以下源碼分析以 JDK 1.7 為主。

1. 存儲結構

內部包含了一個 Entry 類型的數組 table。

transient Entry[] table;

Entry 存儲著鍵值對。它包含了四個字段，從 next 字段我們可以看出 Entry 是一個鏈表。 即數組中的每個位置被當成一個桶，一個桶存放一個鏈表。HashMap 使用拉鏈法來解決沖突， 同一個鏈表中存放哈希值相同的 Entry。

static class Entry<K,V> implements Map.Entry<K,V> {
    //包含了四個字段
    final K key;
    V value;
    //next指向下一個節點，說明是鏈表結構
    Entry<K,V> next;
    int hash;
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    public final K getKey() {
        return key;
    }
    public final V getValue() {
        return value;
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final Boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
                    return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        // k1==k2 比較的是 hashcode 值，
        // k1.equals(k2)比較的是k1和k2的內容 equals 未重寫，則等價于 k1 == k2
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                            return true;
        }
        return false;
    }
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    public final String toString() {
        return getKey() + "=" + getValue();
    }
}

2. 拉鏈法的工作原理

HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");

• 新建一個 HashMap，默認大小為 16；

• 插入

  鍵值對，先計算 K1 的 hashCode 為 115，使用除留余數法得到所在的桶下標 115%16=3。

• 插入

  鍵值對，先計算 K2 的 hashCode 為 118，使用除留余數法得到所在的桶下標 118%16=6。

• 插入

  鍵值對，先計算 K3 的 hashCode 為 118，使用除留余數法得到所在的桶下標 118%16=6，插在前面。

應該注意到鏈表的插入是以頭插法方式進行的，例如上面的不是插在后面，而是插入在鏈表頭部。

查找需要分成兩步進行：

• 計算鍵值對所在的桶；

• 在鏈表上順序查找，時間復雜度顯然和鏈表的長度成正比。

3. put 操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 鍵為 null 單獨處理
    if (key == null)
            return putForNullKey(value);
    int hash = hash(key);
    // 確定桶下標
    int i = indexFor(hash, table.length);
    // 先找出是否已經存在鍵為 key 的鍵值對，如果存在的話就更新這個鍵值對的值為 value
    // 時間復雜度顯然和鏈表的長度成正比。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // 插入新鍵值對
    addEntry(hash, key, value, i);
    return null;
}

HashMap 允許插入鍵為 null 的鍵值對。但是因為無法調用 null 的 hashCode() 方法，也就無法確定該鍵值對的桶下標，只能通過強制指定一個桶下標來存放。HashMap 使用第 0 個桶存放鍵為 null 的鍵值對。

private V putForNullKey(V value) {
    //HashMap 使用第 0 個桶 table[0] 存放鍵為 null 的鍵值對。
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            // 更新值
            e.recordAccess(this);
            return oldValue;
            // 返回舊值
        }
    }
    modCount++;
    //void addEntry(int hash, K key, V value, int bucketIndex)
    addEntry(0, null, value, 0);
    return null;
}

使用鏈表的頭插法，也就是新的鍵值對插在鏈表的頭部，而不是鏈表的尾部。

//TODO:使用鏈表的頭插法，也就是新的鍵值對插在鏈表的頭部，而不是鏈表的尾部。
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 頭插法，鏈表頭部指向新的鍵值對
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

4. 確定桶下標

很多操作都需要先確定一個鍵值對所在的桶下標。

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

①. 計算 hash 值

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash42((String) k);
    }
    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

②. 取模

令 x = 1<<4，即 x 為 2 的 4 次方，它具有以下性質：

x   : 00010000
x-1 : 00001111

令一個數 y 與 x-1 做與運算，可以去除 y 位級表示的第 4 位以上數：

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010

這個性質和 y 對 x 取模效果是一樣的：

y   : 10110010
x   : 00010000
y%x : 00000010

我們知道，位運算的代價比求模運算小的多，因此在進行這種計算時用位運算的話能帶來更高的性能。

確定桶下標的最后一步是將 key 的 hash 值對桶個數取模： hash%capacity，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個操作轉換為位運算。

static int indexFor(int h, int length) {
    return h & (length-1);
}

就等價于

static int indexFor(int h, int length) {
    return h % length;
}

但是效率會更高。

5. 擴容-基本原理

設 HashMap 的 table 長度為 M，需要存儲的鍵值對數量為 N，如果哈希函數滿足均勻性的要求，那么每條鏈表的長度大約為 N/M，因此平均查找次數的復雜度為 O(N/M)。

為了讓查找的成本降低，應該盡可能使得 N/M 盡可能小，因此需要保證 M 盡可能大，也就是說 table 要盡可能大。 HashMap 采用動態擴容來根據當前的 N 值來調整 M 值，使得空間效率和時間效率都能得到保證。

和擴容相關的參數主要有：capacity、size、threshold 和 load_factor。

static final int DEFAULT_INITIAL_CAPACITY = 16;
//保證 capacity 為 2 的 n 次方，那么就可以將indexFor方法中操作轉換為位運算
static final int MAXIMUM_CAPACITY = 1 << 30;
//保證 capacity 為 2 的 n 次方，那么就可以將 indexFor 方法中操作轉換為位運算
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

從下面的添加元素代碼中可以看出，當需要擴容時，令 capacity 為原來的兩倍。

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
            resize(2 * table.length);
    //令 capacity 為原來的兩倍
}

擴容使用 resize() 實現，需要注意的是，擴容操作同樣需要把 oldTable 的所有鍵值對重新插入 newTable 中，因此這一步是很費時的。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
            while (e != null);
        }
    }
}

6. 擴容-重新計算桶下標

在進行擴容時，需要把鍵值對重新放到對應的桶上。HashMap 使用了一個特殊的機制，可以提升重新計算桶下標的效率。

假設原數組長度 capacity 為 16，擴容之后 new capacity 為 32：

capacity     : 00010000
new capacity : 00100000

對于一個 Key，

• 它的哈希值如果在第 5 位上為 0，那么取模得到的結果和之前一樣；

• 如果為 1，那么得到的結果為原來的結果 +16。

7. 計算數組容量

HashMap 構造函數允許用戶傳入的容量不是 2 的 n 次方，因為它可以自動地將傳入的容量轉換為 2 的 n 次方。

先考慮如何求一個數的掩碼，對于 10010000，它的掩碼為 11111111，可以使用以下方法得到：

mask |= mask >> 1    11011000
mask |= mask >> 2    11111110
mask |= mask >> 4    11111111

mask+1 是大于原始數字的最小的 2 的 n 次方。

num     10010000
mask+1  100000000

以下是 HashMap 中計算數組容量的代碼：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //得到n的掩碼
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

8. 鏈表轉紅黑樹

從 JDK 1.8 開始，一個桶存儲的鏈表長度大于 8 時會將鏈表轉換為紅黑樹。

9. 與 HashTable 的比較

• HashMap 是非線程安全的，HashTable 使用 synchronized 來進行同步，是線程安全的。

• HashMap 要比 HashTable 效率高一點。Hashtable 基本被淘汰，不要在代碼中使用它。

• HashMap 可以插入鍵為 null 的 Entry；HashTable 中插入的鍵只要有一個為 null，直接拋出 NullPointerException。

• HashMap 的迭代器是 fail-fast 迭代器。

• HashMap 不能保證隨著時間的推移 Map 中的元素次序是不變的。

• HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間；Hashtable 沒有這樣的機制。

• HashMap 默認的初始化大小為16。之后每次擴充，容量變為原來的2倍；Hashtable 容量默認的初始大小為11，之后每次擴充，容量變為原來的2n+1。 在初始化時如果給定了容量初始值，HashMap 會將其擴充為2的冪次方大小；Hashtable 會直接使用初始值。

10. 與 HashSet 的比較

HashSet 底層就是基于HashMap實現的。 (HashSet 的源碼非常非常少，因為除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實現之外， 其他方法都是直接調用 HashMap 中的方法。)

二、LinkedHashMap

1.存儲結構

繼承自 HashMap，因此具有和 HashMap 一樣的快速查找特性。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

內部維護了一個雙向鏈表，用來維護插入順序或者 LRU 順序。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

accessOrder 決定了順序，默認為 false，此時維護的是插入順序。

final boolean accessOrder;

LinkedHashMap 最重要的是以下用于維護順序的函數，它們會在 put、get 等方法中調用。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

2.afterNodeAccess()

當一個節點被訪問時，如果 accessOrder 為 true，則會將該節點移到鏈表尾部。也就是說指定為 LRU 順序之后，在每次訪問一個節點時，會將這個節點移到鏈表尾部，保證鏈表尾部是最近訪問的節點，那么鏈表首部就是最近最久未使用的節點。

void afterNodeAccess(Node<K,V> e) {
    // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
                    head = a; else
                    b.after = a;
        if (a != null)
                    a.before = b; else
                    last = b;
        if (last == null)
                    head = p; else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3.afterNodeInsertion()

在 put 等操作之后執行，當 removeEldestEntry() 方法返回 true 時會移除最晚的節點，也就是鏈表首部節點 first。

evict 只有在構建 Map 的時候才為 false，在這里為 true。

void afterNodeInsertion(Boolean evict) {
    // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry() 默認為 false，如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個方法的實現，這在實現 LRU 的緩存中特別有用，通過移除最近最久未使用的節點，從而保證緩存空間足夠，并且緩存的數據都是熱點數據。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

4.LRU 緩存

以下是使用 LinkedHashMap 實現的一個 LRU 緩存：

• 設定最大緩存空間 MAX_ENTRIES 為 3；

• 使用 LinkedHashMap 的構造函數將 accessOrder 設置為 true，開啟 LRU 順序；

• 覆蓋 removeEldestEntry() 方法實現，在節點多于 MAX_ENTRIES 就會將最近最久未使用的數據移除。

public class LRUCache<K,V> extends LinkedHashMap<K,V>{
    private static final int MAX_ENTRIES = 3;
    LRUCache(){
        super(MAX_ENTRIES,0.75f,true);
    }
    /**
     * removeEldestEntry() 默認為 false，
     * 如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個方法的實現，
     * 這在實現 LRU 的緩存中特別有用，通過移除最近最久未使用的節點，
     * 從而保證緩存空間足夠，并且緩存的數據都是熱點數據。
     */
    @Override
        protected Boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
    public static void main(String[] args) {
        LRUCache<Integer,String> cache=new LRUCache<>();
        cache.put(1, "a");
        cache.put(2, "b");
        cache.put(3, "c");
        cache.get(1);
        //LRU  鍵值1被訪問過了，則最近最久未訪問的就是2
        cache.put(4, "d");
        System.out.println(cache.keySet());
    }
}

[3, 1, 4]

三、WeakHashMap

1.存儲結構

WeakHashMap 的 Entry 繼承自 WeakReference，被 WeakReference 關聯的對象在下一次垃圾回收時會被回收。

WeakHashMap 主要用來實現緩存，通過使用 WeakHashMap 來引用緩存對象，由 JVM 對這部分緩存進行回收。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

2.ConcurrentCache

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 來實現緩存功能。

ConcurrentCache 采取的是分代緩存：

• 經常使用的對象放入 eden 中，eden 使用 ConcurrentHashMap 實現，不用擔心會被回收；

• 不常用的對象放入 longterm，longterm 使用 WeakHashMap 實現，這些老對象會被垃圾收集器回收。

• 當調用 get() 方法時，會先從 eden 區獲取，如果沒有找到的話再到 longterm 獲取，當從 longterm 獲取到就把對象放入 eden 中，從而保證經常被訪問的節點不容易被回收。

• 當調用 put() 方法時，如果 eden 的大小超過了 size，那么就將 eden 中的所有對象都放入 longterm 中，利用虛擬機回收掉一部分不經常使用的對象。

public final class ConcurrentCache<K, V> {
    private final int size;
    private final Map<K, V> eden;
    private final Map<K, V> longterm;
    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }
    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            v = this.longterm.get(k);
            if (v != null)
                            this.eden.put(k, v);
        }
        return v;
    }
    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            this.longterm.putAll(this.eden);
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

上述內容就是如何理解Java容器中Map的源碼分析，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。