Java基础之LinkedHashMap源码解析

Java集合源码解析系列

• Java基础之HashMap源码解析
• Java基础之HashTable源码解析
• Java基础之ArrayList源码解析
• Java基础之LinkedList源码解析
• HashSet和LinkedHashSet

LinkedHashMap

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

    /**
     * HashMap.Node的子类
     * 增加了前后节点的引用，因此不再是单链表而是双向链表
     */
    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表示按节点访问顺序排序
     * 默认是false
     */
    final boolean accessOrder;
    
    /**
     *将节点插入链表尾部
     */
    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;
        //src是第一个节点
        if (b == null)
            head = dst;
        else
            b.after = dst;
        //src是最后一个节点
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

    /**
     *初始化LinkedHashMap，这里在调用HashMap的初始化方法之外，还需要将头节点和尾节点初始化
     */
    void reinitialize() {
        super.reinitialize();
        head = tail = null;
    }
    
    /**
     * 这里覆写了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;
    }
    
    /**
     * 用next节点替换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);
        return t;
    }
    
    /**
     * 红黑树节点的相关方法
     */
    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;
    }

    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }
    
    /**
     * 覆写HashMap中的afterNodeRemoval方法
     * 将节点从链表中删除
     */
    void afterNodeRemoval(Node<K,V> e) {
        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;
    }

    /**
     * 覆写HashMap中的afterNodeInsertion方法
     * evict为true并且removeEldestEntry方法也为true的话就会删除近期最少使用的节点
     * 所以这里可以看出LinkedHashMap能实现LRU算法
     * 由HashMap的源码可知evict默认是true
     */
    void afterNodeInsertion(boolean evict) {
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            //满足条件则删除近期使用最少的节点
            removeNode(hash(key), key, null, false, true);
        }
    }

    /**
     * 覆写HashMap中的afterNodeAccess方法，每当节点被访问时被调用
     * 如果accessOrder为true，也就是LinkedHashMap的节点是按照访问顺序排序的，则需要将节点移到链表的末尾
     * 这也是LinkedHashMap实现LRU算法的条件之一，即accessOrder要为true
     */
    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;
        }
    }
    
    /**
     * 可以看到默认accessOrder为false，也就是按节点插入顺序排序
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    
    /**
     * 这个构造函数可以设置排序规则
     * 所以如果要实现LRU算法，也就是要设置accessOrder为true，就要用这个构造函数
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
    /**
     * 判断值是否存在，只需要循环双向链表
     * 这里相比HashMap需要2层循环，提升了效率
     */
    public boolean containsValue(Object value) {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }
    
    /**
     * LinkedHashMap的get方法调用的是HashMap的getNode方法
     * 注意这里会调用recordAccess方法
     */
    public V get(Object key) {
        Node<K,V> e;
        //如果没找到返回null
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //如果节点是按照访问顺序排序的，那就得去更新下顺序，把刚刚获取的节点放到链表末尾去    
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
    
    /**
     * 跟上面的方法一样，只是如果对应的key的节点不存在，会返回一个默认的数据
     */
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }
   
    /**
     * 这个好理解，清空数据
     */
   public void clear() {
        super.clear();
        head = tail = null;
    }
    
    /**
     * 这个方法用于控制是否要删除近期使用最少的节点
     * 默认返回是false，所以如果要实现LRU算法，需要覆写该方法，比如节点满了返回true以便删掉使用较少的节点
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
    
    <!--省略其他方法-->
    
}

LinkedHashMap没有put方法，是怎么插入数据的呢

• 答案就在newNode方法

/**
 * 这里覆写了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;
}

/**
 * 红黑树节点的相关方法
 */
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实际只是在HashMap的基础上加上了一个双向链表来保存节点插入的顺序，因此很多的逻辑都和HashMap是一样的。比如插入节点时，LinkedHashMap相比HashMap只需要在HashMap的基础上将节点插入双向链表，以及根据排序要求更新节点的顺序就行了
• 对于插入双向链表的功能，LinkedHashMap覆写了HashMap的newNode方法；而对于更新节点的顺序问题，LinkedHashMap覆写了afterNodeAccess方法和afterNodeInsertion方法

总结

• LinkedHashMap继承自HashMap，是HashMap的子类，因此也不是线程安全的
• LinkedHashMap底层存储结构与HashMap一样，不同的是LinkedHashMap增加了一个双向链表的头节点，插入的数据除了插入HashMap，还会插入链表中，因而可以保存插入节点的顺序
• LinkedHashMap的节点在HashMap节点的基础上增加了前后节点的引用
• LinkedHashMap可以插入null
• LinkedHashMap相比HashMap在查找值和删除值时效率要高
• LinkedHashMap还可以设置按插入顺序排序或是按访问顺序排序，默认是按插入顺序排序
• LinkedHashMap没有put方法，而是覆写了afterNodeAccess方法和afterNodeInsertion方法。当插入的数据已经存在时，会调用afterNodeAccess方法看是否需要将数据插入到链表末尾；当插入的数据是新数据时，会通过afterNodeInsertion方法来根据设置删除近期使用最少的节点
• LinkedHashMap可以用来实现LRU算法。首先需要用可以设置accessOrder的构造函数设置accessOrder为true，也就是按照节点访问顺序排序；然后removeEldestEntry方法设置当超过节点数时返回true，也就是删除近期最少使用的数据

以上是基于Java1.8并且只介绍了常用的一些方法的原理，详细的LinkedHashMap源码请查看：LinkedHashMap源码

---

欢迎关注我的微信公众号，和我一起学习一起成长！

AntDream