源码分析之LinkedHashMap

概念

LinkedHashMap也是Java集合框架的一员，是HashMap的子类。LinkedHashMap可以保存插入顺序，底层是通过HashMap的哈希表和双向链表保存数据。

类结构

LinkedHashMap继承于HashMap，实现了Map接口。重写了部分HashMap类中的方法。

类成员

Entry 类

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

Entry是LinkedHashMap静态内部类，继承了HashMap.Node<K,V>类，在Node类的基础上增加了before、 after节点用来构成双向循环链表。

head & tail

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

head和tail节点分别记录分别记录着双向循环链表头结点和尾节点。

accessOrder

    final boolean accessOrder;

accessOrder 用来区分对LinkedHashMap中元素顺序。accessOrder为false时（默认为false），按照插入顺序，accessOrder为true时，按照访问顺序。

构造函数

LinkedHashMap提供了5种构造函数。

    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);
    }
    
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

实际上LinkedHashMap的构造函数时调用父类HashMap的构造函数实现的。前四种accessOrder均为false，也就是表明默认按照插入顺序。第五种构造函数可以指定accessOrder的值。

get(Object key) 方法

    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方法重写了HashMap中get方法。不同的时候，在查找出元素后，如果当前是按照元素访问顺序的模式，这里会通过调用afterNodeAccess方法把元素添加至链表的尾部。因为按照元素访问的模式中，会按照访问效率排序，最少访问的靠前，最新访问的靠后。

put(K key, V value) 方法

LinkedHashMap的put方法并没有重写父类HashMap的put方法。而是重写了其中的newNode、newTreeNode、afterNodeAccess和afterNodeInsertion方法。

linkNodeLast 方法

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

    
        TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

LinkedHashMap重写了newTreeNode和newTreeNode方法。这两个方法在创建新节点的时候，都调用了linkNodeLast方法。

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            // 尾节点为空，p设置为head节点
            head = p;
        else {
            // 将节点添加至链表尾部
            p.before = last;
            last.after = p;
        }
    }

linkNodeLast方法中将给定的节点，将节点添加到双向链表的尾部。

afterNodeAccess 方法

LinkedHashMap重写了afterNodeAccess方法，在put方法中，当遇到了put的key相同的时候，更新节点的同时，调用afterNodeAccess方法，如果accessOrder为true的时候，将会把节点添加至链表尾部。

afterNodeInsertion 方法

    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方法在LinkedHashMap直接return false。如果有需要，我们可以选择重写removeEldestEntry方法，来定义老节点first在put新数据时的删除机制。

总结

LinkedHashMap通过重新HashMap部分方法来实现其可以按插入顺序或者访问顺序的特性。由于LinkedHashMap按照访问顺序的特性，可以用来实现LRU算法。

LinkedHashMap是非线程安全的，只适用于单线程，多线程环境慎用。