LinkedHashMap浅析

今天看到LinkedList的时候，突然想到Linked这东西有没有LinkedHashMap！

​

然后就搜了一下源码，WC，还真有！！呵！～ 今天又是才疏学浅的一天。

既然咱之前不了解，那就去探究一下这里面到底是个什么呗。

打开LinkedHashMap类，从类的结构上可以看出LinkedHashMap继承自HashMap，并且实现了Map接口。

​

LinkedHashMap拥有一个静态内部类Entry<K,V>，并且继承自HashMap.Node<K,V>，扩展了两个指针属性，before和after。

这两个指针分别指向链表中前后两个元素：“前面元素的after指针指向自己，自己的before指针指向前一个元素；after指针同理”。

​

在LinkedHashMap内部还有两个属性：head和tail，就是双向链表的头节点和尾节点。

​

看注释会发现这两个属性上还有一个表示时间概念的词语，啊！这……还有排序？

​

再往下瞅，就会看到一个boolean类型的属性accessOrder。

这个值表示LinkedHashMap的迭代排序方法，true表示按访问排序，false表示按插入顺序排序（原来这确实有排序的）。

HashMap插入后遍历输出时顺序和插入的顺序不一致，但是LinkedHashMap在accessOrder默认的情况下是可以确保插入和输出的顺序是一致的。

accessOrder在LinkedHashMap初始化时未指定的话，默认为false。

​

接下来，在LinkedHashMap的几个构造方法和HashMap基本类似，除了无参构造方法外，有参参数包括：初始容量、负载因子、传入Map类型等。唯一一个可以指定accessOrder的构造方法，需传入初始容量，负载因子和accessOrder的值。

​

LinkedHashMap基本构造看完了，接下来了解一下他的工作原理。

put方法

在LinkedHashMap中并未重写put方法，说明他完全使用了HashMap的插入逻辑（我们这里就不对HashMap的put方法作展开）。那既然是完全使用HashMap的插入逻辑，那链表是何时去维护的呢？

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  boolean evict) {
    ... //省略部分代码
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        ... //省略部分代码
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

首先，LinkedHashMap重写了HashMap的**newNode()**方法。

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;
}
复制代码

在newNode方法里面调用了一个**linkNodeLast()**方法，这个方法是将插入的元素链到链表的最后。这里就清楚是何时将元素放进链表的了。

// link at the end of list
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;
    }
}
复制代码

其次，在HashMap的put方法中有两个方法在LinkedHashMap中做了具体实现。

afterNodeInsertion(boolean evict)

该方法有一个boolean类型的参数，参数的意思是指在插入新的元素之后是否移除最早访问的或者说很久没访问的。在put方法中传入的参数始终是true（evict = true），但是**removeEldestEntry()**在LinkedHashMap中始终返回false，所以并不存在移除元素。

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);
    }
}
复制代码

afterNodeAccess()

该方法是当插入的key存在时调用，方法中用到一个变量是LinkedHashMap初始化时指定的accessOrder，只有当此变量为真时，该方法才有效。将访问的元素置于链表的尾部。

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;
    }
}
复制代码

通过put()方法可以看出来，LinkedHashMap每在插入新的元素时，将元素链到链表的尾部。在accessOrder为true时将已存在并且未在尾部的元素重新放回到链表的尾部。

get方法

LinkedHashMap重写了HashMap的get方法，不过依然使用的HashMap的getNode()方法，只不过在getNode()方法后面追加了当accessOrder为真时调用**afterNodeAccess()**方法。

remove方法

LinkedHashMap的remove()方法也是直接使用的HashMap的remove方法，在remove方法中调用了在LinkedHashMap中实现的**afterNodeRemoval()**方法。afterNodeRemoval方法只是将链表中的数据进行解链移除。

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
复制代码

遍历

LinkedHashMap是一个具有排序性质的Map。当accessOrder为false时，从链表的头节点开始按照插入时的顺序进行遍历，因为插入新的元素时会将元素放在链表的尾部。当accessOrder为true时，从链表的头节点开始按照访问顺序进行遍历，访问次数越少的越靠前，访问次数最多的在最后。

总结

LinkedHashMap大多方法都是直接继承自HashMap的方法，部分重写了HashMap的方法来负责维护链表数据。比如：**newNode()， newTreeNode()， afterNodeInsertion()， afterNodeRmoval()， afterNodeAccess()**等。

accessOrder为true的时候可能会有人想到LRU（Least Recently Used）算法。但是前面我们说过在插入数据时removeEldestEntry()方法默认返回的是false，所以要实现LRU算法需要重写removeEldestEntry()方法。

最后上个图看下LinkedHashMap的链表结构

LinkedHashMap的数据结构继承自HashMap，橙色的线代表双向链表的before和after指针。

鄙人不才，只能浅浅道来，如果有什么不对和不足之处，还请各位大神倾囊相授啊。

争取早日做一个日更博主