快捷導(dǎo)航

Java源碼解析之LinkedHashMap

更新時(shí)間：2021年05月25日 10:55:45 作者：不會編程的派大星

LinkedHashMap是HashMap的子類,所以也具備HashMap的諸多特性.不同的是,LinkedHashMap還維護(hù)了一個(gè)雙向鏈表,以保證通過Iterator遍歷時(shí)順序與插入順序一致.除此之外,它還支持Access Order, ,需要的朋友可以參考下

一、成員變量

先來看看存儲元素的結(jié)構(gòu)吧：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

這個(gè)Entry在HashMap中被引用過，主要是為了能讓LinkedHashMap也支持樹化。在這里則是用來存儲元素。

// 雙向鏈表的頭，用作AccessOrder時(shí)也是最老的元素
transient LinkedHashMap.Entry<K,V> head;

// 雙向鏈表的尾，用作AccessOrder時(shí)也是最新的元素
transient LinkedHashMap.Entry<K,V> tail;

// true則為訪問順序，false則為插入順序
final boolean accessOrder;

二、構(gòu)造函數(shù)

關(guān)于LinkedHashMap的構(gòu)造函數(shù)我們只關(guān)注一個(gè)，其他的都和HashMap類似，只是把a(bǔ)ccessOrder設(shè)置為了false。在上邊的文檔說過，initialCapacity并沒有在HashMap中那般重要，因?yàn)殒湵聿恍枰駭?shù)組那樣必須先聲明足夠的空間。下面這個(gè)構(gòu)造函數(shù)是支持訪問順序的。

// 雙向鏈表的頭，用作AccessOrder時(shí)也是最老的元素
transient LinkedHashMap.Entry<K,V> head;

// 雙向鏈表的尾，用作AccessOrder時(shí)也是最新的元素
transient LinkedHashMap.Entry<K,V> tail;

// true則為訪問順序，false則為插入順序
final boolean accessOrder;

三、重要方法

LinkedHashMap并沒有再實(shí)現(xiàn)一整套增刪改查的方法，而是通過復(fù)寫HashMap在此過程中定義的幾個(gè)方法來實(shí)現(xiàn)的。對此不熟悉的可以查看上一篇關(guān)于HashMap分析的文章，或者對照HashMap的源碼來看。

1、插入一個(gè)元素

HashMap在插入時(shí)，調(diào)用了newNode來新建一個(gè)節(jié)點(diǎn)，或者是通過replacementNode來替換值。在樹化時(shí)也有兩個(gè)對應(yīng)的方法，分別是newTreeNode和replacementTreeNode。完成之后，還調(diào)用了afterNodeInsertion方法，這個(gè)方法允許我們在插入完成后做些事情，默認(rèn)是空實(shí)現(xiàn)。

為了方便分析，我們會對比HashMap中的實(shí)現(xiàn)與LinkedHashMap的實(shí)現(xiàn)，來摸清它是如何做的。

// HashMap中的實(shí)現(xiàn)
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap中的實(shí)現(xiàn)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

// HashMap中的實(shí)現(xiàn)
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

// LinkedHashMap中的實(shí)現(xiàn)
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

// newTreeNode和replacementTreeNode和此類似

通過以上對比，可以發(fā)現(xiàn)，LinkedHashMap在新增時(shí)，調(diào)用了linkNodeLast，再替換時(shí)調(diào)用了transferLinks。以下是這兩個(gè)方法的實(shí)現(xiàn)。

// 就是將元素掛在鏈尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

// 用dst替換src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                            LinkedHashMap.Entry<K,V> dst) {  
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

最后我們看下afterNodeInsertion做了哪些事情吧：

// evict在HashMap中說過，為false表示是創(chuàng)建階段
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 不是創(chuàng)建階段
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 自動刪除最老的元素，也就是head元素
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry是當(dāng)想要在插入元素時(shí)自動刪除最老的元素時(shí)需要復(fù)寫的方法。其默認(rèn)實(shí)現(xiàn)如下：

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

2、查詢

因?yàn)橐С衷L問順序，所以獲取元素的方法和HashMap也有所不同。下面我們看下其實(shí)現(xiàn)：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        // 數(shù)據(jù)被訪問，需要將其移動到末尾
        afterNodeAccess(e);
    return e.value;
}

getNode方法是在HashMap中實(shí)現(xiàn)的，所以這是包裝了一下HashMap的方法，并添加了一個(gè)afterNodeAccess，其實(shí)現(xiàn)如下：

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // e元素不在末尾
    if (accessOrder && (last = tail) != e) {
        // p是e，b是前一個(gè)元素，a是后一個(gè)元素
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // e要放在末尾，所以沒有after
        p.after = null;

        // 把e去掉，把b和a接起來
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;

        //把e接在末尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

到此這篇關(guān)于Java源碼解析之LinkedHashMap的文章就介紹到這了,更多相關(guān)Java LinkedHashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: