LinkedHashMap

概述

LinkedHashMap与HashMap的主要区别不在多述：LinkedHashMap是有序的而HashMap是无序的。具体来说，LinkedHashMap可以基于插入顺序或者访问顺序（Least Recently Used，最近最少使用）进行遍历。从这两个类名上，我们就可以一窥LinkedHashMap实现有序性的关键词：linked。

大体来说，相对于HashMap，LinkedHashMap的每个节点都额外增加了before与after两个链接，来记录顺序。遍历之时，只需把after复制给next即可：

// 迭代器
abstract class LinkedHashIterator {
    // next结点
    LinkedHashMap.Entry<K,V> next;

    LinkedHashIterator() {
        next = head; // next初始化
        expectedModCount = modCount;
        current = null;
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        // fast-fail
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        // 将after赋值给next
        next = e.after;
        return e;
    }
}

既然LinkedHashMap相对于HashMap的最大区别仅仅是多维护了两个链接，那么这样的继承关系也是自然而然了：

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

所以我们可以思考一下，在哪里需要对这两个链接进行维护？要记录插入顺序的话，需要在put后维护；访问顺序则在get后维护；而remove之后当然也需要维护，所以大致可以这样处理：

public class MyLinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    public V put(K k,V v){
        V v= super.put(k,v);
        afterNodeInsertion();
        return v;
    }

    public V get(K k){
        V v= super.get(k);
        afterNodeAccess();
        return v;
    }

    public boolean remove(K k){
        boolean res= super.remove(k);
        afterNodeRemoval();
        return res;
    }

    // 维护before与after链接方法
    void afterNodeAccess(Node<K,V> old) { }
    void afterNodeInsertion() { }
    void afterNodeRemoval(Node<K,V> old) { }

}

在LinkedHashMap中，也维护了这三个方法，并运行了设计模式：模板方法模式。

导航

• 概述
• LinkedHashMap与HashMap：模板方法模式
• 钩子方法
• 其他

  LinkedHashMap与HashMap：模板方法模式

模板方法模式定义了一些概念，如在父类中，相关方法被分为模板方法与基本方法两大类，基本方法又分为三类：钩子方法、抽象方法、具体方法。先看一个简单的例子：

abstract class Foo {
    // 模板方法
    void meet() {
        greet();
        chat();
        if (isFriend()) {
            // do something
        }
        farewell();
    }

    //  钩子方法
    void greet() {
    }

    // 钩子方法
    boolean isFriend(){
        return false;
    }

    // 抽象方法
    abstract void chat();

    // 具体方法
    void farewell(){
        System.out.println("Goodbye!");
    }
}

class Sub extends Foo {

    void greet() {
        System.out.println("Hello!");
    }

    boolean isFriend(){
        return true;
    }

    @Override
    void chat() {
        System.out.println("blablabla...");
    }
}

LinkedHashMap与HashMap的实现也运用了这种模式,如

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            // 钩子
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

    // 钩子方法
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }
}

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
    // 实现钩子
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // ...
    }
}

钩子方法

现在，我们来具体看看这三个钩子方法:

// 头结点
transient LinkedHashMap.Entry<K,V> head;
// 尾结点
transient LinkedHashMap.Entry<K,V> tail;

// 遍历顺序
// true:访问顺序，false:插入顺序
final boolean accessOrder;

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last; // 访问e之前的tail
    // 如果按照访问顺序排序
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;

        // 以下操作将p移动至末尾,并在p.before与p.after之间建立双向链接

        // 建立p.after->p.before链接
        if (b == null) // p是头结点，无需建立链接，设置head
            head = a;
        else // 否则建立链接
            b.after = a;

        // 建立p.before->p.after链接
        if (a != null) // p不是尾结点，建立链接
            a.before = b;
        else // p是尾结点，无需建立，设置last
            last = b;

        if (last == null) // 只有p一个结点
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // 更新尾结点
        tail = p;
        ++modCount;
    }
}

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;
    // 建立after->before链接
    if (b == null)
        head = a;
    else
        b.after = a;
    // 建立before->after链接
    if (a == null)
        tail = b;
    else
        a.before = b;
}

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // evict && head不为null && 允许删除eldest结点 才可以删除
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

其他

除了实现钩子方法之外，LinkedHashmap还重写了一些HashMap的具体方法来维护before/after,head/tail

// 维护head、tail结点
void reinitialize() {
    super.reinitialize();
    head = tail = null;
}

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); // 新建结点时加入before/after链表尾部
    return p;
}


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);  // replace时新结点继承原先链接
    return t;
}

// 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;
    }
}

// apply src's links to dst
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;
}