LinkedHashMap源码分析

LinkedHashMap是前面分析过的HashMap的子类，主要的作用就是在HashMap的基础上可以保证元素的插入顺序或访问顺序，内存访问算法中很经典的LRU算法就可以基于LinkedHashMap实现，在面试中也很常见。

LinkedHashMap继承自HashMap，关于map的操作基本一样，只是加入了维护访问顺序加入了一些新的特性。

1. 重写HashMap.Node，加入了before和after两个属性，用于表示双向链表中的前后结点。
2. 关键方法如put()、get()、remove等基本与父类操作相同，只是有少量的改动或者直接调用父类方法。
3. 三个关键方法：afterNodeInsertion()、afterNodeAccess()、afterNodeRemoval()在执行完可能会影响插入或访问顺序的操作后调用这三个方法，来维持顺序。

一、基本构造函数

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{  
	//继承HashMap.Node，加入了before和after两个属性，用于表示双向链表中的前后结点
    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);
        }
    }

    //双向链表的头结点
    transient LinkedHashMap.Entry<K,V> head;

    //双向链表的尾结点
    transient LinkedHashMap.Entry<K,V> tail;

    // false: 基于插入顺序     true:  基于访问顺序 
    final boolean accessOrder;


    /*
     * 构造函数
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    //通过accessOrder，来设置LinkedHashMap是保证插入顺序还是访问顺序
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

1、加入双向链表

可以看出，LinkedHashMap对结点加入了新的属性，before和after，用以表示形成双向链表。

同时加入了head和tail结点，表示双向链表的头结点和尾结点，通过链表头结点到尾结点的顺序来表示map中元素的插入顺序或访问顺序。

2、accessOrder

accessOrder是LinkedHashMap中一个关键的属性。

上面说到LinkedHashMap能够保存元素的插入顺序或者是访问顺序，就是通过accessOrder这一变量来决定的。

accessOrder默认为false，即保存插入顺序。

accessOrder为true时，保存访问顺序，其实访问顺序只是在插入顺序的基础上，在每次访问元素时，对链表顺序进行修改。

3、构造函数

从构造函数可以看出，LinkedHashMap的构造函数都是调用父类的，默认将accessOrder设置为false。

最后一个构造函数可以自己指定accessOrder。

下面来看一下map最常用的几个方法是如何实现的。

二、put()方法

首先还是put方法，看过源码才知道原来LinkedHashMap并没有重写父类的put方法，所以还是要再回到前面分析的HashMap的put方法中。

 public V put(K key, V value) {  
     return putVal(hash(key), key, value, false, true);  
 }      

 static final int hash(Object key) {  
     int h;  
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
 }  


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;        


    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);//新建结点

    else {
        Node<K, V> e;
        K k;


        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;  


        else if (p instanceof TreeNode)  
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  


        else {  
            for (int binCount = 0;; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;  
                }  
                if (e.hash == hash && 
                        ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  

                p = e;  
            }  
        }  
        if (e != null) { 
            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相关的地方。

1、newNode

LinkedHashMap与HashMap在map的存储方式上实现过程是一样的，区别在于LinkedHashMap需要通过双向链表来保存map的插入顺序，所以，区别之一就是新建的结点肯定不能是父类中原有的结点，所以LinkedHashMap重写了父类的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;
}



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

可以看出，在新建一个node之后，又调用了linkNodeLast方法，目的在于把这个新建的结点加入到双向链表的尾结点上，这样就保证了插入的顺序。

2、afterNodeInsertion()方法

上面的put方法中第二个注释的地方，调用了afterNodeInsertion方法，

在父类HashMap中，afterNodeInsertion和其他两个方法并没有具体实现

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

注释写的很明白，是为了LinkedHashMap准备的。方法名也很清楚，就是插入一个结点之后要做的事。下面是LinkedHashMap中重写的方法：

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

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

正常来说，在插入结点的时候通过链表保存插入顺序，这就足够了，那么为什么还要调用这个方法呢，插入之后还有什么需要做的呢？

注释里面写了，这个方法可能的作用就是删除掉最老的元素，也就是离当前访问最远的元素。没错，这也是实现LRU时要重写的一个方法。下面的removeEldestEntry给出了判断的条件，重写时可以自由指定，比如当size大于指定的值后，就返回true。

public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    return size() > capacity;
}

返回true后，就会删除掉head结点，也就是链表中的第一个结点。

三、get方法

1、重写get方法

与put方法不一样的是LinkedHashMap直接重写了get方法，原因在于在get的过程中需要判断accessOrder，这是子类的属性

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

看一下父类的get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

子类中并没有重写getNode方法，所以两个get方法唯一的区别就在于，子类在getNode之后会判断accessOrder，以判断是否调用afterNodeAccess方法。

也就是说，get方法正常来说是不会影响map的结构的也不会影响插入的顺序，但是这个操作会影响访问的顺序，所以如果accessOrder为true，那么在调用get方法之后，访问顺序就发生了变化，就需要调用afterNodeAccess方法来改变访问顺序。

2、afterNodeAccess()方法

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

afterNodeAccess做的很简单，当访问元素e之后，它就成了最新访问的，所以需要把它移动到链表的尾部。

四、remove方法

1、直接调用父类remove方法

remove方法与put方法基本类似，子类都没有重写，再来看一下父类中的实现：

   public V remove(Object key) {  
       Node<K,V> e;  
       return (e = removeNode(hash(key), key, null, false, true)) == null ?  
           null : e.value;  
   }  

   /* 
    * 实现Map.remove及相关方法 
    */  
final Node<K, V> removeNode(int hash, Object key, Object value,   
        boolean matchValue, boolean movable) {  
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, index; 

    if ((tab = table) != null && (n = tab.length) > 0 &&   
        (p = tab[index = (n - 1) & hash]) != null) {              
        Node<K, V> node = null, e;  
        K k;  
        V v;  
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  
            node = p;  

        else if ((e = p.next) != null) {  
            if (p instanceof TreeNode)  
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);  
            else {  
                do {  
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {  
                        node = e;  
                        break;  
                    }  
                    p = e;  
                } while ((e = e.next) != null);  
            }  
        }  


        if (node != null && (!matchValue ||  
            (v = node.value) == value || (value != null && value.equals(v)))) {  

            if (node instanceof TreeNode)
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);  

            else if (node == p)
                tab[index] = node.next;

            else 
                p.next = node.next; 
            ++modCount;  
            --size;
            afterNodeRemoval(node); //调用函数
            return node;  
        }  
    }   
    return null;  
}

这也是从上篇分析中粘下来的，由于不用新建结点，所以remove方法只是在后面调用了afterNodeRemoval方法，这是唯一的区别

2、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;
}

afterNodeRemoval方法也很简单，就是更新删除的结点e的前后结点的指针，以保证链表的结构。

五、总结

1. 了解HashMap之后再来看LinkedHashMap就会快很多。

2. 两个类是父子关系，所以大部分实现方法都是相同的。

3. 子类是父类的扩展，扩展的地方就是保证插入或访问的顺序，而扩展的方式就是通过加入一个双向链表来维持。

4. 子类主要重写了几个可能会影响到插入或访问顺序的方法，比如put，get，remove

5. 重写的方法主要就是加入了对链表的维护

   • put方法，新建结点时指定前后结点，超过了某范围后可以进行删除
   • get方法在访问元素时更新链表结构来更新访问顺序
   • remove方法也是在删除结点后更新链表的结构

​

​

​